The Best of Both Worlds in Network Population Games: Reaching Consensus and Convergence to Equilibrium
Authors: Shuyue Hu
Harold Soh
Georgios Piliouras
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Agent Learning
Consensus Formation
Smooth Fictitious Play
Network Game
Population Game
TL;DR: Smooth fictitious play achieves both consensus and convergence to equilibrium in diverse population network games

Abstract: Reaching consensus and convergence to equilibrium are two major challenges of multi-agent systems. Although each has attracted significant attention, relatively few studies address both challenges at the same time. This paper examines the connection between the notions of consensus and equilibrium in a multi-agent system where multiple interacting sub-populations coexist. We argue that consensus can be seen as an intricate component of intra-population stability, whereas equilibrium can be seen as encoding inter-population stability. We show that smooth fictitious play, a well-known learning model in game theory, can achieve both consensus and convergence to equilibrium in diverse multi-agent settings. Moreover, we show that the consensus formation process plays a crucial role in the seminal thorny problem of equilibrium selection in multi-agent learning.

The Best of Both Worlds in Network Population Games: Reaching Consensus & Convergence to Equilibrium
Shuyue Hu Shanghai Artificial Intelligence Laboratory hushuyue@pjlait org. cn
Harold Soh National University of Singapore harold@comp.. nus edu sg
Georgios Piliouras
Singapore University of Technology and Design georgios@sutd, edu.
Abstract
Reaching consensus and convergence to equilibrium are two major challenges of muulii-agent systems. Although each has attracted significant attention, relatively few studies address both challenges at the same time. This paper examines the connection between the notions of consensus and equilibrium in multi-agent sys- tem where multiple interacting sub-populations coexist. We argue that consensus can be seen as an intricate component of intra-population stability, whereas equi- librium can be seen encoding piter-population stability. We show that smooth fictitious play, well-known learning model in game theory, can achieve both con- sensus and convergence to equilibrium in diverse multi-agent settings. Moreover, we show that the consensus formation process plays a crucial role in the seminal thorny problem of equilibrium selection in multi-agent learning.
Introduction
Two fundamental problems of multi-agent systems are consensus formation 26 3 12 30
28
86 (68) and learning in games [48 33 66 58 57 70 71
13 (55) The former (sometimes also referred cooperative control, flocking, synchronization. and social norms) aims to understand how a decentralized system of agents. which starts off in an initially disordered state, is able to develop shared coordinated beliefs, opinions, or behaviors (7]. The latter (also known multi-agent learning) examines whether, how and what type of equilibrium arises as the result of the long-run learning processes of individual agents 33 Each problem has attracted significant interest, yet, these two problems are largely studied in isolation.
Is there unified way to think about consensus formation and learning in games? We argue that sensus and equilibrium, the fundamental notions of these two fields, can be both understood as sta- bility concepts in multi-agent system where there co-exist multiple interacting sub- sub-populations (or populations hereafter). Consensus can be seen as an intricate component of imtra-population stability that reflects whether each population is internally cohesive, i.c., population is stable if all the agents belonging to this population achieve consensus and develop the same belief, opinion, or behavior. In contrast, game- theorettc (c.g.. Nash) equilibrium can be seen at a more macro level as encoding inter-pon inter-population stability, i.e., the stability between different populations is achieved by alignment to their population- tiiti incentives. Namely, stable system of populations is characterized by the internal cohesion of each population as well as the game-theoretic equilibration between different populations. The merits of this way of thinking are twofold. presents a non-tr non-trivial connection
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

between consensus and equilibrium, bringing them together under the same umbrella of stability concepts for a system of populations. Moreover, it distinguishes between intra-population stability and inter-population stability so that the emerging phenomena that it can describe are significantly richer, and that allows for important distinctions that would have otherwise been impossible.
In the rich literature on consensus formation, the idea of building up connection to same-theoretic equilibration is not entirely new. Classic matherattcal models, such as the Degroot model [27] and the Friedkin-Johnsen model [T showed that consensus of opinions can be reached if individuals form their opinions taking a weighted average of their own opinions and the opinions of others. In seminal work, Bindel et al. [I3] showed that such a repeated averaging process is equivalent to a best-response play in the game with a quadratic reward function measuring the distance between individuals' opinions. leading to interest in understanding consensus from the perspective of learning in games [38 23 2
14 36 10 9 In parallel, Marden et al. [2] demonstrated how the cooperative control problem of consensus can be formulated as better reply with inertia dynamics in potential games, while Young (89) proved the emergence of social norms using evolutionary game theory. These notable advances, however, typically assumed the reward structure to encode an incentive to align individual agents' opinions or behaivors with those of others. Little is formally known about consensus formation in the absence of such coordinative reward structure, or whether such a coordinative reward structure is a prerequisite for achieving both consensus formation and game- theoretic equilibration.
In the literature on multi-agent learning, the concept of consensus has been less explored compared to the abundant study of convergent or non-convergent learning behaviors in games 13
79 66
81
6
57 [6]. We argue that consensus of crucial importance to multi-agent learning-
ensures not only intra-population stability when there co-exist multiple interacting populations but also complete predictability and computational efficiency in more general settings. Imagine the case that for system of agents, the average probability (i A and T B) of choosing between two strategies (A and B) is shown to equilibrate at F A = FB = 0.5. If consensus is reached, it is completely predictable that every agent plays A and B with equal probability 0.5. However, if consensus is not reached, there are many possibilities for agents' behaviors, to name a few it is possible (i) that exactly half of the agents play A with probability and the other half plays B with probability 1, and (ii) that some agents play A and B with equal probability 0.5 whereas the rest constantly switches between these two strategies. The unpredictability in agents' behaviors can be problematic for system design, especially in safety-critical scenarios, where a system designer ought to rule out the possibility of getting the system to evolve into some (e.g., unsafe) states 774
76 73 91)
From the perspective of computational efficiency, consensus is usually a desirable property and is embedded in the mean field game literature to simplify the characterization of equilibrium- by exploiting the homogeneity of the population, it suffices to understand the behavior of a single
representative agent facing the mean field 555 54 5T
Putting these together motivates our central questions:
Are there natural multi-agent learning models that can achieve the best of both worlds- reaching consensus as well as convergence to equilibrium-ii in diverse settings?
How does the consensus formation process affect equilibrium selection in multi-agent learning?
Our Model. We provide an affirmative answer to the first question, and our solution smoohh fictitious play (SFP) [32] well-known belief-based learning model in game theory. In this paper, we consider a network of populations, where each vertex represents a population (or continuum) of agents and each edge denotes that agents from connected populations subgames. We call this type of game a network population game as it has a close connection to the network (or graphical polymatrix) games [52] and the population games (75). By SFP, each agent forms beliefs about the strategies of agents of the connected populations based on the average
paired up to play 2-player
A good survey for network population games and variants thereof is 83 A prototypical example is the men-women interactions that give rise to 2-population Battle of the Sexes game, which corresponds a single-edge network in our case. Similarly, one can think of an ecosystem with a graph predator prey interactions: the fact that there is no self-interaction within a population captures that there is no in-species cannibalism. Another example is the multi army combat setting: combatants of the same army do not face each other.
2

---

Predicted Belief D Distribution
Empiriaal Beliel Distribution
Varianoe of Beliefs
Distance to the Equillihriam (8,5)
Yaraec afBllcck
Delane Expillioic
Pobbbiiy druiyyydrnyy Eraty
Tebboc
Belicf colinna fac Otker' Plyinng
Belicl door dec Otber Playing
Tia
(a) The initial beliefs are distributed according (14, 6) for both populations. The variance initial beliefs is 0.01 and the mean of initial belief' is 0.7.
Predicted Belief Distribution
Empiricaal Belief Distribution
Variance Beliefs
Distanoc the Equilibriun (H
Dicle:31 deaats
Podtiblly Jondy
EM MEMURCAA
2.25
Bdic5 sboo de Pkylng
Dallet' 30OUt the Dtber's Flaying
(b) The initial beliefs are distributed according to Beta(280, 120) for both populations. The variance of initial beliefs is z 0.0005 and the mean of initial beliefs is 0.7.
System evolution in 2-population stag hunt games. Over time, the belief distributions become more concentrated (left panel: the predictions of our continuity equations, middle panel: the empirical distributions in agent- (Ll norm) to the equilibrium are both decreasing (right panel). Even though the consensus formation process starts with the same initial mean belief, small variance of initial beliefs results in the risk dominant equilibrium (H, H) (subplot (b)), whereas a large variance of initial beliefs results in the payoff dominant equilibrium (S, S) (subplot (a)). video for the evolution of these two belief distributions is available at htttps://ssttss.. gowgle. www.gggooo....oiiw/iieee wtw.e//////wwe////eeeeeett
Figure 1:
simulations). and the variance of beliefs and the distance
plays of those populations, and responds with an aggregated smoothed best response. To allow for a meaningful study of consensus formation, assume that agents within each population have differ- ent beliefs and different behaviors in the initial state. In other words, our model a heterogeneous belief model [35] unlike the homogeneous belief models extensively studied in the SFP literature
32
46
Our Approach & Key Results. To see whether consensus is reached, needs measure of it. A natural approach is to assume the system state to be a probability measure (or distribution) over the set of belief's (referred as the belief distribution). This notion of system state allows to quantify how much agents reach a consensus by examining the variance of the belief distribution. Intuitively, value of zero for the variance means that agents have the same belief and have achieved consensus. However, analyzing the evolution of the belief distribution requires new techniques be- yond the classic approach of stochastic approximation [8] 35 44 47). We address this challenge by establishing a system of nonlinear partial differential equations continuity equations - to de- scribe the continuous-time change in the belief distribution (Proposition [ This approach allows us to analyze the evolution of the variance without deriving analytical form of the belief distribu- tion. We show that for any network population games, the variance of beliefs decreases to zero at a quadratic rate with time in every population (Theorem []. This means that even if the 2-player sub- games that agents (of different populations) play are not coordinative but zero-sum, consensus will still be reached. Put differently, coordinative reward structure is not prerequisite for achieving consensus.
2 A continuity equation is a PDE commonly encountered in physics, which describes the transport phenom- of some quantity (e.g.. mass, energy, momentum and other conserved quantities) in physical system.
3

---

The next step is to examine the convergence to equilibrium. Our finding that the variance of beliefs decreases to zero suggests that the asymptotic behavior of a population that starts with different beliefs can be understood by studying that of single representative agent. Inspired by this, we temporarily override the assumption of the heterogeneous belief model and assume single repre- sentative agent for each population, resulting in the classic form of network games with each vertex representing a single agent. Under this assumption, we use Lyapunov arguments to prove the con- vergence of SFP to quantal response equilibria (QRE in two classes of network games that capture network competition and network coordination. Specifically, we show that for a weighted zero-sum network game, SFP converges to a unique QRE even if the underlying game has many distinct Nash equilibria (Theorem 2. We also show that for an exact potential network game that exhibits a star structure, SFP converges to the set of QRE (Theorem 3) We then use the techniques of asymp- totically autonomous dynamical systems to show that the convergence to QRE holds for network population games as well (Theorem 4 and Theorem 5). Therefore, SFP converges to QRE in all weighted zero-sum network (population) games as well as all exact potential star-graph (population) games.
At this point, we have shown that SFP can achieve consensus as well as convergence to equilibrium in wide range of network population games. Specifically, consensus is always reached, regardless of the specific setting. In the language of stability concepts, by SFP, the intra-population stability is always guaranteed, but the inter potruloopl stability may require additional assumptions about the incentive nature as well as the network topology. This may lead to an error- pron- intuition that the consensus formation process is orthogonal to the equilibrium selection process and thus has little effect on it. This is indeed not true. We illustrate this through an example of a 2-population stag hunt game, where different variances of initial beliefs result in qualitatively different long- term system behaviors. As we show in Figure even though the initial mean belief is the same, the consensus formation process starting with low level of initial disagreement small value for initial variance) results in the risk dominant equilibrium (H, H), while starting with a high level of initial disagreement large value for initial variance) leads to the payoff dominant equilibrium (S, S). We provide additional evidence covering all possible initial mean beliefs under the same 2-population stag-hum hang game setting in Figure 2 (Section 6). Figure shows that increasing the variance of initial beliefs from 0 to 0.02, 0.05, and 0.1 expands the region of attraction of the payoff dominant equilibrium S), allowing a wider range of initial mean beliefs approach it. Thus, in the case of network coordination, consensus formation plays a crucial role in the seminal thorny problem of equilibrium selection, and a larger initial variance can promote convergence to the equilibrium (S. In the case of network competition, convergence to a unique QRE is formally guaranteed (Theorem 4. we empirically verify this in 5-population asymmetric matching pennies games with many distinct Nash equilibria (Section of the Appendix).
Other Related Work. SFP is a well-studied model that converges in various classes of games, including most 2-player-2-action games 32
44
TT
47). n-player potential game s182 45), and
78 59 However, SFP in network (population) games has not been previously explored. Our research extends the findings of Fudenberg and Taka- hashi (35) (who showed that agents with different beliefs in 2-population setting will converge to the same belief) to the network settings, but we demonstrate that the variance of initial beliefs plays a crucial role in equilibrium selection, which has not been found in (35] On the other hand, networked multi-agent learning is a current frontier in AI research 990 61 43
zero-sum and
stochastic games g
25 Previ- ous studies have shown the convernenggnnt behavior of replicator dynamics in (weighted) zero-sum network games [72 18 66 79], the convergence of smooth Q-learning in weighted potential (56) and weighted zero-sum network games [57], and the convergence of fictitious play in zero-sum net- work games (29.. This paper provides new convergence results for SFP in both network games and network population games, covering wide range of generic 2-population-2-actie star-graph settings that admit an exact potential, and all weighted zero-sum settings. Finally, the evolution of probability distributions over initial conditions or strategies has also received increas- ing interest (22 53 55 24 66). Continuity equations have been used as a tool to show that under Cross learning, agents with different mixed strategies in a population game will not converge to the same mixed strategy [53], and to also describe the more complicated Q Q-learning dynamics in various settings
settings,
49 50
24 60 This paper formally shows that the probability distribution over
'uanttual response equilibrium is game theoretic solution concept under bounded rationality 66

---

initial conditions can eventually degenerate to a point mass, and leveraging on this, presents a novel technique for proving the convergence of learning dynamics
2 Preliminaries
A network population game I' (V, wi),e, (An))..)eE) consists of a multi-agent system N distributed over connected graph (V, E), where V = (1,...,,)) n) is the set of vertices each represents a population (continuum) of agents, and E' is the set of pairs, (i,j), of population i + j E V. For each population E V. agents of this population has a finite strategies (or actions) with generic elements s; E S.. Agents may also use mixed strategies (or choice distributions). For an arbitrary agent k in population i, its mixed strategy is a vector x (k) E A., where A, is the simplex in @ such that E,,es, Tis,
S; of pure
Tks, (k) 1 and Its, (6) 2 0, Vs; E S,. Each edge (i E E defines series of two-player subgames between populations and j. We denote the payoff matrices for agents of population i and in these two-player subgames by Aij E |X, and Aji E RIS, x s.1, respectively. For every time step, each agent chooses (mixed or pure) strategy and plays that strategy all two-player subgames with agents from the connected (or neighbor) populations. Let x = (x,, {x, (a,))) (e be a mixed strategy profile, where x, (or x,) denotes a generic mixed strategy in population i (or j). Given the mixed strategy profile x, the expected payoff of using in the game I' is
r: (x(x) = (x,, {x (XJIEE)))) =
Σ Σx, A, (L,))E
(1)
Smooth (or stochastic) fictitious play (SFP) is a belief-based model for learning in games. By SFP, agents act as if they are Bayesian such that they assume that the strategies of other agents are drawn from some fixed but unknown distribution. Given game I, consider an arbitrary agent k in a population i E V. Let V, (j E V (i.j) E }} be the set of neighbor populations. Agent k maintains a weight kjs,, (I) for each opponent strategy S E S) of each neighbor population j E Vg, For every time step t, agents refine these weights based on the average play of each neighbor population, i.e., for each opponent strategy 8) E Sj,j Vi.
k),,, (ki 1 = kje,, (k, + +z,,
where æj., is the mean probability of playing strategy 8, in population j , For simplicity, we assume the initial sum of weights Σeyes; ~²=,, (k:, 0) to be the same for every agent in the system and denote this initial sum by A. Based on the weights, agent ls forms a belief about the neighbor population j such that each opponent strategy sy is played with probability
Kijs, (k)
1 (k) EnjEs, j0; (k)
(k) be the vector of beliefs with the 8y-th element equals n),,, (k). Given game r, agent k's expected payoff of using a pure strategy 8; E S₁ in response to the aggregate beliefs (k)), Vj Vi about neighbor populations is
Let (k)
Uie, (k) = Σ JeTAAuu
(4)
JEV;
where es, is unit vector with the sy-th element equal 1. By convention 33 34 44
we suppose that
agents' payoffs are perturbed and that agents play smooth best responses maximizing their perturbed
*Our approach highlights the consensus property as valuable tool for establishing the convergence of learn- ing under population settings. For future research that studies learning dynamics under population settings, one can find inspiration in our approach by initially verifying the consensus property and subsequently leveraging this property to establish convergence results.
$ 'Oservving the average play of other populations is natural in settings with large number of agents and can be viewed as mean-field observations [88 37]: for example, the average household income of each state is made publicly available. and people form belief's about the behaviors of taxi drivers vs non- non-professionl drivers after observing the numerous driving behaviors the road.
5

---

payoffs. Agent k's perturbed payoff of using mixed strategy xx(k) E A, is defined as
(x;()) (k))se))))) = Σ (k)
A. (k) + ev (x;(A)),
(5)
JEV,
where > O, and the function is strictly concave and its gradient becomes arbitrarily large
near the boundary of the simplex A; 44 For the function v; a typical choice is v (x₃(k) =
Es.es. Jis, (k) In( (k)). Under this form, the maximization of the perturbed payoff yields
a unique choice distribution (k) from the logit choice rule [45] that is,
exp(Buge: (k))
Jis, (k: ExeEs. exp(pxxxp (R)))
where / is the temperature (or the degree of rationality). For clarity of presentation, we choose to focus on the logit choice rule in this paper; however, all our results readily generalize to any function v satisfying the above two standard assumptions. In the following, we usually drop the time index and agent index k in the bracket (depending on the context) for notational convenience.
3 Belief Dynamics in Network Population Games
Observe that for an arbitrary agent & of population i, its belief uz (k) (k( about population j is in simplex A, {uJ (k) It | E pis, (k) = 1, i (k) 0, Vs, E Sz}. We assume that the system state is characterized by a Borel probability measure P defined on the state space A Thvv A, Given μ4; E A,, we write the marginal probability density function as p(H,, Note that t(,,,t) represents the density of agents having the belief μ4, about population throughout the system; it does not represent the density of agents of population i that have the belief μ4: nor the density of agents having the belief μ4 about population in a certain population. Define {M: hev E A. Since agents maintain separate beliefs about different neighbor populations, the joint probability density function p(u, t) can be factorized, i.e., p(u, t) = Ihev p(H,,), t). We make the following assumption for the initial marginal density functions.
Assumption 1. At time O, for each population i V, the marginal density function p(Hi, 1) is continuously differentiable and has zero mass at the boundary of the simplex A..
This assumption excludes the setting that population of agents starts off with the same belief as well as the setting that agents start off with extreme beliefs. Under this mild condition, we derive a partial differential equation describe the evolution of the belief distribution.
Proposition 1. population e is described by partial differential equation
The continuou--time dynamic of the marginal density function p(ui, L) for each
@p(p,,t) t) =
(p(H.. -
8 14
1)
Ot.
x+
where V. the divergence operator and x; the mean mixed strategy with each sy-th element
Dia. 1 11bev, A Exees exp (Brss:) jEV,
exp(Buts)
II p(u,,t)
t)
II du, JEV,
where Uis. Ejev, AijHH
The partial differential equation in Equation iss also known as a continuity equation in the study of transport phenomena (e.g., of mass energy) in physical system. We remark that continuity equations, tracking the evolution of a probability distribution, do not allow for general solutions. However, continuity equations provide tractable way to examine the evolution of the moments of the probability distribution, without obtaining an analytical form of that distribution. The analytical form for the dynamic of the variance of beliefs (the second moment of the belief distribution) given as follows.
Alternatively, SEP be defined through truly stochastic perturbation of payoff's 32

---

Theorem 1. The dynamic of the variance of beliefs μ, about each population i E V is governed by an ordinary differential equation such that for each strategy Sü.
dVar((uee)) dl
2Var [
(9)
1+1
X+1 At given time I, Var(jis;) X+++1 variance Var(fus.) decays zero at quadratic rate with time.
oZ (Hiss)) where o² (piss) is the initial variance. Thus, the
Note that the above theorem makes no assumption about the 2-player subgames agents play, the network structure of populations, even the initial belief distribution. Therefore, it shows that for any network of populations, the variance of beliefs about each population always asymptotically tends zero. As an immediate consequence of this theorem, the asymptotic distribution of the beliefs is as follows:
Corollary 1. The probability density function p(u,,t) I) for every population E V will eventually evolve into a Dirac delta function, implying that in the long run agents reach consensus and play the same mixed strategy within each population.
The intuition of Theorem aand Crollary Tis that under SFP, agents revise their beliefs about other populations based on the average play of those populations; consequently, the observations are the same within agent population, and thus it is only matter of time that the agent population will develop the same belief and play the same strategy. Once consensus is reached, agents within a population will not develop different beliefs afterwards, as ensured by Theorem [ agent population is internally cohesive and achieves potulaoopultiion stability.
In this sense, the
However, it does not mean that different agent populations will eventually play the same strategy. This is because agents' strategies are the smooth best responses to their aggregated beliefs about their own set of neighbor populations (which generally vary depending on the network topology). This naturally raises the question of how different agent populations align with their population- wise incentives (which can be of a competitive nature). This also sets our paper apart from previous work
that studies game-theoretic equilibration in the context of consensus formation [IS] 62 38 23 2 [4
36 10, 29, in which consensus is achieved as the result of agents' incentives to align their opinions
or behaiviors to those of others (i.e., the incentives are of a coordinative nature).
Before diving into the convergence results, we take moment to analyze the mean belief (first moment) dynamic. Intuitively, the mean belief represents the average system state. The following proposition provides an analytical form of the mean belief dynamic.
The mean belief dynamic for each population E V is governed by an ordinary differential equation such that for each strategy 8;,
Proposition 2.
8 ((,)((e))) Var(uys;)
dpis fo. ((HyHee - Pis. Sev,E,,es, dt
(0pg,,)
(10)
X+t+1
2(A+++1
where fee (f.))ev) is the logit choice rule (Equation 6) applied to strategy s Sy, and Var(p)e,)
is the variance of belief Uje, in the entire system.
We remark that the mean belief dynamic. to be exact, should be under the joint influence of infinitely many moments of the belief distribution. However, the higher the order of the moments, the less of the influence of the moments, and by convention, the effects of the third and higher moments can be 41 64 Thus, in this proposition, the mean belief dynamic depends on the current mean belief and also on the current variance of beliefs.
assumed negligible (39
Recall that Theorem I shows that the variance of beliefs will eventually decrease to zero. As a result, the second term of the mean belief dynamic (Equation 10) will asymptotically tend zero. This suggests that the asymptotic mean belief dynamic of a population that starts with different beliefs in the initial state might be understood by studying the belief dynamic of a single representative agent.
This formally known as the moment closure approximation to estimate moments of population models. As we detail in the appendix, the effects of the higher moments are counter- counter-balanced by their coefficients as a result of Taylor expansion; moreover, the belief's pay Vi E V, Vs; St are between 0 and 1, which also lead small values of higher moments.
39
which a common method used
7

---

Intuitively, if each population can be represented by single agent, then the concerned network population games will effectively degenerate into the classic form of network games with each vertex representing single agent. Inspired by this, in the next section, we temporarily focus on SFP in the classic network games.
4 Convergence of Smooth Fictitious Play in Classic Network Games
In a classic network game (or network game for short), the only difference with respect to the network population games is that now each vertex represents single agent. We derive the belief dynamic of each vertex (or agent) in the following proposition.
Proposition 3. In a network game, the belief dynamic of each agent is governed by an ordinary differential equation such that for each agent i and each strategy 8i.
ditis: dt
Sa, (su Miss
Tis.
Mis.
(11)
A+t+1
A+t+1
follows from this proposition that the equilibrium state should satisfy the following property.
Proposition 4. In network game, the equilibrium state should satisfy that x; M² for every strategy 8, S; and every population E V. Thus, the equilibrium state corresponds to the solution to the system of equations
(B (eEV e eTAAAxz))
exp
Fiss
As, E V..iv.
(12)
Extes, exp
o7 A,Tx));)))
Such an equilibrium state coincides with the Quantal Response Equilibria
[65] of the network game.
By QRE, in this paper, we refer to their canonical form also referred to as logit QRE in the litera- ture 40). We remark that QRE [65] a game theoretic solution concept under bounded rationality, and is an extension of the standard Nash equilibrium which allows for errors in choice.
Weighted zero-sum network games capture the case of network competition, and are the gen- eralization of 2-player zero-sum games to the network settings 19]. A network game weighted zero-sum if there exist positive constants (or weights) w1,- .....-.-. , such that
Σ (x)(x))=
Σ (wxx) Aijx, + wjX; A = O, Vx E (LJ)E
II A. LEV
(13)
VVV
where rx(x) is the expected payoff of using a mixed strategy x, given the mixed strategy profile x (x,, {x, () If subgames along every edge (i.j) E E are 2-player zero-sum, i.c., x Aiyx, + x] ,: = O, then the network game is zero-sum; however, the converse is not generally true. As opposed to 2-player zero-sum games that admit a unique value at equilibrium [85), the Nash equilibrium payoffs in weighted zero-sum network games need not be unique, and it generally allows for infinitely many Nash equilibria. In the following theorem, we show that regardless of the number of Nash equilibria in a network game, the belief dynamic is guaranteed to converge to unique QRE.
Theorem 2. For any weighted zero-sum network game, the belief dynamic converge a unique QRE which is globally asymptotically stable.
Exact potential network games capture the of network coordination. A network game ad- mits an exact potential if for each edge (i.j) E E, the payoff matrices of the two-player subgame satisfy Aij AJ [21 20). Pure or mixed Nash equilibria
network coordination are complex. As reported in recent works 20 17, 4. finding pure Nash equilibrium is PLS PLS-complete. Hence, learning in the general case of network coordination is difficult and generally requires some condi- tions (67] (69] In the following theorem, show the convergence result in some cases of network coordination.
Theorem 3. For any exact potential network game that exhibits a star structure, each orbit of the belief dynamic converges to the set of QRE.
We remark that we employ the Lyapunov approach (i.e., establishing the existence of the Lyapunov function) prove the above convergence results. As result, the convergence equilibrium is equivalent to the network of agents being stable in the sense of Lyapunov.

---

weighted potential settings Basins of Attraction of (S,S) and (11, M) under Different Variances of Initial Beliefs
o (((n)
0.02
o((w))
0.05
o"(ww) = 0.1
(S,S)
Initial Pay
Initial jlssr
Initial Festt
Initial Rext
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
(H,H)
0.6
0.8
0.8 Initial Jin
0.6
0.8
Initial Piu
Initial Piu
Initial juu
Figure 2: Initial disagreement helps select the payoff dominant equilibrium (S.S) (yellow: the equilibrium (S, S), blue: the equilibrium (H, H)). As the variance of initial beliefs (denoted by (²(w))) increases from the left to right panel, a wider range of initial mean beliefs will approxi- mately reach the equilibrium (S, S) in the limit. For simplicity, we set o (1i o (war)) The black line on the diagonal is there for ease of comparison across different panels.
Convergence of Smooth Fictitious Play Network Population Games
We shall now formalize that the convergence results in network games can be seamlessly carried over to network population games with different beliefs the initial state, and establish the inter- population stability network population games. Recall that the mean belief dynamic (Proposition 2) depends on the current mean belief as well as the current variance of beliefs, with the variance decreasing over time (Theorem TT. Leveraging the definition of asymptotically autonomous dy-
namical systems (63. we establish the following lemma.
Lemma a network population game, for every population V, the mean belief dynamic du, (Equetionn 10) is asymptotically autonomous with the limit equation being di =; H;, which after time reparmeterizaiioo is equivalent to the belief dynamic in a network game (Equation 77p.
Thieme 84 provided the following seminal result that formally connects the asymptotic behavior of an asymptotically autonomous dynamical system to that of its associated limit equation.
Lemma 2 (Thieme 84 Theorem 4.2). Given a metric space (X, d). ler the solution flows of an asymptotically autonomous system and its limit equation be & and θ, respectively. Assume that the equilibria of θ are isolated compact O-invariant subsets of X. The w---llimit set of any pre- compact @-orbit contains a O-equilibrium. The point (s,I),
to, X, have pre-compact é-orbit. Then the following alternative holds: 1) ott, 8, + e,t + 00, for some O-equilibrium and 2) the w-O-limit set of (8,x) x) contains finitely many O-equilibria which are chained to each other in a cyclic way.
Combining the above lemmas and the convergence results under the setting of classic network games, the convergence results of SFP in network population games are readily deducible:
Theorem 4. For any weighted zero-sum network population game, the belief (as well as the choice distribution) of every individual converges to unique QRE.
Theorem 5. For any exact potential network population game that exhibits a star structure, the belief (as well the choice distribution) of every individual converges the set of QRE.
Note that under the 2-population settings, there is only one possible graph structure-one edge connecting the two populations. Hofbauer and Hopkins 44 have shown that SFP converges in all 2 2-player weighted potential games, and observed that almost all 2- 2-player-2-action games are either 2-player weighted potential games or 2-player weighted zero-sum games. Therefore, combining their results and our aforementioned results, SFP converges to the set of QRE under almost all the settings (including all the 2-population-22 and all the 2-population-2-actio weighted zero-sum settings).
2- 2-population-22-1
Experiments: Equilibrium Selection in Two-Population Stag Hunt Games
In a two-population stag hunt game, agents from two populations are paired up to choose between two actions H (hare) and S (stag). If both players hunt hare, they both receive reward of 1. If

---

both players hunt a stag, they both receive a reward of 4. If one hunts a hare and the other hunts stag, the former receives a reward of 2 whereas the latter receives nothing. There are two pure strategy Nash equilibria in each subgame: the risk dominant equilibrium (H, H) and the payoff dominant equílibrium (S,S), which naturally raises the problem of equilibrium selection.
Figure showed that given the same initial mean belief, changing the variances of initial beliefs can result in different limit behaviors. In Figure 2 we systematically studied the effect of the variance of initial beliefs by visualizing how it affects the regions of attraction to different equilibria. To be more specific, we numerically solved the mean belief dynamics for wide range of initial mean beliefs, given different variances of initial beliefs, and colored the regions of attraction. We observed in Figure as the variance of initial beliefs increases (from the left right panel), a wider range of initial mean beliefs results in the convergence to the QRE that approximates the payoff dominant equilibrium (S, 5). Hence, consensus is inevitable, but the initial disagreement still provides an approach to equilibrium selection and helps select the highly desirable equilibrium.
Note that in the case of network competition, the convergence unique QRE formally guar- anteed; we empirically verified this through a 5-population asymmetric matching pennies game presented in Appendix A.
7 Conclusions
This paper presents a formal treatment for SFP network population games where each population of agents start off with different beliefs and strategies. Representing the system state with a distri- bution over beliefs, we show that consensus always reached, and that agents eventually pointwise converge to the same belief, regardless of specific settings. In addition, establish the convergence of SFP to Quantal Response Equilibria in general competitive network population games as well as exact potential network population games with star structure. Empirically, we show that although the initial belief heterogeneity vanishes in the limit, it plays a crucial role in equilibrium selection and helps select highly desirable equilibria.
Acknowledgment
Shuyue Hu would like to thank Ms. Die Hu for her assistance in generating Figure and the corresponding video presented in this paper. This research is supported in part by the Na- tional Research Foundation, Singapore and DSO National Laboratories under its AI Singapore Program (AISG Award No: 2018 Fellowship NRF-NRFF2018-00 grant PIESGP-AI-2020- AME Programmatic Fund (Grant No.A20H6b0151) from A * STAR and Provost's Chair Professorship grant RGEPPV2101.
ALIAS grant, NRF
References
[1] Andrea Angiuli, Nils Detering, Jean-Pierre Fouque, Mathieu Lauriere, and Jimin Lin. Reinforcement learning algorithm for mixed mean field control games. arXiv preprint arXiv:2205.02330, 2022.
[2] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Per- siano. Generalized discrete preference games. In IJCAI, volume 16, pages 53-59, 2016.
[3] Vincenzo Auletta, Angelo Fanelli, and Diodato Ferraioli. Consensus in opinion formation processes in fully evolving environments. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 6022-6029, 2019.
[4] Yakov Babichenko and Aviad Rubinstein. Setting the complexity of nash equilibrium con- gestion games. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1426-1437, 2021.
[5] Rafael Bailo, Mattia Bongini, José A Carrillo, and Dante Kalise. Optimal consensus control of the cucker-smale model. IFAC- TTAC-PapersOnLine 51(13):1-6, 2018.
[6] Balduzzi, S Racaniere, Martens, J Foerster, K Tuyls, and T Graepel. The mechanics of n-player differentiable games. In ICML, volume 80, pages 363-372. JMLR. org, 2018.
10

---

[7] Andrea Baronchelli. The emergence of consensus: a primer. Royal Society open science, 5(2):17218,, 2018.
[8] Lucas Baudin and Rida Laraki. Smooth fictitious play in stochastic games with perturbed payoffs and unknown transitions. In Advances in Neural Information Processing Systems.
[9] Dario Bauso and Mark Cannon. Consensus in opinion dynamics as a repeated game. Automat- ica, 90:204-21 221004111, 2018.
[10] Dario Bauso, Hamidou Tembine, and Tamer Basar. Opinion dynamics in social networks through mean-field games. SIAM Journal on Control and Optimization, 54(6))3225-322 3257, 2016.
[11] Michel Benarm and Morris W Hirsch. Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games and Economic Behavior, 2911-):36-72, 1999.
[12] Jon Atli Benediktsson and Philip H Swain. Consensus theoretic classification methods. IEEE transactions Systems, Man, and Cybernetics, 22(():688-77) 704, 1992.
[13] Martino Bernasconi, Federico Cacciamani, Simone Fioravanti, Nicola Gatti, and Francesco Trovo. The evolutionary dynamics of soft-max policy gradient in games. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[14] Kshipra Bhawalkar, Sreenivas Gollapudi, and Kamesh Munagala. Coevolutionary opinion formation games. Proceedings of the forty-fitth annual ACM symposium on Theory of com- puting, pages 41-50, 2013.
[15] David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your opinion? In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 57-66. IEEE, 2011.
[16] Daan Bloembergen, Karl Tuyls, Daniel Hennes, and Michael Kaisers. Evolutionary dynamics of multi-agent learning: A survey. Journal of Artificial Intelligence Research, 53:659-697, 2015.
[17] Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Smoothed efficient algorithms and reductions for network coordination games. arXiv preprint /rX9v:/809.000 2018.
[18] Victor Boone and Georgios Piliouras. From darwin to poincaré and von neumann: Recurrence and cycles in evolutionary and algorithmic game theory. In International Conference on Web and Internet Economics, pages 85-99. Springer, 2019.
[19] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero- sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648 655, 2016.
[20] Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. Pro- ceedings of the twenty-second annual ACM-SIAM symposiun Discrete algorithms, pages 217-234. SIAM, 2011.
[21] Yang Cai et al. The complexity of Nash equilibria in multiplayer zero-sum games and coordi- nation games. PhD thesis, Massachusetts Institute of Technology. 2010.
[22] Yun Kuen Cheung, Georgios Piliouras, and Yixin Tao. The evolution of uncertainty of learning games. In International Conference on Learning Representations.
[23] Flavio Chierichetti, Jon Kleinberg, and Sigal Oren. On discrete preferences and coordination. In Proceedings of the fourteenth ACM conference Electronic commerce, pages 233-250, 2013.
[24] Chen Chu, Yong Li, Jinzhuo Liu, Shuyue Hu, Xuelong Li, and Zhen Wang. A formal model for multiagent q-learning dynamics on regular graphs. In Proceedings of the Thirty-First ternational Joint Conference on Artificial Intelligence, IJCAI, pages 194-200, 2022.
11

---

[25] Aleksander Czechowski and Georgios Piliouras. Poincar /eed-xnndixson limit sets in multi- agent learning. 2022.
[26] Abir De, Isabel Valera, Niloy Ganguly, Sourangshu Bhattacharya, and Manuel Gomez Ro- driguez. Learning and forecasting opinion dynamics in social networks. Advances in neural information processing systems, 29, 2016.
[27] Morris H DeGroot. Reaching consensus. Journal of the American Statistical association, 69(345):1188 18-1121, 1974.
[28] Yucheng Dong, Quanbo Zha, Hengjie Zhang, Gang Kou, Hamido Fujita, Francisco Chiclana, and Enrique Herrera- Viedma. Consensus reaching in social network group decision making: Research paradigms and challenges. Knowledge-Bar Based Systems, 162:3-13, 2018.
[29] Christian Ewerhart and Kremena Valkanova. Fictitious play in networks. Games and Economic Behavior, 123:182-206, 2020.
[30] Dimitris Fotakis, Dimitris
and Stratis Skoulakis. Opinion dynamics with local interactions. In IJCAI, pages 279-285, 2016.
[31] Noah E Friedkin and Eugene Johnsen, Social influence and opinions. Journal of Mathemat- ical Sociology, 15(3-4): 1e::1993-2000 1990.
[32] Drew Fudenberg and David M Kreps. Learning mixed equilibria. Games and economic be- havior, 5(3):320-367, 1993.
[33] Drew Fudenberg and David K Levine. The theory of learning games, volume 2. MIT press, 1998.
[34] Drew Fudenberg and David K Levine. Conditional universal consistency. Games and Eco- nomic Behavior, 29(1-22 (911-2)1044-330 1999.
[35] Drew Fudenberg and Satoru Takahashi. Heterogeneous beliefs and local information in stochastic fictitious play. Games and Economic Behavior, 71(1): 2011.
[36] Jason Gaitonde, Jon Kleinberg, and Éva Tardos. Polarization in geometric opinion dynamics. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 499-519, 2021.
[37] Sriram Ganapathi Subramanian, Pascal Poupart, Matthew Taylor, and Nidhi Hegde. Multi type mean field reinforcement learning. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 411-419, 2020.
[38] Javad Ghaderi and Rayadurgam Srikant. Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate. Automatica, 50(12):3209-322 2014.
[39] Colin S Gillespie. Moment-closure approximations for mass-action models. IET systems biology, 3(1):52-58, 2009.
[40] Jacob K Goeree, Charles A Holt, and Thomas R Palfrey. Quantal response equilibrium. In Quantal Response Equilibrium. Princeton University Press, 2016.
[41] Leo A Goodman. Population growth of the sexes. Biometrics, 922:212-225, 1953.
[42] Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. In Advances in Neural Information Processing Systems, pages 4967-4977,2011
[43] Shubham Gupta, Rishi Hazra, and Ambedkar Dukkipati. Networked multi- multi-agent reinforcement learning with emergent communication. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1858-1860, 2020.
[44] Josef Hofbauer and Ed Hopkins. Learning in perturbed asymmetric games. Games and Eco- nomic Behavior, 52(1):133-152 2005.
12

---

[45] Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 70(6):2265-222 229944 2002.
[46] Josef Hofbauer and William Н Sandholm. Evolution in games with randomly disturbed pay- offs. Journal of economic theory, 132((): 2007.
[47] Ed Hopkins. A note on best response dynamics. Games and Economic Behavior, 29(1-2):138- 150, 1999.
[48] Junling Hu, Michael P Wellman, et al. Multiagent reinforcement learning: theoretical frame- work and an algorithm. In ICML, volume 98, pages 242-250 Citeseer, 1998.
[49] Shuyue Hu, Chin-wing Leung, and Ho-fung Leung. Modelling the dynamics of multiagent q- learning in repeated symmetric games: a mean field theoretic approach. In Advances in Neural Information Processing Systems, pages 12102-12112, 2019.
[50] Shuyue Hu, Chin-Wing Leung, Ho-fung Leung, and Harold Soh. The dynamics of q-learning in population games: A physics-insplnn continuity equation model. In Proceedings of the 2 st International Conference on Autonomous Agents and Multiagent Systems, page 615-623, 2022.
[51] Minyi Huang, Roland P Malhaméé, Peter E Caines, et al. Large population stochastic dynamic games: closed-loop mckean-vlason systems and the nash certainty equivalence principle. Com- munications in Information & Systems, 6(3):221-25) 2006.
[52] Elena Janovskaja. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2):381-344 1968.
[53] Ratul Lahkar and Robert M Seymour. Reinforcement learning in population games. Games and Economic Behavior, 80:10-35 2013.
[54] Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathemat- ics, 2(1):229-266) 2602, 2007.
[55] Mathieu Laurière, Sarah Perrin, Matthieu Geist, and Olivier Pietquin. Learning mean field games: A survey. arXiv preprint arXiv:2205.12990 2022.
[56) Stefanos Leonardos and Georgios Piliouras. Exploration-exploiniie in multi-agent learning: Catastrophe theory meets game theory. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11263-1127 2021.
[57] Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. multi-agent competition: Convergence with bounded rationality. Advances in Neural Informa- tion Processing Systems, 34, 2021.
in
(58) Stefanos I Leonardos, losif Sakos, Costas Courcoubetis, and Georgios Piliouras. Catastrophe by design in population games: Destabilizing wasteful locked-in technologics. In Proceedings of the 16th International Conference Web and Internet Economics, pages 7-11, 2020.
[59] David S Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189:105093 2020.
[60] Chin-wing Leung, Shuyue Hu, and Ho-fung Leung. Modelling the dynamics of multi-agent q-learnin: The stochastic effects local interaction and incomplete information.
[61] Yiwei Liu, Jiamou Liu, Kaibin Wan, Zhan Qin, Zijian Zhang, Bakhadyr Khoussainov, and Liehuang Zhu. From local to global norm emergence: Dissolving reinforinn substruc- tures with incremental social instruments. In International Conference on Machine Learning, pages 6871-6881 PMLR, R, 2021.
[62] Jason R Marden, Gürdal Arslan, and Jeff's S Shamma. Connections between cooperative control and potential games illustrated on the consensus problem. In 2007 European Control Confer- ence (ECC), pages 4604-4611 IEFF, 2007.
13

---

[63] L Markus. Asymptotically autonomous differential systems. contributions to the theory of nonlinear oscillations iii (s. lefschetz, ed.). 17-29. Annals of Mathematics Studies, 36, 1956.
[64] Timothy Matis and Ivan G Guardiola. Achieving moment closure through cumulant neglect. The Mathematica Journal, 12:12-2, 2010.
[65] Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
[66] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversar- ial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717. SIAM, 2018.
[67] Sai Ganesh Nagarajan, David Balduzzi, and Georgios Piliouras. From chaos to order: Sym- metry and conservation laws in game dynamics. In International Conference on Machine Learming, pages 7186-7196. PMLR, 2020.
[68] Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimiza- tion multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922 0302229938111 2010.
[69] Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. Advances in Neural Information Processing Systems, 30, 2017.
[70] Julien Perolat, Remi Munos, Caan-Baptiste Lespiau, Shayegan Omidshafici, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference Machine Learning, pages 2021.
PMLR,
[71] Sarah Perrin, Julien Pérolat, Mathieu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13199-13211 2020.
[72] Georgios Piliouras and Jeff S Shamma. Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence. In Proceedings of the twenty-fitth annual ACM- SIAM symposium on Discrete algorithms, pages 861-873. SIAM, 2014.
[73] Wei Qiu, Xinrun Wang, Runsheng Yu, Rundong Wang, Xu He, Bo An, Svetlana Obraztsova, and Zinovi Rabinovich. Rmix: Learning risk-sensitive policies for cooperative reinforcement learning agents. Advances in Neural Information Processing Systems, 34:23049 2021.
[74] D Sai Koti Reddy, Amrita Saha, Srikanth G Tamilselvam, Priyanka Agrawal, and Pankaj Dayama. Risk averse reinforcement learning for mixed multi-agent environments. In Pro- ceedings of the 18th international conference on autonomous agents and multiagent systems, pages 2171-2173, 2019.
[75] William H Sandholm. Population games and evolutionary dynamics. MIT press, 2010.
[76] Arnab Sarker, Peter Fisher, Joseph E. Gaudio, and Anuradha M. Annaswamy. Accurate param- eter estimation for safety-critical systems with unmodeled dynamics. Artificial Intelligence, 3 316: 103857, 2023.
[77] Yuzuru Sato, Eizo Akiyama, and J Doyne Farmer. Chaos in learning a simple two-person game. Proceedings of the National Academy of Sciences, 99(7):474--475) 2002.
[78] Muhammed O Sayin, Kaiqing Zhang, and Asuman Ozdaglar. Fictitious play in markov games with single controller. In Proceedings of the 23rd ACM Conference on Economics and Com- putation, pages 919-936, 2022.
[79] Stratis Skoulakis. Tanner Fiez, Ryann Sim, Georgios Piliouras, and Lillian Ratliff. Evolution- ary game theory squared: Evolving agents in endogenously evolving zero-sum games. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11343-11351, 2021.
14

