Regret Matching Potential — Regret Matching+ in Potential Games
Descriptions may be stale. Consult the linked Lean sources.
Regret Matching+ in Potential Games · Lean proof
Regret Matching+ in Potential Games
We consider a two-player game with payoff matrices
Write
Our assumptions:
Assumption 1 (Bounded exact potential). There exists
a matrix
Queries may be made at any
The setup is algorithm-specific: we analyze Regret Matching+ with
simultaneous updates and retention of the most recent pair passing the
deviation test. For
The required accuracy is an
Proved result
OracleTemplate.Convergence LongTails.Setups.RegretMatchingPotential.spec OracleTemplate.RegretMatchingPotential.budgetRelevant previous results
- Dov Monderer and Lloyd S. Shapley. Potential Games. 1996.
Complexity:
paired payoff-vector oracle calls for ε-improvement dynamics to obtain a pure ε-Nash equilibrium, including the final check; deterministic worst-case cost. - Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis
Panageas, Vincent Conitzer, and Tuomas Sandholm. Convergence
of Regret Matching in Potential Games and Constrained Optimization.
2026 (preprint 2025; published version used). Complexity:
paired payoff-vector oracle calls for ε-lazy alternating discounted regret matching⁺ with fixed discount factor , obtaining an ε-Nash equilibrium; deterministic worst-case cost including initialization and equilibrium checks.