betaFeedback

WorksComputer Science

Cycle structure of best-response dynamics in random bimatrix games

Abstract

We study the best-response dynamics in games with random payoffs. We consider two-player bimatrix games, with nn strategies each. We assume that payoffs come from a continuous distribution, and study the best-response dynamics of these games, after imposing some structure on their payoff matrices. In particular, we focus on symmetric games, antisymmetric games, common-interest games, zero-sum games, and games with independent payoffs. When two players take turns in playing the best response to the opponent's action, they eventually end up cycling through the same sequence of actions. The main focus of the paper is the cycle structure of large random games. In particular, we study the number of cycles, the number of cycles of a certain length, the length of the longest cycle, and related quantities. We show that the structure of the game has an important impact on the typical cycle structure. Our arguments are based on a representation of the best-response dynamics of these games as directed bipartite graphs, and on the cycle structure that arises in them.

Introduction

Best-response dynamics is arguably the most natural way of repeatedly playing a game in multi-agent systems. This dynamical process starts from an initial strategy profile, and at each step, players sequentially update their strategies by choosing the pure strategy that yields the highest payoff, given the other player’s chosen strategy. We study best-response dynamics within the framework of two-player, nn-action random games, assuming payoffs are drawn from the same continuous distribution.

Because best-response dynamics frequently lead to indefinite cycling over a subset of strategies rather than settling at a pure Nash equilibrium, a deeper investigation into this non-converging behavior is of particular interest. These cycles, together with the pure Nash equilibria, act as the natural “sink equilibria” of the game.

In this paper, we provide a rigorous analysis of the typical cycle structure of random games. We consider five types of random games, defined by the relation between the payoff matrices of both players. These games include: games with independent payoffs, symmetric, antisymmetric, zero-sum, and common-interest games. Using the properties of the games, we find the expected total number of cycles, the number of short cycles, as well as the length of the longest cycle and other related combinatorial quantities that characterize the typical geometry of the non-convergent behavior of the best-response dynamics.

Random payoffs and the best-response digraphs

Let AA and BB denote the two n×nn \times n payoff matrices of the two players. The game structure is determined by the relationship between these two matrices. In particular, we consider five types of games, each imposing a different structure on the players’ payoff matrices.

The first type is the random game with independent payoffs, in which no structure is imposed. More precisely, the two n×nn \times n matrices AA and BB of the two players have i.i.d. entries, and they are independent of each other. We also consider symmetric games, where the payoff matrix of each player is the transpose of their opponent’s. More precisely, the matrix AA of the first player has i.i.d. entries, and B=ATB = A^{\mathsf{T}}. The third type of game is an antisymmetric game, where B=−ATB = -A^{\mathsf{T}}. We also study common-interest games, where players have the same payoff matrices, A=BA = B. Lastly, we consider zero-sum games, in which the players’ payoffs satisfy B=−AB = -A.

Note that for all cases, we first assume matrix AA has i.i.d. entries, and then BB is defined according to the game types, the five classes are mutually exclusive almost surely, as each entry follows the i.i.d. continuous distribution.

By a digraph (or directed graph), we mean D=(V,E)D = (V, E) where V(D)V(D) is a nonempty set of distinct elements called vertices; and E(D)E(D) is a set of ordered pairs (u,v)(u, v) of distinct vertices u,v∈Vu, v \in V called arcs. We use a natural representation of the best-response dynamics in a two-player game by bipartite graphs, which we call best-response digraphs. Best-response digraphs allow us to extract all quantities of interest, such as the number of cycles, their length, etc. We use [n][n] for the set of integers from 1 up to nn, for any integer n≥1n \ge1. The set of all kk-element subsets of the set [n][n] is denoted by ([n]k)\binom{[n]}{k}.

