CS Paper Radar

Arbitrarily Slow Polynomial Convergence of Fictitious Play

Jacob Abernethy, John Lazarsfeld, Andre Wibisono

cs.GT ·submitted 2026-10-06 17:52 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games

cs.GT cs.CCmath.OC ·2026-10-19 ·Sanyou Mei
theory similarity 0.73
Abstract

We study turn-based deterministic zero-sum games with discounted and long-run average costs. For discounted costs, we establish exponential and superpolynomial iteration lower bounds for the simple strategy-iteration method with Dantzig's rule under unrestricted costs and unit weights, respectively. To the best of our knowledge, we establish for the first time that the method is not strongly polynomial, and this remains true even when all action costs belong to $\{-1,0,1\}$. For long-run average costs, we extend the Dantzig counterpart in~\cite{zhongye2026} to the two-player setting and prove that it terminates at an optimal strategy profile. However, a similar counterexample construction establishes an exponential iteration lower bound for termination with unrestricted costs. This construction does not extend to unit weights, for which we prove that the algorithm admits a strongly polynomial implementation.

0.05

The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games

cs.GT cs.CC ·2026-09-07 ·Noah Golowich
theory similarity 0.68
Abstract

We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = ω(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).

0.49

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

cs.GT ·2026-11-16 ·Daisuke Hirota
similarity 0.67
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.43

Cycle structure of best-response dynamics in random bimatrix games

cs.GT ·2026-10-21 ·Georgios Nikolaos Karelas, Gábor Lugosi, Rui-Ray Zhang
similarity 0.67
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.

0.10

Fictitious Play When Agents Are Not Expected-Utility Maximizers: A Geometric Analysis in $2$-Action Games

cs.GT eess.SYmath.OC ·2026-11-12 ·Hao Liang, Solaleh Mohammadi, Kaiqing Zhang
similarity 0.66
Abstract

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in $2\times2$ games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in $2\times2$ games, even when the SCP fails. Beyond $2\times2$ games, we show that the convergence of NL-FP in $2\times n$ ($n\ge3$) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a $2\times3$ game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general $2\times n$ games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

0.13

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

cs.LG cs.GT ·2026-09-28 ·Yuheng Zhang
theory similarity 0.64
Abstract

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.

0.33

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.64
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50

Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

cs.LG cs.GT ·2026-11-04 ·Yuval Dagan, Nadav Eisen, Liad Erez, Tomer Koren
theory similarity 0.63
Abstract

Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{Ω(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{Ω(mn)}$; for learning rates above $2^{-Ω(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.

0.16