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
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
Results
Two-player exact potential games with
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RegretMatchingPotential (Ours) (review) | |||
| (2) |
(1): Analysis of plain simultaneous RM+, with uniformly bounded regret states; no equilibrium-computation improvement. | (1): Dimension factor
|
|
| (3) |
(1): |
(1): Larger bound above
that threshold for |
|
| (4) Zero-initialized
|
Derived bound on these games: |
(1): Dominant bound
smaller by |
(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: |
(1): No established improvement in equilibrium computation; analyzes simultaneous RM+ rather than centralized reconstruction. | (1): Larger bound for
|
| (6) Unilateral improvement (Monderer and Shapley 1996, Lem. 4.2) | Derived bound: |
(1): No established complexity improvement; analyzes simultaneous RM+ without coordinating unilateral deviations. | (1): Larger bound for
|
Abbr: