Learning to Coordinate over Networks with Bounded Rationality
2026-04-09 • Multiagent Systems
Multiagent Systems
AI summaryⓘ
The authors study how groups of limited-thinking agents coordinate their actions on networks using a game called the stag hunt. They show that as agents become more rational, the chance of everyone perfectly coordinating increases. In networks where each agent has the same number of connections (K-regular), coordination improves with more connections, and the authors identify the minimum rationality needed for good coordination. For uneven networks, coordination also grows with more connections overall. Their findings suggest that evenly spreading connections among agents helps the group coordinate best when agents have limited rationality.
Network coordination gamesBounded rationalityStag hunt gameLog-Linear LearningNash equilibriumK-regular networksStationary probabilityGibbs measureDegree distributionPartition function
Authors
Zhewei Wang, Emrah Akyol, Marcos M. Vasconcelos
Abstract
Network coordination games are widely used to model collaboration among interconnected agents, with applications across diverse domains including economics, robotics, and cyber-security. We consider networks of bounded-rational agents who interact through binary stag hunt games, a canonical game theoretic model for distributed collaborative tasks. Herein, the agents update their actions using logit response functions, yielding the Log-Linear Learning (LLL) algorithm. While convergence of LLL to a risk-dominant Nash equilibrium requires unbounded rationality, we consider regimes in which rationality is strictly bounded. We first show that the stationary probability of states corresponding to perfect coordination is monotone increasing in the rationality parameter $β$. For $K$-regular networks, we prove that the stationary probability of a perfectly coordinated action profile is monotone in the connectivity degree $K$, and we provide an upper bound on the minimum rationality required to achieve a desired level of coordination. For irregular networks, we show that the stationary probability of perfectly coordinated action profiles increases with the number of edges in the graph. We show that, for a large class of networks, the partition function of the Gibbs measure is well approximated by the moment generating function of Gaussian random variable. This approximation allows us to optimize degree distributions and establishes that the optimal network - i.e., the one that maximizes the stationary probability of coordinated action profiles - is $K$-regular. Consequently, our results indicate that networks of uniformly bounded-rational agents achieve the most reliable coordination when connectivity is evenly distributed among agents.