Do Not Discretize, Optimize: Almost Greedy Fictitious Play

Christodoulos Santorinaios; Evangelos Markakis

REVIEW 2 major objections 2 minor 17 references

Do Not Discretize, Optimize: Almost Greedy Fictitious Play

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Almost Greedy Fictitious Play reaches O(1/T) duality-gap convergence by optimizing stepsizes in a constrained line search.

desk verdict Almost Greedy Fictitious Play matches the O(1/T) duality-gap rate of continuous fictitious play by constraining the greedy stepsize search to nearly the full line to the best response. read the letter →

arxiv 2606.12149 v1 pith:SX3P6AYM submitted 2026-06-10 cs.GT

Evangelos Markakis , Christodoulos Santorinaios This is my paper

classification cs.GT

keywords FictitiousPlayNashequilibriumzero-sumgamesconvergenceratedualitygapiterativemethodsgametheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents Almost Greedy Fictitious Play as a variant of the classic iterative method for zero-sum games. At each step the algorithm selects the best stepsize along nearly the entire segment connecting the current cumulative mixed strategy to the best response, without discretizing the choice. The central result establishes an instance-dependent O(1/T) rate on the duality gap. A reader would care because the approach recovers the rate of continuous fictitious play while remaining computationally practical for equilibrium computation.

What carries the argument

Constrained greedy stepsize optimization along the line from cumulative mixed strategy to best response.

What would settle it

A zero-sum game instance in which the duality gap fails to decrease at rate O(1/T) under the algorithm's updates.

Watch

Extended reading notes

Core claim

Almost Greedy Fictitious Play greedily attempts to find the optimal stepsize at each iteration but restricts the search space to a set that includes almost the full line between the cumulative mixed strategy and the current best response. Under this construction the method converges to a Nash equilibrium at an instance-dependent rate of O(1/T) measured by the duality gap.

Load-bearing premise

The search space at each iteration is constrained yet includes almost all the line between the cumulative mixed strategy and the current best response.

Editorial extensions

If this is right

The convergence rate matches that of Continuous Fictitious Play.
The method supplies a practical alternative to discretization of the stepsize.
Empirical runs confirm faster practical progress than standard discretized variants.
The rate holds instance-dependently for any zero-sum payoff matrix.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same constrained-optimization idea could be tested on non-zero-sum or extensive-form games where fictitious-play variants are already used.
Implementation cost remains linear in the support size, so the approach may scale to matrix games larger than those solvable by full continuous optimization.
If the line-search constraint is relaxed further, the rate might degrade to the slower 1/sqrt(T) bound of classical fictitious play.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main takeaway is that this paper gives a discrete algorithm that reaches the same instance-dependent O(1/T) rate as continuous fictitious play without discretizing time. The trick is limiting the stepsize search at each iteration so it covers almost the entire segment from the running average strategy to the current best response.

What is new is the specific constrained-greedy rule and the claim that this restriction is enough to recover the continuous rate. The authors position it as a practical alternative to discretization methods, and they include experiments that show faster practical convergence than plain fictitious play.

The approach is straightforward and the rate result is stated clearly. The instance-dependent framing is also honest rather than overstated. Experiments add some evidence that the method is usable.

The softer part is the precise meaning of "almost all the line." The paper must define how close the search interval gets to the full segment and whether any extra parameter is needed to guarantee the rate. If that parameter has to be tuned close to the boundary, the practical advantage over other accelerations could shrink. The proof presumably shows that the constraint still lets the continuous analysis go through, but any gap between the stated constraint and the actual implementation would matter.

This is for people working on iterative equilibrium methods in zero-sum games, especially those who want to stay in discrete time. A reader already following fictitious-play variants will find the construction and the rate claim useful.

