← All setups

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 A,C∈Rm×n, where m,n≥1 are the players’ numbers of actions. Mixed strategies are probability vectors in Rm and Rn. Unilateral payoff differences agree with those of an exact potential taking values in [0,B], where B>0. The oracle returns Ay and C⊤x at a strategy pair (x,y). For ε>0, Regret Matching+ must return probability vectors (x¯,y¯) for which neither player can increase its expected payoff by more than ε through any unilateral pure-action deviation.

Write Δd={z∈Rd:zi≥0 for all i, ∑i=1dzi=1}. The players maximize the respective payoffs x⊤Ay and x⊤Cy over x∈Δm and y∈Δn. The algorithm receives only m, n, and ε; the bound B may enter the oracle-call budget but is not an algorithm input.

Our assumptions:

Assumption 1 (Bounded exact potential). There exists a matrix H∈Rm×n such that, for all i,i′∈{1,…,m} and j,j′∈{1,…,n}, 0≤Hij≤B,Aij−Ai′j=Hij−Hi′j,Cij−Cij′=Hij−Hij′.

Queries may be made at any (x,y)∈Rm×Rn. One oracle call returns both exact payoff vectors ui=∑j=1nAijyj,i=1,…,m,vj=∑i=1mCijxi,j=1,…,n.

The setup is algorithm-specific: we analyze Regret Matching+ with simultaneous updates and retention of the most recent pair passing the deviation test. For d≥1 and q∈Rd, define Sd(q)i={qi/∑ℓ=1dqℓ,∑ℓ=1dqℓ>0,1/d,∑ℓ=1dqℓ≤0. Initialize the two regret vectors as q0=0∈Rm and r0=0∈Rn, and initialize the retained pair as z0=(Sm(0),Sn(0)). At iteration t≥0, query xt=Sm(qt),yt=Sn(rt),ut=Ayt,vt=C⊤xt. Define the instantaneous deviation gains and update the regret vectors by ait=uit−(xt)⊤ut,qit+1=max{qit+ait,0},bjt=vjt−(yt)⊤vt,rjt+1=max{rjt+bjt,0}. The retained pair is updated using the strategies queried at that iteration: zt+1={(xt,yt),ait≤ε for every i and bjt≤ε for every j,zt,otherwise. After the allotted T oracle calls, the output is (x¯,y¯)=zT. Thus, if no queried pair passes the test, the output remains the initial uniform pair.

The required accuracy is an ε-Nash equilibrium: x¯∈Δm,y¯∈Δn,(Ay¯)i≤x¯⊤Ay¯+ε,i=1,…,m,(C⊤x¯)j≤x¯⊤Cy¯+ε,j=1,…,n. These requirements hold for every realization, rather than only in expectation or almost surely.

Proved result

⌈20000⋅B2⋅(m+n)4ε2⌉++1

OracleTemplate.Convergence LongTails.Setups.RegretMatchingPotential.spec OracleTemplate.RegretMatchingPotential.budget

Relevant previous results

  • Dov Monderer and Lloyd S. Shapley. Potential Games. 1996. Complexity: O(1+B/ε) 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: O(1+max{m,n}B2/ε2) paired payoff-vector oracle calls for ε-lazy alternating discounted regret matching⁺ with fixed discount factor 1/2, obtaining an ε-Nash equilibrium; deterministic worst-case cost including initialization and equilibrium checks.