← All setups

Regret Matching+ in Potential Games

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Two-player exact potential games with m,n≥1, B,ε>0, payoff matrices A,C, and an exact potential P∈[0,B]m×n: unilateral payoff differences equal potential differences; payoff levels are unrestricted. Each oracle call returns (Ay,C⊤x) exactly. The setup fixes zero-initialized, undiscounted simultaneous RM+; public inputs are m,n,ε, while B determines the horizon. Its saved certified pre-update profile (x,y)∈Δm×Δn satisfies maxi(Ay)i−x⊤Ay≤ε and maxj(C⊤x)j−x⊤Cy≤ε for every seed. Prior methods are compared on these games in paired-vector calls; alternating sweeps cost two calls.

Comparison for RegretMatchingPotential.
Result Oracle complexity Novelty Limitations
(1) RegretMatchingPotential (Ours) (review) O(1+B2(m+n)4ε2)
(2) ε-lazy discounted alternating RM+ (Anagnostides et al. 2025, Cor. 3.5), γ=1/2 O(1+B2max(m,n)ε2) (1): Analysis of plain simultaneous RM+, with uniformly bounded regret states; no equilibrium-computation improvement. (1): Dimension factor (m+n)4 instead of max(m,n); only two players instead of arbitrary player counts.
(3) ε-lazy alternating RM+ (Anagnostides et al. 2025, Thm. 3.4) O(1+B4max(m,n)2ε4) (1): ε−2 instead of ε−4; smaller bound when 0<ε<Bmax(m,n)/(m+n)2. Always-updating simultaneous play. (1): Larger bound above that threshold for ε≤B; only two players.
(4) Zero-initialized ε-lazy simultaneous RM+ (Anagnostides et al. 2025, Thm. 3.12, App. C.1)

Derived bound on these games:

O(1+B8(m+n)10ε8), 0<ε≤B.

(1): Dominant bound smaller by B6(m+n)6/ε6 for 0<ε≤B; no lazy skipping. (1): Only two-player bilinear potentials; (4) also covers smooth objectives on arbitrary products of simplices.
(5) Matrix recovery and potential maximization (Monderer and Shapley 1996, Lem. 2.1) Derived bound: O(max(m,n)); exact pure Nash equilibrium, using paired basis queries and uncharged arithmetic. (1): No established improvement in equilibrium computation; analyzes simultaneous RM+ rather than centralized reconstruction. (1): Larger bound for 0<ε≤B; only approximate mixed-profile accuracy, not exact pure equilibrium.
(6) Unilateral improvement (Monderer and Shapley 1996, Lem. 4.2) Derived bound: O(1+B/ε); pure ε-Nash profile, one paired call per tested profile. (1): No established complexity improvement; analyzes simultaneous RM+ without coordinating unilateral deviations. (1): Larger bound for 0<ε≤B; does not guarantee a pure profile.

Abbr: Δd is the probability simplex on d actions; RM+ is regret matching with nonnegative clipping; γ is the geometric discount parameter. An ε-lazy update skips a player whose deviation gain is at most ε.

Anagnostides, Ioannis, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, and Tuomas Sandholm. 2025. Convergence of Regret Matching in Potential Games and Constrained Optimization. https://doi.org/10.48550/arXiv.2510.17067.
Monderer, Dov, and Lloyd S. Shapley. 1996. “Potential Games.” Games and Economic Behavior 14 (1): 124–43. https://doi.org/10.1006/game.1996.0044.

Lean setup