It deserves a serious referee because the central claim is a concrete new variant with a matching rate and supporting experiments. I recommend sending it to peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Almost Greedy Fictitious Play (AGFP), a variant of fictitious play for zero-sum games. At each iteration, AGFP optimizes the stepsize but constrains the search space to include almost the entire line segment from the current cumulative mixed strategy to the best response. The central claim is that this yields an instance-dependent O(1/T) convergence rate on the duality gap, matching Continuous Fictitious Play while avoiding explicit discretization.

Significance. If the central claim holds, the result supplies a practical, optimization-based route to the continuous fictitious-play rate without discretization, which is relevant for equilibrium computation in machine-learning settings. The instance-dependent rate and the explicit positioning as an alternative to discretization are the primary contributions.

major comments (2)

[§3, Theorem 1] §3 (algorithm definition) and Theorem 1: the precise mathematical definition of the constrained search set (the set that 'includes almost all the line') is required to verify that the O(1/T) proof does not implicitly rely on a discretization parameter or additional regularity assumptions not stated in the abstract.
[Proof of Theorem 1] Proof of Theorem 1: the argument that the constrained greedy step preserves the continuous-time rate must be checked for circularity; specifically, whether the 'almost all' inclusion is used in a way that reduces the claimed rate to a fitted or post-hoc quantity.

minor comments (2)

[Abstract] Abstract: the phrase 'almost all the line' is informal; replace with a precise set-theoretic or measure-theoretic description once the algorithm is defined.
[Experiments] Experiments section: clarify whether the reported duality-gap curves are averaged over random seeds and whether the instance-dependent rate is measured against a known lower bound for the chosen game class.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the major comments point by point below.

read point-by-point responses

Referee: [§3, Theorem 1] §3 (algorithm definition) and Theorem 1: the precise mathematical definition of the constrained search set (the set that 'includes almost all the line') is required to verify that the O(1/T) proof does not implicitly rely on a discretization parameter or additional regularity assumptions not stated in the abstract.

Authors: We agree that greater precision in the definition of the constrained search set will improve clarity. In the revised version we will state explicitly that the search set at iteration t is the line segment [x_t, b_t] minus an open ball of radius ε_t > 0 centered at x_t, where ε_t can be chosen arbitrarily small (independent of any grid) subject only to ensuring a strictly positive step length. No discretization parameter or extra regularity assumptions beyond those required for continuous fictitious play are introduced; the set remains uncountable and the optimization is performed over a continuum. revision: yes
Referee: [Proof of Theorem 1] Proof of Theorem 1: the argument that the constrained greedy step preserves the continuous-time rate must be checked for circularity; specifically, whether the 'almost all' inclusion is used in a way that reduces the claimed rate to a fitted or post-hoc quantity.

Authors: The proof is not circular. We first recall the standard continuous-time fictitious-play ODE and its instance-dependent O(1/T) duality-gap bound (which holds for any zero-sum game). We then show that, because the admissible step-size set contains every point on the line segment except an arbitrarily small neighborhood of the current iterate, there always exists a feasible step whose instantaneous decrease in the Lyapunov function matches the continuous-time decrease up to an o(1/T) remainder that is uniform over the instance class. The o(1/T) term is derived from the geometry of the line segment and does not rely on any post-selection or fitting; the same bound holds for every admissible choice inside the set. We are happy to insert an expanded proof sketch that separates the continuous analysis from the discrete approximation argument. revision: partial

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper presents Almost Greedy Fictitious Play as a new algorithmic variant whose stepsize search is explicitly constrained to nearly the full line segment to the best response. Its central claim—an instance-dependent O(1/T) duality-gap rate—is stated as a derived theoretical result that matches but does not reduce to the rate of Continuous Fictitious Play. No equations, definitions, or citations in the provided abstract or description exhibit self-definition, fitted inputs renamed as predictions, load-bearing self-citations, or imported uniqueness theorems. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claim rests on the domain assumption that the setting is zero-sum games and on the modeling choice that the constrained line segment is sufficient to recover the continuous-time rate. No free parameters or invented entities are mentioned.