---

[80] Gordon Dennis Smith. Numerical solution of partial differential equations: finite difference methods. Clarendon Press, 1985.
[81] Sriram Srinivasan, Marc Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling, Actor-critic policy optimization in partially observable multiagent en- vironments. Advances in neural information processing systems, 31, 2018.
[82] Brian Swenson and H Vincent Poor. Smooth fictitious play in nx potential games. In 2019 53rd Asilomar Conference Signals, Systems, and Computers, pages 1739-1743. IEEE, 2019.
[83] György Szabó and Gabor Fath. Evolutionary games on graphs. Physics reports, 446(4-6);97- 216, 2007.
[84] Horst Thieme. Convergence results and cehincréé-endixsen trichotomy for asymptotically autonomous differential equations. Journal of mathematical biology, 30(7):755-763, 1992.
[85] J Neumann. Zur theorie der gesellschafftspicce. Mathematische annalen, 100((1)295-320,
1928.
[86] Tushar Vaidya, Carlos Murguia, and Georgios Piliouras. Learning agents in financial markets:
Consensus dynamics volatility. In AAMAS, pages 2106-2108, 2018.
[87] Qiaomin Xie, Zhuoran Yang, Zhaoran Wang, and Andreea Minca. Provable fictitious play for general mean-field games. arXiv preprint arXiv:2010.04211, 2020.
[88] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5567-5576, 2018.
[89] H Peyton Young. The evolution of social norms. economics, 7(1):359337722) 2015.
[90] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872-5881. PMLR, 2018.
[91] Andrey Zhitnikov and Vadim Indelman. Simplified risk-aware decision making with belief- dependent rewards in partially observable domains. Artificial Intelligence, 312:103775, 2022.
15

