is described. Static and dynamic equilibria in a noisy binary choice game with Ising externalities on complete and random graphs with topology corresponding to configuration model are considered. It is shown that static equilibria realise Quantal Response Equilibria (QRE). Corresponding regime switching (phase transitions) at critical values of parameters is discussed. Myopic dynamics having the discussed static equilibria as stationary configurations Nosy binary choice game, Quantal Response Equilibrium, Master equation Let us consider a noisy binary choice game played by agents placed at vertices of a graph with an adjacency matrix equipped with a set of strategies parametrized by = ±1, = 1, ⋯ in which a utillity of each agent contains a strategy-dependent additive random contribution to but unknown to his neighbours characterised by a common distribution function ( ) assumed to be common knowledge. Games of this type were considered in a variety os socioeconomic settings, see e.g. [1, 2, 3, 4]. Let us note that a presence of random contributions to utility means that a description of this game (equilibria, evolution, et.) is necessarily probabilistic, i.e. its equilibrium is characterised by probabilities of playing certain strategies 0000-0002-6714-6261 (A. Leonidov); 0000-0002-6942-2282 (A. Savvateev); 0000-0002-6992-7862 (A.G. Semenov)
{ = ±1} → { ±} In what follows we shall restrict our consideration to the case of independent random contributions to utility for diferent agents corresponding to Nash equilibrium in mixed strategies. The Ising game is defined by the corresponding expected utility of the following form A choice of an agent is determined by his expectations concerning the choices of his neighbours. (1) ⟨ ( )⟩ = + ∑ ⟨ ⟩( ) + [ ≠ ] preferred to − if where ⟨ ⟩( ) stands for ′ expectation with respect of the choice of the neighbour Strategy is ⟨ ( )⟩ > ⟨ (− )⟩ Probability of choosing the strategy
by an agent is = <( ) ([ 2 + 2 ∑ ⟨ ⟩( ) Russia © 2020 Copyright for this paper by its authors. where <( )( ) is a distribution function for the diference − −
<( )( ) = ∫
1 ∫ 2 ( )( 2) ( )( 2 + 1) In particular, the probability of choosing = 1 is equal to + = <( ) ( 2 + 2 ∑ ⟨ ⟩( ) )
Quantal response equilibrium (QRE) [5, 6, 7] is a particular form of mixed strategies in which the vector of expected payofs for agent’s alternative actions is mapped into a probability distribution of choices over these strategies. The QRE does arise from realization of beliefs. A player’s payofs are computed based on beliefs about other players’ probability distribution over strategies. An equilibrium is a set of probabilities such that player’s beliefs are correct.
Quantal response equilibrium (QRE) of the Ising game under consideration is thus a set of
probabilities ( 1+, ⋯ , + ) such that
⟨ ⟩( ) = 2 − 1
+
so that mixed strategies chosen by all agents are consistent with the corresponding expectations of
other agents with respect to this choice. From (
( = 2 <( ) ( 2 + 2 ∑ (2 − 1) ,
∀ +
) 2 + 2 ∑ − 1 ,
∀ )
Let us now consider the Ising game on the complete graph. In this case it is customary to rescale
all local averages are the same and QRE is defined by the single equation
the coupling = / . Besides that, we assume for simplicity that = . For the complete graph
= 2 < [2 + 2 ] − 1
in the physics of magnetics, see e.g. [9]:
for 4 (0) > 1 there appears a pair of additional solutions ±
coinciding with the equation obtained in [8, 1]. For
= 0 the space of solutions of (
In physics the Curie-Weiss equation (
1 [ 2
2 − ( )] = 0
( ) = −
1 −
2
ln
1 −
2
−
1 +
2
ln
1 +
2
Let us note that it is possible to define an optimisation problem in which the equation (
Let us now turn to the analysis of the so-called annealed approximation, see e.g. [10], which is in fact equivalent to a random graph topology as generated by the so-called configuration model, see e.g. [11], in which the matrix elements are replaced by the probabilities of forming a link , between In this approximation all vertices having the same degree are equivalent so QRE is now defined in terms of averages for the nodes with the same degree: ≃ ⟨ ⟩ = ⟨ ⟩|∀ ∶ deg( )= (3) (4) where we have defined the weighted average The corresponding generalised Curie-Weiss equation for reads The corresponding system of equations defining QRE reads = 2 < 2 + 2
[ = 2 < [2 + 2
′ ′ ∑ ′ ⟨ ⟩ ] − 1 ′ − 1
] = ∑
⟨ ⟩ = ∑
2 < [2 + 2 ⟨ ⟩
] − 1 2 4 ⟨ ⟩ (0) = ⟨ ⟩ The phase transition takes place at difering from the result for the complete graph by the factor the analysis of random graph related problems (appearance of giant cluster, epidemic threshold, etc. ⟨ ⟩/⟨ 2 ⟩ which routinely appears in [11]).
Is it possible to recover the above-found QRE equilibrium as a stationary point of a dynamical game? Generically stochastic dynamics operates with a probability distribution of observing a certain configuration of strategies { } at time :
({ }( )) = [ 1( ), 2( ), ⋯ ( )] Conventional independent choice assumption corresponding to nixed state static Nash equilibria corresponds to a factorised distribution ({ }( )) = [ 1( ), 2( ), ⋯ ( )] = ∏ ( ( )) =1 Temporal evolution is driven by strategy flips ( ) → − ( )
Let us assume that within an infinitesimally small time interval one can have only one strategy lfip. Then the process of dynamical evolution is fully described by a time-dependent strategy flip probability ( →
− ). The local strategy change can in principle take into account past realized (memory) and future expected (forward-looking) configurations of strategies. In the simplest myopic response approximation agents base their decisions on the configuration of neighbour’s strategies immediately preceding the decision time. The evolution equation for ({ }( )) then reads ({ }( )) = ∑[ (− → ) ( 1, ⋯ , − , ⋯ ) − ( → − ) ( 1, ⋯ , , ⋯ )] ( )
= −2⟨ ( ) ( → − )⟩ ({ }( ))
The corresponding evolution equation of the local average strategies ( ) = ⟨ ⟩ ({ }( )) then reads A natural choice for ( → − ) is [1]
To derive the evolution equation for ( ) it is convenient to use the following identity: ( → − ) = − = <( )
− 2 + 2 ∑ ( ) ( ) [1 − ( − − )] ≡
[1 − ⟨ ⟩] 1 2 The resulting evolution equation for ( ) reads ( ) = − ( ) − ( 2 <( ) [2 + 2 ∑ ( ) − 1
]
)
We see that stationary points of this system of evolution equations are exactly the above-described
QRE equilibria described by the equations (
} 1 2 { [1] L. Blume, S. N. Durlauf, The interactions-based approach to socioeconomic behavior, Social dynamics 15 (2001). nomics Letters 111 (2011) 88–90.
Journal of Statistical Physics 151 (2013) 567–606. [3] M. Le Breton, S. Weber, Games of social interactions with local and global externalities, Eco[4] J.-P. Bouchaud, Crises and collective socio-economic phenomena: simple models and challenges, economic behavior 10 (1995) 6–38.
nomic Review 47 (1996) 186–209. [5] J. K. Goeree, C. A. Holt, T. R. Palfrey, Quantal response equilibria, Springer, 2016. [6] R. D. McKelvey, T. R. Palfrey, Quantal response equilibria for normal form games, Games and [7] R. D. McKelvey, T. R. Palfrey, A statistical theory of equilibrium in games, The Japanese Eco[8] W. A. Brock, S. N. Durlauf, Discrete choice with social interactions, The Review of Economic
Studies 68 (2001) 235–260.
[9] S. Salinas, Introduction to statistical physics, Springer Science & Business Media, 2001. [10] S. N. Dorogovtsev, A. V. Goltsev, J. F. Mendes, Critical phenomena in complex networks, Reviews of Modern Physics 80 (2008) 1275. [11] M. E. Newman, The structure and function of complex networks, SIAM review 45 (2003) 167– 256.