CS Paper Radar

Cycle structure of best-response dynamics in random bimatrix games

Georgios Nikolaos Karelas, Gábor Lugosi, Rui-Ray Zhang

cs.GT ·submitted 2026-10-21 03:40 UTC · v2

Abstract

We study the best-response dynamics in games with random payoffs. We consider two-player bimatrix games, with $n$ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Equilibrium Numbers in Non-Square Bimatrix Games

cs.GT math.CO ·2026-09-21 ·Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
theory similarity 0.70
Abstract · 32 pages

Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.

0.29

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.69
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

Arbitrarily Slow Polynomial Convergence of Fictitious Play

cs.GT ·2026-10-06 ·Jacob Abernethy, John Lazarsfeld, Andre Wibisono
similarity 0.67
Abstract

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k \ge 2$, we construct a payoff matrix with $(k+1)^2 - 5$ actions per player for which the duality gap of the empirical strategies decays as $Θ(t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k \ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $Θ(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.

0.42

Payoff-Based Certificates for Convergence to Pure Nash Equilibria under Replicator Dynamics

cs.GT ·2026-11-16 ·Daisuke Hirota
similarity 0.66
Abstract · 18 pages, 1 figure

For finite bimatrix games, we give a payoff-based sufficient condition $E>0$ for an interior initial state to converge to a specified strict pure Nash equilibrium under replicator dynamics. The construction combines lower bounds on the growth rates of log probability ratios between target and alternative actions with a first integral of a two-dimensional comparison system. It allows one player's payoff advantage to compensate for the other's disadvantage, certifying convergence even when a target action initially loses probability. For rational inputs and integration base points with algebraic exponentials, we give a finite exact test. We obtain closed-form box probabilities and, when all nontarget actions are included, closed-form upper bounds on convergence time. In two-action coordination games, choosing the base points at the sign thresholds recovers the full basin of attraction. Experiments on random games show that basin coverage shrinks rapidly with the number of actions. For $n=4,5,6$, median entry times are approximately 70% of median box-entry times without shifts and 40% for a union over 16 shift choices. Extensions cover multiplayer games through cooperative comparison systems and explicit boxes, and discrete-time exponential-weights learning under explicit step-size conditions.

0.42

Performance of Zero-determinant Strategies in Repeated Games without Discounting

cs.MA physics.soc-pheess.SY ·2026-10-02 ·Masahiko Ueda
similarity 0.64
Abstract · 4 pages, 1 figure

Zero-determinant (ZD) strategies are a class of strategies in repeated games, which unilaterally control payoffs. It has been shown that several ZD strategies promote cooperation in social dilemma games. It has been widely believed that the performance of ZD strategies is expressed as ``unilaterally enforce linear relations between payoffs''. However, in order to interpret properties of ZD strategies in repeated games without discounting, previous studies assumed that the limit of the Cesaro average of the probability distribution of the action profile exists. Here, we explain the performance of ZD strategies without this assumption, which leads to a stronger result than previous ones.

0.41

On Periodic and Aperiodic Optimal Strategies in Solvency Games

cs.GT math.PR ·2026-09-16 ·Quentin Guilmant, Florian Luca, Richard Mayr, Joël Ouaknine, James Worrell
similarity 0.62
Abstract

Solvency games are a gambling problem on infinite-state Markov decision processes in which the state $n \in \mathbb{N}$ represents an investor's fortune. In every round, the investor chooses an action from a finite action set, and every action yields a distribution over integer-valued gains in an interval $\{-\ell,\ldots,m\}$. The risk-averse investor wants to minimise the probability of eventual ruin (reaching a fortune $\le 0$). It was shown in [Berger et al.] that memoryless deterministic optimal strategies exist, but they are not eventually constant in general. Even in the special case of gains in $\{-2,\ldots,1\}$, the optimal strategy may need to make use of two different actions at arbitrarily high fortunes. We show that optimal strategies in solvency games need not be ultimately periodic in general (thus disproving a 2012 conjecture of Kučera). Already in the case of gains in $\{-3,\ldots,1\}$, it is possible for the optimal strategy to be unique but aperiodic. For gains in $\{-2,\ldots,1\}$, there always exists an ultimately periodic optimal strategy whose tail is constant or alternates between two actions. Finally, we show that the optimal strategy is computable if it is unique. Moreover, (some) optimal strategy can always be computed in the case of gains in $\{-\ell,\ldots,1\}$ for any $\ell \in \mathbb{N}$. Computability in the general case however remains open.

0.32

A Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.62
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26

Normal-Form Correlation in Markov Games

cs.GT cs.CCcs.DScs.LG ·2026-10-02 ·Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm +1 more
similarity 0.62
Abstract

There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $1/ε$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

0.41