assumptions (1)

domain assumption The game is zero-sum
Convergence statement is given specifically for zero-sum games.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Do Not Discretize, Optimize: Almost Greedy Fictitious Play." pith.science (2026). https://pith.science/paper/SX3P6AYM

@misc{pith2026260612149,
  author       = {Pith},
  title        = {Pith review of: Do Not Discretize, Optimize: Almost Greedy Fictitious Play},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SX3P6AYM}},
  note         = {Machine review of arXiv:2606.12149}
}

abstract

Our work revolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a revived interest, due to applications in various machine learning problems, which has motivated a line of work on its convergence properties and on proposing new variants of the initial algorithm. Our paper is along this direction and introduces one new variant, which we refer to as Almost Greedy Fictitious Play. The proposed algorithm greedily attempts to find the optimal stepsize at each iteration but its search space is constrained and includes almost all the line between the cumulative mixed strategy and the current best response. Our main result is that the method achieves an instance dependent convergence rate of $\mathcal{O}(1/T)$ with respect to the duality gap. This matches the rate of Continuous Fictitious Play, and offers an alternative to discretization. We complement our theoretical findings with experiments that demonstrate the effectiveness of the method.

Figures

Figures reproduced from arXiv: 2606.12149 by the authors.

**Figure 2.** The steps the algorithm selected greedily [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** AGFP in the RPS game with δ = 10−4 Performance in random games. We move forward by testing our method in randomly generated games. More specifically, we sample the entries of the matrix independently from a standard Gaussian distribution and normalize them in [0, 1]. Since we have already tested the “small” Rock-PaperScissors game, we first test at a moderate game of size 50 × 50 using δ = 10−8 . The results are pr… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: AGFP in a 50 × 50 random Gaussian game. Before exploring further the effect of the dimension in the dynamics, we have to comment about the optimal steps in the random case. We observe that the nice picture of the Rock-Paper-Scissors games changes: the stepsizes are sti…

**Figure 5.** Figure 5: AGFP in a 500 × 500 random Gaussian game 12 [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

**Figure 6.** Figure 6: Time comparison between FP and AGFP in a Gaussian random [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 7.** Figure 7: AGFP steps in the 17 × 17 RPS game as an open question. Another avenue for future work is to study our algorithm, and especially the condition-like number, in the smooth regime. Anagnostides and Sandholm [2024] provided a similar treatment to gradient-based algorithms.…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 4 canonical work pages

[1]

Fast convergence of fictitious play for diagonal payoff matrices

Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Fast convergence of fictitious play for diagonal payoff matrices. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1387–1404. SIAM,

2021
[2]

Convergence oflog(1/ϵ)for gradient-based algorithms in zero-sum games without the condition number: A smoothed analysis

Ioannis Anagnostides and Tuomas Sandholm. Convergence oflog(1/ϵ)for gradient-based algorithms in zero-sum games without the condition number: A smoothed analysis. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Conferenc...

2024
[3]

(doubly) exponential lower bounds for follow the regularized leader in potential games.arXiv preprint arXiv:2601.23248,

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, and Tuomas Sandholm. (doubly) exponential lower bounds for follow the regularized leader in potential games.arXiv preprint arXiv:2601.23248,

work page arXiv
[4]

Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games

Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors,International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 ofProceedings of...

2022
[5]

On the convergence of fictitious play: A decomposition approach

Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, and Yaodong Yang. On the convergence of fictitious play: A decomposition approach. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 179–185. ijcai.org,

2022
[6]

Anticipatory fictitious play

Alex Cloud, Albert Wang, and Wesley Kerr. Anticipatory fictitious play. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 73–81. ijcai.org,

2023
[7]

A descent-based method on the duality gap for solving zero-sum games

15 Michail Fasoulakis, Evangelos Markakis, Georgios Roussakis, and Christodoulos Santorinaios. A descent-based method on the duality gap for solving zero-sum games. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 3839–3847. ijcai.org,

2025
[8]

Frank-wolfe algorithms for saddle point problems

Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Aarti Singh and Xiaojin (Jerry) Zhu, editors,Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 ofProceedings of Machine Learning Research, ...

2017

Show all 17 references

[9]

Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C

Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors,Advances i...

2014
[10]

Optimism without regu- larization: Constant regret in zero-sum games

John Lazarsfeld, Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimism without regu- larization: Constant regret in zero-sum games. InAdvances in Neural Information Processing Systems 38 (NeurIPS 2025), volume 38, San Diego, CA, USA, 2025a. John Lazarsfeld, Georgios P...

2025
[11]

Fictitious play property for games with identical interests

Dov Monderer and Lloyd S Shapley. Fictitious play property for games with identical interests. Journal of economic theory, 68(1):258–265, 1996a. Dov Monderer and Lloyd S Shapley. Potential games.Games and economic behavior, 14(1):124–143, 1996b. Paul Muller, Shayegan Omidshafi...

2020
[12]

doi: 10.3934/jdg.2014.1.621

ISSN 2164-6066. doi: 10.3934/jdg.2014.1.621. Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. Exponential lower bounds for fictitious play in potential games. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, edi...

2014 doi
[13]

Fictitious play in zero-sum stochastic games.SIAM Journal on Control and Optimization, 60(4):2095–2114,

Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games.SIAM Journal on Control and Optimization, 60(4):2095–2114,
[14]

Tie-breaking agnostic lower bound for fictitious play.arXiv preprint arXiv:2507.09902,

17 Yuanhao Wang. Tie-breaking agnostic lower bound for fictitious play.arXiv preprint arXiv:2507.09902,
[15]

Linear last-iterate conver- gence in constrained saddle-point optimization

Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate conver- gence in constrained saddle-point optimization. In9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7,

2021
[16]

An overview of multi-agent reinforcement learning from game theoretical perspective.arXiv preprint arXiv:2011.00583,

Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective.arXiv preprint arXiv:2011.00583,

2011
[17]

Mean field multi-agent reinforcement learning

Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In Jennifer G. Dy and Andreas Krause, editors,Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sw...

2018

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

Fast convergence of fictitious play for diagonal payoff matrices

Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Fast convergence of fictitious play for diagonal payoff matrices. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1387–1404. SIAM,

2021

[2] [2]

Convergence oflog(1/ϵ)for gradient-based algorithms in zero-sum games without the condition number: A smoothed analysis

Ioannis Anagnostides and Tuomas Sandholm. Convergence oflog(1/ϵ)for gradient-based algorithms in zero-sum games without the condition number: A smoothed analysis. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Conferenc...

2024

[3] [3]

(doubly) exponential lower bounds for follow the regularized leader in potential games.arXiv preprint arXiv:2601.23248,

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, and Tuomas Sandholm. (doubly) exponential lower bounds for follow the regularized leader in potential games.arXiv preprint arXiv:2601.23248,

work page arXiv

[4] [4]

Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games

Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors,International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 ofProceedings of...

2022

[5] [5]

On the convergence of fictitious play: A decomposition approach

Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, and Yaodong Yang. On the convergence of fictitious play: A decomposition approach. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 179–185. ijcai.org,

2022

[6] [6]

Anticipatory fictitious play

Alex Cloud, Albert Wang, and Wesley Kerr. Anticipatory fictitious play. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 73–81. ijcai.org,

2023

[7] [7]

A descent-based method on the duality gap for solving zero-sum games

15 Michail Fasoulakis, Evangelos Markakis, Georgios Roussakis, and Christodoulos Santorinaios. A descent-based method on the duality gap for solving zero-sum games. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 3839–3847. ijcai.org,

2025

[8] [8]

Frank-wolfe algorithms for saddle point problems

Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Aarti Singh and Xiaojin (Jerry) Zhu, editors,Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 ofProceedings of Machine Learning Research, ...

2017