---

A Experiments on Network Competition
We have shown in Theorem 5 (of the main paper) that SFP converges to unique QRE in any weighted zero-sum network population game even if there are multiple Nash equilibria underlying that game. In the following, we corroborate this by providing empirical evidence in agent-based simulations with different belief initialization.
Game Description. Consider a ive-population asymmetric matching pennies game [56], where the network structure is a line (depicted in Figure 1). Each agent has two actions H, T) Agents in populations 1 and do not learn; they always play strategies H and T, respectively. For agents in populations 2 to 4, they receive +1 if they match the strategy of the opponent in the next population, and receive -1 they mismatch. On the contrary, they receive +1 if they mismatch the strategy of the opponent in the previous population, and receive -1 if they match. Hence, this game has infinitely many Nash equilibria of the form: agents in populations 2 and 4 play strategy T, whereas agents in population 3 are indifferent between strategies // and T'
Experimental Setups. In this game, agents in each population form two beliefs (one for the pre- vious population and one for the next population). We are mainly interested in the strategies of population 3, as the Nash equilibria differ in the strategies in population 3. Thus, we let the initial beliefs about populations 1, 3 and remain unchanged across different cases, and vary population 3's initial beliefs about populations 2 and 4. The initial beliefs about populations 3 and 5, denoted by Ya Par and μaı,, are distributed according to the distributions Beta(20, 10), Beta(6, 4), and Beta 10, 5). respectively. The initial beliefs about populations In all cases, the initial sum of weights À = 10 and the temperature 3 = 10. Note that p:T = 1 рad for all populations simulation run consists of 1, 000 agents in each population.
given in the legends of Figure 2.
1, 3, 4, 5. We run 100 simulation runs for each initialization, and each
Results. As shown in Figure given differential initialization of beliefs, agents in population 3 converge to the same equilibrium where they all take strategy H with probability 0.5. Therefore, even when the underlying zero-sum game has many Nash equilibria, SFP with different initial belief heterogeneity selects a unique equilibrium, addressing the problem of equilibrium selection.
Population 1 H
Population 2 (H,
Population 3 (H, T) Match
Population (H. T)
Population
T
Match
Match
Match
Figure 3: Asymmetric Matching Pennies.
Probability of Playing H Population 3
Vary the inital Mean, Fix the initial Variance
Vary the initial Variance, Fix the initial Mean
B13, 8(8, 2)
#110, 20), 9(16, 4)
B3,, 10), B(2 8) B3(0, B 2)
(2(255 5), B34, 33(00, 100), (3(00
0.5
0.5
100
200
300
400
100
200
300
400
Time
Time
Figure 4: With different belief initialization, SFP selects a unique equilibrium where all agents in population 3 play strategy H with probability 0.5. The thin lines represent the mean mixed strategy (the choice probability of H) and the shaded areas represent the variance of the mixed strategies in the population. In the legends, denotes Beta distribution: the two Beta distributions correspond to the initial beliefs about the neighbor populations and respectively.
16

---

B Proof of Proposition 1
follows from Equation 2 and Equation of the main paper that the change in (k, t) between two discrete time steps is
11 xt(t) uz (k,
(14)
x
Under Assumption of the main paper, for an arbitrary agent in population i, its belief u (k, 1) about neighbor population will never reach the extreme belief, i.e., the probability density for the boundary of the simplex A will remain zero.
Lemma 3.
Proof. Assumption ensures that x0( in the interior of the simplex Ay. Moreover, the logit choice function (Equation 5 in the main paper) also ensures that X₃(t) (t) stays in the interior of A afterwards for a finite temperature 33. Hence, from Equation 14, one can see that uz (k, 1) for every time step will stay in the interior Ay.
In the following, for notation convenience, we sometimes drop the agent index & and the time index t depending on the context. Consider a population i. We rewrite the change the beliefs about this population as follows.
[t + 1) = (t) + x (t) (.(t)
(15)
x+++1
Suppose that the amount of time that passes between two successive time steps is E (0, 1]. We rewrite the above equation
(1 + 6) (. xx(() (t)
(16)
-+1+1
Next, we consider a test function 0(H:). Define
(l + 8))1 BiO(H,
(17)
Applying Taylor series for ((u, 8)) at (t),, we obtain
+ ()) = ((H,(t) +
A on, (1:)) (x, - (t)]
8²
[8:(1) (() HO(H)) [R:(t) (t)
2(A + 1)2
(x((t)--((t))
+0
(18)
X+1+1
where H denotes the Hessian matrix. Hence, the expectation E[0(H:(( + 5)) is
5
E( + 6))] [()( + X+1+1 Eie,, (z) - (.))
82
[t, - (t) HA())) [x((t) - [t(+
2(A t + 1)2
82
([)((x((1) (c(())3))
(19)
2(A t 1)2
Moving the term ([O(H:(()) to the left hand side and dividing both sides by d, we recover the quantity Y, i.e.,
Y
E (t) (()
1
8
E
E[ (+) (O) (x(+) +o ((x:(1) (,(())²)] (20)
2(A + + 1)3
17

---

Taking the limit of Y with 8 + O, the contribution of the second term on the right hand side vanishes, yielding
1
lim 6-00
BIo ((,, - (.())
(21)
1
A -+t+1 (() ((),0)))))) - (x((t)] du.(t).
(22)
Apply integration by parts. We obtain
lim Y - x / (()((t))V
ur(t)) du,(t)
(23)
where have leveraged that the probability mass p(u,, t) at the boundary 0A; remains result of Lemma 1. On the other hand, according to the definition of Y.
lim Y = = / (())(()) p(u,, t + 8) p(u; t)
dui / ((4x(t))0pppm;)))d) t)du.
(24)
Therefore, have the equality
/ (1),())) Oddp;
/ /(LL(()) ((((0),)((((0) (:(1)) du,(). (25)
A 1+4+1
As is a test function, this leads to
0.plp, x+t+1 (L)
(())]
(26)
Rearranging the terms, obtain Equation 7 of the main paper. By the definition of expectation
given a probability distribution, straightforward to obtain Equation the main paper. Q.E.D.
C Proof of Theorem 1
Without loss of generality, we consider the variance of the belief pis, about strategy s; of population Note that
Var(uus;) = B[((us,))) (Miss;) )
(27)
Hence, we have
d'Var((uss)) dt
dB (Hiss:) )
27 dpis.
(28)
dt
Consider the first term on the right hand side. We apply the Leibniz rule to interchange differentia- tion and integration, and then substitute @p(u...) with Equation 8 in the main paper.
51
dI (Hie, )1
dl
{(uin) (on.)2pppp @p((u,)) du4, OL
(29)
/ ( 25 (p(He,))
x; H:
1)
dui
(30)
X x+
1 x+1+1
/ (Wite)) Σ
Dinc Mise du p((,,.) 1)
Opir:
(31)
A x+t+1
S,E8,
= /Ween 12
Σ
Opm, pluts 1) (Tit; )is,)) dhp + f (1is,) PP(Hi, 1)
Σ Open (Tis, - Mis;) dup
8,ES,
s.ES.
(32)
where = *4t+1
Applying integration by parts to the first term in Equation 32 yields
/ (Mise)) Σ
2 Oun, p(u:, 1) (Tis. (iis.) dut,
SLES.
=- =-/(ues)Pp(unn (pp(
Eom, ( (Zie mest)
+ p(u. t)0 [(poo) ( [isc]] du
EEE.
(33)
18

---

where we have leveraged that the probability mass at the boundary remains zero (Lemma 1). Com- bining the above two equations, we obtain
dE (p(s))) dt
=-y = Pp(Hi;)) (uin)ii
Σ
Omne (Fie) msse))
+ p(Hi, 1000s (uixs ( Min,)) du
KEE
+ (rin t)
Σ
Opene (Biss - Mssse) dui
(34)
=Y / p-p( 1)0mm ((ris)) (Tis. [is)]] + (prie,) pl t) (Zie. piee) du:
(35)
Y / 2prra) p(H,, t)dd - 7 /
Mis, Mis, p(u,, t)dui
(36)
[ )²1 2Tis, Dis. X+t+1
(37)
Next, we consider the second term in Equation 28 By Lemma we have
ditis
20ss (Tiss Fisss)
2/ss
(38)
di
A+1+1
Combining Equations 37 and 38, the dynamics of the variance
d(VarJui))
[ ) 2Bin Pie:
2paa (Zio; Mis,)
(39)
dt
A+t+1
2( )2 2B (1 )
(40)
+ 1
2Var(Mio
(41)
A+
Q.E.D.
D Proof of Proposition
Lemma The dynamics of the mean belief μ.; about each population E is governed by differential equation
dpis.
Dis.
Piss
vss E S..
(42)
dt A+t+1
Proof. The time derivative of the mean belief about strategy s; is
dpis.
d d dl di ʃ pis.p(us (dd t)d
(43)
19

---

We apply the Leibniz rule to interchange differentiation and integration, and then substitute 3p(p..)) with Equation 8 in the main paper.
d dt.
/ M(s, l)dpe
(44)
@p(Hi,() 1)
Miss
du:
(45)
Ot
/ Miss V (p(m):t) 8; ui
du
(46)
x+t+1
/ Miss Σ
(p(Ms:) t)
Fis: Mini du:
Opene
(47)
A + +
&:ES;
/ Mie: Σ
(Om,; (Zis: - pis.) dui / plss)
E
Opin (Bis. pis.) du
n,68,
(48)
where 7= X+++I
Apply integration by parts the first term in Equation 48
[ |Mee Σ B.ES.
(Oni, p(H:; ()) (Tis: Messs) ddpss
=-f /iosP(Hest)
Σ
Omng (Frs) - mesl) + p(m,, t)0pm..
(Tin Miss du:
(49)
where we have leveraged that the probability mass at the boundary remains zero. Hence, it follows from Equation 48 that
dt / pis, t)du,
d
(50)
-x/ / ((i,)( SEE
Omen (āint - )ds -7 / p(u t)0me,, Wis (Zie: - -Mses) du
+r (Ms. Σ
Opein (Fres Mieo dip:
(51)
B.ES,
=7 / p(Hes 1) Opico (Dis: - piss)) Opeic (Mrss (Tis: - pis,))] du
(52)
7 /
p(u,, t)pee - / p(us,
plusst)osssd4 t)āss, dus
(53)
Tis. Dis.
(54)
X+1+1
We repeat the mean probability B.n., which has been given in Equation 8 in the main paper, as follows:
Diss / Enees exp (Briss))
exp (Buts,)
II p(H,,t) JEV:
II du, JEV
(55)
where Uiss = Eye,, AigH, Define य ū== {ū, bie and
fe ((Hubeee = exp Ejev, e, A.jHH)))))
(56)
Exees, exp (3 Ejev, e Aiju,))))
20

---

Applying the Taylor expansion to approximate this function at the mean belief μi, we have
1 2! (n m)) Hf ( n 3!
1
(x((H))eex) = fs. (m) + fss (i) (n (1)
O(I [4|19)
(57)
where denotes the Hessian matrix. Hence, we can rewrite Equation 55 as
Lis. = / ((H))b))) II p(u,,t) t)
II duy
(58)
jEV.
jEV,
ff,(1) + V
p( t)
II du,
(M)
JEV
JEV.
/ (H (1) HSa, (1) (1) II p(Hj,t)
II dhu JEV.
JEV.
/ 3! O(1 Ell
II p(uj,t) t)
II JEV,
duz
(59)
JEV.
59] the second and the third can be canceled out. Moreover, for any two neighbor populations J. V4, the beliefs μý μ4; about these two populations are updated separately and independently. Hence, the covariance of these beliefs are zero. We apply the moment closure approximation 64 39 with the second order and obtain
Observe that in Equation
Tie, (H) + Σ (
Var(pgs;)-
(60)
JEV (0pjs,) )2
Hence, substituting Zie, in Lemma with the above approximation, we have the mean belief dy- namics
dpis: (a) Pies Ejev. SievEr,eeh E,JES, [ōpss,]] dt A+t+1
80,,, Var(Ujs;)
(61)
2()++++
Q.E.D.
E Proof of Proposition 3
It follows from Equation 2 and Equation 3 of the main paper that the change in beliefs between two successive time steps as follows.
H4 (t 11++1)= x1(1) (t(
(62)
+
Suppose that the amount of time that passes between two successive time steps E (0, 1]. We rewrite the above equation
( + 8) -;, + (;( (1)
(63)
--t+1
Move the term (t:(t) to the right hand side and divide both sides by 6,
M (t + 8) (t(()
(t) (t())
(64)
À x+t+1
Assume that the amount of time between two successive time steps goes to zero. we have
du,
(t 8) mx(t)
xx( (:((t)
lim
(65)
dt
A+t+1
Q.E.D.
21

---

Proof of Proposition 4
is straightforward to see that
du
X; 14;
x; μ.:
(66)
Denote the equilibrium points of the system dynamics, which satisfies the above equation, by (x,,4 for each population i. By the logit choice rule, we have
exp (Buis;)
exp (3 bjer C, A Ex
Fis. Σ ES exp (Buis)
(67)
ot ES, exp (3 Ejen, A.))))
Leveraging that x3 = ni Vi E at equilibrium, we can replace 13 with xj. Q.E.D.
G Proof of Theorem
Consider an agent in a classic network game. The set of neighbors V,, the set of beliefs about the neighbors is (ey, and the choice distribution is x,. Given classic network game, the expected payoff is given by x E(s)er My. Define perturbed payoff function
mi (xi, (Hyleeu) = X Σ
Aigty + v(x))
(68)
JEV.
where v(x,) = - & Tis, (n(ee,)). Under this form of u(x)). the maximization of m yields the choice distribution x; from the logit choice function 33 Based on this, we establish the fol- lowing lemma.
Lemma 5. For a choice distribution x, of SFP in a network game,
0x (Xi, (H, jev)) = and E (AiHH)) = -xx, v(x:). jeV;
(69)
Proof. This lemma immediately follows from the fact that the maximization of n, will yield the choice distribution x; from the logit choice function [33
The belief dynamics of an agent can be simplified after time-reparameterization.
Lemma 6. Given = In A+t+1, the belief dynamics of homogeneous systems (given in Equation 11 in the main paper) is equivalent to
X+1,
dμ,
X; - 44.
(70)
dr
Proof. From = In A+++1 X+1 we have
1 = (A+ 1)(xpp (T) (Axxxx(ex
-1).
(71)
By the chain rule, for each dimension 8i.
dpii
dptis, dt dt dr
(72)
dr
Tis, - pis, d ((A ()( (T) 1))
(73)
X t+1
dr
Zie;
Hie,
X+ (A+ (exp 1) + (A 1) exp (T)
(74)
Diss Minc
(75)
22

---

Next, we define the Lyapunov function L as
1wiT4 s.t. 1=== mi (xi, (uj)jev;) n. (Hi (Hj)eev;)
(76)
iEV
where fwi)iev the set of positive weights defined in the weighted zero-sum I. The function L non-negative because for every i E V. x, maximizes the function Ty. When for every E V. x; u4, the function L reaches the minimum value O.
Rewrite as
L Σ witte (xi, (usliev;) - Will iEV
Σ JEV/
Aijty - wir((H)))
(77)
We observe that my (x,; jev) is convex in Mý.ă Vi by Danskin's theorem, and -v(M;) is strictly convex in μıy Moreover, by the weighted zero-sum property given in Equation in the main paper, we have
Σ REV
WilL
Σ
AigHt
=0
(78)
JEV.
since 14 Ai, M4 E Aj for every i, V. Therefore, the function L is strictly convex function and attains its minimum value O at a unique point x; = M. Vi
Consider the function Li. Its time derivative is
L Oz n. (xi, (M, Jev.) x;; +
Σ
[n, Te (x;, fuy hevv) زرز]
jeV,
(79)
0n ne (μi (Hy (jv,) ir;
Σ
[Uy (Hi, (uy As]
JEV;
Note that the partial derivative 0x Tr equals by Lemma
5 Thus, we can rewrite this as [On, Ti (xi, (Hileev) On (Hi (Mibiev)] i
L, 0n, (Hi, (Mi)eev; A4: Σ
(80)
JEV
Σ (AijH))) + (((e)
(x:) Σ (x] Aij - MT Aig) (x5 Hj)
(81)
JEV.
SEV.
10x, u(x,) - ((H)) M4)
Σ jEV
(x] Aiy m Aiyx, A + m Aigu;)
(82)
where from Equation 81 to 82 we apply Lemma to substitute Ejen, (Aiju;)) with 0xx v(xi). Hence, summing over all the populations, the time derivative of L is
i
Σ
wi 1xx v(x,) -u, (H,)) (x: m4)
ΣΣ wi (x. A,xx nn Agxx x3_ Aij + ut AijHy)
(83)
BEV jEV,
The summation in the second line is equivalent to
Σ (wix. Anyx + w A,iX,) (w A,yX, + w Azau.))
(84)
(U)EE
(wix] Aij44 + W AJix;) + (iir) Aigty + w AjaU.).
(85)
By the weighted zero-sum property given in Equation 2 in the main paper, this summation equals 0, yielding
:= Σ wi u(x,) Uu, (H+)) (x; M:))
(86)
iEV
Note that the function v strictly concave such that second derivative negative definite. By this property, f. S with equality only if x; = μ4 Vi E V. which corresponds to the QRE Therefore, L is strict Lyapunov function, and the global asymptotic stability of the QRE follows. Q.E.D.
23

---

H Proof of Theorem
Consider root agent j of star structure. Its set of leaf (neighbor) agents is V,, the of beliefs about the leaf agents is (Hi,,v, and the choice distribution X,. Given the game T, the expected payoff is x EiEv, Ajau, Define perturbed payoff function
Jj (xj, (Hiheee)) = xj Σ tEV,
Ajitt: + v(x;)
(87)
where v(x,) - -3 3 Tisy (n(gs))) Under this form of o(x;), the maximization of ny yields the choice distribution xj from the logit choice function 33
Consider leaf agent of the root agent J. It has only neighbor, which is population Thus, given the game r, the expected payoff is x, Ai juy. Define perturbed payoff function
(xi, My) x. A.j + v(x,)
(88)
where v(x,) = - - E,,es, Tis; In( Similarly, the maximization x; yields the choice distri- bution x, from the logit choice function [33]. Based on this, we establish the following lemma.
Lemma 7. For choice distributions of SFP in a network game with star structure,
0x, RJ (xj, (He)eev)) = =0 and Σ (AsiH))) = -0x, v(x;)
if is root agent,
(89)
NVV
8x, Ti (x: 11) = 0 and (Aiguj) vxx,x(x))
if i is a leaf agent.
(90)
Proof. This lemma immediately follows from the fact that the maximization of π and TT respec- tively, yield the choice distributions Xj and x, from the logit choice function 33
Let R V be the of all root agents. We define
L = Σ1, L, s.t. L Hy
Σ VEV,
Ajm, + v(M,) +
Σ v(H)). SEV,
(91)
JER
Consider the function T.g. Its time derivative f.g is
Ż, = Ou (M,} Σ Asau +
E On Σ
A
+ Sp o(u +
Σ
pu. (Hi));
iEV,
NVV
iEV,
iEV,
(92)
(Ajii))) (x, H4² + iEV,
Σ LEV,
MJ Ayi(x; - Hi) o,, - 14)) + Σ
On ((H) 14).
iEV,
(93)
Since we have (AijH;) H A un Aja, applying Lemma 7 we can substitute Eiev, (Ajiui) with -Ox, v(xx), and un Aşa with -xx, v(x;), yielding
t, o(x)((x) -1;)+ +
(-oo, ui) + ou (H;)({ m4)
LvV
+ Σ (H:) - -wi
(94)
KEV;
(0,, 8x, v(xx))((xx)))))))))))))))))))) H4) +
(0m, 2x, (xx:)) pi)
(95)
VEV,
Note that the function v is strictly concave such that its second derivative is negative definite. By this property, f,, 2 0 with equality only if x; μ; Vi E Vj and x, = Mj. Thus, the time derivative
of the function L, i.e., L EjeR i, with equality only x; μ4, Vi Vy. My Vij R. Q.E.D.
24