Definition 1.1. Given a bimatrix game with n×nn \times n payoff matrices A=(ai,j)A = (a_{i,j}) and B=(bi,j)B = (b_{i,j}), we define a directed bipartite graph Dn=Dn(A,B)D_n = D_n(A, B) as follows. DnD_n has a vertex bipartition, RR and CC, where R={r1,…,rn}R = \{r_1, \ldots, r_n\} and C={c1,…,cn}C = \{c_1, \ldots, c_n\}. We call RR and CC the row and column parts, respectively. Digraph DnD_n contains arc (ri,cj)(r_i, c_j) if and only if bi,j=max⁡k∈[n]bi,kb_{i,j} = \max_{k \in[n]} b_{i,k}; and similarly, (cj,ri)⊂Dn(c_j, r_i) \subset D_n if and only if ai,j=max⁡k∈[n]ak,ja_{i,j} = \max_{k \in[n]} a_{k,j}.

Relations among random games of different types

Figure 1. Relations among random games of different types, which are exclusive almost surely.

Figure 2. An example of the best-response digraph. The dotted cycle cannot appear in DnD_n, otherwise, strategy r3r_3 has 2 best responses, namely strategies c2c_2 and c3c_3. The pair of strategies (r6,c5)(r_6,c_5) is a pure Nash equilibrium.

The two sets of nn vertices correspond to the nn strategies available to each player. Two vertices (one from each set) are connected with a directed edge whenever the strategy at the head of the directed edge is a best response to the strategy at the tail of that edge. If a pair of strategies {ri,cj}\{r_i,c_j\} induces a directed 2-cycle in DnD_n, then (ri,cj)(r_i,c_j) is a pure Nash equilibrium.

Definition 1.2. Let Kn,nK_{n,n} be the complete bipartite directed graph with bipartition (R,C)(R,C), where R={r1,…,rn}R=\{r_1,\ldots,r_n\} and C={c1,…,cn}C=\{c_1,\ldots,c_n\}. For a fixed ℓ≥1\ell\ge1, consider size-ℓ\ell index sets I={i1<i2<…<iℓ}∈([n]ℓ)\mathcal{I}=\{i_1<i_2<\ldots<i_\ell\}\in\binom{[n]}{\ell} and J={j1<j2<…<jℓ}∈([n]ℓ)\mathcal{J}=\{j_1<j_2<\ldots<j_\ell\}\in\binom{[n]}{\ell}. Define SmS_m as the set of permutations on [m][m]. The set of directed 2ℓ2\ell-cycles with vertex sets I,J\mathcal{I},\mathcal{J} is defined as

C2ℓ(I,J)={(ri1,cjτ(1),riσ(2),cjτ(2),…,riσ(ℓ),cjτ(ℓ))∣σ∈Sℓ−1,τ∈Sℓ}.\mathcal{C}_{2\ell}(\mathcal{I},\mathcal{J})=\left\{\left(r_{i_1},c_{j_{\tau(1)}},r_{i_{\sigma(2)}},c_{j_{\tau(2)}},\ldots,r_{i_{\sigma(\ell)}},c_{j_{\tau(\ell)}}\right)\mid\sigma\in S_{\ell-1},\tau\in S_\ell\right\}.

where each element of C2ℓ(I,J)\mathcal{C}_{2\ell}(\mathcal{I},\mathcal{J}) corresponds to the directed closed walk

ri1→cjτ(1)→riσ(2)→cjτ(2)→⋯→riσ(ℓ)→cjτ(ℓ)→ri1.r_{i_1} \to c_{j_{\tau(1)}} \to r_{i_{\sigma(2)}} \to c_{j_{\tau(2)}} \to\cdots\to r_{i_{\sigma(\ell)}} \to c_{j_{\tau(\ell)}} \to r_{i_1}.

The set of all directed 2ℓ2\ell-cycles in Kn,nK_{n,n} is

C2ℓ=⋃I,J∈([n]ℓ)C2ℓ(I,J).\mathcal{C}_{2\ell} = \bigcup_{\mathcal{I},\mathcal{J}\in\binom{[n]}{\ell}} \mathcal{C}_{2\ell}(\mathcal{I},\mathcal{J}).

For a cycle C=(ri1,cj1,…,riℓ,cjℓ)∈C2ℓC=(r_{i_1},c_{j_1},\ldots,r_{i_\ell},c_{j_\ell})\in\mathcal{C}_{2\ell}, the position subscript kk in iki_k and jkj_k is always modulo ℓ\ell; in particular iℓ+1=i1i_{\ell+1}=i_1. For C∈C2ℓC\in\mathcal{C}_{2\ell}, let I(C)⊆[n]\mathcal{I}(C)\subseteq[n] be the set of row indices used by the left vertices of CC, and let J(C)⊆[n]\mathcal{J}(C)\subseteq[n] be the set of column indices used by the right vertices of CC. The index overlap of CC is

