Rationality and Connectivity in Stochastic Learning for Networked Coordination Games

Yifei Zhang, Marcos M. Vasconcelos

TL;DR

This paper explores how the "rationality" of agents and the "connectivity" of their network influence their ability to coordinate in a task allocation game. They discover a fascinating trade-off: in more connected networks, agents can actually afford to be less rational and still achieve near-optimal collective outcomes, echoing the "wisdom of crowds" phenomenon.

What Problem Does This Paper Address?

Many real-world systems, from robot teams to social networks, rely on agents coordinating their actions to achieve a common goal. This coordination is often challenging because agents might not be perfectly rational (they make mistakes) and their interactions are structured by a network. The paper investigates how these two factors – agent rationality and network connectivity – interact in a specific type of game called a "networked coordination game." Specifically, they ask: does higher connectivity mean agents need to be more or less rational to successfully coordinate? They aim to understand the conditions under which a group of boundedly rational agents, learning through interaction, can converge to a desirable collective strategy.

Methods

The authors model the problem as a binary networked coordination game played over a regular graph (where every agent has the same number of neighbors). They first establish that this game is a "potential game," a property that simplifies the analysis of learning dynamics. They then employ Log-Linear Learning (LLL), a common model for boundedly rational agents, where agents update their actions probabilistically based on their neighbors' actions and their own payoffs. A key part of their analysis involves characterizing the "potential function" of the game and finding its maximizers, which correspond to the game's Nash equilibria. They then analyze the steady-state distribution of the LLL process to understand the probability of agents converging to the optimal collective action. This involves deriving mathematical bounds and analyzing how this probability changes with both the rationality parameter (β in LLL) and the network's connectivity (K).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical simulations rather than empirical evaluation on real-world datasets.

Key Insights and Ideas

  • The "Wisdom of Crowds" in Action: The most striking finding is that increased network connectivity can reduce the required level of individual rationality for successful coordination. This means agents in a highly interconnected network can make more mistakes, yet the group as a whole can still achieve a near-optimal outcome.
  • Potential Games Simplify Coordination Analysis: Identifying the game as a potential game is crucial. It allows researchers to leverage the properties of potential functions to analyze learning dynamics and equilibrium convergence, which is a standard but powerful technique in game theory.
  • Log-Linear Learning as a Model for Bounded Rationality: LLL provides a flexible framework to model agents who aren't perfectly rational. By varying the rationality parameter (β), the authors can explore the spectrum from near-random choices to near-best responses.
  • Connectivity Threshold for Monotonicity: The paper suggests that the positive relationship between connectivity and successful coordination (i.e., lower rationality needed for higher connectivity) holds above a certain connectivity threshold, which depends on the task difficulty.

Key Results

The paper demonstrates that for a networked coordination game over a regular graph, the probability of agents converging to the optimal collective action profile (using LLL) is an increasing function of both the rationality parameter (β) and, for sufficiently high connectivity, the network's degree (K). Specifically, they show that for a given desired success probability (1-δ), there's a minimum rationality level (β_min) required, and this β_min decreases as K increases. They provide a formula quantifying this trade-off: β_min is inversely related to K for certain parameter regimes. Numerical simulations visually support these theoretical findings, showing how the probability of optimal coordination increases with both β and K.

Limitations and Future Work

The authors acknowledge that their analysis is primarily theoretical and relies on specific assumptions, such as the game being played on a regular graph and agents using LLL. They note that the monotonicity of coordination probability with respect to connectivity might be reversed for very low connectivity values, and they leave a rigorous proof for this reversed behavior for future work. They also suggest exploring the finite-time analysis of LLL, specifically the expected first hitting time to the optimal state, and investigating other learning algorithms and network structures. The current work focuses on the steady-state behavior of LLL.

Summary updated

Abstract

Coordination is a desirable feature in many multi-agent systems such as robotic and socioeconomic networks. We consider a task allocation problem as a binary networked coordination game over an undirected regular graph. Each agent in the graph has bounded rationality, and uses a distributed stochastic learning algorithm to update its action choice conditioned on the actions currently played by its neighbors. After establishing that our framework leads to a potential game, we analyze the regime of bounded rationality, where the agents are allowed to make sub-optimal decisions with some probability. Our analysis shows that there is a relationship between the connectivity of the network, and the rationality of the agents. In particular, we show that in some scenarios, an agent can afford to be less rational and still converge to a near optimal collective strategy, provided that its connectivity degree increases. Such phenomenon is akin to the wisdom of crowds.
BibTeX
@misc{zhang2023rationality,
  author = {Yifei Zhang and Marcos M. Vasconcelos},
  title = {{Rationality and Connectivity in Stochastic Learning for Networked Coordination Games}},
  year = {2023},
  eprint = {2309.16931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.16931},
}

Loading related content...

Figure