---

I Proof of Lemma
Definition 1. nonautonomous system of differential equations in
R
I' ft,
(96)
is said to be asymptotically autonomous with limit equation
y' = g
(97)
if [(, g(x); co, where the convergence uniform on each compact subset of R Con- ventionally, the solution flow of Eq. 16 is called the asymptotically autonomous semiflow (denoted by 6) and the solution flow of Eq. 97 called the limit semiflow (denoted by θ).
We first renraaeparaiiteriz the mean belicf dynamics of heterogeneous systems. Assume In A+++1 By the chain rule and Equation 61 for each dimension 8;
X+I
dptis dr
dpis: dt dl dr
(98)
Sr, (P) Var(pje,) Ejev EnyEs, (8pse,]}
Ss, (s,(H) pis.
((A+1))(xxp))
(99)
x+t+1
2
dr
(i) - -Bis; + Ejei E ESJES; (ōpss,)
A+1
o² o2((js)))
X+++1
() + 1)xp (100)
x (A + cxxp (T) - -1) +1
1 Σ Σ
02 fmr (H) d² ) exp (-2T).
= (a) Piss +
(101)
2
(Opys,) )2 85ES,
jEVi
Observe that exp (-2r) decays to zero exponentially fast and that both 0² (pjs,) and 8 f.,
(8pt,,)) are
bounded for every in the simplex IiEv, Aj. Hence, Equation 101 converges locally and uni- formly to the following equation:
dpis, fz. (τ) Pis-
(102)
dr
Note that Vis, = (ū) for single representative agent, and thus the above equation is algebraically equivalent to the limit equation Lemma 1 of the main paper. Q.E.D.
J Numerical Methods, Source Code, and Computing Resource
Numerical Method for the PDE model. Only limited types of PDEs allow analytic solutions.
Hence, numerically solve the PDE using the finite difference method [80]. The theoretical pre- dictions in Figure 1 of the main paper are generated using the finite difference method given specific initial setting (the initial sum of weights is 10, the temperature is 3 10, the initial belief distribution is specified in the caption of the figures).
Source Code and Computing Resource. The source code for reproducing our main experiments is included in the supplementary material (available at httpps://sttes.googs google..oom/vee///hheee hu)). The Matlab script finitedifference.m numerically solves our continuity equation model. Figure of the main paper is generated using the Origins Lab based on the numerical solution of the con- tinuity equations. The Matlab script regionofatraacion..n visualizes the region of attraction of dif- ferent equilibria in stag hunt games, which are depicted in Figure 2. The Python scripts simula- tion(staghunn pp and (antuaattioimmtcccinnnnnennn two-population stag hunt games and five-population asymmetric matching pennies games, respec- tively. use a laptop (CPU: AMD Ryzen? 5800H) to run all the experiments.
correspond to the agent-based simulations in
25


Reviews:
[{"review_id": "C6PuWjVxAT", "reviewer": "Reviewer_3EKR", "summary": "This paper examines the connection between the notions of consensus and equilibrium in a multi-agent system where multiple interacting sub-populations coexist, and it aims at answering below two central research questions in network (population) games scenario: \n     [1] Are there natural multi-agent learning models that can achieve the best of both worlds—reaching consensus as well as convergence to equilibrium—in diverse settings?\n     [2] How does the consensus formation process affect equilibrium selection in multi-agent learning?\n\nThe authors argue that consensus and equilibrium, the fundamental notions of these two fields, can be both understood as stability concepts in a multi-agent system where there co-exist multiple interacting sub-populations. In particular, consensus can be seen as an intricate component of intra-population stability, whereas equilibrium can be seen as encoding inter-population stability. The authors show that SFP (smooth fictitious play) algorithm can achieve consensus as well as convergence to equilibrium in a wide range of network population games (and unlike previous literature, here a coordinative reward structure is not a prerequisite for achieving\nconsensus). They also empirically shows that consensus formation process plays a crucial role in the seminal thorny problem of equilibrium's election in multi-agent learning (e.g., starts with the same initial mean belief, a large variance of initial beliefs results in a more desired equilibrium). Experiments were conducted for the scenario of Equilibrium Selection in Two-Population Stag Hunt Games.", "questions": "Please see my questions/comments/suggestions in above section when talking about weakness.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is organized and presented well and clearly, I found the manuscript is reader friendly.\n\n2. This work extend existing literature in multiple directions and presented a couple of nontrivial novel theoretical results, which is quite beneficial to the research community. E.g., SFP in network (population) games has not been previously explored until this work, unifying consensus formation and learning in multi-agent games, etc., proving consensus without assuming a coordinative reward structure, etc..\n\n3. There are quite some helpful/valuable elaborations/explanations about comparing this work with relevant literature and discussing the differences and advantages.", "weaknesses": "1. I'd like to see some discussions about the future research directions, and how this work could inspire/benefit other future research.\n\n2. Regarding the figure 1 about impacts of variances of initial beliefs, it seems to be just plot of one example setting, and the empirical conclusion is not very convincing to me and I'd like to see some more clarification/elaboration/justification. For example, consider such a scenario where the starting mean belief is already the optimal value of a final desired steady state/equilibrium, it seems that if the staring variance is 0 (extreme case of small variance), then convergence to optimal results is already achieved, which is obviously better than a larger initial variance with the same starting mean belief, which is a counter example of the empirical conclusion of the paper saying that a larger initial variance (given same starting mean belief) is preferred. I would like to see either some rigorous mathematical proofs about such conclusion, or very comprehensive empirical studies on this before drawing the conclusions on this. \n\n3. In page 4, it was mentioned that \"This paper formally shows that the probability distribution over initial conditions can eventually degenerate to a point mass, and leveraging on this, presents a novel technique for proving the convergence of learning dynamics.\" It would be good to see some more elaborations on how this \"novel technique\" could be used for proving the convergence of learning dynamics in other relevant problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you! We sincerely appreciate your diligent and thoughtful comments on our paper. \n\n**Comment**: “I'd like to see some discussions about the future research directions, and how this work could inspire/benefit other future research.”\n\n**Response**:  We appreciate your interest in future directions of our work! We will be more than happy to add a section at the end of the paper where we expand on them.\n\n**Comment**: “Regarding the figure 1 about impacts of variances of initial beliefs, it seems to be just plot of one example setting, and the empirical conclusion is not very convincing to me and I'd like to see some more clarification/elaboration/justification. ... before drawing the conclusions on this.” \n\n**Response**: Our main argument regarding our stag-hunt game experiments is that a larger initial variance can promote convergence to the payoff dominant equilibrium (S,S). However, this does not imply “a larger initial variance (given same starting mean belief) is preferred”. \n\nWhile Figure 1 presents two example belief distributions with the same initial mean belief, Figure 2 provides additional evidence covering *ALL* possible initial mean beliefs under the same game settings. In Figure 2, we demonstrated that increasing the variance of initial beliefs from 0 to 0.02, 0.05, and 0.1 expands the region of attraction of the payoff dominant equilibrium (S,S), allowing a wider range of initial mean beliefs to approach it. Based on the enlarged region of attraction, we concluded that a larger initial variance can promote convergence to the equilibrium (S,S). Importantly, this does not mean that a larger initial variance is always preferred. We will make sure to add further elaboration on our empirical results to make the above points more precise in our revision.\n\n**Comment**: “In page 4, … how this \"novel technique\" could be used for proving the convergence of learning dynamics in other relevant problems.”\n\n**Response**: By “novel technique”, we meant our approach for establishing the convergence result of smooth fictitious play in network population games. The novelty of our approach is largely characterized by two key steps: (i) we proved the variance of the belief distribution tends to zero in the limit, and (ii) we leveraged the zero-variance (i.e. consensus) property to extend the convergence result in classic network games to network population games. Our approach highlights the zero-variance/consensus property as a valuable tool for establishing the convergence of learning under population settings. For future research that studies learning dynamics under population settings, one can find inspiration in our approach by initially verifying the zero-variance/consensus property and subsequently leveraging this property to establish the convergence result. We will incorporate the above points into our revision.\n\nThank you again for your positive feedback and constructive comments!"}, {"review_id": "c2aOkewZLg", "reviewer": "Reviewer_2uya", "summary": "This paper combines reaching consensus and convergence to equilibrium for network population games. Consider a network whose vertices correspond to a population. Edges between vertices (or populations) represent two-player sub-games between each pair of agents in these neighboring populations. The authors specifically focus on smoothed fictitious play for these two-player sub-games while agents seek to reach consensus in their beliefs about agents' policies in neighboring populations. In that sense, the approach is analogous to (or motivated by) the anonymous random matching interpretation of fictitious play dynamics to justify the myopic nature of the agents [Fudenberg and Kreps, Learning mixed equilibria. Games and Economic Behavior, 1993]. In particular, consider (large) populations of agents in each player role. Each period, all agents are matched to play the game and are told only to play in their own match. Agents are unlikely to play their current opponent again for a long time, even unlikely to play anyone who played anyone who played her. So, if the population size is large enough compared to the discount factor, it is not worth sacrificing current payoff to influence an opponent’s future play. In these populations, agents share their belief. The consensus dynamics presented serve this purpose. Therefore, the results are expected to hold even though I have not checked the proofs in detail.", "questions": "- Can you provide a motivating example justifying the network population model in practice (specifically the 2-player sub-games)?\n- What is the reason to restrict the network structure to star structure only in potential network games? ", "limitations": "I have not identified any discussion about the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Convergence of SFP dynamics in weighted zero-sum network games and exact potential network games with star structure.", "weaknesses": "- There is no motivating example for the network population game formulation.\n- Results for potential network games are presented only for star structure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and for your constructive comments on our paper!\n\n**Comment**: “There is no motivating example for the network population game formulation” and “Can you provide a motivating example justifying the network population model in practice (specifically the 2-player sub-games)?”\n\n**Response**: Network population games are widely studied with numerous well-known variants. A good survey is [1]. This survey has been cited nearly 3000 times indicating the wide applicability and interest in related questions. Arguably, one the simplest and very natural settings are interactions between two different type of agents (e.g. male and female) that gives rise to bi-matrix population games that correspond to single-edge networks in our case. Moreover, the survey shows a lot of interest in focusing on interactions where each type of agents have only a handful of options (e.g. Battle of the Sexes, Prisoner's Dilemma etc).  We briefly described some applications in Footnote 1 in the paper. We sincerely appreciate your feedback, and we will gladly elaborate more on these and further examples in the introduction in our revision.\n\n**Comment**: “Results for potential network games are presented only for star structure” and “What is the reason to restrict the network structure to star structure only in potential network games?”\n\n**Response**:  Our proof of the Lyapunov function in the case of potential games depends on the cancellation of several terms, which currently utilises the assumption of a star structure. We agree that it is a very interesting direction to extend our results further. Nevertheless, we want to point out that several prior works in learning in games have utilised similar assumptions such as star network structure, e.g., [2-4].\n\n\nThank you again for your positive assessment and constructive comments on our paper! \n\n[1] Gyorgy Szabo, Gabor Fath Evolutionary games on graphs, Physics reports, 2007.\n\n[2] Panageas, Ioannis, and Georgios Piliouras. \"Average case performance of replicator dynamics in potential games via computing regions of attraction.\" Proceedings of the 2016 ACM Conference on Economics and Computation. 2016.\n\n[3] Sai Ganesh Nagarajan, et al. From chaos to order: Symmetry and conservation laws in game dynamics. In International Conference on Machine Learning, pages 7186–7196. PMLR, 2020.\n\n[4] Sela, Aner. \"Fictitious play in ‘one-against-all’multi-player games.\" Economic Theory 14.3 (1999): 635-651."}, {"review_id": "PaUQQC93za", "reviewer": "Reviewer_3rNt", "summary": "The authors defined a network population game, which is a multipartite network game where each partite is a population and agents in the same population do not interact with each other and only interact with agents from other populations. In this way, each population can be easily abstracted into a \"super-agent\", and each population has separate beliefs about different neighbor populations. \n\nThe authors show that when the agents perform interactions using the network population model and adopt a smooth fictitious play dynamic, the population's belief will gradually have lower variance and the mean belief will reach a quantal response equilibrium (QRE) in both weighted zero-sum games and exact potential network games.", "questions": "1. What is the intuition behind the perturbed payoff in Eqn (5)? Is this cost term a necessity for consensus and convergence?\n2. Line 203 says \"Agents maintain separate beliefs about different neighbor populations\", where is this previously justified and why is this reasonable?\n", "limitations": "The authors did not discuss the limitations of this work in the paper.\n\nI'm not sure if and how the population size of each population will influence the consensus and equilibrium outcome and whether there will be any fairness issues based on this. For now, I will not flag ethics review issues since I can't identify or exclude them. \n\nIt will be nice for the authors to add discussions on the limitations, at least in the appendix.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The intention of this paper is good, which tries to address both the consensus and the convergence of multi-agent learning systems\n2. The overall flow of this paper is easy to follow, and the authors conduct both theoretical and numerical studies", "weaknesses": "1. The justification for using the network population game is not sufficient. When this specific game model fits real-world problems, especially related to belief updates. For now, the purpose of this assumption seems like making the convergence and part much easier to study. \n2. The reason for using the smooth fictitious play dynamics is also not sufficiently justified. The reason for including the \\nu penalty term in the utility function should be provided (e.g., saying this is an entropy-based cost and why this is reasonable), and whether it is necessary for the convergence and consensus study should be elaborated. \n3. No elaboration on how the \\epsilon term and the A_ij influence the consensus and convergence\n4. Lack of discussion on the limitations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to provide us with your valuable feedback. \n\n**Comment**: “The justification for using the network population game is not sufficient…easier to study.”\n\n**Response**: Network population games model scenarios which are characterized by the presence of multiple interacting populations. A good survey is [1]. This survey has been cited nearly 3000 times indicating the wide applicability and interest in related questions. Arguably, one the simplest and very natural settings are interactions between two different type of agents (e.g. male and female) that gives rise to bi-matrix population games that correspond to single-edge networks in our case. We gave a brief description of some applications in Footnote 1 in the paper, however, we will be more than happy to expand on it. Overall, you can think of nodes as types and each agent needs to formulate beliefs about how other types of agents will act when they interact with them in the world.\n\n**Comment:** ”The reason for using the smooth fictitious play dynamics is also not sufficiently justified… elaborated.” and  “What is the intuition behind the perturbed payoff…convergence?”\n\n**Response**: We chose smooth fictitious play due to two reasons: (i) it is amongst the most well-known and commonly studied models in AI and game theory, and (ii) it is a belief-based learning model and naturally suits the investigation of consensus formation (consensus can be intuitively understood as the convergence of agents’ beliefs).\n\nThe term $ v( x_i(k))$ in Equation 5 is standard for smooth fictitious play ([1] and the references therein); it represents the perturbation on the expected payoffs and can also be understood as the control cost to implementing a strategy. A typical form is an entropy-based one $v (x_i(k)) =  -\\frac{1}{\\beta}\\sum_{s_i \\in S_i} x_{is_i}(k)\\ln (x_{is_i}(k))$. The rationale is that by adopting this form, an agent’s choice in response to his/her beliefs becomes probabilistic such that better responses are more likely than worse responses, but the best ones are not played with absolute certainty; this aligns with human’s bounded rationality and error-prone decision-making [2]. We will elaborate more on this in our revision.\n\nImportantly, a specific form of $ v( x_i(k))$ is NOT necessary for our study. We wrote in Line 192-193 that “all our results readily generalize to any function $v$ satisfying the above two standard assumptions.” We explained the two standard assumptions in Line 187-188.\n\n**Comment**: “No elaboration on how the \\epsilon term and the A_ij influence the consensus and convergence.”\n\n**Response**: All our consensus and convergence results hold given a positive value of $\\epsilon$. The payoff matrix $A_{ij}$ of the 2-player subgames has NO effect on consensus formation. We showed this formally in Theorem 1, and discuss this in Line 226 (where we wrote “Note that the above theorem makes no assumption about the 2-player subgames agents play”).\n\nRegarding the effect of the payoff matrices $A_{ij}$ on convergence to equilibrium, we defined in Equation 13 $A_{ij}$ that satisfies the weighted zero-sum property, and established the convergence in weighted zero-sum network (population) games in Theorem 2 and Theorem 4. Moreover, we defined in line 296 $A_{ij}$ that satisfies the exact potential property, and established the convergence in star-structure exact potential network (population) games in Theorem 3 and Theorem 5. In the Introduction, we summarized the effects of $A_{ij}$ on convergence to equilibrium in Line 109-116.\n\n**Comment**: “Lack of discussion on the limitations” and “The authors did not discuss the limitations … at least in the appendix.”\n\n**Response**:  Thank you! We will make sure to expand on this more intuitively, however, our theorems discuss precise conditions on the dynamics and games such that they apply. Expanding these results even further is an interesting direction for future work.\n\nIn terms of the population size, we wrote in Line 77 and Line 158 that this paper considers “a population (continuum) of agents”. This assumption allows for better analytical tractability, and is standard in studies of population games [3] and mean-field games [4]. Empirically, we observed that if the number of agents is sufficiently large (e.g., more than hundreds) for each population, our theoretical findings still hold. We will discuss the above limitations in our revision.\n\n**Comment**: “Line 203 says…  why is this reasonable?”\n\n**Response**: We mentioned this in Line 174, where we wrote “Agent $k$ maintains a weight $\\kappa^i_{js_j}(k)$ for each opponent strategy $s_j \\in S_j$ of each population $j\\in V_i$.” As agents maintain $\\kappa$ for each population and form their beliefs based on $\\kappa$ (Equation 3), they naturally maintain separate beliefs about different populations. We gave a real-world example for separate beliefs in Footnote 4, where we wrote “people form beliefs about the behaviours of taxi drivers vs non-professional drivers after observing the numerous driving behaviours on the road.”  \n\nThank you again for your constructive comments! We hope that you will consider revising the score if we have addressed your concerns satisfactorily.\n\n[1] J. Hofbauer, E. Hopkins. Learning in perturbed asymmetric games.Games Econ. Behav., 2005\n\n[2] R. McKelvey, T. Palfrey. Quantal response equilibria for normal form games.Games Econ. Behav., 1995\n\n[3] W. Sandholm. Population games and evolutionary dynamics. 2010\n\n[4] J. Lasry and P. Lions. Mean field games. Japanese journal of mathematics, 2007\n\n"}, {"review_id": "F3SSKM8ooX", "reviewer": "Reviewer_YUjL", "summary": "This paper examines the connection between the notions of consensus and equilibrium in a multi-agent system where multiple interacting sub-populations coexist. They argue that consensus can be seen as an intricate component of intra-population stability, whereas equilibrium can be seen as encoding inter-population stability. They show that smooth fictitious play can achieve both consensus and convergence to equilibrium in diverse multi-agent settings. ", "questions": "please comment on 2) above.", "limitations": "yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Excellent paper that brings together the concepts of consensus and equilibrium. Strong theory, interesting experiments.", "weaknesses": "1) don't forget the conclusion in the final version of the paper. \n2) It is clear that in the long run, due to the strong law of large numbers, FP is such that agents within a population will form the same beliefs. Therefore, the point of view taken by the authors is to study a representative agent. I say: what could be interesting is the transient regime where agents beliefs have not yet converged. There, one could use the central limit theorem, and look at the interplay between, on the one side, consensus that has not been reached yet, and the convergence of populations to equilibria. You could also look at it with 2 different learning rates (one for intra, one for inter populations, I suggest you explore connections with this https://arxiv.org/pdf/2205.02330.pdf)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to provide us with your valuable feedback, and also for recognizing our paper to be an “Excellent paper Excellent paper that brings together the concepts of consensus and equilibrium” with “Strong theory, interesting experiments.”\n\n**Comment**: \"don't forget the conclusion in the final version of the paper.\"\n\n**Response**: We will be more than happy to add a conclusion section in our final version. \n\n**Comment**: “It is clear that in the long run, due to the strong law of large numbers, FP is such that agents within a population will form the same beliefs. Therefore, the point of view taken by the authors is to study a representative agent. I say: what could be interesting is the transient regime where agents beliefs have not yet converged. There, one could use the central limit theorem, and look at the interplay between, on the one side, consensus that has not been reached yet, and the convergence of populations to equilibria. You could also look at it with 2 different learning rates (one for intra, one for inter populations, I suggest you explore connections with this https://arxiv.org/pdf/2205.02330.pdf)”\n \n**Response**: This is indeed an excellent and deep direction for follow-up work that will probably require to bring in the mix a number of new technical ideas. Thank you very much for the suggestion! We will make sure to include in the discussion of interesting future work as well as add the relevant citation. Thank you again! \n"}]

Author rebuttal:

Meta-review: The paper showed that smoothed fictitious play achieves both consensus and convergence to equilibrium in diverse population network games, which is an interesting result and well-presented. There was some concern regarding the generality of the setting (multi-population assumption) considered. I found the paper solid and cleared the bar of acceptance.
Decision: Accept (poster)