Coordination is a desirable feature in many multi-agent systems, such as robotic, social and economic networks, allowing the execution of tasks that would be impossible by individual agents. This thesis addresses two problems in stochastic coordination where each agent make decisions strategically, taking into account the decisions of its neighbors over a regular network.
In the first problem, we study the coordination in a team of strategic agents choosing to undertake one of the multiple tasks. We adopt a stochastic framework where the agents decide between two distinct tasks whose difficulty is randomly distributed and partially observed. We show that a Nash equilibrium with a simple and intuitive linear structure exists for textit{diffuse} prior distributions on the task difficulties. Additionally, we show that the best response of any agent to an affine strategy profile can be nonlinear when the prior distribution is not diffuse. Then, we state an algorithm that allows us to efficiently compute a data-driven Nash equilibrium within the class of affine policies.
In the second problem, we assume that the payoff structure of the coordination game corresponds to a single task allocation scenario whose difficulty is perfectly observed. Since there are multiple Nash equilibria in this game, the agents must use a distributed stochastic algorithm know as textit{log linear learning} to play it multiple times.
First, we show that this networked coordination game is a potential game. Moreover, we establish that for regular networks, the convergence to a Nash equilibrium depends on the ratio between the task-difficulty parameter and the connectivity degree according to a threshold rule. We investigate via simulations the interplay between rationality and the degree of connectivity of the network. Our results show counter-intuitive behaviors such as the existence of regimes in which agents in a network with larger connectivity require less rational agents to converge to the Nash equilibrium with high probability. Simultaneously, we examined the characteristics of both regular graphical coordination games and non-regular graphical games using this particular bi-matrix game model. / Master of Science / This thesis focuses on addressing two problems in stochastic coordination among strategic agents in multi-agent systems, such as robotic, social, and economic networks. The first problem studies the coordination among agents when they need to choose between multiple tasks whose difficulties are randomly distributed and partially observed. The thesis shows the existence of a Nash equilibrium with a linear structure for certain prior distributions, and presents an algorithm to efficiently compute a data-driven Nash equilibrium within a specific class of policies. The second problem assumes a single task allocation scenario, whose difficulty is perfectly observed, and investigates the use of a distributed stochastic algorithm known as log-linear learning to converge to a Nash equilibrium. The thesis shows that the convergence to a Nash equilibrium depends on the task-difficulty parameter and the connectivity degree of the network, and explores the influence of rationality of the agents and the connectivity of the network on the learning process. Overall, the thesis provides insights into the challenges and opportunities in achieving coordination among strategic agents in multi-agent systems.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/115127 |
| Date | 19 May 2023 |
| Creators | Wei, Yi |
| Contributors | Electrical and Computer Engineering, Pereira da Silva, Luiz Antonio, Muller Vasconcelos, Marcos, Dhillon, Harpreet Singh |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0019 seconds