Paper deep dive
Learning to Coordinate over Networks with Bounded Rationality
Zhewei Wang, Emrah Akyol, Marcos M. Vasconcelos
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 2:00:24 AM
Summary
This paper analyzes network coordination games using a binary stag hunt model with boundedly rational agents. It demonstrates that Log-Linear Learning (LLL) dynamics on these networks are governed by a potential function, and that network connectivity (specifically K-regularity) significantly enhances the probability of achieving perfect coordination. The authors provide theoretical proofs for the monotonicity of coordination probability with respect to rationality and connectivity, and establish that regular graphs are optimal for maximizing coordination in large-scale networks.
Entities (5)
Relation Signals (3)
K-regular network → maximizes → Coordination Probability
confidence 96% · establishes that the optimal network—i.e., the one that maximizes the stationary probability of coordinated action profiles—is K-regular.
Log-Linear Learning → optimizes → Potential Function
confidence 95% · One can think of LLL as a form of stochastic distributed optimization algorithm, where the global function being maximized is the game’s potential function.
Bounded Rationality → influences → Coordination Probability
confidence 94% · stationary probability of states corresponding to perfect coordination is monotone increasing in the rationality parameter β
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\beta$. 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.07751v1
- Canonical: https://arxiv.org/abs/2604.07751v1
Trouble viewing inline? Open PDF directly →
Full Text
100,299 characters extracted from source content.
Expand or collapse full text
Learning to Coordinate over Networks with Bounded Rationality Zhewei Wang, Emrah Akyol and 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 well-known Log-Linear Learning (L) algorithm. While convergence of L to a risk-dominant Nash equilibrium of potential games 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. To analyze these stationary distributions, we study Gibbs measures using a Gaussian approximation for the potential function when the admissible action profiles are uniformly distributed. 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. I Introduction One of the possible applications that calls for the deployment of a multi-agent system is when there is a collective task (or a job) whose difficulty exceeds the capabilities of any individual agent operating in the environment. In this situation, at least a subset of the agents in the system need to work together to perform the task, and such synergistic behavior requires coordination. As a foundational principle in robotics, economics, computer science and microbiology, achieving coordination is a desirable feature and as such has been studied from the point of view of many mathematical models, including game theory. Coordination games are simultaneous-move games in which agents benefit from choosing the same action. Among these, the stag hunt game [50] captures the tension between a safe, low-reward action and a risky, high-reward action that requires cooperation. This simple model of incentives for collaborative interaction can be extended over a multi-agent network, where an agent interacts with a subset of all agents, called a neighborhood, leading to a much more complex and realistic setting suitable for designing modern engineering applications and analyzing socioeconomic phenomena. In practice, learning agents may not best-respond perfectly due to cognitive limitations, computational constraints, or stochastic execution errors - a condition broadly referred to as bounded rationality [49]. While network coordination games provide a rich mathematical framework, a system designer interested in orchestrating collective behavior, must contend with bounded rational agents. This is the case when the agents in our model are humans in socioeconomic networks, their decisions are influenced by highly subjective factors inherent to the human condition [20]. For instance, in the stag hunt game, the choice between hunting a hare or a stag may vary significantly across individuals and may not always be rationalizable [24, 10, 11]. Similarly, engineered agents such as robots or AI agents may not always be able to perform perfect optimization due to computational constraints or model hallucinations. In such cases a suboptimal solution must be implemented [53]. Other times, even if an agent can optimize perfectly, they may fail to execute that particular action due to the stochastic nature of the environment. Therefore, bounded rationality is a limiting factor on the predictability of the system behavior [52]. In this paper, we analyze the interplay of bounded rationality and connectivity in network coordination games. We focus on a binary stag hunt game in which agents decide whether to attempt a collective task of varying difficulty with the help of their neighbors. The underlying model assumes the agents play the game repeatedly, using a logit response dynamics with bounded rationality, seeking to learn to play a coordinated action profile in the network game. Due to the bounded rationality of the agents, there is a non-vanishing probability of miscoordination. We show that the probability of coordination with bounded rationality can be improved by increasing the connectivity of the network. This result is shown both for K-regular and for irregular networks. Then, we show that for a sufficiently large number of agents with a homogeneous level of bounded rationality, the networks that maximize the probability of coordination are K-regular (when one exists for the parameters of the game), or near K-regular. This set of results provides an important design principle for multi-agent network systems with homogeneous bounded rationality: for systems with a large number of agents, the designer can adjust the number of neighbors to achieve a prescribed level of coordination in the long run, even though the agents are responding to the actions of other agents imperfectly. I-A Related Literature I-A1 Network Coordination Games Network games have been extensively studied as models of strategic interaction among agents whose payoffs depend on the actions of their neighbors in a graph. The framework of graphical games was introduced by Kearns et al. in [23], which consisted of an undirected graph and a set of local payoff matrices for multi-player games. Kakade et al. [22] showed how graph structure can be exploited for efficient computation of Nash equilibria. Since their introduction, a rich literature has been developed propelled by the popularization of social networks. Jackson and Zenou [19] provide a comprehensive survey of games on networks, covering both complete-information and Bayesian settings. Coordination games on networks, in which agents benefit from aligning their actions with neighbors, have been studied in many different contexts [39, 19, 38, 55]. Variants of the base model that incorporate the ability to respond to cyberattacks and external biases has been proposed in [43, 44, 3]. A key insight from this literature is that the structure of the network (degree distribution and connectivity) plays a fundamental role in determining which equilibria are selected and how quickly agents converge to them. Our work contributes to this line of research by characterizing how network topology interacts with bounded rationality to affect coordination outcomes under stochastic learning dynamics. I-A2 Models of Bounded Rationality Bounded rationality has a long history tied to the literature on behavioral economics, originating with the seminal work of Simon [49], who argued that human decision makers operate under cognitive and computational constraints and therefore, are unable of achieving perfectly rational behavior. Since the work of Simon, many different models of bounded rationality have emerged. Prospect theory [21, 46, 40], which models risk-sensitive decision making under uncertainty; level-K thinking and cognitive hierarchy models [41, 9, 26, 14, 54], which assume agents perform a limited number of strategic reasoning steps predicting sequences of best-responses to best-responses up to a certain level determined by the cognitive capacity of the agent; and the quantal response equilibrium (QRE) [34, 16, 35], which replaces exact best responses with a stochastic choice rules known as a quantal best response, generalizing the notion of a Nash equilibrium when the agents no longer respond optimally to the others decisions. The QRE framework is closely related to the discrete choice models of McFadden [32] and naturally gives rise to the logit dynamics considered herein. I-A3 Log-Linear Learning Our approach to bounded rationality is based on Log-Linear Learning (L), which is an interactive algorithm where the agents repeatedly play the game revising their actions given the actions played by their neighbors [29]. In L, the agents respond suboptimaly using a logit kernel, which is similar to a quantal-best response, but subtly different in that the agents respond to their neighbors actions and not to their mixed strategies. L was introduced by Blume [6, 7] and has since been extensively studied in the context of potential games [2, 29, 1, 28]. One can think of L as a form of stochastic distributed optimization algorithm, where the global function being maximized is the game’s potential function. In an analogy with annealing [25], the literature on L primarily focuses on the asymptotics when the rationality (inverse temperature) grows without bound. In our model, however, rationality is kept bounded and we use the network as a means to compensate for such limitation. I-B Our Contributions The main contributions of this work are as follows. • We define a binary network coordination stag hunt game, and show that when the graph is undirected, this is a potential game. • Under L with homogeneous bounded rationality, we show that connectivity improves the probability that the agents will asymptotically play one of the two pure NE of the game. • When the network is K-regular, we show that the minimum rationality to achieve coordination with high probability is inversely proportional to the connectivity. • Using a Martingale Central Limit theorem, we show that under mild technical conditions the potential function evaluated at uniformly distributed action profiles converges in distribution to a Gaussian random variable, whose variance only depends on the degree distribution, thereby enabling optimization via Majorization theory. • We show that for a sufficiently large number of agents, regular graphs maximize the probability that homogeneous bounded-rational agents converge to a NE. Preliminary versions of some of the results in this paper have been presented in [57] and [56]. The present work significantly extends the scope of those contributions by providing complete proofs, extending the analysis to irregular graphs, and establishing the optimality of regular networks in the large-network regime and small rationality regimes. I-C Notation We use [N]=def1,2,…,N[N] def=\1,2,…,N\ to denote the set of agents. The symbols 0 and 1 denote the all-zeros and all-ones vectors in ℝNR^N, respectively. For a vector a∈0,1Na∈\0,1\^N, we denote by ‖a‖1=∑i=1Nai\|a\|_1= _i=1^Na_i its ℓ1 ^1 norm and by ‖a‖2=(∑i=1Nai2)1/2\|a\|_2=( _i=1^Na_i^2)^1/2 its ℓ2 ^2 norm; since a is binary, ‖a‖1=‖a‖22\|a\|_1=\|a\|_2^2. Graphs are denoted by =([N],ℰ)G=([N],E), where ℰ⊆[N]×[N]E [N]×[N] is the edge set. The adjacency matrix of G is denoted ∈0,1N×NA∈\0,1\^N× N, and the graph Laplacian is =def−L def=D-A, where =defdiag()D def=diag(A1) is the degree matrix. The neighborhood of agent i is i=defj∈[N]∣(i,j)∈ℰN_i def=\j∈[N] (i,j) \, and the degree of agent i is di=def|i|d_i def=|N_i|. We write a−ia_-i for the vector of actions of all agents except agent i, and aia_N_i for the sub-vector of actions of agent i’s neighbors. For a matrix M, ‖F\|M\|_F denotes its Frobenius norm and ‖2\|M\|_2 its spectral (operator) norm. The notation → D denotes convergence in distribution and → P denotes convergence in probability. I-D Organization The remainder of the paper is organized as follows. Section I introduces the problem setup, the binary stag hunt coordination game and its extension to networks. Section I establishes that the network coordination game is an exact potential game and characterizes the maximizers of the potential function. Section IV analyzes the trade-off between bounded rationality and connectivity under Log-Linear Learning for K-regular graphs, by proving monotonicity of stationary probability of coordinated action profiles in both β and K, and deriving an upper bound on the minimum rationality required for coordination. Section V extends the analysis to irregular graphs, showing that coordination probability increases with edge connectivity. Section VI addresses the optimal network design problem: we show that the partition function of the Gibbs distribution proportional to a moment generating function, and use this connection to prove the optimality of regular graphs in two regimes: small β (via Taylor series expansion) and large N (via a Gaussian approximation). When β and N are moderate, we show that regular graphs maximize a nontrivial spectral lower bound on the stationary probability of coordinated action profiles. Finally, Section VII concludes the paper and discusses directions for future work. I Problem Setup Consider a binary action networked coordination game with N agents. Let [N]=def1,2,…,N[N] def=\1,2,…,N\ denote the set of agents, whose interactions are described by an undirected and connected graph =def([N],ℰ)G def=([N],E). Each agent i∈[N]i∈[N] has a binary action space i=0,1A_i=\0,1\. Two nodes i,j∈[N]i,j∈[N] are connected if (i,j)∈ℰ(i,j) . The set of neighbors of agent i is denoted by i=defj∈[N]∣(i,j)∈ℰN_i def=\j∈[N] (i,j) \. The number of neighbors of agent i is denoted by |i||N_i|. We assume there are no self loops, i.e., (i,i)∉ℰ,(i,i) , i∈[N]i∈[N]. Let (i,j)∈ℰ(i,j) , and suppose that ai,aj∈0,1a_i,a_j∈\0,1\ are the actions played by agents i and j, respectively. Let θ∈ℝθ . The following bimatrix game specifies the payoffs for the pairwise interaction between agents i and j. game 22[aia_i][aja_j] 11 0 11 (1−θ,1−θ (1-θ,1-θ) (−θ,0) (-θ,0 ) 0 (0,−θ) (0,-θ ) (0,0) (0,0 ) Figure 1: A coordination game with parameter θ between two players. Remark 1 (Payoff interpretation) The payoff structure of the bimatrix game in Fig. 1 corresponds to a stag hunt coordination game [50] between two agents i and j. Notice the payoff matrix depends on the task difficulty θ∈ℝθ . A (binary) stag hunt coordination game between two agents is characterized by the existence of two pure strategy Nash equilibria. The following result establishes the range of values of θ for which the game in Fig. 1 corresponds to a coordination game. Proposition 1 Consider the bimatrix game in Fig. 1, and let ijS_ij denote its set of pure-strategy Nash equilibria. Then, ij=(0,0)ifθ>1(0,0),(1,1)if 0≤θ≤1(1,1)ifθ<0.S_ij= cases \(0,0) \&if\ \ θ>1\\ \(0,0),(1,1) \&if\ \ 0≤θ≤ 1\\ \(1,1) \&if\ \ θ<0. cases (1) Proof: The proof can be obtained by inspection using the definition of a Nash equilibrium [15]. ∎ I-A Coordination games over networks We study a network coordination game with N agents, where agent i plays the same action with all of its neighbors j∈ij _i. Let Vi:0,12→ℝV_i:\0,1\^2 be defined as Vi(ai,aj)=defai(aj−θ).V_i(a_i,a_j) def=a_i (a_j-θ ). (2) In a network game, the payoff that one player receives is the sum of all the payoffs of the bimatrix games Vi(ai,aj)V_i(a_i,a_j) played with each one of its neighbors. Therefore for the i-th player, the utility is determined as follows Ui(ai,a−i)=def∑j∈iVi(ai,aj).U_i(a_i,a_-i) def=Σ _j _iV_i(a_i,a_j). (3) The payoff of the i-th agent in our game is Ui(ai,a−i)=ai(∑j∈iaj−θ|i|).U_i(a_i,a_-i)=a_i ( _j _ia_j-θ|N_i| ). (4) I Potential Network Coordination Games The network stag hunt coordination game considered herein is always an exact potential game regardless of the graph structure. I-A Potential games Definition 1 Let iA_i denote the action set of the i-th agent in a game with payoff functions Ui(ai,a−i)U_i(a_i,a_-i), i∈[N]i∈[N]. Let =1×⋯×nA=A_1×·s×A_n. A game is an exact potential game if there is a potential function Φ : →ℝA such that Ui(ai′,a−i)−Ui(ai′,a−i)=Φ(ai′,a−i)−Φ(ai′,a−i),U_i(a _i,a_-i)-U_i(a _i,a_-i)= (a _i,a_-i)- (a _i,a_-i), (5) for all ai′,ai′∈ia_i ,a_i _i, a−i∈−ia_-i _-i, i∈[N]i∈[N]. Theorem 1 Let =([N],ℰ)G=([N],E) be an undirected and connected graph. Consider a networked coordination game defined by the payoff in (4) indexed by the parameter θ. The game is an exact potential game for any θ. Proof: The proof is in Appendix B. ∎ We have established that this networked coordination game always an exact potential game. In the next proposition, we obtain a closed form expression for its potential function. Proposition 2 Let ∈0,1N×NA∈\0,1\^N× N be the adjacency matrix of a graph G. The exact potential function for the network coordination game defined over G is given by Φ(a) _A(a) defined as Φ(a)=def12aa−θa+θ2⊤, _A(a) def= 12a TAa- 1 TAa+ θ21 A1, (6) where θ is the task difficulty and a∈0,1Na∈\0,1\^N is the action profile. Proof: The proof follows from equations (122) and (123) by expanding the sums and using the symmetry of A. ∎ A seminal result by Monderer and Shapley [37] establishes that, in an exact potential game, a strategy profile is a pure-strategy Nash equilibrium if and only if it is a local maximizer of the potential function. Consequently, identifying all pure-strategy Nash equilibria of the game is equivalent to finding all local maximizers of Φ . We will show that when the graph is connected, the potential function is maximized when every agent in the system plays the same action. We proceed with the characterization of the set of optimal solutions for the following optimization problem maximizea∈0,1N a∈\0,1\^Nmaximize 12aa−θa=deff0(a). 12a TAa- 1 TAa def=f_0(a). (7) Theorem 2 Consider a connected undirected graph G, with an adjacency matrix A. Let ⋆S _G denote the set of maximizers of the potential Φ(a) _A(a) for the network coordination game defined over G. Then, ⋆⊆,.S _G \0,1\. (8) Proof: Rewriting the objective function in (LABEL:OriginalProblem) in terms of the graph Laplacian111The graph Laplacian is defined as =def−L def=D-A such that =defdiag()D def=diag(A1)., we obtain f0(a)=(12−θ)d⊤a−12a⊤a,f_0(a)= ( 12-θ )d a- 12a La, (9) where d=defd def=A1 denotes the graph’s degree sequence. Since L is always a positive semidefinite matrix [8], if the graph is connected, the following holds a⊤a≥0,a∈0,1N,a La≥ 0,\ \ a∈\0,1\^N, (10) with equality if and only if a∈,.a∈\0,1\. Therefore, maxa∈0,1Nf0(a)≤maxa∈0,1N(12−θ)d⊤a. _a∈\0,1\^Nf_0(a)≤ _a∈\0,1\^N ( 12-θ )d a. (11) Since the function on the right hand side of (11) is linear in a, and di≥0d_i≥ 0 for all i∈[N]i∈[N], it is either increasing or decreasing depending on θ, which implies that a⋆=ifθ>12or 1ifθ=12ifθ<12.a = cases0&if\ \ θ> 12\\ 0\ or\ 1\ &if\ \ θ= 12\\ 1&if\ \ θ< 12. cases (12) Therefore, ⋆=argmaxf0(a)∣a∈0,1N⊆,.S_G = \f_0(a) a∈\0,1\^N \ \0,1\. ∎ IV Trade-off Between Rationality and Connectivity The correspondence between maximizers of the potential function and pure-strategy Nash equilibria establishes a link between optimization and the rational behavior of agents playing our network coordination game. Moreover, the equilibrium selected through interactive game play can be justified using the Log Linear Learning framework [6, 29, 2]. When bounded-rational agents gradually increase their rationality over time the learning dynamics converge to the risk-dominant equilibrium, which coincides with the global maximizer of the potential function. In the limit of infinite rationality, the network connectivity does not affect the induced Markov chain induced by L in the action space. However, it affects its convergence rate [38, 4]. In this section we will establish that the connectivity and rationality have a non-trivial interplay in the bounded rationality regime with respect to the stationary probability of coordinated action states. In the next subsection, we describe the L framework. IV-A Log-Linear Learning with Bounded Rationality Suppose that the agents in the network coordination game interact asynchronously over time as follows. At time t=0t=0, agent i picks an action ai(0)∈0,1a_i(0)∈\0,1\, i∈[N]i∈[N]. At all subsequent times t>0t>0, an agent is randomly selected with uniform probability, observes noiselessly the actions of its neighbors at the previous time, ai(t−1)=defaj(t−1)∣j∈ia_N_i(t-1) def=\a_j(t-1) j _i\, and updates its action according to a logit stochastic kernel defined as ℙ(Ai(t)=ai∣Ai(t−1)=ai)=σi(ai,β∣ai),P (A_i(t)=a_i A_N_i(t-1)=a_N_i )= _i(a_i,β a_N_i), (13) where σi(ai,β∣ai)=defeβUi(ai,ai)∑ai′∈0,1eβUi(ai′,ai),ai∈0,1. _i(a_i,β a_N_i) def= e^β U_i (a_i,a_N_i ) _a _i∈\0,1\e^β U_i (a _i,a_N_i ),\ a_i∈\0,1\. (14) In behavioral economics, the logit kernel is used to model discrete choice under bounded rationality [33, 51, 47, 48, 31]. The parameter β captures the agent’s level of rationality, varying between random behavior (β=0β=0) and deterministic best-response behavior (β→∞β→∞). The logit kernel defines a Markov chain with a state space =0,1NS=\0,1\^N corresponding to all possible strategy profiles a∈a for the network coordination game. For exact potential games, this Markov chain has a unique stationary distribution given by the Gibbs–Boltzmann distribution [6, 29, 38]. In particular, for our network coordination game defined over a graph with adjacency matrix A, the stationary distribution μ:→[0,1] _A:S→[0,1] is given by μ(a∣β)=defeβΦ(a)∑a′∈eβΦ(a′), _A(a β) def= e^β _A(a) _a e^β _A(a ), (15) where Φ _A is the potential function in (6). The existing analysis of L shows that as β→∞β→∞, the probability mass concentrates on the risk-dominant pure strategy NE, i.e., the maximizers of the potential function, which means that the only stochastically stable states of the Markov chain are the ones in ⋆S_G . However, we are interested in analyzing the bounded rationality regime, β<∞β<∞. In this case, the probability of any state distributed according to the Gibbs–Boltzmann distribution evaluated at a⋆∈⋆a _G is bounded away from one. In this section we are interested in the minimum value of β such that the agents coordinate on one of the states in ⋆S_G with high probability. For δ∈(0,1)δ∈(0,1) and θ∈[0,1]θ∈[0,1], for a connected undirected graph with adjacency matrix A define βmin(δ)=defminβ∣μ(a⋆∣β)≥1−δ, _A (δ) def= \β _A(a β)≥ 1-δ \, (16) where a⋆a is a maximizer of Φ _A given by (12). IV-B Regular graphs The class of K-regular graphs is characterized by nodes that each have a constant number of neighbors, i.e., |i|=K|N_i|=K for all i∈[N]i∈[N] [42]. Restricting our analysis to K-regular graphs allows us to examine how βmin(δ) _A (δ) varies as a function of the connectivity parameter K. Before discussing the interplay between rationality and connectivity in K-regular graphs, it is important to note that multiple non-isomorphic regular graphs may share the same degree K. These graphs cannot, in general, be related by a similarity transformation of their adjacency matrices. For instance, a bipartite and a non-bipartite regular graphs with the same degree are not isomorphic. Nevertheless, in what follows we construct a sequence of graphs K\A_K\ with increasing degree K, such that all graphs within the same isomorphism class yield the same value of βKmin(δ) _A_K (δ). Applying a similarity transformation is equivalent to re-assigning indices to agents. Although for a specific action profile a∈0,1N\a⋆a∈\0,1\^N \a \, the corresponding potential value can be different on two isomorphic graphs 1G_1 and 2G_2 with the same K and N, there exists a unique a~∈0,1N a∈\0,1\^N such that Φ1(a)=Φ2(a~) _G_1(a)= _G_2( a). Such a~ a can be derived by applying the same similarity transformation on a. Therefore, when computing the exact value of μ(a∣β) _A(a β) for a specific a≠a⋆a≠ a , we must specify and fix a graph G. Nevertheless, Φ(a⋆) _A(a ) remains constant for all isomorphic graphs with the same degree and so does μ(a⋆∣β) _A(a β). This is further discussed in the proof of our next theorem. The following lemma from graph theory characterizes the conditions under which a regular graph exists. Lemma 1 ([13]) A simple K-regular graph KG_K with N vertices of degree K exists if and only if K∈0,…,N−1K∈\0,…,N-1\ and NKNK is even. Lemma 2 Let KA_K be the adjacency matrix of a connected K-regular graph KG_K. The following statements hold: (a) If N is even and K<N−1K<N-1, then K+1G_K+1 always exists. Moreover, the adjacency matrix of a regular graph K+1G_K+1 can be constructed as follows: there exists a symmetric permutation matrix Π1 _1, and a permutation matrix Π2 _2 such that K+1=Π2(K+Π1)Π2⊤.A_K+1= _2(A_K+ _1) _2. (17) (b) If N is odd, K is even and K<N−2K<N-2, then K+1G_K+1 does not exist. However, K+2G_K+2 exists, and its adjacency matrix can be constructed as follows: there exist two distinct symmetric permutation matrices Π1,Π2 _1, _2 and a permutation matrix Π3 _3 such that K+2=Π3(K+Π1+Π2)Π3⊤.A_K+2= _3(A_K+ _1+ _2) _3 . (18) Proof: We start with part (a). Since N is even, NKNK is even for any K. By Lemma 1, KG_K exists for every K∈0,…,N−1K∈\0,…,N-1\. We construct K+1G_K+1 from KG_K by adding a perfect matching [13]. Let ¯K G_K denote the complement of KG_K. Since KG_K is K-regular, ¯K G_K is (N−1−K)(N-1-K)-regular with N−1−K≥1N-1-K≥ 1. By the handshaking lemma [13], ¯K G_K has at least N/2N/2 edges, and since it is regular of degree at least 11 on an even number of vertices, it contains a perfect matching ℳM. Let Π1 _1 be the permutation matrix associated with the matching ℳM. Adding ℳM to KG_K yields a (K+1)(K+1)-regular graph whose adjacency matrix is K+Π1A_K+ _1. The permutation matrix Π2 _2 accounts for a possible relabeling of the vertices. For part (b), when N is odd and K is even, NKNK is even so KG_K exists. However, (K+1)N(K+1)N is odd, so by Lemma 1, K+1G_K+1 does not exist. Since (K+2)N(K+2)N is even, K+2G_K+2 exists. We construct it by adding two disjoint perfect matchings (symmetric permutation matrices Π1 _1 and Π2 _2) from the complement graph, with Π3 _3 introduced for node relabeling. ∎ The following lemma provides an upper bound on the binary quadratic form aKa TA_Ka. Lemma 3 Let KA_K be the adjacency matrix of a connected K-regular graph. Let a∈0,1Na∈\0,1\^N be such that ‖a‖1=m\|a\|_1=m. The following inequality holds a⊤Ka≤mK,a∈0,1N.a A_Ka≤ mK,\ \ a∈\0,1\^N. (19) Proof: Let ‖K‖2\|A_K\|_2 denote the ℓ2 ^2 induced operator norm222The ℓ2 ^2 induced operator norm of KA_K is ‖K‖2=defsupx≠‖Kx‖2‖x‖2\|A_K\|_2 def= _x 0 \|A_Kx\|_2\|x\|_2. of KA_K. It is well known that ‖K‖2\|A_K\|_2 is the largest singular value of KA_K, which in this case is K. Since operator norms are consistent with the vector norm inducing them, we have ‖Ka‖2≤‖K‖2‖a‖2,a∈0,1N.\|A_Ka\|_2≤\|A_K\|_2\|a\|_2,\ \ a∈\0,1\^N. (20) Using the Cauchy–Schwarz inequality on aKa TA_Ka, we obtain aKa≤‖a‖2‖Ka‖2≤‖a‖22‖K‖2=‖a‖1‖K‖2=mK.a TA_Ka≤\|a\|_2\|A_Ka\|_2≤\|a\|^2_2\|A_K\|_2\\ =\|a\|_1\|A_K\|_2=mK. (21) ∎ Intuitively, aKa TA_Ka measures the total interaction among the m active nodes selected by the binary vector a. Since each node contributes at most K connections in a K-regular graph, the bound aKa≤mKa TA_Ka≤ mK follows from ‖K‖2=K\|A_K\|_2=K. From this point on, for simplicity, we ignore the constant term in our potential function ΦK _A_K and use the following expression instead Φ^K(a)=def12aKa−Kθ∑i∈[N]ai. _A_K(a) def= 12a TA_Ka-Kθ _i∈[N]a_i. (22) Theorem 3 Consider a network stag hunt coordination game defined over a connected K-regular graph KG_K with adjacency matrix KA_K and payoffs given by (4). Let the agents update their actions according to L with a rationality parameter β≥0β≥ 0. Define g(β,K)=defμK(a⋆∣β),g(β,K) def= _A_K(a β), (23) where a⋆∈,a ∈\0,1\ denotes a maximizer of the potential function ΦK _A_K and μK(a⋆∣β) _A_K(a β) is given by (15). Then, g is strictly increasing in β and monotone increasing in K. That is 1. g(β,K)<g(β,K+1)g(β,K)<g(β,K+1) for even N; 2. g(β,K)<g(β,K+2)g(β,K)<g(β,K+2) for odd N. Proof: First, we prove the monotonicity with respect to β. Computing the derivative of g with respect to β, we obtain the following equivalence: ∂g∂β>0 ∂ g∂β>0 if and only if Φ^K(a⋆)eβΦ^(a⋆)∑a′∈0,1NeβΦ^K(a′)>eβΦ^K(a⋆)∑a′∈0,1NΦ^K(a′)eβΦ^(a′). _A_K(a )e^β (a )\!\!\!\!\!\!\! _a ∈\0,1\^Ne^β _A_K(a )>\\ e^β _A_K(a )\!\!\!\!\!\!\! _a ∈\0,1\^N _A_K(a )e^β (a ). (24) Since eβΦ^K(a⋆)>0e^β _A_K(a )>0, the condition in (24) becomes ∑a′∈0,1N(Φ^K(a⋆)−Φ^K(a′))eβΦ^K(a′)>0. _a ∈\0,1\^N ( _A_K(a )- _A_K(a ) )e^β _A_K(a )>0. (25) Since a⋆a is a maximizer of Φ^K _A_K, we have that Φ^K(a⋆)≥Φ^K(a′),a′∈0,1N. _A_K(a )≥ _A_K(a ),\ \ a ∈\0,1\^N. (26) Moreover, since there is at least one a~∈0,1N a∈\0,1\^N such that ΦK(a⋆)>ΦK(a~) _A_K(a )> _A_K( a), we have that (25) holds and consequently, ∂g∂β>0 ∂ g∂β>0. Therefore, the function g(β,K)g(β,K) is continuous and strictly increasing in β, with g(β,K)→1g(β,K)→ 1, as β→∞β→∞. To obtain the monotonicity property with respect to K, let KA_K be the adjacency matrix of a fixed connected K-regular graph. Suppose N is even. Then a (K+1)(K+1)-regular graph K+1G_K+1 exists, and we denote its adjacency matrix by K+1A_K+1. By construction, from Lemma 2, there exist permutation matrices Π1 _1 and Π2 _2 such that K+1=Π2(K+Π1)Π2.A_K+1= _2(A_K+ _1) _2 T. (27) Define a~=Π2a a= _2 Ta, then aK+1a a TA_K+1a =aΠ2(K+Π1)Π2a =a T _2(A_K+ _1) _2 Ta (28) =a~(K+Π1)a~ = a T(A_K+ _1) a =a~Ka~+a~Π1a~. = a TA_K a+ a T _1 a. Note that the ℓp ^p-induced operator norm ‖Π1‖p=1\| _1\|_p=1 for all p. Let m=def‖a‖1m def=\|a\|_1. Using Hölder’s inequality, we have a~Π1a~ a T _1 a ≤‖a~‖∞‖Π1a~‖1 ≤\| a\|_∞\,\| _1 a\|_1 (29) ≤‖a~‖∞‖Π1‖1‖a~‖1=m. ≤\| a\|_∞\,\| _1\|_1\,\| a\|_1=m. Combining (28) and (29) gives aK+1a≤a~Ka~+m.a TA_K+1a≤ a TA_K a+m. (30) Without loss of generality, assume θ<1/2θ<1/2. Then, the unique global maximizer of ΦK _A_K is a⋆=a =1 and Φ^K(a⋆)=(1/2−θ)NK _A_K(a )=(1/2-θ)NK. For any a≠a 1, we have Φ^K(a)=12aKa−Kθm _A_K(a)= 12a TA_Ka-Kθ m (31) and Φ^K+1(a)≤12a~Ka~+m2−(K+1)θm. _A_K+1(a)≤ 12 a TA_K a+ m2-(K+1)θ m. (32) Therefore, Φ^K(Π2⊤a)−Φ^K+1(a)≥(θ−12)‖a‖1,a≠. _A_K ( _2 a )- _A_K+1(a)≥ (θ- 12 )\|a\|_1,\ \ a 1. (33) Now consider μK+1(a⋆∣β) _A_K+1(a β) =eβΦ^K+1(a⋆)∑a′∈0,1NeβΦ^K+1(a′) = e^β _A_K+1(a ) _a ∈\0,1\^Ne^β _A_K+1(a ) (34) =eβ(12−θ)NeβΦ^K(a⋆)∑a′∈0,1NeβΦ^K+1(a′), =e^β ( 12-θ )N e^β _A_K(a ) _a ∈\0,1\^Ne^β _A_K+1(a ), where we used Φ^K+1(a⋆)=Φ^K(a⋆)+(1/2−θ)N _A_K+1(a )= _A_K(a )+(1/2-θ)N. Since a~′=Π2a′ a = _2 Ta and Π2 _2 is bijective on 0,1N→0,1N\0,1\^N→\0,1\^N, we have ∑a′∈0,1NeβΦ^K(a′) _a ∈\0,1\^Ne^β _A_K(a ) =∑a~′∈0,1NeβΦ^K(a~′) = _ a ∈\0,1\^Ne^β _A_K( a ) (35) ≥∑a′∈0,1Neβ(Φ^K+1(a′)+(θ−12)‖a′‖1). ≥ _a ∈\0,1\^Ne^β ( _A_K+1(a )+ (θ- 12 )\|a \|_1 ). For a′=a⋆=a =a =1, we have ‖a′‖1=N\|a \|_1=N. For a′≠a 1, the bound Φ^K(a~′)≥Φ^K+1(a′)+(θ−1/2)‖a′‖1 _A_K( a )≥ _A_K+1(a )+(θ-1/2)\|a \|_1 holds, and in particular for a′=a⋆=a =a =1 we obtain equality. The above inequality yields ∑a′∈0,1NeβΦ^K(a′)≥eβ(θ−1/2)N∑a′∈0,1NeβΦ^K+1(a′). _a ∈\0,1\^N\!\!\!e^β _A_K(a )≥ e^β(θ-1/2)N\!\!\! _a ∈\0,1\^N\!\!\!e^β _A_K+1(a ). (36) Rearranging, we obtain ∑a′∈0,1NeβΦ^K+1(a′)≤eβ(1/2−θ)N∑a′∈0,1NeβΦ^K(a′). _a ∈\0,1\^N\!\!\!e^β _A_K+1(a )≤ e^β(1/2-θ)N\!\!\! _a ∈\0,1\^N\!\!\!e^β _A_K(a ). (37) Substituting back, we get μK+1(a⋆∣β)≥eβΦ^K(a⋆)∑a′∈0,1NeβΦ^K(a′)=μK(a⋆∣β). _A_K+1(a β)≥ e^β _A_K(a ) _a ∈\0,1\^Ne^β _A_K(a )= _A_K(a β). (38) Figure 2: Stationary probability μ(a⋆∣β) _A(a β) for K-regular graphs with N=14N=14 agents and θ=0.3θ=0.3, as a function of β for varying K. For any finite β, the probability of the risk-dominant action profile a⋆=a =1 is strictly increasing in K, while differences vanish as β→∞β→∞. Suppose N is odd. Then K+1G_K+1 does not exist. By construction, from Lemma 2, there exists an adjacency matrix for a regular graph K+2G_K+2 given by K+2=Π3(K+Π1+Π2)Π3⊤A_K+2= _3(A_K+ _1+ _2) _3 . Using a similar inductive procedure as when N is even and defining a~=Π3⊤a a= _3 a, then aK+2a≤a~Ka~+2m.a TA_K+2a≤ a TA_K a+2m. (39) The remainder of the argument proceeds identically, yielding μK(a⋆∣β)<μK+2(a⋆∣β) _A_K(a β)< _A_K+2(a β). Therefore, the function g is strictly monotone increasing in K. ∎ Remark 2 The inequality (38) above is in fact strict. To see this, note that for any a′a with ‖a′‖1<N\|a \|_1<N, the bound (θ−1/2)‖a′‖1<(θ−1/2)N(θ-1/2)\|a \|_1<(θ-1/2)N when θ<1/2θ<1/2, which introduces a strict gap in (37). The cases θ>1/2θ>1/2 (where a⋆=a =0) and θ=1/2θ=1/2 (where a⋆=or 1a =0\ or\ 1) follow by a analogous arguments. To illustrate the monotonicity results in Theorem 3 for networked coordination games with θ=0.3θ=0.3, we evaluated μ(a∣β) _A(a β) for K-regular graphs with N=14N=14 agents as a function β and different values of K. Figure 2 shows how for any fixed β<∞β<∞, the stationary probability of a⋆=a =1 is strictly increasing in K. Also notice that in the limit of β→∞β→∞ of Figure 2, the network connectivity does not make a significant difference as far as the stationary probability distribution. IV-C Minimum rationality required for coordination Recall the definition of βmin(δ)β _A(δ) in (16). Suppose that δ, the probability that agents fail to coordinate on the risk-dominant equilibrium, is fixed. Then there exists a trade-off between the minimal rationality βmin(δ)β _A(δ) and the connectivity K since μK(a⋆∣β) _A_K(a β) is increasing in both β and K. Intuitively, for θ≠1/2θ≠1/2, a more connected network allows for a smaller βmin(δ)β _A(δ) in order to guarantee that L achieves the same probability of coordination on a⋆a . Theorem 4 Suppose L is performed on a networked coordination game over a connected K-regular graph with task difficulty θ≠1/2θ≠1/2. Then, βKmin(δ)≤|(12−θ)K|−1×(log(1−δ)N−log(1−elog(1−δ)N)). _A_K (δ)≤ | ( 12-θ )K |^-1×\\ ( (1-δ)N- (1-e (1-δ)N ) ). (40) Proof: First, notice that μK(a⋆∣β)=eβ(12a⋆Ka⋆−Kθa⋆)∑a′∈0,1Neβ(12a′Ka′−Kθa′). _A_K(a β)= e^β ( 12a TA_Ka -K 1 Ta ) _a ∈\0,1\^Ne^β ( 12a TA_Ka -K 1 Ta ). (41) From Lemma 3 and the fact that β≥0β≥ 0, we have eβ(−Kθa′+12a′Ka′)≤eβ(−Kθm+12mK),e^β (-K 1 Ta + 12a TA_Ka )≤ e^β (-Kθ m+ 12mK ), (42) where ‖a′‖1=m\|a \|_1=m. Since exp(⋅) (·) is a strictly increasing function, for all a′∈0,1Na ∈\0,1\^N, we can group terms by their Hamming weight to obtain ∑a′∈0,1Neβ(−KθNa′+12a′Ka′)≤∑m=0N(Nm)eβ(−Kθm+12mK). _a ∈\0,1\^N\!\!\!\!\!\!\!\!e^β(-K 1_N Ta + 12a TA_Ka )≤ _m=0^N Nme^β(-Kθ m+ 12mK). (43) Applying the Binomial Theorem to the right-hand side of (43), we obtain ∑m=0N(Nm)eβK(12−θ)m=(1+eβK(12−θ))N. _m=0^N Nme^β K( 12-θ)m= (1+e^β K( 12-θ) )^N. (44) Therefore, a lower bound on (41) is given by μK(a⋆∣β) _A_K(a β) ≥eβK(12−θ)N(1+eβK(12−θ))N ≥ e^β K( 12-θ)N (1+e^β K( 12-θ) )^N (45) =(11+e−βK(12−θ))N. = ( 11+e^-β K( 12-θ) )^\!N. The proof follows immediately from setting the right-hand side of (45) equal to 1−δ1-δ and solving for β. ∎ Remark 3 Note that the right-hand side of (45) is also an increasing function of β, which can be verified by taking its derivative with respect to β. Moreover, this lower bound matches the true value of μK(a⋆∣β) _A_K(a β) when β=0β=0 and β→∞β→∞, so the bound in (45) is asymptotically tight. Corollary 1 Suppose L is performed on a networked coordination game over a connected K-regular graph with task difficulty θ≠1/2θ≠1/2. Then, βKmin(δ)∝1K. _A_K (δ) 1K. (46) Proof: The proof follows from Theorem 4 and the definition in (16). ∎ The consequence of Theorem 4 and Corollary 1 is that when agents are involved in the networked coordination game, more connected agents can afford to be less rational then less connected ones. The upper bound and the true value (obtained numerically) of βKmin(δ)β^min_A_K(δ) are shown in Figure 3 for different values of K. Figure 3: Upper bound and numerical value of βKmin(δ)β _A_K(δ) versus K (Theorems 4 and 1). Higher connectivity reduces the rationality required for coordination. V Irregular Graphs Having characterized the effect of connectivity on the stationary probability of jointly selecting the risk-dominant equilibrium a⋆a for regular graphs, we extend the analysis to irregular graphs. We show that the coordination probability remains monotone in the number of edges in this more general setting. V-A Inductive improvement by edge augmentation An important measure of graph connectivity is the number of edges. As shown in the next theorem, the stationary probability of L learning to play the optimal action profile grows monotonically with the number of edges. Definition 2 Graph s=([N],ℰ∪(i,j))G_s=([N],E∪\(i,j)\) is called a successor of graph =([N],ℰ)G=([N],E) if (i,j)∉ℰ(i,j) . Theorem 5 Let sG_s be a successor of G. Then, for any β>0β>0, μs(a⋆∣β)>μ(a⋆∣β), _A_s(a β)> _A(a β), (47) where A and sA_s are the adjacency matrices of G and sG_s, respectively. Proof: Let A and sA_s denote the adjacency matrices of G and sG_s, respectively. We have s−=ij+ji,A_s-A=e_ie_j T+e_je_i T, (48) where ie_i and je_j are the i-th and the j-th standard basis vectors in ℝNR^N. We prove the theorem for the case θ<1/2θ<1/2, so that a⋆=a =1. The case θ>1/2θ>1/2 is symmetric, and θ=1/2θ=1/2 is simpler, thus are omitted here. For a⋆=a =1, the potential values on sG_s and G satisfy Φs(a⋆)−Φ(a⋆)=(12−θ)(eiej+ejei)=2(12−θ). _s(a )- (a )= ( 12-θ )1 T(e_ie_j T+e_je_i T)1=2 ( 12-θ ). (49) However, for all a∈a such that ai=0a_i=0 or aj=0a_j=0, we have Φs(a)=Φ(a). _s(a)= (a). (50) The set a∈∣ai=0 or aj=0\a a_i=0 or a_j=0\ has cardinality 3⋅2N−23· 2^N-2 and is never empty. Then, we can compare μs(a⋆∣β) _G_s(a β) and μ(a⋆∣β) _G(a β) as follows μ(a⋆∣β) _G(a β) =eβΦ(a⋆)eβ(1−2θ)∑a∈eβΦ(a)eβ(1−2θ) = e^β (a )e^β(1-2θ) _a e^β (a)e^β(1-2θ) (51) <eβΦs(a⋆)∑a∈eβΦs(a)=μs(a⋆∣β). < e^β _s(a ) _a e^β _s(a)= _G_s(a β). The inequality is strict since there exists at least one a with ai=0a_i=0 or aj=0a_j=0 such that eβΦ(a)eβ(1−2θ)>eβΦs(a),e^β (a)e^β(1-2θ)>e^β _s(a), (52) which increases the denominator on the left-hand side relative to the right-hand side of (51), while both expressions share the same numerator eβΦs(a⋆)e^β _s(a ). ∎ Theorem 5 states that an increase in edge connectivity reduces the value of βmin(δ)β _A(δ). This can be visualized for a system with N=14N=14 agents in Fig. 4 where edges are randomly placed between two previously disconnected agents. That observation leads naturally to the question of how to distribute edges among a set of agents such that we maximize the stationary probability of coordination. Figure 4: Coordination probability μ(a⋆∣β) _G(a β) versus number of edges |ℰ||E| for N=14N=14 agents and a coordination game with θ=0.3θ=0.3. Adding edges monotonically increases the probability of coordination. VI Optimal Network Design Consider the problem of constructing a network with a fixed number of edges |ℰ||E| among N boundedly rational agents using L with a fixed parameter β, where the objective is to maximize the stationary probability of jointly selecting the risk-dominant action profile a⋆a . This problem is in general NP-hard due to the combinatorial explosion in the number of possible graphs and the non-convexity of the objective function. Moreover, evaluating the objective requires computing a sum of cardinality 2N2^N, which is impractical even for networks of moderate size. Nevertheless, in this section we characterize the role of regular graphs in three regimes: (1) small rationality; (2) moderate rationality; and (3) asymptotically large networks, N→∞N→∞. VI-A Ising stag hunt game reparameterization We reparametrize our game using Rademacher variables si=2ai−1∈−1,1s_i=2a_i-1∈\-1,1\, obtaining an Ising game [27] with the following equivalent potential function, Φ~(s)=18ss+(14−θ2) 1s+18 1, _A(s)= 18\,s TAs+ ( 14- θ2 )\,1 TAs+ 18\,1 TA1, (53) where s∈−1,1N.s∈\-1,1\^N. This reparameterization symmetrizes the state space and simplifies the analysis. Disregarding the constant term, we write Φ~(s)=18ss+(14−θ2) 1s, _A(s)= 18\,s TAs+ ( 14- θ2 )\,1 TAs, (54) which leads to the following stationary probability for an optimal strategy profile s⋆∈−,s ∈\-1,1\, μ~(s⋆∣β)=defeβΦ~(s⋆)∑s′∈−1,1NeβΦ~(s′). μ_A(s β) def= e^β _A(s ) _s ∈\-1,1\^Ne^β _A(s ). (55) We are interested in solving the following optimization problem ⋆∈argmax∈(N,|ℰ|)μ~(s⋆∣β),A ∈ *arg\,max_A\,∈\,G(N,|E|) μ_A(s β), (56) where (N,|ℰ|)G(N,|E|) denotes the set of all connected simple graphs on N nodes with |ℰ||E| edges. VI-B Partition function as a moment generating function In statistical physics, the denominator of the Gibbs distribution is known as the partition function [36]. The key tool for optimizing over graph structures is the observation that the partition function can be expressed in terms of a moment generating function (MGF). The partition function in the Rademacher coordinates is Z(β)=def∑s∈−1,1NeβΦ~(s)=2NS[eβΦ~(S)],Z_A(β) def= _s∈\-1,1\^Ne^β _A(s)=2^N\,E_S\! [e^β _A(S) ], (57) where S is a uniformly distributed random vector taking values on the set −1,1N\-1,1\^N, i.e., ℙ(S=s)=12N,s∈−1,1N.P(S=s)= 12^N,\ \ s∈\-1,1\^N. (58) The expectation on the right-hand side is the MGF of Φ~(S) _A(S) evaluated at β. We first observe that the numerator of the stationary distribution at the optimal action profile depends only on the number of edges and it is independent of graph’s degree distribution. Lemma 4 Let G be a simple undirected graph with |ℰ||E| edges. In the Rademacher parametrization, the potential at s⋆=s =1 and at s⋆=−s =-1 are Φ~()=(34−θ)|ℰ|,Φ~(−)=(θ−14)|ℰ|, _A(1)= ( 34-θ )|E|, _A(-1)= (θ- 14 )|E|, (59) Therefore, Φ~(s⋆) _A(s ) depends on A only through |ℰ||E|. Proof: The proof follows from direct computation. ∎ Since eβΦ~(s⋆)e^β _A(s ) is constant for all graphs with the same number of edges |ℰ||E|, maximizing the stationary probability of s⋆s given by μ~(s⋆∣β)=eβΦ~(s⋆)Z(β) μ_A(s β)= e^β _A(s )Z_A(β) (60) is equivalent to minimizing Z(β)Z_A(β), or equivalently, minimizing S[eβΦ~(S)]E_S[e^β _A(S)]. This equivalence holds for all values of β. VI-C Optimality of regular graphs for small rationality We first consider case when the agent’s rationality β is small. Expanding the MGF in a Taylor series around β=0β=0, we obtain S[eβΦ~(S)]=1+β[Φ~(S)]+β22[Φ~(S)2]+O(β3).E_S\! [e^β _A(S) ]=1+β\,E [ _A(S) ]+ β^22\,E [ _A(S)^2 ]+O(β^3). (61) Since A is the adjacency matrix of an undirected simple graph, we have =A=A T and Aii=0A_i=0. For S∈−1,1NS∈\-1,1\^N uniformly distributed, we have [Si]=0E[S_i]=0 and [SiSj]=0E[S_iS_j]=0 for all i≠ji≠ j. Therefore, [SS]=∑i≠jAij[SiSj]=0E[S TAS]= _i≠ jA_ij\,E[S_iS_j]=0 (62) and [S]=∑i=1Ndi[Si]=0.E[1 TAS]= _i=1^Nd_i\,E[S_i]=0. (63) Computing the first and second moments of Φ~(S) _A(S), we get [Φ~(S)]=18[SS]+(14−θ2)[S]=0E [ _A(S) ]= 18\,E[S TAS]+ ( 14- θ2 )E[1 TAS]=0 (64) and, after some algebra and using properties of Rademacher random variables, we obtain [Φ~(S)2]=|ℰ|16+(14−θ2)2∑i=1Ndi2=defσ2.E [ _A(S)^2 ]= |E|16+ ( 14- θ2 )^2 _i=1^Nd_i^2 def= _A^2. (65) Finally, S[eβΦ~(S)]=1+β22σ2+O(β3).E_S\! [e^β _A(S) ]=1+ β^22 _A^2+O(β^3). (66) Theorem 6 For sufficiently small β>0β>0, the stationary probability μ~(a⋆∣β) μ_A(a β) is maximized, over all graphs on N vertices with |ℰ||E| edges, by the K-regular graph with K=2|ℰ|/NK=2|E|/N, or by a near-K-regular graph when 2|ℰ|/N2|E|/N is not an integer. Proof: From (66), the partition function is Z(β)≈2N(1+β22σ2),Z_A(β)≈ 2^N (1+ β^22 _A^2 ), (67) which is monotone increasing in σ2 _A^2. Therefore, we are interested in minimizing the variance σ2=|ℰ|16+(14−θ2)2∑i=1Ndi2. _A^2= |E|16+ ( 14- θ2 )^2 _i=1^Nd_i^2. (68) The first term is fixed for a given |ℰ||E|. For the second term, minimizing σ2 _A^2 is equivalent to minimizing ∑i=1Ndi2 _i=1^Nd_i^2 over all degree sequences (d1,…,dN)(d_1,…,d_N) with ∑i=1Ndi=2|ℰ| _i=1^Nd_i=2|E|. We use Majorization theory [30] to characterize the minimizer. Recall that a vector x is majorized by y, i.e., ⪯x , if for all k=1,…,Nk=1,…,N, we have ∑i=1kx[i]≤∑i=1ky[i],∑i=1Nxi=∑i=1Nyi, _i=1^kx_[i]≤ _i=1^ky_[i], _i=1^Nx_i= _i=1^Ny_i, (69) where ξ[1]≥ξ[2]≥⋯≥ξ[N] _[1]≥ _[2]≥·s≥ _[N] denotes the decreasing rearrangement of a vector ∈ℝN ξ ^N. Since f(d)=d2f(d)=d^2 is convex, it is also Schur-convex, i.e., ⪯⟹∑i=1Nf(xi)≤∑i=1Nf(yi).x _i=1^Nf(x_i)≤ _i=1^Nf(y_i). (70) Therefore, ∑i=1Ndi2 _i=1^Nd_i^2 is minimized by the least majorized degree sequence, i.e., the most uniform one. Among all non-negative integer sequences with fixed sum 2|ℰ|2|E|: • When K=2|ℰ|/NK=2|E|/N is an integer, the least majorized sequence is the constant sequence (K,…,K)(K,…,K), which corresponds to a K-regular graph. • When K=2|ℰ|/NK=2|E|/N is not an integer, the minimizer is a near-K-regular sequence in which each di∈⌊K⌋,⌈K⌉d_i∈\ K , K \, since any other sequence with the same sum is majorized by it. Therefore, σ2 _A^2 is minimized by the K-regular (or near-K-regular) graph. From Lemma 4, Φ~(a⋆) _A(a ) depends only on |ℰ||E| and not on the graph structure, the numerator of μ~(a⋆∣β) μ_A(a β) is identical across all graphs with the same |ℰ||E|. For sufficiently small β, μ~(a⋆∣β)≈eβΦ~(s⋆)2N(1+β22σ2), μ_A(a β)≈ e^β _A(s )2^N (1+ β^22 _A^2 ), (71) which is decreasing in σ2 _A^2. Consequently, minimizing σ2 _A^2 maximizes μ~(a⋆∣β) μ_A(a β) for small β, and the K-regular graph is the optimizer. ∎ Remark 4 Theorem 6 reveals that, in the low-rationality regime, the graph structure affects the stationary distribution of coordination only through its degree distribution, while higher-order graph invariants (triangles, spectral gap, etc.) do not play a significant role and can be ignored. VI-D Moderate rationality For moderate values of β, the Taylor expansion is no longer accurate. We instead employ a spectral upper bound on the partition function that is valid for any β>0β>0 and N≥2N≥ 2. Theorem 7 Among all simple connected graphs on N vertices with |ℰ||E| edges, the coordination probability under L satisfies μ(a⋆∣β)≥(11+e−βλ1()2|1−2θ|)N, _A(a β)≥ ( 11+e^- β _1(A)2|1-2θ| )^\!N, (72) for all β>0β>0. This lower bound is maximized over all graphs with |ℰ||E| edges by the K-regular graph with K=2|ℰ|/NK=2|E|/N (when it exists). Therefore, the optimal graph ⋆A satisfies μ⋆(a⋆∣β)≥(11+e−βK2|1−2θ|)N. _A (a β)≥ ( 11+e^- β K2|1-2θ| )^\!N. (73) Proof: Working in the original binary action coordinates, recall the potential function Φ(a)=12aa−θ 1a. _A(a)= 12a TAa-θ\,1 TAa. (74) Completing the square, we obtain Φ(a)=12yy−θ2|ℰ|, _A(a)= 12y TAy-θ^2|E|, (75) where y=defa−θy def=a- 1. By the Rayleigh quotient characterization of the largest eigenvalue [18], we have yy≤λ1()‖y‖22,y∈ℝN,y TAy≤ _1(A)\,\|y\|_2^2,\ \ y ^N, (76) where λ1() _1(A) denotes the denotes the largest eigenvalue of A. For an action profile a with m=def‖a‖1m def=\|a\|_1, we have ‖y‖22=m(1−θ)2+(N−m)θ2.\|y\|_2^2=m(1-θ)^2+(N-m)θ^2. (77) Substituting (76) and (77) into (75), we obtain the following upper bound for the potential function Φ(a)≤λ1()2(m(1−θ)2+(N−m)θ2)−θ2|ℰ|. _A(a)≤ _1(A)2 (m(1-θ)^2+(N-m)θ^2 )-θ^2|E|. (78) Figure 5: Coordination probability μ(a⋆∣β) _A(a β) versus degree variance Var(d)Var(d) for irregular and K-regular graphs with N=14N=14 nodes and |ℰ|=42|E|=42 edges. The K-regular graph achieves the highest coordination probability. The bound (78) depends on a only through m=‖a‖1m=\|a\|_1. Hence, taking the exponential and summing over all a∈0,1Na∈\0,1\^N, we get Z(β)≤eβ(λ1()Nθ22−θ2|ℰ|)∑a∈0,1Neβλ1()2[(1−θ)2−θ2]‖a‖1.Z_A(β)≤ e^β ( _1(A)Nθ^22-θ^2|E| )\!\!\! _a∈\0,1\^Ne β _1(A)2 [(1-θ)^2-θ^2 ]\|a\|_1. (79) Since ∑a∈0,1Neβλ1()2[(1−θ)2−θ2]‖a‖1=∑m=0N(Nm)eβλ1()2[(1−θ)2−θ2]m. _a∈\0,1\^Ne β _1(A)2 [(1-θ)^2-θ^2 ]\|a\|_1\\ = _m=0^N Nme β _1(A)2 [(1-θ)^2-θ^2 ]m. (80) Writing eβλ1()2[(1−θ)2−θ2]m=(eβλ1()(1−θ)22)m(e−βλ1()θ22)me β _1(A)2 [(1-θ)^2-θ^2 ]m= (e β _1(A)(1-θ)^22 )^m (e^- β _1(A)θ^22 )^m (81) and multiplying and dividing by eβλ1θ22(N−m)e β _1θ^22(N-m), the sum becomes ∑m=0N(Nm)(eβλ1()(1−θ)22)m(eβλ1()θ22)N−m. _m=0^N Nm (e β _1(A)(1-θ)^22 )^m (e β _1(A)θ^22 )^N-m. (82) Using the Binomial Theorem yields Z(β)≤eβ(λ1()Nθ22−θ2|ℰ|)(eβλ1()θ22+eβλ1()(1−θ)22)N.Z_A(β)≤ e^β ( _1(A)Nθ^22-θ^2|E| ) (e β _1(A)θ^22+e β _1(A)(1-θ)^22 )^N. (83) From the Rayleigh quotient, we have that for any graph with |ℰ||E| edges, the largest eigenvalue satisfies the following inequality λ1()≥ 1‖22=2|ℰ|N _1(A)≥ 1 TA\,1\|1\|_2^2= 2|E|N (84) with equality if and only if A is the adjacency matrix of a K-regular graph with K=2|ℰ|/NK=2|E|/N. The upper bound in (83) is an increasing function of λ1() _1(A) for all β>0β>0. By (84), λ1 _1 is minimized by the K-regular graph, so the upper bound is also minimized when the graph is K-regular. To obtain (72), consider a⋆=a =1 (the case when a⋆=a =0 is analogous). Then, ΦK()=K(1/2−θ)N _A_K(1)=K(1/2-θ)N. Using Φ^K(a)=ΦK(a)−θ2|ℰ| _A_K(a)= _A_K(a)-θ^2|E|, we have μ⋆(∣β)≥eβK(1−θ)2N/2(eβKθ22+eβK(1−θ)22)N=(11+e−βK(1−2θ)2)N. _A (1 β)≥ e^β K(1-θ)^2N/2 (e β Kθ^22+e β K(1-θ)^22 )^N\\ = ( 11+e^- β K(1-2θ)2 )^\!N. (85) Since θ<1/2θ<1/2 implies a⋆=a =1, we have 1−2θ=|1−2θ|1-2θ=|1-2θ|. The case a⋆=a =0 gives the same expression with 2θ−12θ-1. ∎ Remark 5 Theorem 7 shows that using K-regular graph maximizes a lower bound on μ⋆(a⋆∣β) _A (a β) that depends on the graph only through λ1() _1(A). Whether exact optimality holds for all β remains an open question. Figure 5 shows that when compared with randomly generated connected irregular graphs with a fixed number of edges, the K-regular graph yields the largest stationary probability of coordination. The spectral bound reveals two distinct ways by which regularity improves coordination. First, the spectral radius λ1 _1 is minimized, giving the tightest Rayleigh quotient bound on the quadratic form yy TAy. Second, the leading term in (83) is equal to one: the condition λ1N/2=|ℰ| _1N/2=|E| holds if and only if the graph is regular, and for irregular graphs the leading factor eβ(λ1Nθ2/2−θ2|ℰ|)>1e^β( _1Nθ^2/2-θ^2|E|)>1, increasing the partition function and reducing the coordination probability. For K-regular graphs, the lower bound in (72) can be compared with the bound in (45). Both have the sigmoid-power form, but they arise from different bounding techniques: (45) uses the operator norm bound on aKa≤mKa TA_Ka≤ mK applied directly to the potential, while (72) uses the Rayleigh quotient after completing the square. For θ∈(0,1)θ∈(0,1), the two bounds are equivalent and yield the same minimum-β condition of Theorem 4. VI-E Optimization of asymptotically large graphs For arbitrary β, the partition function depends on more than just the graph’s degree distribution, and as a result the optimization becomes extremely challenging. Here, we show that tractability is recovered in the regime of large graphs, when N→∞N→∞. Under mild technical conditions, we can show that the partition function can be well approximated by the MGF of a Gaussian random variable. This is illustrated in Fig. 6. We begin with the following lemmata, which establishes the the asymptotic normality of the the potential function for a sequence of graphs satisfying two technical conditions. In this section we will use the reparameterization as an Ising game. Lemma 5 (Martingale Central Limit Theorem [17]) For a martingale difference sequence Dkk=1N\D_k\_k=1^N with a filtration ℱkk=1N\F_k\_k=1^N, define VN=def∑k=1N[Dk2∣ℱk−1]V_N def= _k=1^NE[D_k^2 _k-1] and σN2=def∑k=1N[Dk2] _N^2 def= _k=1^NE[D_k^2]. If (i) max1≤k≤N|Dk|/σN→0 _1≤ k≤ N|D_k|/ _N P0, (i) VN/σN2→1V_N/ _N^2 P1, then ∑k=1NDkσN→(0,1). _k=1^ND_k _N\; d\;N(0,1). (86) Figure 6: Convergence in distribution of the normalized potential function ΦN(S)/σN _N(S)/ _N to a standard Gaussian for Erdös–Rényi random graphs G(N,p)G(N,p) with p=10/Np=10/N and θ=0.3θ=0.3. As N grows, the empirical density (histogram) concentrates around the (0,1)N(0,1) density (solid curve), illustrating Lemma 6 for the sparse graph regime. Lemma 6 Let (N)\A^(N)\ be a sequence of adjacency matrices of simple undirected graphs with degrees di(N)d_i^(N) and |ℰN||E_N| edges, and let S=(S1,…,SN)S=(S_1,…,S_N) be an i.i.d. sequence of Rademacher random variables. Define Φ~N(S)=def18S(N)S+(14−θ2) 1(N)S, _N(S) def= 18\,S TA^(N)S+ ( 14- θ2 )\,1 TA^(N)S, (87) and set c=def14−θ2c def= 14- θ2 and σN2=def|ℰN|16+c2∑i=1N(di(N))2. _N^2 def= |E_N|16+c^2 _i=1^N (d_i^(N) )^2. (88) Assume that (N)A^(N) satisfies the following conditions: (i) ΔN=defmaxidi(N)=o(σN) _N def= _id_i^(N)=o( _N), (i) ∑i=1N(di(N))2=O(σN2) _i=1^N(d_i^(N))^2=O( _N^2). Then, Φ~N(S)−[Φ~N(S)]σN D(0,1). _N(S)-E [ _N(S) ] _N\; D\;N(0,1). (89) Proof: We apply the martingale central limit theorem in Lemma 5. We begin by writing the potential function as Φ~N(S)=14∑1≤i<j≤NAij(N)SiSj+c∑i=1Ndi(N)Si. _N(S)= 14 _1≤ i<j≤ NA^(N)_ij\,S_iS_j+c _i=1^Nd_i^(N)S_i. (90) Since [Si]=0E[S_i]=0 and [SiSj]=0E[S_iS_j]=0 for i≠ji≠ j, we have [Φ~N(S)]=0E [ _N(S) ]=0 and Var(Φ~N(S))=|ℰN|16+c2∑i=1N(di(N))2=defσN2.Var ( _N(S) )= |E_N|16+c^2 _i=1^N(d_i^(N))^2 def=σ^2_N. (91) Define the following filtration333Here σ(S1,…,Sk)σ(S_1,…,S_k) denotes the smallest σ-algebra generated by S1,…,SkS_1,…,S_k. Not to be confused with standard deviation. ℱk=defσ(S1,…,Sk)F_k def=σ(S_1,…,S_k) (92) and Mk=def[Φ~N(S)∣ℱk],Dk=defMk−Mk−1.M_k def=E [ _N(S) _k ], D_k def=M_k-M_k-1. (93) Since [Sℓ∣ℱk]=0E [S_ _k ]=0 for ℓ>k >k, we have Mk=14∑1≤i<j≤kAij(N)SiSj+c∑i=1kdi(N)Si,M_k= 14 _ subarrayc1≤ i<j≤ k subarrayA^(N)_ij\,S_iS_j+c _i=1^kd_i^(N)S_i, (94) and therefore Dk=Sk(14∑i=1k−1Aik(N)Si+cdk(N)).D_k=S_k\! ( 14 _i=1^k-1A^(N)_ik\,S_i+c\,d_k^(N) ). (95) Observe that DkD_k is ℱkF_k-measurable and [Dk∣ℱk−1] [D_k _k-1] =[Sk∣ℱk−1](14∑i=1k−1Aik(N)Si+cdk(N)) =E[S_k _k-1] ( 14 _i=1^k-1A^(N)_ik\,S_i+c\,d_k^(N) ) (96) =(a)0, (a)=0, (97) where (a)(a) follows from SkS_k being independent of ℱk−1F_k-1 and having zero mean. Therefore, Dkk=1N\D_k\_k=1^N is a martingale difference sequence [12], and Φ~N(S)=∑k=1NDk. _N(S)= _k=1^ND_k. (98) Since |Si|=1|S_i|=1, we can bound the increments using the triangle inequality as |Dk|≤(14+|c|)dk(N).|D_k|\;≤\; ( 14+|c| )\,d_k^(N). (99) By assumption (i), max1≤k≤N|Dk|σN≤(14+|c|)ΔNσN⟶0, _1≤ k≤ N |D_k| _N\;≤\; ( 14+|c| )\, _N _N 0, (100) which verifies condition (i) of Lemma 5. Next, consider the conditional variance process defined as VN=def∑k=1N[Dk2∣ℱk−1].V_N\; def=\; _k=1^NE\! [D_k^2 _k-1 ]. (101) Since Sk2=1S_k^2=1 and SkS_k is independent of ℱk−1F_k-1, we have [Dk2∣ℱk−1]=(14∑i=1k−1Aik(N)Si+cdk(N))2,E [D_k^2 _k-1 ]= ( 14 _i=1^k-1A^(N)_ik\,S_i+c\,d_k^(N) )^2, (102) and taking its expectation, we obtain [VN]=∑k=1N[Dk2]=σN2.E[V_N]= _k=1^NE[D_k^2]= _N^2. (103) It remains to verify condition (i) of Lemma 5. Since [VN]=σN2E[V_N]= _N^2, we will show that Var(VN)=o(σN4)Var(V_N)=o( _N^4). Now consider the from S we construct new sequence of random variables S(i)=(S1,…,Si−1,Si′,Si+1,…,SN),S^(i)=(S_1,…,S_i-1,S_i ,S_i+1,…,S_N), (104) where Si′S_i is an independent copy of SiS_i with the same distribution. Let VN(i)V_N^(i) denote the same quantity as VNV_N constructed from S(i)S^(i) instead of S. From (102), the k-th term in VNV_N given in (101) depends on SiS_i only if k>ik>i and Aik(N)=1A_ik^(N)=1. Since Si′−Si∈−2,0,2S_i -S_i∈\-2,0,2\ and enters the expression inside the square of (102) linearly, the change in the k-th summand is at most Cdk(N)C\,d_k^(N) for a constant C that depends only on c. Summing over the neighbors of node i such that k>ik>i and bounding dk(N)≤ΔNd_k^(N)≤ _N, we obtain |VN−VN(i)|≤C∑k>iAik(N)=1dk(N)≤Cdi(N)ΔN. |V_N-V_N^(i) |\;≤\;C\! _ subarrayck>i\\ A_ik^(N)=1 subarrayd_k^(N)\;≤\;C\,d_i^(N)\, _N. (105) By the Efron–Stein inequality (cf. Lemma 7 in Appendix A), Var(VN)≤12∑i=1N[(VN−VN(i))2]≤C22ΔN2∑i=1N(di(N))2.Var(V_N)\;≤\; 12 _i=1^NE\! [ (V_N-V_N^(i) )^2 ]\;≤\; C^22\, _N^2 _i=1^N (d_i^(N) )^2. (106) Since [VN]=σN2E[V_N]= _N^2, using (103), we have VNσN2−1=VN−[VN]σN2. V_N _N^2-1\;=\; V_N-E[V_N] _N^2. (107) By Chebyshev’s inequality and the variance bound in (106), ℙ(|VNσN2−1|>ε)≤Var(VN)ε2σN4≤C22ε2ΔN2∑i=1N(di(N))2σN4.P\! ( | V_N _N^2-1 |> )\;≤\; Var(V_N) ^2\, _N^4\;≤\; C^22 ^2\, _N^2 _i=1^N (d_i^(N) )^2 _N^4. (108) By assumptions (i) and (i), ΔN2/σN2→0 _N^2/ _N^2→ 0 and ∑i=1N(di(N))2=O(σN2) _i=1^N(d_i^(N))^2=O( _N^2), we have ΔN2∑i=1N(di(N))2σN4⟶ 0. _N^2 _i=1^N (d_i^(N) )^2 _N^4\; \;0. (109) Therefore, Var(VN)=o(σN4)Var(V_N)=o( _N^4) which implies VN/σN2→1V_N/ _N^2 P1. Finally, from Lemma 5, we have ΦN(S)−[ΦN(S)]σN⟶(0,1). _N(S)-E [ _N(S) ] _N D N(0,1). (110) ∎ The Gaussian approximation established in Lemma 6 provides a way to establish the optimality of regular graphs in the asymptotic regime N→∞N→∞. Theorem 8 Consider the ensemble of adjacency matrices (N)A^(N) that satisfy the following asymptotic conditions: (i) ΔN=defmaxidi(N)=o(σN) _N def= _id_i^(N)=o( _N), (i) ∑i=1N(di(N))2=O(σN2) _i=1^N(d_i^(N))^2=O( _N^2). Then, for sufficiently large N and for all β>0β>0, the stationary probability μ~(N)(a⋆∣β) μ_A^(N)(a β) is maximized, over all graphs on N vertices with |ℰN||E_N| edges, by the K-regular graph with K=2|ℰN|/NK=2|E_N|/N, or by a near-K-regular graph when 2|ℰN|/N2|E_N|/N is not an integer. Proof: Under conditions (i) and (i), Lemma 6 implies that a Gaussian approximation for Φ~(N)(S) _A^(N)(S) holds. That is, Φ~(N)(S)≈(0,σN2) _A^(N)(S) (0, _N^2), and thus the MGF in the denominator of the objective function is approximately S[eβΦ~(N)(S)]≈eβ2σN2/2.E_S\! [e^β _A^(N)(S) ]≈ e^β^2 _N^2/2. (111) Since the exponential function is monotone increasing, minimizing (111) over the class of graphs for a given |ℰN||E_N| edges reduces to minimizing σN2 _N^2. Recall from (88) that σN2=|ℰN|16+c2∑i=1N(di(N))2. _N^2= |E_N|16+c^2 _i=1^N (d_i^(N) )^2. (112) The first term is fixed for a given |ℰN||E_N|. Hence, the network design problem reduces to minimized1(N),…,dN(N) d_1^(N),…,d^(N)_Nminimize ∑i=1N(di(N))2 _i=1^N (d^(N)_i )^2 (113) subject to ∑i=1Ndi(N)=2|ℰN|,di(N)∈ℤ. _i=1^Nd_i^(N)=2|E_N|, d_i^(N) . We can solve this optimization problem and characterize the optimal degree distribution using Majorization theory as in (69) and (70). Therefore, the optimal degree sequence is regular or near-regular as in Theorem 6 depending on the prescribed number of nodes N and edges ℰNE_N in NA_N. ∎ VI-F Price of Irregularity - PoI Theorems 6, 7 and 8 provide a new design principle for multi-agent networks. Given a connectivity budget of |ℰN||E_N| communication links among N homogeneously bounded rational agents, the system designer should distribute edges as evenly as possible. The detailed topology matters for intermediate values of rationality, but when β→0β→ 0 and when N→∞N→∞ (under mild technical conditions), only the degree distribution matters, and the optimal graphs are either regular or near-regular. In the limit N→∞N→∞, the “price of irregularity” is captured by the empirical degree variance Var(d(N))Var(d^(N)), where d(N)d^(N) denotes the degree distribution of NA_N, i.e., d(N)=⊤Nd^(N)=1 A_N. To see this, compare a K-regular graph N′A_N with an arbitrary graph N′A_N having the same number of edges. Since both graphs share the same |ℰN||E_N|, the potential functions evaluated at the coordinated action profile a⋆∈,a ∈\1,0\ coincide, i.e. ΦN′(a⋆)=ΦN′(a⋆) _A_N (a )= _A_N (a ), therefore PoI=deflogμN′(a⋆)μN′(a⋆)=logZN′−logZN′.PoI def= _A_N (a ) _A_N (a )= Z_A_N - Z_A_N . (114) Applying the Gaussian approximation from Lemma 6, each log-partition function is determined by the variance of the potential: logZN≈Nlog2+β22σN2, Z_A_N≈ N 2+ β^22 _N^2, (115) where σN2=|ℰN|16+c2∑j=1Ndj2,c=14−θ2. _N^2= |E_N|16+c^2 _j=1^Nd_j^2, c= 14- θ2. (116) Since the term |ℰN|16 |E_N|16 is common to both graphs, the difference only depends on the degree distribution. We decompose ∑j=1Ndj2=N(d¯2+Var(d)), _j=1^Nd_j^2=N\! ( d^2+Var(d) ), (117) and note that the average degree of any graph is d¯=1N∑j=1Ndj=2|ℰN|N. d= 1N _j=1^Nd_j= 2|E_N|N. (118) Since both graphs share the same |ℰN||E_N| and N, they have the same average degree d¯=K d=K. Since Var(d′)=0Var(d )=0 for the K-regular graph N′A_N , we obtain PoI=logμN′(a⋆)μN′(a⋆)≈β2c2N2Var(d′)>0,PoI= _A_N (a ) _A_N (a )≈ β^2c^2N2\,Var(d )>0, (119) where d′d is the degree distribution of N′A_N . This penalty is larger for networks with heterogeneous degree distributions and large N. It scales quadratically in both the rationality parameter β and the parameter c=14−θ2c= 14- θ2, vanishing only at θ=12θ= 12, where the potential becomes insensitive to degree heterogeneity. To empirically validate the price of irregularity, we generate random connected graphs with the same number of edges as a K-regular graph (K=6K=6) across several values of N and compare the Gibbs probability of the optimal action profile on each irregular graph to that of the regular graph. Figure 7 plots the log-ratio log(μN′/μN′) ( _A_N / _A_N ) against N⋅Var(d)N·Var(d) for each irregular graph. The results confirm an approximately linear relationship between the PoIPoI and NVar(d)N\,Var(d), which holds even for modest values of N. This is consistent with the asymptotic expression obtained in (119). Figure 7: Price of Irregularity VII Conclusions and Future Work We studied the problem of learning to coordinate with bounded rationality over a network. Assuming the agents adhere to L with a homogeneous bounded rationality parameter, we showed that the stationary probability of coordinated (risk-dominant) action profiles can be increased by improving connectivity in regular graphs. We also showed that more connected networks can operate with agents with lower rationality and still achieve a given level of coordination than less connected ones. This is the first design principle from this work. This creates a form of Wisdom of Crowds [5], where a NE (approximately) emerges by aggregating information from neighbors and decisions propagating imperfectly over the network. Additionally, we proved that when the networks are irregular, the stationary probability of a coordinated action profile is monotone increasing with respect to the operation of adding new edges to the graph. Finally, we proved that for small rationality, and for networks with a sufficiently large number of agents, regular (or near-regular) graphs are optimal when the agents have homogeneous bounded rationality. When rationality and the number of agents is moderate, regular graphs maximize a lower bound on the stationary probability and are a robust choice for maximizing the coordination of bounded rational agents. This is the second design principle from this work. This work can be extended in many different directions. The first is to consider the possibility of having agents with heterogeneous bounded rationalities, and design the connectivity among them so as to promote coordination. In particular, we are interested in the question of whether higher rationality agents must be more connected among themselves (segregation), or if connectivity should be distributed by connecting lower rationality agents to agents with higher rationality. Yet another important research problem is to consider the scheduling of agents in heterogeneous systems. In that case, we would like to determine the optimal agent schedule to maximize their ultimate coordination. We would like to determine whether higher rationality agents should be updated more or less frequently than other agents. Finally, we suggest the generalization of this approach to handle very large scale graphs using graphons [45]. VIII Acknowledgments The authors would like to thank Dr. Yifei Zhang for discussions and insightful suggestions at an early stage of this work. Appendix A Auxiliary Results Lemma 7 (Efron–Stein inequality) Let X1,…,XnX_1,…,X_n be independent random variables and let f(X1,…,Xn)f(X_1,…,X_n) be square-integrable. For each 1≤i≤n1≤ i≤ n, let Xi′X_i be an independent copy of XiX_i and define f(i)=f(X1,…,Xi−1,Xi′,Xi+1,…,Xn).f^(i)=f(X_1,…,X_i-1,X_i ,X_i+1,…,X_n). (120) Then Var(f)≤12∑i=1n[(f−f(i))2].Var(f)\;≤\; 12 _i=1^nE\! [(f-f^(i))^2 ]. (121) Appendix B Proofs B-A Proof of Theorem 1 Consider the following potential function Φ(a)=def12∑i∈[N]∑j∈iϕ(ai,aj), (a) def= 12Σ _i∈[N]Σ _j _iφ(a_i,a_j), (122) where ϕ(ai,aj)=defaiaj+(1−ai−aj)θ.φ(a_i,a_j) def=a_ia_j+(1-a_i-a_j)θ. (123) The function ϕφ is an exact potential for the two-player game with payoff ViV_i. Therefore, the following holds: ϕ(ai′,aj)−ϕ(ai′,aj)=Vi(ai′,aj)−Vi(ai′,aj),φ(a_i ,a_j)-φ(a_i ,a_j)=V_i(a_i ,a_j)-V_i(a_i ,a_j), (124) for all ai′,ai′∈0,1a_i ,a_i ∈\0,1\ such that ai′≠ai′a_i ≠ a_i . We proceed by verifying that the function in (122) satisfies the condition in (5). Let m∈[N]m∈[N], and am′,am′∈0,1a _m,a _m∈\0,1\ such that am′≠am′a _m≠ a _m. Then, Φ(am′,a−m)−Φ(am′,a−m)=12∑i∈[N]∑j∈iϕ(ai,aj)|(am′,a−m)−12∑i∈[N]∑j∈iϕ(ai,aj)|(am′,a−m). (a _m,a_-m)- (a _m,a_-m)=\\ 12 _i∈[N] _j _iφ(a_i,a_j) |_(a_m ,a_-m)\\ - 12 _i∈[N] _j _iφ(a_i,a_j) |_(a_m ,a_-m). (125) Then, notice that ∑i∈[N]∑j∈iϕ(ai,aj)=∑j∈mϕ(am,aj)+∑i≠m∑j∈iϕ(ai,aj). _i∈[N] _j _iφ(a_i,a_j)= _j _mφ(a_m,a_j)+ _i≠ m _j _iφ(a_i,a_j). (126) Recall that ϕ(am′,aj)−ϕ(am′,aj)=Vm(am′,aj)−Vm(am′,aj).φ(a_m ,a_j)-φ(a_m ,a_j)=V_m(a_m ,a_j)-V_m(a_m ,a_j). (127) Therefore, Φ(am′,a−m)−Φ(am′,a−m)=12∑j∈m[Vm(am′,aj)−Vm(am′,aj)]+12∑i≠m∑j∈iϕ(ai,aj)|(am′,a−m)−12∑i≠m∑j∈iϕ(ai,aj)|(am′,a−m). (a _m,a_-m)- (a _m,a_-m)=\\ 12 _j _m [V_m(a_m ,a_j)-V_m(a_m ,a_j) ]\\ + 12 _i≠ m _j _iφ(a_i,a_j) |_(a_m ,a_-m)\\ - 12 _i≠ m _j _iφ(a_i,a_j) |_(a_m ,a_-m). (128) The first term in (128) is equal to 12[Um(am′,a−m)−Um(am′,a−m)]. 12 [U_m(a _m,a_-m)-U_m(a _m,a_-m) ]. (129) We proceed with showing that the remaining two terms yield an identical contribution. For all i≠mi≠ m such that m∉im _i, ∑j∈iϕ(ai,aj)|(am′,a−m)=∑j∈iϕ(ai,aj)|(am′,a−m). _j _iφ(a_i,a_j) |_(a_m ,a_-m)= _j _iφ(a_i,a_j) |_(a_m ,a_-m). (130) Define the following set m=defi∣i≠m and m∈iS_m def= \i i≠ m and m _i \ (131) and evaluate the difference ∑i∈m∑j∈iϕ(ai,aj)|(am′,a−m)−∑i∈m∑j∈iϕ(ai,aj)|(am′,a−m), _i _m _j _iφ(a_i,a_j) |_(a_m ,a_-m)\\ - _i _m _j _iφ(a_i,a_j) |_(a_m ,a_-m), (132) which is equal to ∑i∈mϕ(ai,am′)|(am′,a−m)−∑i∈mϕ(ai,am′)|(am′,a−m). _i _mφ(a_i,a _m) |_(a_m ,a_-m)\!\!\!- _i _mφ(a_i,a_m ) |_(a_m ,a_-m). (133) Since ϕ(ai,aj)=ϕ(aj,ai),φ(a_i,a_j)=φ(a_j,a_i), (134) we have that (133) is equal to ∑i∈m[ϕ(am′,ai)−ϕ(am′,ai)]. _i _m [φ(a_m ,a_i)-φ(a_m ,a_i) ]. (135) Finally, since ϕφ is a potential function for the two-player game between i and j when j∈ij _i, and the graph is undirected so that m=mS_m=N_m, we have ∑i∈m[Vm(am′,ai)−Vm(am′,ai)]=Um(am′,a−m)−Um(am′,a−m). _i _m [V_m(a_m ,a_i)-V_m(a_m ,a_i) ]\\ =U_m(a_m ,a_-m)-U_m(a_m ,a_-m). (136) Combining the two contributions, we obtain Φ(am′,a−m)−Φ(am′,a−m)=Um(am′,a−m)−Um(am′,a−m), (a _m,a_-m)- (a _m,a_-m)=U_m(a _m,a_-m)-U_m(a _m,a_-m), (137) which is the condition in (5). ■ References [1] A. S. Akbar, H. Jaleel, W. Abbas, and J. S. Shamma (2022) Robustness of learning in games with heterogeneous players. IEEE Transactions on Automatic Control 68 (3), p. 1553–1567. Cited by: §I-A3. [2] C. Alós-Ferrer and N. Netzer (2010) The logit-response dynamics. Games and Economic Behavior 68 (2), p. 413–427. Cited by: §I-A3, §IV. [3] L. Arditti, G. Como, F. Fagnani, and M. Vanelli (2024) Robust coordination of linear threshold dynamics on directed weighted networks. IEEE Transactions on Automatic Control (), p. 1–15. External Links: Document Cited by: §I-A1. [4] I. Arieli, Y. Babichenko, R. Peretz, and H. P. Young (2020) The speed of innovation diffusion in social networks. Econometrica 88 (2), p. 569–594. External Links: Document Cited by: §IV. [5] J. Becker, D. Brackbill, and D. Centola (2017) Network dynamics of social influence in the wisdom of crowds. Proceedings of the national academy of sciences 114 (26), p. E5070–E5076. Cited by: §VII. [6] L. E. Blume (1993) The statistical mechanics of strategic interaction. Games and economic behavior 5 (3), p. 387–424. Cited by: §I-A3, §IV-A, §IV. [7] L. E. Blume (1995) The statistical mechanics of best-response strategy revision. Games and Economic Behavior 11 (2), p. 111–145. Cited by: §I-A3. [8] F. Bullo (2024) Lectures on network systems. 1.7 edition, Kindle Direct Publishing. External Links: ISBN 978-1986425643, Link Cited by: §I-A. [9] C. F. Camerer, T. Ho, and J. Chong (2004) A cognitive hierarchy model of games. The Quarterly Journal of Economics 119 (3), p. 861–898. Cited by: §I-A2. [10] C. F. Camerer and T. Ho (1999) Experience-weighted attraction learning in normal form games. Econometrica 67 (4), p. 827–874. Cited by: §I. [11] C. F. Camerer (2003) Behavioral game theory: experiments in strategic interaction. Princeton University Press, Princeton, NJ. Cited by: §I. [12] E. Çınlar (2011) Probability and stochastics. Graduate Texts in Mathematics, Vol. 261, Springer, New York. Cited by: §VI-E. [13] R. Diestel (2017) Graph theory. 5th edition, Springer, Berlin. Note: Cited by: §IV-B, Lemma 1. [14] P. L. Ferreira, F. C. Santos, and S. Pequito (2021-07) Risk sensitivity and theory of mind in human coordination. PLOS Computational Biology 17 (7), p. e1009167. External Links: Document Cited by: §I-A2. [15] D. Fudenberg and J. Tirole (1991) Game theory. MIT Press, Cambridge, MA. External Links: ISBN 9780262061414 Cited by: §I. [16] J. K. Goeree, C. A. Holt, and T. R. Palfrey (2016) Quantal response equilibrium: a stochastic theory of games. Princeton University Press. External Links: ISBN 9780691124230, Document Cited by: §I-A2. [17] P. Hall and C. C. Heyde (1980) Martingale limit theory and its application. Academic Press, New York. External Links: ISBN 0-12-319350-8 Cited by: Lemma 5. [18] R. A. Horn and C. R. Johnson (2012) Matrix analysis. 2nd edition, Cambridge University Press, Cambridge. External Links: Document Cited by: §VI-D. [19] M. O. Jackson and Y. Zenou (2015) Games on networks. In Handbook of Game Theory with Economic Applications, Vol. 4, p. 95–163. Cited by: §I-A1. [20] M. O. Jackson (2008) Social and economic networks: models and analysis. Princeton University Press, Princeton, NJ. Cited by: §I. [21] D. Kahneman and A. Tversky (1979) Prospect theory: an analysis of decision under risk. Econometrica 47 (2), p. 263–292. Cited by: §I-A2. [22] S. M. Kakade, M. Kearns, and L. E. Ortiz (2004) Graphical economics. In Proceedings of the 17th Annual Conference on Learning Theory (COLT 2004), J. Shawe-Taylor and Y. Singer (Eds.), Lecture Notes in Computer Science, Vol. 3120, Berlin, Heidelberg, p. 17–32. External Links: Document Cited by: §I-A1. [23] M. Kearns, M. L. Littman, and S. Singh (2001) Graphical models for game theory. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI 2001), San Francisco, CA, p. 253–260. Cited by: §I-A1. [24] J. Kim and T. R. Palfrey (2025) An experimental study of prisoners’ dilemma and stag hunt games played by teams of players. Games and Economic Behavior. Note: External Links: Document Cited by: §I. [25] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi (1983-05) Optimization by simulated annealing. Science 220 (4598), p. 671–680. External Links: Document Cited by: §I-A3. [26] N. T. Kokolakis and K. G. Vamvoudakis (2023) Bounded rational dubins vehicle coordination for target tracking using reinforcement learning. Automatica 149, p. 110732. Cited by: §I-A2. [27] A. Leonidov, A. Savvateev, and A. G. Semenov (2024) Ising game on graphs. Chaos, Solitons & Fractals 180, p. 114497. Note: External Links: Document Cited by: §VI-A. [28] A. Maddux, R. Ouhamma, H. Catic, and M. Kamgarpour (2026) Finite-time convergence to an ϵε-efficient nash equilibrium in potential games. IEEE Transactions on Control of Network Systems (), p. 1–12. External Links: Document Cited by: §I-A3. [29] J. R. Marden and J. S. Shamma (2012) Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation. Games and Economic Behavior 75 (2), p. 788–808. Cited by: §I-A3, §IV-A, §IV. [30] A. W. Marshall, I. Olkin, and B. C. Arnold (2011) Inequalities: theory of majorization and its applications. 2nd edition, Springer, New York. Cited by: §VI-C. [31] F. Matějka and A. McKay (2015) Rational inattention to discrete choices: a new foundation for the multinomial logit model. American Economic Review 105 (1), p. 272–298. Cited by: §IV-A. [32] D. McFadden (1973) Conditional logit analysis of qualitative choice behavior. Frontiers in Econometrics, p. 105–142. Cited by: §I-A2. [33] D. McFadden (1984) Econometric analysis of qualitative response models. In Handbook of Econometrics, Z. Griliches and M. D. Intriligator (Eds.), Vol. 2, p. 1395–1457. Cited by: §IV-A. [34] R. D. McKelvey and T. R. Palfrey (1995) Quantal response equilibria for normal form games. Games and Economic Behavior 10 (1), p. 6–38. Cited by: §I-A2. [35] E. Melo (2022) On the uniqueness of quantal response equilibria and its application to network games. Economic Theory 74 (3), p. 681–725. External Links: Document Cited by: §I-A2. [36] M. Mézard and A. Montanari (2009) Information, physics, and computation. Oxford Graduate Texts, Oxford University Press, Oxford. External Links: ISBN 9780198570837, Document Cited by: §VI-B. [37] D. Monderer and L. S. Shapley (1996) Potential games. Games and economic behavior 14 (1), p. 124–143. Cited by: §I-A. [38] A. Montanari and A. Saberi (2010) The spread of innovations in social networks. Proceedings of the National Academy of Sciences 107 (47), p. 20196–20201. Cited by: §I-A1, §IV-A, §IV. [39] S. Morris (2000) Contagion. The Review of Economic Studies 67 (1), p. 57–78. Cited by: §I-A1. [40] V. S. S. Nadendla, C. Langbort, and T. Başar (2018) Effects of subjective biases on strategic information transmission. IEEE Transactions on Communications 66 (12), p. 6040–6049. Cited by: §I-A2. [41] R. Nagel (1995) Unraveling in guessing games: an experimental study. The American Economic Review 85 (5), p. 1313–1326. Cited by: §I-A2. [42] M. E. J. Newman (2018) Networks. 2nd edition, Oxford University Press, Oxford. External Links: ISBN 9780198805090 Cited by: §IV-B. [43] K. Paarporn, M. Alizadeh, and J. R. Marden (2020) A risk-security tradeoff in graphical coordination games. IEEE Transactions on Automatic Control 66 (5), p. 1973–1985. Cited by: §I-A1. [44] K. Paarporn, B. Canty, P. N. Brown, M. Alizadeh, and J. R. Marden (2020) The impact of complex and informed adversarial behavior in graphical coordination games. IEEE Transactions on Control of Network Systems 8 (1), p. 200–211. Cited by: §I-A1. [45] F. Parise and A. Ozdaglar (2021) Analysis and interventions in large network games. Annual Review of Control, Robotics, and Autonomous Systems 4, p. 455–486. Cited by: §VII. [46] M. O. Rieger and M. Wang (2008) Prospect theory for continuous distributions. Journal of Risk and Uncertainty 36 (1), p. 83–102. External Links: Document Cited by: §I-A2. [47] F. Sandomirskiy, P. H. Sung, O. Tamuz, and B. Wincelberg (2023) Independence of irrelevant decisions in stochastic choice. arXiv preprint arXiv:2312.04827. Cited by: §IV-A. [48] F. Sandomirskiy and O. Tamuz (2025/08/01) On the origin of the Boltzmann distribution. Mathematische Annalen 392 (4), p. 5617–5638. External Links: Document, ISBN 1432-1807, Link Cited by: §IV-A. [49] H. A. Simon (1955) A behavioral model of rational choice. The Quarterly Journal of Economics 69 (1), p. 99–118. Cited by: §I-A2, §I. [50] B. Skyrms (2004) The stag hunt and the evolution of social structure. Cambridge University Press, Cambridge. External Links: ISBN 9780521826518 Cited by: §I, Remark 1. [51] K. E. Train (2009) Discrete choice methods with simulation. Cambridge university press. Cited by: §IV-A. [52] P. Tsiotras and K. G. Vamvoudakis (2021) Bounded rationality in learning, perception, decision-making, and stochastic games. In Handbook of Reinforcement Learning and Control, K. G. Vamvoudakis, Y. Wan, F. L. Lewis, and D. Cansever (Eds.), Studies in Systems, Decision and Control, Vol. 325. External Links: Document Cited by: §I. [53] K. G. Vamvoudakis, F. Fotiadis, J. P. Hespanha, R. Chinchilla, G. Yang, M. Liu, J. S. Shamma, and L. Pavel (2023) Game theory for autonomy: from min-max optimization to equilibrium and bounded rationality learning. In 2023 American Control Conference (ACC), Vol. , p. 4363–4380. External Links: Document Cited by: §I. [54] W. Yoshida, R. J. Dolan, and K. J. Friston (2008) Game theory of mind. PLoS Computational Biology 4 (12), p. e1000254. Cited by: §I-A2. [55] H. P. Young (1993) The evolution of conventions. Econometrica: Journal of the Econometric Society, p. 57–84. Cited by: §I-A1. [56] Y. Zhang and M. M. Vasconcelos (2024) On the role of network structure in learning to coordinate with bounded rationality. In 2024 IEEE 63rd Conference on Decision and Control (CDC), p. 1684–1689. Cited by: §I-B. [57] Y. Zhang and M. M. Vasconcelos (2024) Rationality and connectivity in stochastic learning for networked coordination games. In 2024 American Control Conference (ACC), p. 1622–1627. Cited by: §I-B.