Z(C):=∣I(C)∩J(C)∣.Z(C):=|\mathcal{I}(C)\cap\mathcal{J}(C)|.

It is easy to check (see also, e.g., [21 Eq. (1)]) that the number of directed 2ℓ2\ell-cycles in Kn,nK_{n,n} is

∣C2ℓ∣=(nℓ)2∣C2ℓ([ℓ],[ℓ])∣=(nℓ)2ℓ!2ℓ=(n)ℓ2ℓ.(1)|\mathcal{C}_{2\ell}|=\binom{n}{\ell}^{2}|\mathcal{C}_{2\ell}([\ell],[\ell])|=\binom{n}{\ell}^{2}\frac{\ell!^{2}}{\ell}=\frac{(n)_{\ell}^{2}}{\ell}. \tag*{(1)}

Since the payoffs follow a continuous distribution, ties in the payoffs occur with probability zero. Hence, there is exactly one best response given the other player’s strategy, and therefore, there is exactly one directed edge coming out of every node on both sides of the best-response digraph. This observation leads to the next lemma about the structural properties of the best-response digraphs, whose proof is a simple exercise.

Lemma 1.3. Consider a bimatrix game, where the best response is unique given the other player’s strategy. Let DnD_n be the corresponding best-response digraph.

  1. The digraph DnD_n is a directed 1-pseudoforest, that is, a directed graph, in which each vertex has outdegree exactly one;

  2. Any two distinct cycles in the graph are vertex-disjoint in DnD_n;

  3. If two paths in DnD_n intersect, then from their first point of intersection onward, they coincide.

  4. If the game is one of the five random models of § 1.1, then for any vertex uu, the in-degree of uu converges, in distribution, to Poi⁡(1)\operatorname{Poi}(1).

Overview of results and related work

The study of Nash equilibria and best-response dynamics in random games is a central research topic in game theory. In tables 1 and 2, we give a summary of the results of the paper, together with some existing results in the literature.

