Game theoretic algorithms for decentralized decision-making environments

Abstract

Traditional viewpoints on the decision-making environment have been centered on a top-down perspective, guided by a hierarchy in which only one entity may establish desirable criteria and pursue them while considering others to be quiet agents in the system, merely obeying instructions and judgments taken. Many research studies and mathematical formulations have been developed with this centralized approach in mind. Although systems in the past were not entirely centralized in architecture, researchers assumed this simplification because systems were less complex and with fewer interdependent relationships. Therefore, considering a centralized mathematical formulation describing such systems' behavior was sufficient. However, today's complex systems, which have a very high degree of interconnectedness, exhibit distinct dynamics as subsystems are increasingly dependent on one another. Additionally, considering the free market environment, which encourages reserving government function to the privet sector, the number of decision-makers with distinguished interests and profiteering behavior that can affect the system has been increased. Therefore, two types of interdependencies can be realized in dealing with today's complex systems: (i) physical interdependency among the systems, and (ii) interdependency among decisions made by the decision-makers in the system. Focusing on these two interdependency types, this research proposes algorithms incorporating mathematical formulations addressing decentralized decision-making environments considering interdependent complex systems. The game theory concept has been utilized to address the decentralized decision-making environment, while permanent or temporal networks represent the interdependencies between the subsystems. This research has four research threads, each focusing on a decentralized decision-making environment where one can realize a kind of dependency among decision-makers and physical sub-systems. The first research thread, like the second, considers multiple decision-makers only interested in recovering their associated network post-disruption. However, the research addresses the problem of interdependent infrastructure network restoration where both decision-makers depend on each other. Therefore, the research develops an iterative algorithm on a game-theoretic basis, enabling to effectively search the solution space for possible Nash equilibria in the system. Also, we have illustrated that a lower bound could be discovered for each decision-maker’s best response in every iteration of the algorithm, where using that can reduce the number of algorithm iterations and, subsequently, calculation time. The second research thread proposes an adaptive algorithm using machine learning to integrate predictions about other decision-maker behaviors into interdependent network restoration planning under an imperfect information-sharing environment. The proposed algorithm considers a permanent network representing a dependent infrastructure network where each network has a separate decision-maker (i.e., utility) only interested in and benefiting from the recovery of its associated network post-disruption. As one decision-maker is dependent on the other and lacks complete information about the leader’s restoration activities, a predictive model based on a machine learning approach was designed to predict the behavior of the leader decision-maker. The proposed algorithm provides a solution sufficiently close to the optimal solution showing the algorithm performs well in situations where the information sharing environment is incomplete. The third research thread focuses on the impact of demand surge on critical supply chain networks due to disinformation propagation in the communities. In this research, we presented a framework that enables the modeling of these fluctuations and the evaluation of their impact on the adaptability of the supply chain. The objective was to identify any vulnerabilities or shortcomings within the supply chain by analyzing its flexibility in response to these variations. The forth research thread focuses on a semi-decentralized, three-stage algorithm based on game theory to resolve potential conflicts among multiple aircraft travelling in a 3D shared airspace. Considering the aircraft pilots as decision-makers, the main objective of this research was to allow pilots to pursue their interests and have the liberty to select their flight characteristics freely while maintaining a safe distance from others. Conflicts among aircraft were considered logical, and temporal interdependency relationships existed between them, considering their route and flight characteristics.