References

  1. [1]Ben Amiet, Andrea Collevecchio, and Kais Hamza. “When “better” is better than “best””. In: Operations Research Letters 49.2 (2021), pp. 260–264.arxiv.org/abs/2011.00239
  2. [2]Ben Amiet, Andrea Collevecchio, Marco Scarsini, and Ziwen Zhong. “Pure Nash equilibria and best-response dynamics in random games”. In: Mathematics of Operations Research 46.4 (2021), pp. 1552–1572.arxiv.org/abs/1905.10758
  3. [3]Pierre Baldi, Yosef Rinott, and Charles Stein. “A normal approximation for the number of local maxima of a random function on a graph”. In: Probability, statistics, and mathematics. Elsevier, 1989, pp. 59–81.DOI
  4. [4]Oliver Biggar and Christos H. Papadimitriou. “Sink equilibria and the attractors of learning in games”. In: 37th International Conference on Algorithmic Learning Theory. 2026.arxiv.org/abs/2502.07975
  5. [5]Andrea Collevecchio, Gábor Lugosi, Adrian Vetta, and Rui-Ray Zhang. “Finding a Nash equilibrium of a random win-lose game in expected polynomial time”. In: arXiv preprint arXiv:2510.12846 (2025).arxiv.org/abs/2510.12846
  6. [6]Andrea Collevecchio, Hlafo Alfie Mimun, Matteo Quattropani, and Marco Scarsini. “Basins of attraction in two-player random ordinal potential games”. In: arXiv preprint arXiv:2407.05460 (2024).arxiv.org/abs/2407.05460
  7. [7]Melvin Dresher. “Probability of a pure equilibrium point in n-person games”. In: Journal of Combinatorial Theory 8.1 (1970), pp. 134–145.DOI
  8. [8]Philippe Flajolet and Andrew M. Odlyzko. “Random Mapping Statistics”. In: Advances in Cryptology — EUROCRYPT ’89. Ed. by Jean-Jacques Quisquater and Joos Vandewalle. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990, pp. 329–354.
  9. [9]K. Goldberg, A. J. Goldman, and M. Newman. “The probability of an equilibrium point”. In: Journal of Research of the National Bureau of Standards. Mathematical sciences. B 72 (1968), p. 93.
  10. [10]Alan J. Goldman. “The probability of a saddlepoint”. In: The American Mathematical Monthly 64.10 (1957), p. 729.DOI
  11. [11]Bernard Harris. “Probability distributions related to random mappings”. In: The Annals of Mathematical Statistics 31.4 (1960), pp. 1045–1062.DOI
  12. [12]Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Alex Scott, Bassel Tarbush, and Samuel Wiese. “Best-response dynamics, playing sequences, and convergence to equilibrium in random games”. In: International Journal of Game Theory 52.3 (2023), pp. 703–735.DOI
  13. [13]Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. John Wiley & Sons, 2000.
  14. [14]Jerzy Jaworski. “A random bipartite mapping”. In: North-Holland Mathematics Studies. Vol. 118. Elsevier, 1985, pp. 137–158.DOI
  15. [15]Tom Johnston, Michael Savery, Alex Scott, and Bassel Tarbush. “Game connectivity and adaptive dynamics”. In: arXiv preprint arXiv:2309.10609 (2023).arxiv.org/abs/2309.10609
  16. [16]Tom Johnston, Michael Savery, Alex Scott, and Bassel Tarbush. “Game connectivity and adaptive dynamics in many-action games”. In: arXiv preprint arXiv:2601.05965 (2026).arxiv.org/abs/2601.05965
  17. [17]Valentin F. Kolchin. Random Mappings. Translated from the Russian. Translations Series in Mathematics and Engineering. New York: Optimization Software, Inc., Publications Division, 1986. ISBN: 0911575162.
  18. [18]Andrew McLennan. “The expected number of Nash equilibria of a normal form game”. In: Econometrica 73.1 (2005), pp. 141–174.
  19. [19]Hlafo Alfie Mimun, Matteo Quattropani, and Marco Scarsini. “Best-response dynamics in two-person random games with correlated payoffs”. In: Games and Economic Behavior 145 (2024), pp. 239–262.arxiv.org/abs/2209.12967
  20. [20]Dov Monderer and Lloyd S. Shapley. “Potential games”. In: Games and Economic Behavior 14.1 (1996), pp. 124–143.
  21. [21]Marco Pangallo, Torsten Heinrich, and J. Doyne Farmer. “Best reply structure and equilibrium convergence in generic games”. In: Science Advances 5.2 (2019), eaat1328.
  22. [22]Imelda Young Powers. “Limiting distributions of the number of pure strategy Nash equilibria in n-person games”. In: International Journal of Game Theory 19 (1990), pp. 277–286.
  23. [23]Paul W Purdom and John H Williams. “Cycle length in a random function”. In: Transactions of the American Mathematical Society 133.2 (1968), pp. 547–551.DOI
  24. [24]Yosef Rinott and Marco Scarsini. “On the number of pure strategy Nash equilibria in random games”. In: Games and Economic Behavior 33.2 (2000), pp. 274–293.DOI
  25. [25]William Stanford. “A note on the probability of k pure Nash equilibria in matrix games”. In: Games and Economic Behavior 9.2 (1995), pp. 238–246.DOI
  26. [26]William Stanford. “The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games”. In: Mathematics of Operations Research 21.3 (1996), pp. 726–733.DOI
  27. [27]William Stanford. “On the number of pure strategy Nash equilibria in finite common payoffs games”. In: Economics Letters 62.1 (1999), pp. 29–34.DOI
  28. [28]Brian Swenson, Ryan Murray, and Soummya Kar. “On best-response dynamics in potential games”. In: SIAM Journal on Control and Optimization 56.4 (2018), pp. 2734–2767.arxiv.org/abs/1707.06465
  29. [29]Samuel C Wiese and Torsten Heinrich. “The frequency of convergent games under best-response dynamics”. In: Dynamic Games and Applications 12.2 (2022), pp. 689–700.DOI

Paper details

vlnc:W_755sakq2
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…
Contents