Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
Authors: Brian Hu Zhang
Gabriele Farina
Ioannis Anagnostides
Federico Cacciamani
Stephen Marcus McAleer
Andreas Alexander Haupt
Andrea Celli
Nicola Gatti
Vincent Conitzer
Tuomas Sandholm
Venue: NeurIPS 2023 poster (2023)
Keywords: extensive-form games
deep reinforcement learning
mechanism design
correlated equilibria
TL;DR: We introduce a new scalable approach for computing optimal equilibria in games via a reduction to a zero-sum extensive-form game.

Abstract: We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensive-form zero-sum game. This reformulation allows to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning.

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
Brian Hu Zhang*
Gabriele Farina" MIT gfarinaCmit.edu
Ioannis Anagnostides Carnegie Mellon University ianagnos@cs. cmu. edu
Carnegie Mellon University bhzhang@cs. cmu. edu
Federico Cacciamani
Stephen McAleer Carnegie Mellon University smcaleer&cs, cmu. edu
Andreas Haupt
DEIB, Politecnico di Milano federico. cacciamani@pol
MIT haupt@mit.edi edu
Andrea Celli Bocconi University
Nicola Gatti
DEIB, Politecnico di Milano nicola. datoll.gatt@pool..... imi. it
andrea. www.:iiuuniboccooi......
Vincent Conitzer Carnegie Mellon University conitzer@cs. cmu. edu
Tuomas Sandholm
Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. candholm@cs cmu, edu
Abstract
We introduce a new approach for computing optimal equilibria and mechanisms via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such correlated. communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensive- form zero-sum game. This reformulation allows to apply techniques for learn- ing in zero-sum games, yielding the first learning dynamics that converge to opti- mal equilibria, only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-ar performance benchmark tabular games, and by computing an optimal mecha- nism for sequential auction design problem using deep reinforcement learning.
Introduction
What does it mean to solve a game? This is one of the central questions addressed in game theory, leading variety of different solution concepts. Perhaps first and foremost, there various notions equilibrium, strategically stable points from which no rational individual would be inclined deviate. But is it enough to compute, of a game? In two-player zero-sum games, one can make a convineing argument that a single equilibrium in fact constitutes complete solution to the game, based on the celebrated minimax theorem of von Neumann [97]. Indeed, approaches based on computing minimax equilibria in
indeed learn, just any equilibrium
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

two-player zero-sum games have enjoyed remarkable success in solving major Al challenges, exemplified by the recent development of superhuman poker AI agents [10, 11].
However, in general-sum games it becomes harder to argue that any equilibrium constitutes a com- plete solution. Indeed, one equilibrium can offer vastly different payoffs to the players than another. Further, if player acts according to one equilibrium and another player according to different one, the result may not be an equilibrium at all, resulting in a true equilibrium selection problem. In this paper, therefore, we focus on computing an optimal equilibrium, that is, one that maximizes a given linear objective within the space of equilibria. There are various advantages to this approach. First, in many contexts, we would simply prefer to have an equilibrium that maximizes, say. the sum of the players' utilities- and by computing such an equilibrium we also automatically avoid pareto-dominate equilibria. Second, it can mitigate the equilibrium selection problem: if there is a convention that we always pursue an equilibrium that maximizes social welfare, this reduces the risk that players end up playing according to different equilibria. Third, if one has little control over how the game will be played but cares about its outcomes, one may like to understand the space of all equilibria. In general, a complete picture of this space can be elusive, in part because game can have exponentially many equílibria: but computing extreme equilibria in many directions-sayy one that maximizes Player I's utility-can provide meaningful information about the space of equilibria.
That being said, many techniques that have been successful at computing a single equilibrium do not lend themselves well to computing optimal equilibria. Most notably, while no-regret learning dynamics are known to converge to different notions of correlated equilibria [49, 38, 39, 47], little is known about the properties of the equilibrium reached. In this paper, therefore, we introduce new paradigm of learning in games for computing optimal equilibria. applies to extensive-fore settings with any number of players, including information design, and solution concepts such as correlated, communication, and certification equilibria. Further, our framework is general enough to also capture optimal mechanism design and optimal incentive design problems in sequential settings.
Summary of Our Results A key insight that underpins our results is that computing optimal equilibria in multi-player extensive-form games can be cast via a Lagrangian relaxation as a two-player zero-sum extensive-fome game. This unlocks rich technology, both theoretical and experimental, developed for computing minimax equilibria for the more challenging andnnng--ndddd much less understood- porind-rrolemmmem of computing optimal equilibria. In particular, building the framework of Zhang and Sandholm [100], our reduction lends itself to mechanism design and information design, well as entire hierarchy of equilibrium concepts, including normal-form coarse correlated equilibria (NFCCE) [79], extensive-form coarse correlated equilibria (EFCCE) [31], extensive-form correlated equilibria (EFCE) [98], communication equilibria (COMM) [36], and certification equilibria (CERT) [37]. In fact, for communication and certification equilibria, our framework leads the first learning-based algorithms for computing them, addressing a question left open by Zhang and Sandholm [100] (cf. [40], discussed in Appendix B).
We thus focus computing an optimal equilibrium by employing regret minimization techniques in order to solve the induced bilinear saddle-poin problem. Such considerations are motivated in part by the remarkable success of no-regret algorithms for computing minimax equilibria in large two-player zero-sum games (e.g., see [10, 11)). which we endeavor to transfer to the problem of computing optimal equilibria in multi-player games.
In this context, we show that employing standard regret minimizers, such as online mirror de- scent [91] or counterfactual regret minimization [106], leads to a rate of convergence of 1/4 to optimal equilibria by appropriately tuning the magnitude of the Lagrange multipliers (Corollary 3.3). We also leverage the technique of optimism. pioneered by Chiang et al. [18], Rakhlin and Sridha- ran [87] and Syrgkanis et al. [94], to obtain an accelerated 1/2 rate of convergence (Corollary 3.4). These are the first learning dynamics that (provably) converge to optimal equilibria. Our bilinear for- mulation also allows us to obtain last-iterate convergence optimal equilibria via optimistic gradi- ent descent/ascent (Theorem 3.5), instead of the time-average guarantees traditionally derived within the no-regret framework. As such, we bypass known barriers in the traditional learning paradigm by incorporating an additional player, a mediator, into the learning process. Furthermore, we also study an alternative Lagrangian relaxation which, unlike our earlier approach, consists of solving a sequence of zero-sum games (cf. [30]). While the latter approach is less natural, we find that it is preferable when used conjunction with deep RI. solvers since it obviates the need for solving games with large reward ranges- a byproduct of employing the natural Lagrangian relaxation.

---

Experimental results We demonstrate the practical scalability of our approach for computing optimal equilibria and mechanisms. First, we obtain state-of-the-art performance different benchmark game instances for seven different equilibrium concepts. Our algorithm sig- nificantly outperforms existing LP-based methods, typically by more than one order of magnitude. We also use our algorithm to derive an optimal mechanism for a sequential auction design problem, and we demonstrate that our approach is naturally amenable to modern deep RL techniques.
suite of 23
1.1 Related work
In this subsection, we highlight prior research that closely relates to our work. Additional related work is included in Appendix B.
A key reference point is the recent paper of Zhang and Sandholm [100], which presented a unifying framework that enables the computation via linear programming of various mediator- equilib- rium concepts in extensive-form games, including NFCCE, EFCCE, EFCE, COMM, and CERT. Perhaps surprisingly, Zhang et al. [101] demonstrated that computing optimal communication and certification equilibria is possible in time polynomial in the description of the game, estab- lishing a stark dichotomy between the other equilibrium concepts pancepts-namlly.. NFCCE, EFCE, and EFCCE-for which the corresponding problem is NP-hard [98]. In particular, for the latter notions intractability turns out to be driven by the imperfect recall of the mediator [101]. ]. Although imperfect recall induces computationally hard problem in general from the side of the mediator [19, 59], positive parameterized results have been documented recently in the literature [103].
Our work significantly departs from the framework of Zhang and Sandholm [100] in that we follow a learning-based approach, which has proven to particularly favorable avenue in practice; egg. we refer to [26, 16, 78, 77, 104] for such approaches in the context of computing EFCE. Further, frameworks are amenable to modern deep reinforcement beyond the tabular setting. learning-basee
learning methods (see [70, 71, 62, 69, 51, 76, 57, 13, 52, 73, 72, 86, 105, 42], and references therein). Most of those techniques have been developed to solve two-player zero-sum games, which provides another crucial motivation for main reduction. We demonstrate this experimentally in large games in Section 4. For multi-player games, Marris et al. [70] developed a scalable algorithm based on policy space response oracles (PSRO) [62] (a reep-reinforcemen-teeamae baased double-oracle technique) that converges to NFC(C)E, but does not find an optimal equilibrium.
Our research also relates to computational approaches to static auction and mechanism design through deep learning [27, 86). In particular, similarly to the present paper, Dütting et al. [27] study a Lagrangian relaxation of mechanism design problems. Our approach is significantly more general in that we cover both static and sequential auctions, as well as general extensive-fone games. Fur- ther, as a follow-up. Rahme al. [86] frame the Lagrangian relaxation however, is not zero-sum, thereby not enabling leveraging the tools known for solving zero-sum games. Finally, in a companion paper [102], we show how the framework developed in this work can be used to steer no-regret learners to optimal equilibria via nonnegative vanishing payments.
two-player game, which,
2 Preliminaries
We adopt the general framework of mediator-augmented games of Zhang and Sandholm [100] to define class of instances. At high level, medintor--uggmeneed game explicitly incorporates an additional player, the mediator, who can exchange messages with the players and issue action recommendations; different assumptions on the power of the mediator and the players' strategy sets induce different equilibrium concepts, as we clarify for completeness in Appendix A.
Definition 2.1. A mediator- augnentte. extensive-form game I' has the following components:
1. set of players, identified with the of integers [m]] (1,...,n). We will -i, for i E [[z]], to denote all players except i;
a directed tree of histories or nodes, whose root is denoted Ø. The edges of H are labeled with actions. The set of actions legal at h is denoted Aç. Leaf nodes of H are called terminal, and the of such leaves is denoted by Z:
NNttbbyy missing from this list is the normal-fore correlated equilibrium (NFCE), the complexity status of which (in extensive- form games) is long-standing open problem.
3

---

3. partition H Z = H
where H; is the set of nodes at which i takes an action, and and 0 denote chance and the mediator, respectively;
4. for each agent' E [n] U (0), a partition ΣN of i's decision nodes H; into information sets. Every node in a given information set must have the same set of legal actions, denoted by Ar; 5. for each agent a utility function u, Z + R; and
6. for each chance node E Hc. a fixed probability distribution cf- (h) over An.
To further clarify this definition, in Appendix A provide two concrete illustrative examples: single-item auction and a welfare-optimal correlated equilibrium in normal-form games.
At node h E H, the sequence (h) of an agent is the set of all information sets encountered by agent i, and the actions played at such information sets, along the Ø + path, excluding at itself. An agent has perfect recall if (h)
a;(h') for all h, h in the same infoset. We will use E, == {=)(=) : 2 E 3} to denote the set of all sequences of player that correspond to terminal nodes. We will assume that all players have perfect recall, though the mediator may not."
A pure strategy of agent is a choice of one action in A, for each information set I I. The sequence form of a pure strategy is the vector H; E {0. 2 given by 2;(o] = 1 if and only if i plays every action on the path from the root to sequence a Σ, We will use the shorthand 2 [z)]. A mixed strategy is a distribution over pure strategies, and the sequence form of a mixed strategy is the corresponding convex combination x; E [0, 1 We will use X; to denote the polytope of sequence-form mixed strategies of player i, and use E to denote the polytope of sequence-form mixed strategies of the mediator.
For fixed E E, we will say that (H, x) is an equilibrium of I if, for each player i, x; is best response to (H, x-i). that is, e u, (H, 2/j xr-) S uu u,(H, 3i, x-1). We do not require that the mediator's 's strategy μ is a best response. As such, the mediator has the power to commit to its
strategy. The goal in this paper will generally be reach an optimal (Stackelberg) equilibrium, that is, an equilibrium (H,, æ) maximizing the mediator utility uo (o(H,,)) We will use uo to denote the value for the mediator in an optimal equilibrium.
Revelation principle The revelation principle allows us, without loss of generality, to restrict our attention to equilibria where each player is playing some fixed pure strategy d, E X₁-
Definition 2.2. The game I' satisfies the revelation principle if there exists a direct pure strategy profile d = (di...., d,) for the players such that, for all strategy profiles (n, x) for all players including the mediator, there exists a mediator strategy pt and functions fi X; -> X, for each player i such that:
1. f.(.)) = Fg, and
2. uy(n', x d_i)= u, (, f((a)), .) for all xy e X,, and agents j E [n] (0).
U
The function fa in the definition of the revelation principle can be seen simulator for Player i: it tells Player that playing xf if other players play (Ju, d-i) would be equivalent, in terms of all the payoff's to all agents (including the mediator), playing f (ax() if other agents play (1s, x.). It follows immediately from the definition that if (n, x)) is an e-equilibrium, then so is (fl d) that is, every equilibrium is payoff-equivalent
direct equilibrium.
The revelation principle applies and covers many cases of interest in economics and game theory. For example, in (single-stage dynamic) mechanism design, the direct strategy d, of each player is to report all information truthfully, and the revelation principle guarantees that for all non-truthfiu mechanisms (H, x)) there exists truthful mechanism (μ', d) with the same utilities for all players. For correlated equilibrium, the direct strategy d, consists of obeying all (potentially randomized) recommendations that the mediator gives, and the revelation principle states that can, without loss of generality, consider only correlated equilibria where the signals given to the players are what actions they should play. In both these cases (and indeed in general for the notions consider in this
We will use agent to mean either a player or the mediator. 'Following the framework of Zhang and Sandholm [100]. allowing the mediator have imperfect recall will allow us to automatically capture optimal correlation.
"In mechanism design context, strategy for the mediator μ induces a mechanism; here we slightly abuse terminology by referring to (1,, d) also mechanism.

---

paper), it is therefore trivial to specify the direct strategies d without any computational overhead. Indeed, we will assume throughout the paper that the direct strategies d are given. Further examples and discussion of this definition can be found in Appendix A.
Although the revelation principle is very useful characterization of optimal equilibria, long as we are given d, all of the results in this paper actually apply regardless of whether the revelation principle is satisfied: when it fails, our algorithms will simply yield an optimal direct equilibrium which may not be an optimal equilibrium. Under the revelation principle, the problem of computing an optimal equilibrium can be expressed follows:
max
uo d) S.L. μEE
max (,, d_i) S ue(p,, d) Vi E [n]. m.E..
The objective un uo( d) can be expressed as a linear expression c μa, and us (H,, 24, d-i) u, u, d) can be expressed as a bilinear expression Ju A, Thus, the above program can be rewritten as
max MES
C F
S.L. max 1 A, S vi W [n].
(G)
TEEX;
Zhang and Sandholm [100] now proceed by taking the dual linear program of the inner maximiza- tion, which suffices to show that (G) can be solved using linear programming
Finally, although our main focus in this paper is games with discrete action sets, it is worth pointing out that some of our results readily apply to continuous games as well using, for example, the discretization approach of Kroer and Sandholm [60].
3 Lagrangian relaxations and reduction to zero-sum game
Our approach in this paper relies on I Lagrangian relaxations of the linear program (G). In particular, in this section we introduce two different Lagrangian relaxations. The first one (Section 3.1) reduces computing an optimal equilibrium to solving a single zero-sum game. We find that this approach performs exceptionally well in benchmark extensive-form games the tabular regime, but it may struggle when used in conjunction with deep RL solvers since it increases significantly the range of the rewards. This shortcoming addressed by our second method, introduced in Section 3.2, which instead solves a sequence of suitable zero-sum games.
3.1 "Direct" Lagrangian
Directly taking Lagrangian relaxation of the LP (G) gives the following saddle-poin problem:
max min MEE
c 1
c p A
(L1)
XER20
We first point out that the above saddle-point optimization problem admits a solution (μ", xx, X²): Proposition 3.1. The problem (LI) admits a finite saddle-point solution (μ", x"" ,*), Moreover, for all fixed X X", the problems (Ll) and (G) have the same value and same set of optimal solutions.
The proof is in Appendix C. We will call the smallest possible X* the critical Lagrange multiplier. Proposition 3.2. For any fixed value X, the saddle-point problem (L.1) can be expressed as zero- sum extensive-form game.
Proof. Consider the zero-sum extensive-form game I between two players, the mediator and the deviator, with the following structure:
Nature picks, with uniform probability, whether or not there a deviator. If nature picks that there should be a deviator, then nature samples, also uniformly, deviator E [r]]] Nature's actions are revealed to the deviator, but kept private from the mediator.
'Computing optimal equilibria can be phrased as a linear program, and so in principle Adler's reduction could also lead to an equivalent zero-sum game [2]. However, that reduction does not yield an extensive-form zero-sum game, which is crucial for our purposes; see Section 3.
5

---

2. The game I is played. All players, except if nature picked deviator, are constrained to according to d, The deviator plays on behalf of Player
3. Upon reaching terminal node there are two cases. If nature picked deviator i, the utility is 2An us (2). If nature did not pick a deviator, the utility (2) + 22 Σi= (2)..
The mediator's expected utility in this game is
up (n, d) A a
Σ (,, d-i) us uz d)).
This characterization enables us exploit technology used for extensive-foni zero-sum game solv- ing to compute optimal equilibria for an entire hicrarchy of equilibrium concepts (Appendix A).
We will next focus on the computational aspects of solving the induced saddle-point problem (L1) using regret minimization techniques. All of the omitted proofs are deferred Appendices and E.
The first challenge that arises in the solution of (L1) is that the domain of the minimizing player is unbounded-the Lagrange multiplier is allowed take any nonnegative value. Nevertheless, we show in Theorem D.I that it suffices to set the Lagrange multiplier to a fixed value (that may depend on the time horizon): appropriately setting that value will allow to trade off between the equilib- rium gap and the optimality gap. We combine this theorem with standard regret minimizers (such as variants of CFR employed in Section 4.1) guarantee fast convergence optimal equilibria.
Corollary 3.3. There exist regret minimization algorithms such that when employed in the saddle- point problem (LI), the average strategy of the mediator ç == + Σ (& converges the set of optimal equilibria at a rate of 1/4, Moreover, the per-iteration complexity is polynomial for com- munication and certification equilibria (under the nested range condition [100]), while for NFCCE, EFCCE and CE, implementing each iteration admits a sxted-parameter tractable algorithm.
Furthermore, we leverage the technique of optimism, pioneered by Chiang al. [18), Rakhlin and Sridharan [87], Syrgkanis et al. [94], to obtain a faster rate of convergence.
Corollary 3.4 (Improved rates via optimism). There exist regret minimization algorithums that guar- antee that the average strategy of the mediator fa == + Ei= 10( converges to the set of optimal equilibria at a rate 1//22 The per-iteration complexity is analogous to Corollary 3.3.
While this rate is slower than the (near) 7-1 rates known for converging to some of those equilib- ria [24, 34, 85, 3). Corollaries 3.3 and 3.4 additionally guarantee convergence optimal equilibria; improving the 1 rate of Corollary 3.4 is an interesting direction for future research.
Last-iterate convergence The convergence results we have stated thus far apply for the average strategy of the mediator-a typical feature of traditional guarantees in the no-regret framework. Nevertheless, an important advantage of our mediator-augmennted formulation is that we can also guarantee last-iterate convergence to optimal equilibria in general games. Indeed, this follows readily from our reduction to two- two-player zero-sum games, leading to the following guarantee.
Theorem 3.5 (Last-iterate convergence to optimal equilibria in general games). There exist algo- rithms that guarantee that the last strategy of the mediator p!T) converges to the set of optimal equilibria at a rate of 1/4, The per-iteration complexity is analogous to Corollaries 3.3 and 3.4.
As such, our medietor-augmmnnte paradigm bypasses known hardness results the traditional learn- ing paradigm (Proposition D.2) since iterate convergence is no longer tied to Nash equilibria.
3.2 Thresholding and binary search
significant weakness of the above Lagrangian is that the multiplier X can be large. This means that, in practice, the zero-sum game that needs to be solved to compute an optimal equilibrium could have large reward range. While this is not a problem for most tabular methods that can achieve high precision, more scalable methods based on reinforcement learning tend to be unable to solve games the required precision. this section, we will introduce another Lagrangian- based method for solving the program (G) that will not require solving games with large reward ranges.

---

Specifically, let T E IR be fixed threshold value, and consider the bilinear maddle-point problem
mAX MEE
min ΛEA"T1, "+1 [
Ao(c -)-
Σ Xi A,
(1.2)
where A := {} E R 1= is the probability simplex on lo items. This Lagrangian was also stated but not analyzed- by Farina et al. [30], in the special case of correlated equilibrium concepts (NFCCE, EFCCE, EFCE). Compared to that paper, ours contains more complete analysis, and is general to more notions equilibrium.
Like (LI), this Lagrangian is also zero-sum game, but unlike (LI), the reward range in this La- grangian bounded by an absolute constant:
Proposition 3.6. Let I' be a mmediator-augmmetter game in which the reward for all agents is bounded in [0, 1]. For any fixed e [0, 1], the saddle-poing problem (L2) can be expressed as zero-sum extensive extensive-form game whose reward is bounded in 2..
Proof. Consider the zero-sum extensive-form game f' between players, the mediator and the deviator, with the following structure:
1. The deviator picks an index i [r]] U (0).
2. If A 0, nature picks whether Player i can deviate, uniformly at random.
3. The game played. All players, except if & 0 and nature selected that can deviate, constrained to play according to d,. The deviator plays on behalf of Player i. 4. Upon reaching terminal node z, there are three cases. nature picked uo(2) T. Otherwise, if nature picked that Player i of 0 can deviate, the utility is 10--2u (z). Finally, nature picked that Player of cannot deviate, the utility (2)(2).
0, the utility is
The mediator's expected utility in this game is exactly
(p (e. d)
Σ> x, d up( d)]
where À E g++1 I is the deviator's 's mixed strategy in the first step.
The above observations suggest a binary-search-like algorithm for computing optimal equilibria: the pseudocode given Algorithm 1. The algorithm solves O(log(1/e) zero-sum games, each to precision E. Let e- be the optimal value of (G). If T < v", the value of (L2) is O, and we will therefore never branch low, in turn implying that o" and f 2 0- As result, have proven: Theorem 3.7. Algorithm returns e-approximate equilibrium μ whose value the mediator is at least x" 2e. If the underlying game solver used to solve (1.2) runs in time f(T,e), then Algorithm runs time O( log(1/e)).
ALGORITHM Pseudocode for binary search-baser algorithm
input: game with mediator reward range [0, 1), target precision >
2 + 0, u t-
while eo
+ (e+
run an algorithm to solve game (L2) until either
(1) it finds f achieving value 2 - in (L2), or
(2) it proves that the value of (1.2) is
if cuse (1) happened then & <-
else u f- T
return the last μ found
The differences between the two Lagrangian formulations can be summarized as follows:
7

---

1. Using (L1) requires only single game solve, whereas using (L2) requires ( (/E)) game solves.
2. Using (I.2) requires only an O(e) -aproxipt game solver to guarantee value v* - 6, whereas using (1.1) would require an -approxiapo game solver to guarantee the same, even assuming that the critical Lagrange multiplier X in (L11 1) is known.
Which is preferred will therefore depend on the application. In practice, if the games too large be solved using tabular methods, one can use approximate game solvers based on deep reinforcement learning. In this setting, since reinforcement learning tends be unable achieve the high precision required to use (LI), using (L2) should generally be preferred. In Section 4, we back up these claims with concrete experiments.
4 Experimental evaluation
In this section, we demonstrate the practical scalability and flexibility of our approach, both for computing optimal equilibria in extensive-form games, and for designing optimal mechanisms in large-scale sequential auction design problems.
4.1 Optimal equilibria extensive-form games
We first extensively evaluate the empirical performance of our two-player zero-sum reduction (Sec- tion 3.1) for computing seven equilíbrium solution concepts across 23 game instances; the results using the method of Section 3.2 are slightly inferior, and are included in Appendix H. The game instances we use are described in detail in Appendix F, and belong to following eight different classes of established parametric benchmark games, each identified with alphabetical mnemonic: Battleship [30], Liar's dice [68], GL Goofspiel [88]. K Kuhn poker [61], Ledue poker [93], RS ridesharing game [101], Sheriff [30]. TP- double dummy bridge game [101].
For each of the 23 games, we compare the runtime required by the linear programming method of Zhang and Sandholm [100] ("LP") and the runtime required by our learning dynamics in Section 3.1 ('Ours') for computing e-optimal equilibrium points.
Table shows experimental results for the case in which the threshold & is set to be 1% of the payoff range of the game, and the objective function set to be the maximum social welfare (sum of player utilities) for general-sum games, and the utility of Player 1 in zero-sum games. Each row corresponds a game, whose identifier begins with the alphabetical mnemonic of the game class, and whose size in terms of number of nodes in the game trees is reported in the second column. The remaining columns compare, for each solution concept, the runtimes necessary to approximate the optimum equilibrium point according to that solution concept. Due to space constraints, only five out of the seven solution concepts (namely, NFCCE, EFCCE, EFCE, COMM, and CERT) are shown; data for the two remaining concepts (NFCCERT and CCERT) is given in Appendix G.
We remark that in Table the column 'Ours' reports the minimum across the runtime across the different hyperparameters tried for the learning dynamics. Furthermore, for each run of the algo- rithms, the timeout was set one hour. More details about the experimental setup are available in Appendix G, together with finer breakdowns of the runtimes.
We observe that our learning-based approach is faster-often by more than order of magnitude and more scalable than the linear program. Our additional experiments with different objective functions and values of e, available in Appendix G, confirm the finding. This shows the promise of our computational approach, and reinforces the conclusion that learning dynamics are by far the most scalable technique available today to compute equilibrium points in large games.
4.2 Exact sequential auction design
Next, we use our approach to derive the optimal mechanism for a sequential auction design problem. In particular, we consider two-round auction with two bidders, each starting with budget of 1. The valuation for each item for each bidder is sampled uniformly at random from the set (0, 1/4, 1/2, 1/. We consider a mediator-augmentt outcome (allocation and payment for each player) given their reports (bids). We use CFR+ [95] as learning algorithm and fixed Lagrange multiplier À = 25 to compute the optimal communication
game in which the principal chooses an
8

---

Table I: Experimental comparison between our bearning-based approach ('Ours', Section 3.1) and the linear- proaarrrroraming--aa. -based method ('LP") of Zhang and Sandholm [100]. Within each pair of cells corresponding to 'LP" vs "Ours," the faster algorithm is shaded blue while the hue of the slower algorithm depends on how much slower it If both algorithms timed out, they are both shaded gray.
NFCCE
EFCCE
EFCE
COMM
CERT LP
Game
Nodes
LP
Ours
LP
Ours
LP
Ours
LP
Ours
Ours
B2222
1573
0.00s
0.01s
0.00c
2,00s
1.49
0.00s
0.02s
B2322
23839
0.00s
0.01s
3.00s
0.69s
9.00s
1.60s
limcout
4m 41s
2.00s
1.24s
B2323
254239
6.00s
0.33s
1m 21s
14.23s
3m 40s
44,87
limcout
tmmoout
37 37.00s
40.45%
82324
1420 639
38.00s
2.73%
timeout
3m Is
timeout
10m 48s
timeout
timcout
timeour
6m 14s
D32
1017
0.00s
0.01s
0.00s
0.02s
12.00.
0.06s
0.00s
0.01s
D33
27 622
2m 17s
12.93s
timoout
Im 46s
timcout
timcout
timcout
4m 37s
4.00s
3.14s
GL.3
7735
0.00s
0.01s
1.00s
0.024
0.00s
0.01s
timenut
7.72s
0.00s
0.02s
K35
1501
49.00s
0.76s
46 00s
0.67s
57.00s
0.55s
1.00s
0.03s
0.00s
0.01s
L3132
8917
26.00s
0.59%
8m 43x
5.13s
8m 18s
6.10c
8.00s
3,468
1.00s
0.10s
L3133
12 688
38. 00.
0.94s
20m 26s
8.88s
21m 25s
6.84s
12.00s
3.40s
1.00s
0.22s
L3151
19981
timeout
15.12s
timoout
timcout
timoout
uimout
limouut
16.73s
2.00s
0.21s
L3223
650
4.00s
0.44s
1m 10s
2.94s
2m 2x
5.52s
19.00s
18.19
1.00s
0.61s
L3523
299 005
timeout
7s
timeout
timeout
timeout
timcout
timeout
timenut
timeout
$2122
705
0.00s
0.00s
0.00s
0.01s
0.00s
0.02s
2,00s
0.35s
0.00s
0.02s
$2123
42299
0.00s
0.01s
1.00s
0.06s
1.00s
0,15s
Im 33s
59,63s
1.00s
0.15%
$2133
9648
1.00s
0.02s
3.00s
0.1
3.00s
0.49s
timeout
2m 1s
2.00s
0.92s
712552
7.43x
timeout
22.0
timenut
timeout
timeout
timeout
$2264
1 303
3m 43s
11.74s
tmoout
39.23s
timcout
timcout
timcout
timoout
timcout
timoou
TP8
930737
mm 38s
7.44s
timeout
13.76s
timeout
13.46s
timeout
timcout
timeour
26. 26.70s
RS212
598
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
2,00s
0.01s
0.00s
0.00s
RS222
734
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
3,00s
0.018
0.00s
0.00s
RS213
6274
timenut
14.68s
timeout
15.54s
timeaut
23.374
6m 25x
8.74s
0.00s
0.02s
RS223
6238
timcout
timcout
timoout
timoout
timcout
timcout
8m 54s
4.00s
1.00s
0.01s
equilibrium that corresponds the optimal mechanism. We terminated the learning procedure after 10000 iterations, at a duality gap for (LI) of approximately 4.2 x 10-4, Figure 1 (left) summarizes our results. On the y-axis we show how exploitable (that is, how preentve-iicoompaible each of the considered mechanisms are, confirming that for this type of sequential settings, second-price auctions (SP) with or without reserve price, as well as the first-price auction (FP), are typically prrentve-iicomppatin
On the x-axis, we report the hypothetical revenue that the mechanism would extract assuming truthful bidding. Our mechanism is provably eeventive-ooppatbee and extracts a larger revenue than all considered second-pric mechanisms. It also would extract less revenue than the hypothetical first-price auction if the bidders behaved truthfully (of course, real bidders would not behave honestly in the first-price auction but rather would shade their bids downward, so the shown revenue benchmark Figure is actually not achievable). Intriguingly, we observed that 8% of the time the mechanism gives an item away for free. Despite appearing irrational, this behavior can incentivize bidders to use their budget earlier in order to encourage competitive bidding, and has been independently discovered in manual mechanism design recently [25, 75].
4.3 Scalable sequential auction design via deep reinforcement learning
We also combine our framework with deep-learning-basee -ased algorithms for scalable equilibrium com- putation in two-player zero-sum games to compute optimal mechanisms in two sequential auction settings. To compute an optimal mechanism using our framework, we use the PSRO algorithm [63], a deep reinforcement learning method based on the double oracle algorithm that has empirically scaled to large games such as Starcraft [96] and Stratego [72], as the game solver in Algorithm 1. To train the best responses, we use proximal policy optimization (PPO) [90].
We also tested PSRO on the Lagrangian (LI), but this proved to be incompatible with deep learning due to the large reward range induced by the multiplier X.

---

Small sequential auction (Section 4.2)
Large sequential auction (Section 4.3)
0.6
0.15
Exploitabilit
0.4
FP
Exploitability
FP
0.1
0.2
SP
R1/4 Ray. R
Ours (optimal)
5-10-2
R1/10
Rays
R1/s
Ra/ao Ours
SP
0
0.4
0.6
0.8
1.2
1.4
0.4
0.6
0.8
1.2
1.4
Revenue (if bidders were truthful)
Revenue (if bidders truthful)
FP: First-price auction
SP: Second-price auction
Rg: Second-price action with reserve price
Figure 1: Exploitability is measured by summing the best response for both bidders the mechanism. Zero exploitability corresponds to incentive compatibility. In sequential auction with budgets, our method is able to achieve higher revenue than second-price auctions and better incentive compatibility than a first-price auction.
First, verify that the deep learning method is effective, replicate the results of the tabular experiments in Section 4.2. We find that PSRO achieves the same best response values and optimal equilibrium value computed by the tabular experiment, up small error. These results give us confidence that our method is correct.
Second, demonstrate scalability, tion environment that would be too big to solve with tabular methods. In this environment, there are four rounds, and in each round the valuation of each player is sampled uniformly from The starting budget of each player is, again, 1. We find that, like the 1.1 (right-side of Figure 1). This revenue
run deep learning-based algorithm on a larger
(0, 0.1,0.10.0 0.2, 0.3, smaller setting. the optimal revenue of the mediator exceeds the revenue of every second-price auction (none of which have revenue greater than 1)."
Conclusions
We proposed new paradigm of learning in games. applies to mechanism design, information design, and solution concepts in multi-player extensive-form games such as correlated, communi- cation, and certification equilibria. Leveraging a Lagrangian relaxation, our paradigm reduces problem of computing optimal equilibria to determining minimax equilibria in zero-sum extensive- form games. We also demonstrated the scalability of our approach for computing optimal equilibria by attaining stateoof-hhe-at performance in benchmark tabular games, and by solving sequential auction design problem using deep reinforcement learning.
*We are inherently limited in this setting by the inexactness of best responses based on deep reinforcement learning: such, it is possible that these values are not exact. However, because of the success of above tabular experiment replications, we helieve that our results should be reasonably accurate.
10

---

Acknowledgements
We are grateful to the anonymous NeurIPS reviewers for many helpful comments that helped im- prove the presentation of this paper. Tuomas Sandholm's 's work is supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-28777 National Science Foundation grants RI-2312342 and RI-1901403, ARO award W911NF220026, and NIH award A240108S001. McAleer is funded by NSF grant #2127309 to the Computing Research Association for the CIFellows 2021 Project. The work of Prof. Gatti's research group is funded by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGennrationnFU program within the PNRR-PE-AI scheme (M4C2, In- vestment 1.3, Line Artificial Intelligence). Conitzer thanks the Cooperative Al Foundation and Polaris Ventures (formerly the Center for Emerging Risk Research) for funding the Foundations of Cooperative AI Lab (FOCAL). Andy Haupt was supported by Effective Giving, We thank Dylan Hadfield-Menell for helpful conversations.
References
[1] Kenshi Abe, Mitsuki Sakamoto, and Atsushi Iwasaki. Mutation-driven follow the regular- ized leader for last-iterate convergence in zero-sum games. In Conference on Uncertainty in Artificial Intelligence (UAI), volume 180, pages 1-10. PMLR, 2022.
[2] llan Adler. The equivalence of linear programs and zero-sum games. Int. J. Game Theory, 42 (1):165-17, 2013.
[3] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Symposium on Theory of Computing (STOC), pages 736-749. ACM, 2021.
[4] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last- iterate convergence beyond zero-sum games. In International Conference Machine Learn- ing (ICML), volume 162 of Proceedings of Machine Learning Research, pages 536-581. PMLR, 2022.
[5] Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathe- matical Economics, 1:67-96, 1974.
[6] Waiss Azizian, Franck Tutzeler, Jérôme Malick, and Panayotis Mertikopoulos. The last-iterate convergence rate of optimistic mirror descent stochastic variational inequalities. Con- ference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Re- search, pages 326-358. PMLR, 2021.
[7] Yakov Babichenko and Aviad Rubinstein. Communication complexity of approximate nash equilibria. Games and Economic Behavior, 134:376-398, 2022.
[8] Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning stackelberg equilibria in general-sum games. In Conference Neural Information Processing Systems (NeurIPS), pages 25799-25811 2021.
Siddharth Barman and Katrina Ligett. Finding any nontrivial coarse correlated equilibrium is hard. In ACM Conference on Economics and Computation (EC), pages 815-816. ACM, 2015.
[10] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218), January 2015.
[11] Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-422 2018.
[12] Noam Brown and Tuomas Sandholm. Solving imperfecttinformatioo games via discounted regret minimization. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
11

---

[13] Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforce- ment learning and search for puperfect-information games. In Conference on Neural Infor- mution Processing Systems (NeurIPS), 2020.
[14] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[15] Modibo K. Camara, Jason D. Hartline, and Aleck C. Johnsen. Mechanisms for a no-regret agent: Beyond the common prior. In Annual Symposium on Foundations of Computer Science (FOCS), pages 259-270. IEEE, 2020.
[16] Andrea Celli, Alberto Marchesi, Gabricle Farina, and Nicola Gatti. No-regret learning dy- namics for extensive-form correlated equilibrium. Conference Neural Information Pro- cessing Systems (NeurIPS), 33:7722-7732, 2020.
[17] Xi Chen, Xiaotic Deng, and Shang- Hua Teng. Settling the complexity of computing two- player Nash equilibria. Journal of the ACM, 2009.
[18] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory (COLT), pages 6-1, 2012.
[19] Francis Chu and Joseph Halpern. On the NP-completeness of finding an optimal strategy in games with common payoffs. International Journal of Game Theory, 2001.
[20] Vincent Conitzer and Dmytro Korzhyk. Commitment to correlated strategies. In AAAI Con- ference Artificial Intelligence (AAAT). AAAI Press, 2011.
[21] Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-644 2008. Early version in ICCAI-03.
[22] Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In 10th Innovations in Theoretical Computer Sci- ence Conference, ITCS 2019, volume 124 of LIPIcs, pages 27:1-27:18. Schloss Dagstuhl Leibniz-Zentrrum für Informatik, 2019.
[23] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing nash equilibrium. SIAM Journal on Computing, 39(1), 2009.
[24] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Conference on Neural Information Processing Systems (NeurlPS), pages 77604-27616, 2021.
[25] Yuan Deng, Vahab Mirrokni, and Song Zuo. Non-clairvoyant dynamic mechanism design with budget constraints and beyond. Available at SSRN 3383231, 2019.
[26] Miroslav Dudík and Geoffrey Gordon. sampling sampling-based based approach computing equilibria in succinct extensive-form games. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 151-160, 2009.
[27] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravin- dranath. Optimal auctions through deep learning. In International Conference on Machine Learning, pages 1706-1715. PMLR, 2019.
[28] Gabriele Farina and Tuomas Sandholm. Polynomial time computation of optimal correlated equilibria in two-player extensive-form games with public chance moves and beyond. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[29] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret circuits: Composability of regret minimizers. In International Conference on Machine Learning, pages 1863-1872,
2019.
12

---

[30] Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive- form games: Saddle-point formulation and benchmarks. In Conference on Neural Informa- tion Processing Systems (NeurIPS), 2019.
[31] Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm. Coarse correlation in extensive- form games. AAAI Conference on Artificial Intelligence, 2020.
[32] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential decision spaces: Fast convergence rates for nash, correlated, and team equilibria. In ACM Conference on Economics and Computation (EC), page 432, 2021.
[33] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predic- tive Blackwell approachability: Connecting regret matching and mirror descent. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
[34] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung- Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[35] Tanner Fiez, Benjamin Chasnov, and Lillian J. Ratiff. Convergence of learning dynamics in stackelberg games. CoRR, abs/1906.01217, 2019.
[36] Francoise Forges. An approach to communication equilibria. Econometrica: Journal of the Econometric Society, pages 1385- 1986.
[37] Françoise Forges and Frédéric Koessler. Communication equilibria with partially verifiable types. Journal of Mathematical Economics, 41()):993-811, 2005.
[38] Yoav Freund and Robert Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behuvior, 29:79-103, 1999.
[39] Drew Fudenberg and David Levine. The Theory of Learning in Games. MIT Press, 1998.
[40] Kaito Fujii. Bayes correlated equilibria and no-regret dynamics. CoRR, abs/2304.05005, 2023.
[41] Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considera- tions. Games and Economic Behavior, 1:80-93, 1989.
[42] Denizalp Goktas, David C. Parkes, Ian Gemp, Luke Marris, Georgios Piliouras, Romuald Elie, Guy Lever, and Andrea Tacchetti. Generative adversarial equilibrium solvers. CoRR, abs/2302.06607, 2023.
[43] Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[44] Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradi- ent:
General analysis and improved rates. In International Conference Artificial Intelli- gence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pages 7865-7901. PMLR, 2022.
[45] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last- iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 Proceedings of Machine Learning Research, pages 366-402. PMLR, 2022.
[46] Green and J-J Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427-438, 1977.
[47] Amy Greenwald and Keith Hall. Correlated Q-learning. In International Conference Machine Learning (ICML), pages 242-249, Washington, DC, USA, 2003.
[48] Sergiu Hart and Yishay Mansour. How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior, (9(1):107-11 2010.
13

---

[49] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equi- librium. Econometrica, 68:1 122-1100, 2000.
[50] Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93:1830-188 1808-006666,,0011111111111111161 2003.
[51] Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfectiinformation games. arXiv preprint arXiv:1603.01121, 2016.
[52] Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-fore games. In International Conference on Machine Learning (ICML), volume 37 of JMLR Work- shop and Conference Proceedings, pages 805-813. JMr.. 2015.
[53] Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis. Exponential lower bounds for finding brouwer fix points. J. Complex., 5(4):379 416, 1989.
[54] Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop Internet and Network Economics, pages 506-513. Springer, 2008.
[55] Dmitry Ivanov, Ilya Zisman, and Kirill Chernyshev. Mediated multi-agent reinforcement learning. In Proceedings of the 2023 International Conference Autonomous Agents and Multiagent Systems, pages 49-57, 2023.
[56] Albert Jiang and Kevin Leyton- BBoonn Polynomial-time computation of exact correlated equilibrium in compact games. In ACM Conference on Electronic Commerce (EC), 2011.
[57] Peter H Jin, Sergey Levine, and Kurt Keutzer. Regret minimization for partially observable deep reinforcement learning. In International Conference on Machine Learning (ICML), 2018.
[58] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 10166):2500-211,, 2011.
[59] Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528-555 October 1992.
[60] Christian Kroer and Tuomas Sandholm. Discretization of continuous action spaces in extensive-form games. In Autonomous Agents and Multi-Agent Systems, pages 47-56. ACM, 2015.
[61] H. W. Kuhn. simplified two-person poker. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume of Annals of Mathematics Studies, 24, pages 97-103. Princeton University Press, Princeton, New Jersey, 1950.
[62] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game- theeoretc approach to multiagent reinforcement learning. In Conference on Neural Information Processing Systems (NeurIPS), pages 4100-4203, 2017.
[63] Marc Lanctot, Vinicius Zambaldi. Audrunas Gruslys, Angeliki Lazaridou. Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game- theoreth approach to multiagent reinforeement learning. Advances in neural information processing systems, 30, 2017.
[64] Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive- form games. In Conference on Neural Information Processing Systems (NeurIPS), pages 14293-14305, 2021.
[65] Joshua Letchford and Vincent Conitzer. Computing optimal strategies to commit to in extensive-form games. In ACM Conference on Electronic Commerce (EC), 2010.
[66] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory, Second International Sym- posium, SAGT 2009, volume 5814 of Lecture Notes in Computer Science, pages 250-262. Springer, 2009.
14

---

[67] Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael I. Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In International Conference on Machine Learning (ICML), volume 1 19 of Proceedings of Machine Learning Research, pages 6161-6171. PMLR, 2020.
[68] Viliam Lisy, Mare Lanctot, and Michael H Bowling. Online monte carlo counterfactual regret minimization for search in imperfect information games. In Autonomous Agents and Multi- Agent Systems, 2015.
[69] Siqi Liu, Marc Lanctot, Luke Marris, and Nicolas Heess. Simplex neural population learning: Any-mixture bayes-optimality in symmetric zero-sum games. In International Conference on Machine Learning (ICMIJ, volume 162 of Proceedings of Machine Learning Research, pages 13793-13806, PMLR, 2022.
[70] Luke Marris, Paul Muller, Marc Lanctot, Karl Tuyls, and Thore Graepel. Multi-agent train- ing beyond zero-sum with correlated equilibrium meta-solvers. In Proceedings the 38th International Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 7480-7491. PMLR, 2021.
[71] Luke Marris, Ian Gemp, Thomas Anthony, Andrea Tacchetti, Siqi Liu, and Karl Tuyls. Tur- bocharging solution concepts: Solving NEs, CEs and CCEs with neural equilibrium solvers. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[72] Stephen McAleer, John B. Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable approach for finding approximate nash equilibria in large games. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[73] Stephen McAleer, John B. Lanier, Kevin A. Wang, Pierre Baldi, and Roy Fox. XDO: A double oracle algorithm for extensive-form games. In Conference on Neural Information Processing Systems (NeurIPS), pages 23128 22-23139, 2021.
[74] Jason Milionis, Christos Papadimitriou, Georgios Piliouras, and Kelly Spendlove. An impos- sibility theorem in game dynamics. Proceedings of the National Academy of Sciences, 120 (41), 2023.
[75] Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, and Song Zuo. Non-clairvoyant dy- namic mechanism design. Econometrica, 88(5):1939 199391963,, 2020.
[76] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence heads-up no-limit poker. Science, May 2017.
[77] Dustin Morrill, Ryan D'Orazio, Mare Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. In International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 7818-7828. PMLR, 2021.
[78] Dustin Morrill, Ryan D'Orazio, Reca Sarfati, Mare Lanctot, James R Wright, Amy Green- wald, and Michael Bowling. Hindsight and sequential rationality of correlated play. In AAAI Conference on Artificial Intelligence (AAAI), volume 35, pages 5584-5594, 2021.
[79] H. Moulin and J.-P. Vial. Strategically zero-sum games: The class games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4); 201-221, 1978.
[80] Roger Myerson. Optimal auction design. Mathematics of Operation Research, 6:58-73, 1981.
[81] Roger B Myerson. Econometric Society, pages 323-358, 1986.
Multistage games with communication. Econometrica: Journal of the
[82] Christos Papadimitriou. Algorithms, games and the Internet. In Symposium on Theory of Computing (STOC), pages 749-753, 2001.
15

---

[83] Christos Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 82-91. SIAM, 2005.
[84] Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In AAAI Conference on Artificial Intelligence (AAAI), pages 2149-2156. AAAI Press, 2019.
[85] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. In Conference Neural Information Processing Systems (NeurIPS), 2022.
[86] Jad Rahme, Samy Jelassi, and Matthew Weinberg. Auction learning as two-player game. In 9th International Conference Learning Representations, ICLR 2021. OpenReview.net, 2021.
[87] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Conference on Neural Information Processing Systems (NeurIPS), pages 3066- 3074, 2013.
[88] Sheldon M Ross. Goofspicl game pure strategy. Journal of Applied Probability, (3):621-625, 1971.
[89] Tim Roughgarden and Omri Weinstein. On the communication complexity of approximate fixed points. In Annual Symposium Foundations of Computer Science (FOCS), pages 229-238, 2016.
[90] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: fttv:/700 777.0663777 2017.
[91] Shai Shalev-Shware Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2), 2012.
[92] Maurice Sion. On general minimax theorems. Pacific J. Math., 8(4):171-176, 1958.
[93] Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Conference Uncertainty in Artificial Intelligence (UAT), July 2005.
[94] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Conference on Neural Information Processing Systems (NeurfPS), pages 2989-2997, 2015.
[95] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling, Solving heads-up limit Texas hold'en em.. In International Joint Conference on Artificial Intelligence (IJCAI), 2015.
[96] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grand- master level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782): 350-354,70 2019.
[97] John von Neumann. Zur Theorie der Gesellschafftssieee. Mathematische Annalen, 100:295- 320, 1928.
[98] Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Defini- tion and computational complexity. Mathematics of Operations Research, 1002- 2008.
[99] Chen- Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate con- vergence constrained saddle-poin optimization. In 9th International Conference on Learn- ing Representations, ICLR 2021. OpenReview.net, 2021.
16

---

[100] Brian Hu Zhang and Tuomas Sandholm. Polynomial-tne time optimal equilibria with me- diator in extensive-form games. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[101] Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Optimal correlated equilibria general-sum extensive-form games: Fixed- -arammeeretter algorithms, hardness, and two-sided Dolumn-generateen In ACM Conference Economics and Computation (EC), pages 1119-1120. ACM, 2022.
[102] Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Mar- cus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners to optimal equilibria. CoRR, abs/2306.05221, 2023.
[103] Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief DAG: generalizing the sequence form to team games for fast computation of correlated team max-min equilibria via regret minimization. In International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 40996-41018 8. PMLR, 2023.
[104] Hugh Zhang. A simple adaptive procedure converging forgiving correlated equilibria. CoRR, abs/2207.06545. 2022.
[105] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C. Parkes, and Richard Socher. The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8(18)xeabk2607, 2022.
[106] Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret min- imization in games with incomplete information. In Conference on Neural Information Pro- cessing Systems (NeurIPS), 2007.
17

---

A Illustrative examples of mediator-augmeetted games
this section, we further clarify the framework of mediator- aagiatttr--ummeeeedddd games we operate in through couple of examples. We begin by noting that the family of solution concepts for extensive-form games captured by this framework includes, but is not limited to, the following:
normal-form coarse correlated equilibrium' [5. 79].
extensive-form coarse correlated equilibrium' [31],
extensive-form correlated equilibrium' [98],
certification (under the nested range condition [46, 37J) [37, 100],
communication equilibrium [81, 36).
mechanism design for sequential settings, and
information design/Bayesian persuasion for sequential settings [58].
We refer the interested reader Zhang and Sandholm [100, Appendix G] for additional interesting concepts not mentioned above.
Example A.I (Single-item auction). Consider the single-good monopolist problem studied by My- [n|] has a valuation v; E V,- Agent valuations may be correlated, and distributed according to FF A(V), where V == V V2 ... Vn. The mechanism lects a (potentially random) payment p and winner i' E [n]] The agents' utilities are quasilinear: (i("", pp; v,)) U - p if 1* and 0 otherwise. The seller wishes to maximize expected payment from the agents. This has the following timeline.
erson [80]. Each player
1. The mechanism commits to (potentially randomized) mapping = (V1...., H (i".
2. Nature samples valuations (U1,..., vn.) F.
3. Each player E [n|] privately observes her valuation v;, and then decides what valuation uy to report to the mediator.
4. The winner and payment are selected according to o(v').
5. Player i' gets utility U;- - p. while all other players get 0. The mediator obtains utility
Up
In this extensive-form game, the primitives from our paper are:
a (pure) mediator strategy μ E is mapping from valuation reports v' = (of, v/) to outcomes (i',p) ph)t that is, mediator strategies are mechanisms, and mixed strategies are randomized mechanisms;
a (pure) player strategy æ, E X2 for each player i e [n] is a mapping from V to Vi indicating what valuation Player reports function of its valuation 8/ E V;;
the direct (in mechanism design language, truthful) strategy d; for each player is the identity map from V; to V.. (Hence, in particular, d, E X; is a strategy of Player i, so makes sense, for example, to call (μ,, d) (μ, d di,..., d,)) a strategy profile.)
In particular, if profile (n, di...., d,) is such that each player is playing a best response, then μ a truthful mechanism.
The conversion in Proposition 3.2 creates a zero-sum extensive-form game î. whose equilibria for the mediator (for sufficiently large X) are precisely the evvenue-mxximing mechanisms. f has the following timeline:
'For notions of correlated equilibrium in extensive-form games, the mediator must have imperfect recall, therefore the representation of the mediator's 's decision space may not polynomial. This is unavoidable, since the problem of computing an optimal equilibrium under these notions is NP-hard in general [98]. In this paper, we will largely ignore these concerns and assume that the representation of the mixed strategy set E is part of the input.
18

---

1. Nature picks, with equal probability, whether there is deviator. If nature picks that there is a deviator, nature also selects which player E [n]] is represented by the deviator.
2. Nature samples valuations e = (M1,..., Un) F.
3. If nature selected that there is a deviator, the deviator observes and its valuation 8; Vi, and selects deviation vy V4.
4. The mediator observes (u/, v-s) (i.e., all other players assumed to have reported hon- estly) and selects a winner 8" and payment p. as before.
5. There are now two cases. nature selected at the root that there was to be a deviator, the utility for the mediator is 22 P; v.). If nature selected at the root that there be no deviator, the utility for the mediator is 2p+ 2A Ei=1 u,(i", a 2p+ 2A - -p).
As our second example, we show how the problem of computing a social- sitiaaawllaar--maxiiiiiinnng cor- related equilbrium (CE) in a normal-form game can be captured using mediator- augmented games. Example A.2 (Social welfare-optimmll correlated equilibria in normal-form games). Let A, be the action set for each player i E [n] in the game, and let utility functions u; A - R. where A = A X A2 x X An. The social welfare is the function Up A + given by uo uo In the traditional formulation, a CE is a correlated distribution fe over A. The elements (01,... ,., sampled from μ can thought of as profiles of action recommendations for the players such that no player has any incentive to not follow the recommendation (obedience). This has the following timeline.
Σi= (a).
1. At the beginning of the game, the mediator player chooses a profile of recommendations (01...., an) A.
2. Each player observes its recommendation a, and chooses action d'-
3. Each player gets utility u;(a'), and the mediator gets utility uo(a') Ei u:(a)).
In this game:
mixed strategies for the mediator distributions over A, that is, they correlated profiles;
a (pure) strategy for player i E [m] a mapping from A, to A,, encoding the action player E [[]]]] will take upon receiving each recommendation;
the direct strategy d; is again the identity map (i.e., each player selects as action what the mediator recommended to him/her).
In particular, if profile (1,, di....,d,)) ) such that each player is playing a best response, then μ CE.
Proposition 3.2 yields the following zero-sum game whose mediator equilibrium strategies (for suf- ficiently large X) are precisely the welfare-optimal equilibria:
1. Nature picks, with equal probability, whether there is a deviator. If nature picks that there is deviator, nature also selects which player E [m]] is represented by the deviator.
2. The mediator picks pure strategy profile (a (a an)) E A.
3. If there deviator, the deviator observes i E [n] and the recommendation a; and picks an action d/-
4. There are now two cases. If nature selected at the root that there was to be deviator, the utility for the mediator 222mu (a', a.)). If nature selected at the root that there was to be deviator, the utility for the mediator is 2uo(a) + 2A E ua(a) 2(1 + (a))
19

---

B Further related work
In this section, we provide additional related work omitted from the main body.
We first elaborate further on prior work regarding the complexity of computing equilibria in games. Much attention has been focused on the complexity of computing just any one Nash equilibrium. This has been motivated in part by the idea that if even this is hard to compute, then this casts doubt on the concept of Nash equilibrium as a whole [23]; but the interest also stemmed from the fact that the complexity of the problem was open for long time [82], and ended up being complete for an exotic complexity class [23, 17], whereas computing a Nash equilibrium that reaches a certain ob- jective value is "simply" NP-complete [41, 21J. None of this, however, justifies settling for just any one equilibrium in practice. Moreover, for correlated equilibria and related concepts, the complexity considerations are different. While one (extensive-fone polynomial time even for multi-player succinet games [83, 56, 54] (under the polynomial expecta- that maximizes some objective function is typically NP-hard [83, 98]. To make matters worse, even finding one that is strictly better- in terms of social welfare than the worst one is also computationally intractable [9]. Of course, our results do not contradict those lower bounds. For example, in multi-player normal-form games the strategy space of the mediator has an exponential description, thereby rendering all our algorithms exponential in the number of players. We stress again that while there exist algorithms that avoid this exponential dependence, they are not guaranteed compute an optimal equilibrium, which is the main focus of this paper.
correlated equilibrium can be computed in
tion property), computing
Moreover, in our formulation the mediator has the power to commit to strategy. As such, our results also relate to the literature on learning and computing Stackelberg equilibria [8, 35, 66, 84, 20], as well as the work of Camara et al. [15] which casts mechanism design as a repeated interaction between a principal and an agent. Stackelberg equilibria in sxtensive-form games are, however, hard to find in general [65]. Our Stackelberg game has a much nicer form than general Stackelberg games-in particular, we know in advance what the equilibrium strategies will be for the followers (namely, the direct strategies, ). This observation what allows the reduction to zero-sum games, sidestepping the need use Stackleberg-speciin technology or solvers and resulting efficient algorithms.
In independent and concurrent work, Fujii [40] provided independent learning dynamics converg- ing to the set of communication equilibria in Bayesian games, but unlike our algorithm there are no guarantees for finding an optimal one. Also in independent and concurrent work, Ivanov et al. [55] develop similar Lagrangian- based dynamics for the equilibrium notion that, in the language of this paper and Zhang and Sandholm [100], is coarse full-certification equilibrium. Differing from ours, their paper does not present any theoretical guarantees (instead focusing on practical results).
C Proof of Proposition 3.1
In this section, we provide the proof of Proposition 3.1, the statement of which is recalled below. Proposition 3.1. The problem (LI) admits finite saddle-point solution (μ", x²), Moreover, for fixed x", the problems (L1) and (G) have the same value and same set of optimal solutions.
Proof. Let v be the optimal value of (G). The Lagrangian of (G)
12
max #CE
min A,E m [;
cH Σ Ap A,
Now, making the change of variables क; == A,a,, the above problem is equivalent to
c. Σ CT A
max
min EE a [
where X; is the conic hull of X,; X; == (A.;; : a; E X,). Note that, when X; is polytope of the
form X, := (F = fú, 2 0}, its conic hull can be expressed as X, = (F = X; az 2 0, X2 2 0). Thus, (1) is a bilinear saddle-point problem, where E is compact and convex and X, is
20

---

convex. Thus, Sion's minimax theorem [92] applies, and we have that the value of (1) is equal to the value of the problem
e cJp p Σ A, 1=1
min max N. MEE
Since this linear program" with finite value, its optimum value must be achieved by some @ := (0), .n) == "i.t,,,.,,,,,,,,, Let X == max; )s Using the fact that μ A;d; = 0 for
all Ja, the profile
A (a, - d;)
E' = (X'2) X x where x d, +
) is an optimal solution for the minimizer in (L1) that achieves value of (G), so (G) and (L1) have the same value.
is also optimal solution in (2). Therefore, for any 2 Xt, x' = (a'1 ...... xy,))
Now take A > X", and suppose for contradiction that (LI) admits some optimal μ E E that is not optimal in (G). Then, either c v, or violates some constraint maXe, A,æ; < 0. The first case impossible because then setting x; d; for all i yields value less than in (LI). In the second case, since we know that (L1) and (G) have the same value when = X", we have
μ Amax TEX
Σ
CHAA A <c μ X max xEX
# A.
D Fast computation of optimal equilibria via regret minimization
In this section, we focus on computational aspects of solving the induced saddle-point prob- lem (LI) using regret minimization techniques. In particular, this section serves to elaborate our results presented earlier in Section 3.1. All of the omitted proofs are deferred to Appendix E for the sake of exposition.
As we explained in Section 3.1, the first challenge that arises in the solution of (LI) is that the domain of Player min is unbounded tte Lagrange multiplier is allowed to take any nonnegative value. Nevertheless, we show in the theorem below that it suffices set the Lagrange multiplier to fixed value (that may depend on the time horizon); we reiterate that appropriately setting that value will allow us to trade off between the equilibrium gap and the optimality gap. Before we proceed, we remark that the problem of Player min in (L1) can be decomposed into the subproblems faced by each player separately, so that the regret of Player min can be cast as the sum of the players' regrets (see Corollary E.2); this justifies the notation Σ Regx, used for the regret of Player min below.
Theorem D.1. Suppose that Player max in the saddle saddle-point problem (L1) incurs regret Reg and Player min incurs regret Σ Reg after T N repetitions, for fixed X X(T) 0. Then, the average mediator strategy E 3 p = Et= v( satisfies the following:
1. For any strategy μ³ E such that maxie[]] exxx;ex;(")) A 50
1 pp T n¹ T
Regg
Regx,
2. The equilibrium gap of jı decays with a rate of X -1;
T A, < ma c (μ 11)) +
max max R 2 EX:
Reg T
Regx.
XT
As result, we can simultaneously guarantee that X(T) - +oo and (Rege + i=1 Reg 0, as T + + Theorem D.1 shows that both the optimality gap (Item 1) and the equilibrium gap
Thii holds by taking dual of the inner minimization.
21

---

(Item 2) converge to O. We show that this is indeed possible in the sequel (Corollaries 3.3 and 3.4), obtaining favorable rates of convergence as well.
It is important to stress that while there exists a bounded critical Lagrange multiplier for our problem (Proposition 3. thereby obviating the need for truncating its value, such bound is not necessarily polynomial. For example, halving the players' utilities while maintaining the utility of the mediator would require doubling the magnitude of the critical Lagrange multiplier.
Next, we combine Theorem D.I with suitable regret minimization algorithms in order to guarantee fast convergence to optimal equilibria. Let us first focus the side of Player min in (LI), which, as pointed out earlier, can be decomposed into subproblems corresponding to each player separately (Corollary E.2). Minimizing regret over the sequence-form polytope can be performed efficiently with a variety of techniques, which can be classified into two basic approaches. The first one is based the standard online mirror descent algorithm (see, e-g., [91]), endowed with appropriate distance generating functions (DGFs) [32]. The alternative approach is based on regret decomposition, in the style of CFR [106, 29]. In particular, given that the players' observed utilities have range (()), the regret of each player under suitable learning algorithms will grow as O(XVT) (see Proposition 1. Furthermore, efficiently minimizing regret from the side of the mediator depends on the equilibrium concept at hand. For NFCCE, EFCCE and EFCE, the imperfect recall of the mediator [101] induces a computationally hard probiem [19], which nevertheless admits fixed- parammerr tractable algorithms [103] (Proposition E.3). In contrast, for communication and certification equilibria the perfect recall of the mediator enables efficient computation for any extensive-form game. As result, selecting a bound of À == T1/4 on the Lagrange multiplier, so as optimally trade off Items and 2 of Theorem D.I, leads to the following conclusion.
Corollary 3.3. There exist regret minimization algorithms such that when employed in the saddle- point problem (LI), the average strategy of the mediator ja = + Σt= w converges to the set of optimal equilibria at rate of T-/44 Moreover. the per-iteration complexity is polynomial for com- munication and certification equilibria (under the nested range condition [100]), while for NFCCE, EFCCE and EFCE, implementing each iteration admits a fixed-paaamete tractable algorithu.
Furthermore, we leverage the technique of optimism, pioneered by Chiang et al. [18], Rakhlin and Sridharan [87], Syrgkanis et al. [94] in the context of learning in games, in order to obtain faster rates. In particular, using optimistic mirror descent we can guarantee that the sum of the agents' regrets in the saddle-point problem (LI) will now grow as O()) (Proposition E.4), instead of the previous bound ((vTT) obtained using vanilla mirror descent. Thus, letting À 1/2 leads to the following improved rate of convergence.
Corollary 3.4 (Improved rates via optimism). There exist regret minimizution algorithms that guar- antee that the average strategy of the mediator jı + Et= (t converges the set of optimal equilibria at a rate of 1/22 The per-iteration complexity is analogous to Corollary 3.3.
We reiterate that while this rate is slower than the (near) T rates known for converging to some of those equilibria [24, 34, 85, 31, Corollaries 3.3 and 3.4 additionally guarantee convergence to optimal equilibria; improving the 1 rate of Corollary 3.4 is an interesting direction for the future.
1/2
Last-iterate convergence The results we have stated thus far apply for the average strategy of the mediator- a typical feature of traditional guarantees in the no-regret framework. In contrast, there is recent line of work that endeavors to recover last-iterate guarantees as well [22, 45, 1, 14, 6, 99, 64, 43, 67, 44]. Yet, despite many efforts, the known last-iterate guarantees of no-regret learning algorithms apply only for restricted classes of games, such as two-player zero-sum games. There is an inherent reason for the limited scope of those results: last-iterate convergence is inherently tied to Nash equilibria, which in turn are hard to compute in general games [23, 17]-let let alone computing an optimal one [41, 21]. Indeed, any given joint strategy profile of the players induces a product distribution, so iterate convergence an approximate Nash equilibrium.
by definition-at the very least computing
Proposition D.2 (Informal). Any independent learning dynamics (without a mediator) require perpolynomial time to guarantee e-last-iterate convergence, for a sufficiently small = 0(m even for two-player m- m-action normal-form games, unless PPAD C P.
22

---

There are also unconditional exponential communication wttpriittiiooooieitttt.. lower bounds for uncoupled methods [7. 53, 89, 48], as well as other pertinent impossibility results [50, 74] that document the inherent persistence of limit cycles in general-sum games. In contrast, an important advantage of our
formulation is that we can guarantee last-iterate convergence to optimal equilibria in general games. Indeed, this follows readily from our reduction to two-player zero-sum games, for which the known bound of O(A/VT) for the iterate gap of (online) optimistic gradient descent can be employed (see Appendix E).
Theorem 3.5 (Last-iterate convergence to optimal equilibria in general games). There exist algo- rithms that guarantee that the last strategy of the mediator y(l²) converges to the set of optimal equilibria at a rate Tf The per-iteration complexity analogous to Corollaries 3.3 and 3.4.
As such, our mediator-augun auggenter- learning paradigm bypasses the hardness of Proposition D.2 since last-iterate convergence is no longer tied to convergence to Nash equilibria.
E Omitted proofs from Section D
In this section, we provide the omitted proofss from Appendix D, which concerns the solution of the saddle-point problem described in (L1) using regret minization. Appendix E. then presents slightly different approach for solving (L1) using regret minimization over conic hulls, which is used in our experiments.
We begin with the proof of Theorem D.I, the statement of which is recalled below. In the following proof, we will denote by L = x X D (1,, (2:) + e μ X > /a A,æ; the induced Lagrangian, for a fixed À >>00 0.
Theorem D.1. Suppose that Player max in the caddle-point problem (L1) incurs regret Reg= and Player min incurs regret Ei= Regx, after T NN repetitions, for fixed X = X(T) 0. Then, the average mediator strategy E = a T Et= (0 satisfies the following:
1. For any strategy p* such that maxie[n] exxx;ex(("") A S0
1 T
c cazc
Regg +
Regx, T
2. The equilibrium gap of çt decays with rate of x11
max max A ma c (μ H4) +
1 XI
Reg T
>
Regx.
KE[n] x. EX:
Proof. Let f E E be the average strategy of the mediator and ã; E X, be the average strategy of each player [n] over the T iterations. We first argue about the approximate optimality of μ.. In particular, we have that
c p 2 max ME3
T μ
Σ
11
A
Rog T + Rege
(3)
T
1=1
1
2 c nr" >
(1x²)
A
Σ
Reg - Regg
(4)
T
2 c 11" - > Σ
max (1^)² T A
Σ ReKk + Regg
T
क Ex:
2=1
2c F¹' T
Σ
Reg + -Rege
(5)
where (3) follows from the fact that
1
n
max L(ui, (#+)
min (m
L(a, (x) (= S 7
Σ
Reg Reg
(6)
# EZ
6x
23

---

= 0; (4) uses the notation u² represent any equilibrium strategy optimizing the objective c μe; and (5) follows from the fact that, by assumption, fr satisfies the equilibrium constraint: max (1²) A I 0 for any player i E [ni] as well as the nonnegativity of the Lagrange multiplier. This establishes Item I of the statement.
in turn implying (3) since Ei=1 max i A
Next, we analyze the equilibrium gap of μ. Consider any mediator strategy μ E E such that A, I 0 for any D; E X; and player i E [n]. By (6),
1 A' S T xe
c - Cm
1 A. +
Σ Regx, + Reg
(7)
But, by the equilibrium constraint for μr, it follows that μ A,æ; S for any as E X; and player i [[z]]] in turn implying that Σ A, I 0. So, combining with (7),
max Ø A c μ c cJH #+ mi
Σ
Regx. T + Reg=
T
(8)
T
Finally, given that max, EXy Ø Avay 2 Ji Ardy = 0 for any player i', it follows that
Σ max İ A 2 max max f A, ie[n] m;
m;ex
and (8) implies Item 2 of the statement.
Bounding the regret of the players To instantiate Theorem D.1 for our problem, we first bound the regret of Player min in (LI) in terms of the magnitude of the Lagrange multiplier. As we ex- plained in Appendix D, the regret minimization problem faced by Player min can be decomposed into subproblems over the sequence- form polytope, one for each player. To keep the exposition self- contained, let us first recall the standard regret guarantee of CFR under the sequence-for
polytope.
Proposition E.1 ([106]). Let Regx, be the regret cumulated by CFR [106] over the sequence-form polytope X Then, for any T E N.
Regx. SDDEENT
where D; >> O is the range of utilities observed by player i E [n]] and C > 0 is an absolute constant.
An analogous regret guarantee holds for online mirror descent [91]. As result, given that the range of observed utilities for each player is O()), for a fixed Lagrange multiplier X, we arrive at the following result.
Corollary E.2. If all players employ CFR, the regret of Player min in (L1) can be bounded
Reg = Regx, = 0(VVT).
Here, used the simple fact that regret over a Cartesian product can be expressed as the sum of the regrets over each individual set [29].
Bounding the regret of the mediator We next turn our attention the regret minimization prob- lem faced by the mediator. The complexity of this problem depends on the underlying notion of cquilibrium hand. In particular, for the correlated equilibrium concepts studied in this paper- namely, NFCCE, EFCCE and EFCE, we employ the framework of DAG-form sequential decision problem (DFSDP) [103]. In particular, DFSDP a sequential decision process over a DAG. We will denote by E the set of edges of the DAG, and by S the set of its nodes; we refer to Zhang et al. [103] for the precise definitions. A crucial structural observation the probability simplex after repeated Cartesian products and scaled-extensions operations; suitable DGFs arising from such operations have been documented [32]. As such, we can use the following guarantee shown by Zhang et al. [103].
that a DESDP can be derived from
24

---

Proposition E.3 ([103). Let Regz be the regret cumulated by the regret minimization algorithm R= used by the mediator (Player max in (L1)) up to time T N. Then, if R= is instantiated using CFR, or suitable variants thereof. RegÉ = O(SS)TD)), where is the range of the utilities observed by the mediator. Further, the iteration complexity is E)).
As result, combining Theorem D.I with Proposition E.3 and Corollary E.2, and setting the La- grange multiplier À = T1/4 we establish the statement of Corollary 3.3.
Faster rates through optimism Next, to obtain Corollary 3.4, let us parameterize the regret of optimistic gradient descent in terms of the maximum utility, which can be directly extracted from the work of Rakhlin and Sridharan [87].
Proposition E.4. both agents in the saddle-point problem (L.) employ optimistic gradient descent with sufficiently small learning rate > 0, then the sum of their regrets is bounded by O(X), for any fixed X 0.
Proof Sketch. By the RVU bound [94, 87], the sum of the agents' regrets can be bounded as (diam + d for sufficiently small = (1) where diamg and diamx denote the fg-diameter of = and X, respectively. Thus, taking r ((1/A) to be sufficiently small implies the statement.
As result, taking À T1/2 and applying Theorem D.I leads the bound claimed in Corollary 3.4.
Last-iterate convergence Finally, let us explain how known guarantees can be applied to establish Theorem 3.5. By applying [4], it follows that for sufficiently small learning rate 1j O(1/A)
there is an iterate of optimistic gradient descent with O NVT
duality gap. Thus, setting ")
(1/A) to be sufficiently small get that the duality gap is bounded by O ( (T As result,
for À == T1/1 Theorem D.1 implies a rate of T-1/4, as claimed in Theorem 3.5. We remark that while the guarantee of Theorem D.1 has been expressed in terms of the sum of the agents' regrets, the conclusion readily applies for any pair of strategies (μ,, a)) E X by replacing the term Regg + > Regx, with the duality gap of (p,, with respect to (LI) (for the fixed value A).
We further note that once the desirable duality gap O TVT has been reached, one can fix the players' strategies to obtain last-iterate guarantee as well.
E.1 An alternative approach
In this subsection, we highlight an alternative approach for solving the saddle-point (LI) using regret minimization. In particular, we first observe that it can expressed as the saddle -pint problem
max
min WEB [
cT Σ A
where x= E (0, parameter > Analogously to our approach in Appendix D, suitably tuning the value K will allow trade off between the optimality gap and the equilibrium gap. In this context, we point out below that how to construct regret minimizer over conic hull.
X,) is the conic hull of X; truncated sufficiently large
Regret minimization over conic hulls Suppose that Rx, is regret minimizer over X; and R4 a regret minimizer over the interval [0, K]. Based on those two regret minimizers, Algorithm shows how to construct regret minimizer over the conic hull X,. More precisely, Algorithm 2 fol- lows the convention that a generic regret minizer R interacts with its environment via the following two subroutines:
R.NEXTSTRATEGY: R returns the next strategy based on its internal state; and
ROOOSERVEUUILLTT(AU R receives as input from the environment (compatible) util- ity vector ( at time E N.
25

---

ALGORITHM 2: Regret minimization over a conic hull
function NEXTŠTRATRGYO
A; f R. NEXTSTRAATEE 2; + Rx N R
return C; == λ,æ;
function OBSERVEUTILITY(U))
Rx. (UEEVEEEUUUUL
7
OUSEVEERUUUULL,YY a.))
The formal statement regarding the cumulated regret of Algorithm below is cast in the framework of regret circuits [29].
Proposition E.5 (Regret circuit for the conic hull). Suppose that Regx, and Reg,, is the cumulative regret incurred by Rx, and R4, respectively, up to time horizon T E N. Then, the regret Reg T R constructed based on Algorithm can be bounded as
g,
Regx, I K max(0, Regx, } Reg..
Proof. By construction, we have that Regx, is equal
T Σ 1=1
T
max #1 E
[ - x
max X
(f00 - 1!0 ,u!
(o) , PP + (1 - (z,)) 2;
max
1=1
S K max Reg T
Reg..
where the last derivation uses that X E [0, K].
As a result, by suitable instantiating Rx, and R.+ (e.g., using Proposition E.1), the regret circuit of Proposition E.5 enables us to construct a regret minimizer over X; with regret bounded as O(K K vT). In turn, this directly leads regret minimizer for Player min in (9) with regret bounded by O(VVT), We further remark that Theorem D.I can be readily cast in terms of the saddle-point problem (9) as well, parameterized now by K instead of X. As a result, convergence bounds such as Corollary 3.3 also apply regret minimizers constructed via conic hulls.
F Description of game instances
In this section, we provide a detailed description of the game instances used in our experiments in Section 4.1.
F11 Liar's dice (D), Goofspiel (GL), Kuhn poker (K), and Leduc poker (L)
Liar's dice At the start of the game, each of the three players rolls fair k-sided die privately. Then, the players take turns making claims about the outcome of their roll. The first player starts by stating any number from to & and the minimum number of dice they believe are showing that value among all players. On their turn, each player has the option to make a higher claim or challenge the previous claim by calling the previous player "liar." A claim higher if the number rolled is higher or the number of dice showing that number is higher. If player challenges the previous claim and the claim found to false, the challenger rewarded + and the last bidder receives a penalty of -1. If the claim is true, the last bidder is rewarded +1, and the challenger receives -1. All other players receive 0 reward. We consider two instances of the game, one with 2 (D32) and one with A 3 (D33).
26

---

Goofspiel This is a variant of Goofspiel with limited information. In this variation, in each turn the players do not reveal the cards that they have played. Instead, players show their cards neutral umpire, who then decides the winner of the round by determining which card is the highest. In the event of a tie, the umpire directs the players to divide the prize equally among the tied players, similar to the Goofspiel game. The instance GL3 which we employ has 3 players, 3 ranks, and imperfect information.
Kuhn poker Three-player Kuhn Poker, extension of the original two-player version proposed by Kuhn [61], is played with three players and r cards. Each player begins by paying one chip to the pot and receiving single private card. The first player can check or bet (ie., putting an additional chip in the pot). Then, the second player can check or bet after a first player's s check, or fold/call the first player's s bet. The third player can either check or bet if no previous bet was made, otherwise they must fold or call. At the showdown, the player with the highest card who has not folded wins all the chips in the pot. We use the instance K35 which has rank r = 5.
Ledue poker In our instances of the three- pareer Ledue poker the deck consists of s suits with r cards each. Our instances are parametric in the maximum number of bets b, which in limit hold' em is not necessarely tied to the number of players. The maximum number of raise per betting round can be either 1, 3. At the beginning of the game, players each contribute one chip the pot. The game proceeds with two rounds of betting. In the first round, each player is dealt a private card, and in the second round, shared board card is revealed. The minimum raise is set at 2 chips in the first round and 4 chips in the second round. We denote by L3brs an instance with three players with b bets per round, r ranks, and suits. We employ the following five instances: L3132, L3133, L3151, L3223, L3523.
F22 Battleship game (B) and Sheriff game (S)
Battleship The game is general-sum version of the classic game Battleship, where two players take turns placing ships of varying sizes and values on two separate grids of size h x w. and then take turns firing at their opponent. Ships which have been hit at all their tiles are considered destroyed. The game ends when one player loses all their ships, or after each player has fired r shots. Each player's payoff is determined by the sum of the value of the opponent's 's destroyed ships minus 7 times the number of their own lost ships. We denote by Bphur an instance with p players on a grid of size h w, one unit-size ship for each player, and rounds. We consider the following four instances: B2222, B2322, B2323, B2324.
Sheriff This game is a simplified version of the Sheriff of Nottingham board game, which models the interaction between a Smuggler-who is trying to smuggle illegal items in their cargo-and and the Sheriff-whhe
goal is stopping the Smuggler. First, the Smuggler has decide the number E (0. [O....N] N of illegal items to load on the cargo. Then, the Sheriff decides whether to inspect the cargo. If they choose to inspect, and find illegal goods, the Smuggler has pay p n to the Sheriff. Otherwise, the Sheriff has to compensate the Smuggler with reward of s. If the Sheriff decides not to inspect the cargo, the Sheriff's utility is 0, and the Smuggler's 's utility is u n. After the Smuggler has loaded the cargo, and before the Sheriff decides whether to inspect, the Smuggler can try to bribe the Sheriff to avoid the inspection. In particular, they engage in r rounds of bargaining and, for each round i, the Smuggler proposes a bribe b, E {0.... ... B). and the Sheriff accepts or declines it. Only the proposal and response from the final round r are executed. If the Sheriff accepts a bribe by then they get by. while the Smuggler's 's utility is un b,. Further details on the game can be found in Farina et al. [30]. An instance Sp. Br has p players, N illegal items, maximum bribe of B, and rounds of bargaining. The other parameters v 5, p 1, 1 and they are fixed across all instances. We employ the following five instances: S2122, S2123, S2133, $2254, $2264.
F33 The double-dummy bridge endgame (TP)
The double-dummy bridge endgame is benchmark introduced by Zhang et al. [101] which simu- lates a bridge endgame scenario. The game uses a fixed deck of playing cards that includes three ranks (2, 3. 4) of each of four suits (spades, hearts, diamonds, clubs). Spades are designated as the trump suit. There are four players involved: two defenders sitting across from each other, the dummy, and the declarer. The dummy's ' actions will be controlled by the declarer, so there are only
27

---

three players actively participating, However, for clarity, we will refer to all four players throughout this section.
The entire deck of cards is randomly dealt to the four players. We study the version of the game that has perfect information, meaning that all players' cards are revealed everyone, creating game in which all information is public (i.e., a double-dumny game). The game is played in rounds called tricks. The player to the left of the declarer starts the first trick by playing a card. The suit of this card is known as the lead suit. Going in clockwise order, the other three players play a card from their hand. Players must play card of the lead suit if they have one, otherwise, they can play any card. If a spade is played, the player with the highest spade wins the trick. Otherwise, the highest card of the lead suit wins the trick. The winner of each trick then leads the next one. At the end of the game, each player earns as many points as the number of tricks they won. In this adversarial team game, the two defenders are teammates and play against the declarer, who controls the dummy.
The specific instance that we use (i.e., TP3) has 3 ranks and perfect information. The dummy's hand fixed as 2 2 34.
F.4 Ridesharing game (RS)
This benchmark was first introduced by Zhang et al. [101]. and it models the interaction between two drivers competing to serve requests on a road network. The network defined as an undirected graph G" = (vo, E.). where each vertex v E V corresponds to ride request to be served. Each request has a reward in Rzo. and each edge in the network has some cost. The first driver who arrives on node node has been served, it stays clean until the end of the game. The game terminates when all nodes have been cleared, or when a timeout is met (i.e., there's Saree' a fixed time horizon 7). If the two drivers arrive simultaneously on the same vertex they both get reward The final utility of each driver is computed the sum of the rewards obtained from the beginning until the end of the game. The initial position of the two drivers is randomly selected at the beginning of the game. Finally, the two drivers observe each other's position only when they simultancously the same node, or they are in adjacent nodes.
V serves the corresponding ride, and receives the corresponding reward. Once
Ridesharing games are particularly well-suited to study the computation of optimal equilibria be- cause they are not triangle-free [28].
Setup We denote by R$ p T ridesharing instance with p drivers, network configuration i, and horizon T. Parameter i E {1,2} specifies the graph configuration. We consider the two network configurations of Zhang al. [101], their structure is reported in Figure 2. All edges are given unitary cost. We consider a total of four instances: RS212, RS222, RS213, RS223.
(.5)
(.5)
(2)
(2.5)
(.5)
5
2
(1)
(1)
(4.5)
0
(5}
0
3
4
(1.5)
2
6
(1)
(1.5)
(1.5)
(1.5)
Figure 2: Left: configuration 1 (used for RS212, RS213). Right: configuration 2 (used for RS222, RS223). In both cases the position of the two drivers is randomly chosen at the beginning of the game, edge costs are unitary, and the reward for each node is indicated between curly brackets.
28

---

G Additional experimental results
G.1 Investigation of lower equilibrium approximation
In Table 2 we show results, using the same format as Table shown in the body, for the case in which the approximation is set to be 0.1% of the payoff range of the game, opposed to the 1% threshold of the body.
Table 2: Comparison between the linear- pwwgraaming- baase algorithm ('LP") of Zhang and Sand- holm [100] and our learning- carning-based approach (' ("Ours') ) for the problem of computing an approximate optimal equilibrium within tolerance set to 0.1% of the payoff range of the game.
Game
Nodes
NFCCE
EFCCE
EFCE LP
COMM
CERT
LP
Ours
LP
Ours
Ours
LP
Ours
LP
Ours
1573
0.00s
0.00s
0.02s
0.00:
0.03s
0.00s
0.04s
B2322
23839
1.00s
0.02s
3.00s
1.42s
9.00s
4.11s
timcout
17m 30s
2.00s
2.82s
B2823
254 239
6.00s
0.66s
1m 29s
30.04s
3m 40s
Im 28s
timcout
timcout
39.00s
Im 24s
B2324
639
41 00s
5.25%
timeout
5m 49
timeout
timeout
timenut
timenut
timeout
timcout
D32
1017
0.00s
0.03s
0.00s
0.04s
14.00s
0.92s
0.26s
0.00s
0.03s
D33
27 622
3m 22s
44.41s
Uineou
10m 27s
timeout
Limeout
limeout
66m 38s
6.00s
6.87s
GL3
7735
0.00s
0.06s
1.00s
0.07s
0.00s
0.06s
limeout
36.83s
0.00s
0.1
K35
1501
55.00s
2.46s
53.00s
3.05s
mm
2.99s
1.00s
0.09s
0.00s
0.02s
L3132
8917
28.00s
2.133
11m 26s
22. 14s
9m 41s
26.68s
13.00s
15.41s
1.00s
0.62s
L3133
188
45. 00s
2.83s
timeout
35. 35.86s
26m 52s
22.31s
17.00s
15.27s
1.00s
1.25%
L3151
19998
timcout
54.66s
timcout
timcout
timcout
timcout
timcout
Im 15s
2.00s
0.91s
L3223
5.00s
1.73s
1m
8,58s
38s
20.44s
26.00s
Im 43s
1.00s
2.00s
timenut
4m
timeout
timeout
82122
705
0.00s
0.00s
0.00s
0.02s
0.00s
0.07s
3.00s
6.14s
0.00s
0.03s
82123
4209
0.00s
0.02s
1.00s
0. 14s
1.00s
0.37s
Im 51s
10m 8s
1.00s
0.41s
$2133
9648
1.00s
0.05%
3.00s
0.17s
4.00s
0.95%
limeout
limouu
3,00s
1.99s
712
32.
2s
immout
50s
$2264
1 3033313 177
48s
57.76s
timeout
Im 16s
timcout
timcout
timcout
timcout
timeout
timoout
TP3
910737
mm 4.%
14.28s
timeout
20.81s
timeout
26.28s
timenut
timenut
timeout
52.76s
RS212
598
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
2.00s
0.02s
0.00s
0.00s
BS222
734
0.00s
0.01s
0.00s
0.01s
0.00s
3,00s
0.03s
0.00s
0.00s
RS213
6274
timeout
43.46s
timecut
45.00s
timeout
2m 28s
7m 30s
27.19
0.00s
0.03s
RS223
6238
timeout
timeout
timeout
timeout
timeout
timeout
9m 16s
15.68s
1.00s
0.05s
We observe that none of the results change qualitatively when this increased precision is considered.
G.2 Game values and size of Mediator's strategy space
Tables 3 and 4 reports optimal equilibrium values for all games and all equilibrium concepts for which the LP algorithm was able to compute an exact value (We restrict to the cases solvable by LP because the Lagrangian relaxations only compute an c-equilibrium, but the mediator objective in an e-equilibrium could be arbitrarily far away from the mediator objective in an exact equilibrium). We hope that these will be good references for future researchers interested in this topic. Table 5 reports the size of the strategy space of the mediator player the two-player zero-sum game that captures the computation of optimal equilibria, in terms of the number of decision points and edges. For correlated notions, this number may be exponential in the original game size; for communication and certification notions, it will always be polynomial.
29

---

Table 3: Optimal equilibrium value for correlated equilibrium concepts, 'PI. I' is the utility for Player in the Player I-optimal equilibrium. 'PI. and 'PI. 3' are similar. In two-player games, "SW" is the welfare of the welfare-maxinizing equilibrium. (these three values, of course, may come from three different equilibria.) The three-player games zero-sum, optimizing welfare makes no sense (the welfare is always zero).
NFCCE
EFCCE
EFCE
Game
PL.
PI.
SW
SW
PL. 1
PI. 2
SW
B2222
0.281
0.094
0.000
0.027
0.338
0.525
-0.031
0.338
0.525
B2322
0.181
0.097
0.000
-0.043
-0.123
-0.317
00.04
-0.123
-0.317
B2323
0.250
0.125
0.000
0.000
00.155
-0.375
-0.001
-0.125
-0.375
B2324
0.306
0.139
0.000
$2122
11.636
5.999
13.636
7.652
5.043
9.565
7.262
3.841
9.078
$2123
11.636
5.999
13.636
8.000
5.191
10.000
8.000
4.611
10.000
$2133
15.182
6.992
18. 18.182
12.000
6.557
15.000
12.000
6.407
15.000
$2254
23.571
12.830
28.571
$2264
27.333
13.840
33.333
U212
3.123
3.123
6,010
3.071
3.071
6.010
3.071
3.071
6.010
U213
U222
3.765
3.765
7.188
3.719
3.719
7.176
3.719
3.719
7.176
U223
PI.
2
3
D32
0.250
0.250
0.131
0.250
0.250
0.000
0.250
0.250
0.000
D33
0.422
0.284
0.239
GL3
2.505
2.505
2.505
2.476
2.476
2.476
2.467
2.467
2.467
K35
0.011
0.017
0.057
0.016
0.015
0.052
0.016
0.013
0.052
L3132
0.571
0.504
0.606
0.519
0.467
0.422
L3133
0.419
0.348
0.416
L3151
L3223
1.079
0.992
1.146
0.984
0.959
1.033
0.887
0.883
0.861
L3523
TP3
1.466
1.477
1.037
Table 4: Optimal equilibrium value for communication and certification equilibrium concepts. PPI. 1', 'PL. 2', PPI. 3', and 'SW' have the same meaning in the previous table.
COMM 2L
NFCCERT PL 2
CCERT P1.
CERT PL. 2
Game
PL
SW
PI.
SW
PL.
SW
PL.
SW
B2222
0.187
-0.750
0.094
02.227
-0.525
-0.027
-0.325
B2322
0.181
0.097
0.000
-0.043
-0.123
-0.317
-0.043
-0.123
-0.317
B2323
0.250
0.125
0.000
0.000
-0.125
-0.375
0.000
00.125
-0.375
B2324
0.306
0.139
0.000
82122
0.820
0.000
0.820
50.000
8.508
50.000
8.000
5.191
10.000
8.000
4.611
10.000
$2123
0.820
0.000
0.820
50.000
8.508
50.000
8.000
5.191
10.000
8.000
4.611
10.000
$2133
50.000
8.67
50.000
12. 12.000
6.557
15.000
12.000
6.407
15.000
$2254
100.000
17.284
000.000
20.000
12.190
25.000
S2264
100.000
17.442
100.000
12112
3.184
3.143
6.173
3.184
3.173
6.173
3.184
3.159
6.173
3.184
3.143
6.173
U213
5.160
5.171
9.502
5.316
5.420
9.622
5.204
5.298
9.622
5.198
5.276
9.622
U222
4.023
3.812
7.504
4.023
3.930
7.594
4.023
3,905
7.594
4.023
3.839
7.594
U223
6.537
6.326
11.464
6.567
6.753
11.516
6.631
6.582
11.513
6.576
6.308
11.485
PI.
2L
PI.
Pl.
2
3
PI.
PI.
PI.
Pl.
2
3
D32
0.250
0.250
0.042
0.500
0.250
0.250
0.250
0.250
0.255
0.250
0.250
0.250
0.580
0.432
0.272
GL33
2.505
2.505
2.505
2.505
2.5015
2.505
2.467
2.468
2.468
K35
0.092
0.106
0.109
0.092
0.086
0.090
1.109
L3132
0.646
0.618
0.723
0.853
0.779
0.802
01853
0.779
03.00
01853
0.779
0.802
L3133
0.411
0.459
0.590
0. 6.646
0.054
0.709
0.6:6
0.054
0.709
0.646
0.054
0.709
1.3151
0.179
0.197
0.222
0.179
0.1
0.222
0.177
0.2
0.222
1.379
1.556
1.379
1.556
1.451
L3523
2,000
2.000
2.000
1.739
1.506
1.083
30

---

Table 5: Dimension of the mediator's decision space in terms of number of decision points ('Dec. pts.') and edges.
Game
Dec. pis.
NFCCE
Edges
Dec.
EPCCE
Edges
pts.
EFCE
Edges
pis.
COMM
Dec. pls.
NFCCERT
Edges
Dec.
CCERT
Edges
pis.
CERT
Edges
B2222
6935
5001
9i2
4212
200
16341
65.577
663
27.20
0554
3550)
14668
117707
06
619
13940
010000
596-00
1087
5-488.15
1052019
294
244340
12260800
909-441
6 3339700
88296-681
633836
$160018
49 667
006001
2 2.46755
527
2158.340
9012080
6-776-40
34
5381
108
53-402
5364455
127944
45070
472
1706
2484
91778
D33
427
11.10
651
1509-999
71372680
2854522
10
450812
11 292
44.553
18:306
03.057
135.00
520
02.3
5338
122
100
07.41
5637
16:900
182289
547000
2348
7104
5138
9474
3058
15 204
833
22277
3,002 121
50
257
3822
61217
4535 261
9746
29230
1005
2015
1078
]225
2015
1945
18182
181 011
1,222 126
688
SAA)
162229
505
8844 281
513
325 7300
2000
7274
239319
15789 1
073877 2077
10000
96-66
13101
131385
6897 120
185-99
34 d115 67)
1
500000000
087
680
1002
26
160
405
1010749
14619676
7841955
965189 187
53354996
18.25 285
9660
20.590
54.855
21 21553
36 11.115
105 108345
72:00
448869
217 185
154694
15925
91 735
014
40G 8001
66117 130
0788866
1999 142
1
234
41011040
1418G
30:218
118 8778
837796
27.5 276
1.522
1530
333
3:86
1155978
3:887
11117
402
11
1877
1904
14
01
2144 648
592122
651
2003
2061
78477
1629
6227
4071
12600
108
1,596
805
2627
1740
5465
522123
4415
19
17 15583
72:577
1.
52 550
146631
154 966
2406
86:30
6573
21 21000
15717
49.300
9424
031
40 960
171 915
38
850
778 108
425-675
15:000
09 007
44088
1319511
017056
3768
39774
2017
4,470
26
1,000:00
6:000
7699
579 182
60026666
125
969
12,500
12355865
3125
[3 (3574
7200088
22117712
6714256
1000544
3273/073
[ 488
5.233
184
3.594352
B5212
3317
14550
213
910
184
755
1626
00
1625
25/047
1495
32643
41:42
1593-
2000
1008
202
2302
902
85213
61 122
104 268
62 704
06
250 604
07070
124 653 191
965621
1858788 786
2450 1
10870
2508
12816 1
1286
19 160
B6223
299162
1184114
2778
10854
3224
12 (0000
4500
17776
G.3 Detailed breakdown by equilibrium and objective function (two-player games)
For each two-player game, we try three different objective functions: maximizing the utility of Player 1, maximizing the utility of Player 2, and maximizing social welfare. For each objective, we stop the optimization at the approximation level defined as 1% of the payoff range of the game.
We use online optimistic gradient descent to update the Lagrange multipliers of each player (see Appendix E. For each objective, we report the following information:
The runtime of the linear-programming--assd algorithm ('LP') of Zhang and Sand- holm [100].
The runtime of our algorithm where each agent (player or mediator) uses the Discounted CFR ('DCFR') algorithm set up with the hyperparameters recommended in the work by Brown and Sandholm [12]. In the table, we report the best runtime across all choices of the stepsize hyperparameter 7) f0.01, 0.1, 1.0, 10.0) used in online optimistic gradient descent to update the Lagrange multipliers. The value of that produces the reported runtime is noted in square brackets.
The runtime of our algorithm where each agent (player or mediator) uses the Predictive CFR+ ('PCFR+)) algorithm of [33]. In the table, we report the best runtime across all choices of the stepsize hyperparameter 7) E {0.01, 0.1, 1.0. 10.0} used in online optimistic gradient descent to update the Lagrange multipliers. The value of that produces the reported runtime again noted in square brackets
31

---

G.3.1
Results for NFCCE solution concept
Maximize Player
utility Ours (PCFR")
Maximize Player 2's utility
Maximize social welfare
Game
LP Ours (DCFF)
LP Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCFR*)
B2222
0.008
0.008
[1.0]
0.008
[0.1]
0.00s
0.00s
[1.0]
0.00s
[0.]]
0.00s
0.008
[1.0]
0.00s
[0.1]
B2322
0.00s
0.03%
[0.1]
0.078
[0.1]
0.00s
0.04s
[0.1]
0.04s
[1.0]
0.00s
0.01s
[0.1]
0.01s
[10.0]
B2328
7.00%
1.05%
[0.11
1.61s
[0.1]
6.00s
1.01s
[0.31
1.63s
[0.11
6.00s
0.33x
[0.1]
0.53g
[10.0]
B2324
50.00%
15.57%
[0.1]
20.01s
[0.1]
37.00s
12.80s
[0.3]
20.91s
[0.1]
38 38.00s
2.73%
[0.1]
4.57%
[1.0]
82122
0.00s
0.004
[0.1]
0.00%
[0.1]
0.00s
0.00c
[0.1]
0.00%
[0.1]
0.00s
0.00%
[0.1]
0.00c
[0.1]
82123
0.00s
0.01s
[1.0]
0.01s
[0.1]
0.00s
0.01s
[0.1]
0.01s
[0.1]
0.00s
0.01s
[0.1]
0.01s
[0.1]
$2133
1. 1.00s
0.02s
[1.0]
0.028
[0.1]
1.00s
0.024
[0.1]
0.03s
[0.1]
1 1.00s
0.02s
[1.0]
0.024
[0.1]
$2254
2m Is
6.968
[0:1]
11.43%
[0.1]
1m 14s
10.43%
[0.1]
17.72s
[0:1]
Im 58s
7.43s
[0.1]
11,88s
[0.1]
$2264
3m 368
13,968
[0:1]
23.25%
[0.1]
2m 24s
18.46s
[0.3]
35.04s
[0:1]
3m 43s
11.74s
[0.1]
17.91s
[0.1]
AS212
0.00s
0.00s
[1.0]
0.00s
[1:0]
0.00s
0.00s
[10.0]
0.00s
[1.0]
0.00s
0.00%
[10.0]
0.00s
[1.0]
RS222
0.00k
0.00x
0.01s
0.00s
0.00s
[1.0]
0.01s
[1.0]
0.00s
0.00s
[0.01]
0.01s
[0.01]
R8213
timeout
34.52s
[1.0]
1m 9%
timeout
20.29
[1.0]
41.66%
[0.1]
timeout
14.68s
[0.1]
35.36x
[0.1]
R8223
timeout
[-]
timeout
rimeout
rimeout
timenut
timeout
timeout
timenut
G.3.2
Results for EFCCE solution concept
Maximize Player I's utility
Maximize Player 2's utility
Maximize social welfare
Game
Ours (DCFR)
Ours (PCFR*)
LP Ours (DCFR)
Ours (PCFR )
LP|
Ours (DCFR)
Ours (PCFR*)
B2222
0.008
0.01s
[1.0]
0.028
[1.0]
0.90s
0.01s
[1.0]
0.02s
[1.0]
0.00s
0.015
[1.0]
0.01s
[1.0]
B2522
3.00%
0.41s
[1.0]
1.136
11.01
3.00s
0.69%
11.01
1.19s
11.0]
3.00s
0.69s
[1.0]
1.33
[1.0]
B2323
Im 35s
9.11s
[1.0]
22.38%
[1.01
1m 30s
12.39
[1.0]
23.59:
[1.0]
1m 21s
14.23
[1.0]
20.30s
[1.0]
B2324
iimouut
1m
53%
[1.0]
3m
35p
[1.0]
timeout
2m 44x
[1.0]
4m
29s
[1.0]
dmeoul
3m 1s
[1.0]
4m 166
[1.0]
92122
0.00s
0.01s
[1.0]
0.01s
[1.0) [1.0]
0.00s
0.004
[0.1]
0.01s
[0.1]
0.00s
0.01s
[1.0]
0.02g
[1.0]
$2123
1 1.00
0.03s
[1.0]
0.19
[0.1]
1.00s
0.094
[0.1]
0.05c
[0.1]
1.00s
0.06s
[1.0]
0. 0.16s
[1.0]
$2138
3.00s
0.12s
[1.0]
0.31s
[1.0]
2.00s
0.20s
[0.1]
0.224
[0.1]
3.00s
0.11s
[1.0]
0.41s
[1.0]
$2254
timcout
28.81s
[1.0]
27.31s
[0.1]
timcout
37.43s
[0.1]
53.08s
[0.1]
timcout
22.01s
[1.0]
36.83s
[0.1]
$2264
Eicoout
46.07s
[0.1]
Im
248
[0.1]
timcout
2m 18s
[0.1]
2m
26s
[0.1]
timcout
39.23g
[0.1]
1m
9%
[0.1]
R8212
0.00s
0.00s
[1.0]
0.00s
[1 []
0.00s
0.00s
[1.0]
0.00s
[1.0]
0.00s
0.00s
[0.01]
0.00s
[0.1]
RS222
0.00k
0.00x
[1.0]
0.01s [0.1]
0.00s
0.00s
[1.0]
0.01s [1.0]
0.00s
0.00s
[0.01]
0.00x
[0.1]
R8213
limeout
28.80s
[1.0]
Im 50x
[1.0]
timeout
31.02s
[1.0]
1m 13s
[1.0]
timenut
15.54s
[0.1]
37.73x
[0.1]
R8223
timenut
timenut
rimenur
rimeout
rimeout
timenut
timenut
timenut
rimeout
G.3.3
Results for EFCE solution concept
Game
Maximize Player I's utility
Ours (DCFR)
Ours (PCFR*)
LP Ours (DCFR)
Maximize Player 2's utility
Ours (PCFR )
LP|
Maximize social welfare
Ours (DCFR)
Ours (PCER))
B2222
0.00%
0.01s
[1.0]
[1.0]
0.00s
0.06s
[1.0]
0.05s
[0.11
0.00s
0.03g
[10.0]
0.02s
[1.0]
B2322
9.00k
1.23%
[1.0]
[1:01
9.00s
11.01
4.68s
[1.0]
9.00s
1.60s
[10.0]
2.88s
[1.0]
B2323
3m
40k
[1.0]
1m
[1.0]
38s
[1.0]
27s
[1.0]
45.
[10.0]
44.87
[1.0]
B2324
limenut
9m
[1.0]
8x
[1.0]
timeout
timeout
10m
21s
[1.0]
imeout
14m
[1.0]
[1.0]
82122
0.00%
0.01s
[0.1]
0.02s
[1 [1.0]
0.004
0.024
[0.1]
0.04s
[0.1]
0.00s
0.024
[0.1]
0.02s
[1.0]
$2123
1. 1.00
0.09%
[1.0]
0.234
[0.1]
1.00s
0.34s
[0.1]
0.434
[1.0]
1.00s
0.15s
[0.1]
0.25%
[0.1]
$2133
4.00%
0.52s
[1.0]
0.778
[0.1]
3.00s
1.86s
[0.1]
1.31s
[0.1]
3.00s
0.49%
[1.0]
0.96s
[1.0]
$2254
Emcout
2m
17s
[0.1]
2m
108
[0.1]
timcout
timcout
[
tincout
timcout
3m
34s
[0.1]
timcout
92264
Eimoout
timcout
[-]
Gimcout
timcout
timcout
timcout
timcout
timeout
[
timoout
R8212
0.00s
0.00s
[1.0]
0.00s [1.0]
0.00s
0.00s
[1.0]
0.00s [1.0]
0.00s
0.00s
[0.01]]
0.00s
[0.01]
R6222
0.00x
0.00k
[1.0]
0.01s [0.1]
0.00c
0.004
[1.0]
0.01s [1.0]
0.00s
0.00s
[1.0]
0.00s
[0.
R6213
limenut
35.37%
[1.0]
Im 28s
[0.1]
timeout
32.49
[1.0]
Im
27x
[1.0]
timenut
23.37%
[0.01]
57.68%
[0.01]
R8223
timenut
timenut
rimeour
timeout
timeout
timeout
timenut
timerut
rimcout
32

---

G.3.4
Results for COMM solution concept
Maximize Player I's utility
Maximize Player 2's utility
Maximize social welfare
Game
LP
Ours (DCFR)
Ours (PCFR")
LP|
Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCFR*)
B2222
2,00s
0.88s
[1.0]
1.14s [1.0]
2.00s
1,23s
[10.0]
0.89%
[1.0]
2,00s
1.49s
[10.0]
2.33s
[1.0]
B2522
Emcout
5m 47s
[1.0]
10m 17s
[1.0]
iimoout
3m 45s
[1.0]
5m 2s
[1.0]
timeout
4m 41s
[1.0]
7mu 66
[1.0]
B2328
iimouut
timoout
1-1
timeout
timeout
timeout
timeout
1
timeout
timeout
[-]
timeout
|-]
B2324
iimout
timoout
timeout
timeout
timeout
timeout
timeout
timeuut
timeout
82122
20x
0.21s
[0.1]
0.36s
[0.1]
2.00s
0.484
[0.n1]
0.48s
[0.1]
2.00s
0.366
[0.01]
0. 0.35s
[0.
92123
Im 30s
38.95s
[0.1]
1m 7s
[0.
Im 36s
Im 10s
[0.01]
Im 52s
[0.01]
1m 33s
59.63s
[0.01]
1m 30s
[0.1]
82133
timcout
7m 34s
[0.01]
4m 26s
[0.1]
timcout
7m 27%
[0.01]
14m 12s
[0.01]
timcout
12m 11s
[0.01]]
13m 40s
[0.01]
$2254
timcout
timcout
timcoot
timcout
timcout
tincour
timcout
timcout
timcout
$2264
timcout
timcout
timcout
timcout
timcout
Uincour
timcout
timcout
uimcout
RS212
2.00s
0.018
[1.0]
0.01s
[1.0]
2.00s
0.01s
[1.0]
0.03%
[10.0]
2.00s
0.01s
[1.0]
0.03s
[1.0]
RS222
3.00%
0.0
[1.0]
0.01s
[0.1]
3.00s
0.024
[10.0]
0.04s
[1.0]
3.00s
0.02s
[10.0]
0.03s
[0.03]
R8213
6m 51s
11.05s
[1.0]
10.24x
[1.0)
6m 27s
14.66s
[10.0]
12.83%
[1.0]
25x
9.00s
[1.0]
8.74s
[1.0]
R8223
8m 41s
5.79
[10.0]
10.49k
[1.0]
8m 24x
8.45K
[1.00
11.146
[1.0]
8m 54s
4.00s
[1:0]
7.02s
[1.0]
G.3.5
Results for NFCCERT solution concept
Maximize Player I''s utility
Maximize Player 2's utility
Maximize social welfare
Game
Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCFR*)
B2222
0.008
0.008
[1.0]
0.00s
[0.1]
0.008
0.008
[1.0]
0.00s
[0.1]
0.00s
0.00s
[0.01]
0.00s
[10.0]
B2522
0.00s
0.02s
[1.0]
0.02s
10.11
0.008
0.028
10.11
0.024
10.11
0.00s
0.01s
[0.01]
0.01s
[0.1]
B2323
2.00k
0.62s
[0.11
0.63s
[0.11
1.00%
0.48%
10.11
0.73s
10.11
2.00s
0.14s
[1.0]
0.18s
[0.1]
B2324
11.00k
4.8%
[0.1]
11.06s
[0.1]
11.00%
5.248
[0.1]
9.92c
[0.1]
10.00s
1.82s
[0.01]
2.51s
[1.0]
92122
0.00s
0.00%
[0:01]
0.00c
[0.01]
0.00s
0.00s
[0.01]
0.004
[0.1]
0.00s
0.00s
[1.0]
0.00s
[0.01]
$2123
0.00s
0.00%
[0:01]
0.00s
[0.01]
0.00s
0.01s
[0.01]
0.00s
[0.1]
0.00s
0.00s
[0.01]
0.00s
[0.01]
$2138
0.00s
0.01s
[0.01]
0.01s
[0.1]
0.00s
0.01s
[1.0]
0.01s
[0.1]
0.00s
0.01s
[0.1]
0.01s
[0.1]
$2254
25 00.00
1.23s
[0.01]
2.49s
[0.01]
24.00s
3.02s
[0.1]
3.02s
[0.1]
28 00.00s
1.32s
[0.1]
2.00s
[0.01]
$2264
$6.00s
2.71s
[0.1]
4.93s
[0.01]
42.00s
5.43s
[0.1]
6.88s
[0.01]
50.00s
2.73%
[0.1]
3.65s
[0.01]
RS212
0.00k
0.00g
[0.1]
0.00s
[10.0]
0.00s
0.008
[10.0]
0.00s
[0.1]
0.006
0.006
[0.1]
0.00s
[0.01]
RS222
0.00k
0.00x
[10.0]
0.00s
[1.0]
0.00s
0.00s
[10.0]
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.00s
[0.1]
R8213
0.00x
0.00k
[0.1]
0.00s
[0.01]
0.00s
0.00s
[10.0]
0.00s
[0.1]
0.00s
0.00s
[1.0]
0.00s
[0.01]
R8223
0.00s
0.00s
[1.0]
0.00s
[0.1]
0.00s
0.00s
[10.0]
0.01s
[1.0]
0.00s
0.00s
[0.01]
0.01s
[1.0]
G.3.6
Results for CCERT solution concept
Maximize Player I's utility
Maximize Player 2's utility
Maximize social welfare
Game
Ours (DCFR)
Ours (PCFR*)
LP Ours (DCFR)
Ours (PCFR")
LP
Ours (DCFR)
Ours (PCFR
B2222
0.00k
0.00%
[1.0]
0.01s
[1.0]
0.018
[1.0]
0.01s
[1.0]
0.00s
0.01s
[1.0]
0.01s
[1.0]
B2322
0.00k
0.078
[1.0]
0.22s
[1.0]
11.0]
0.34s
[1.0]
0.00ss
0.22s
[1.0]
0.33s
[1.0]
B2323
7.00k
3.75%
[1.0]
7.37%
[1.0]
4.69%
[1.0]
9.79s
[1.0]
5.39s
[1.0]
6.08s
[1.0]
B2324
limeout
54.92%
[1.0]
2x
[1.0]
immout
59.02%
[1.0]
1m
28s
[1.0]
iimout
31x
[1.0]
41x
[1.0]
82122
0.00%
0.00%
[1.0]
0.01s
[0.1]
0.00s
0.00s
[0.1]
0.004
[0.1]
0.00s
0.00s
[1:0]
0.01s
[0.
$2123
0.00s
0.01s
[1.0]
0.05s
[1.0]
0.00s
0.02s
[1.0]
0.03s
[0.1]
0.00s
0.01s
[1.0]
0.05s
[1.0]
$2133
1 1.00
0.04s
[1.0]
0.07s
[1.0]
1.00s
0.08s
[0.1]
0.094
[0.1]
1.00s
0.05s
[1.0]
0.11s
[1.0]
$2254
1m 41s
8.61s
[0.1]
15.31s
[0.1]
1m
478
25.
38,
[0.1]
23.28%
[0.1]
2m 3s
8.22s
[0.1]
16.08s
[0.1]
82264
Emcout
20.11s
[1.0]
23.99%
[0.1]
timoouu
1m 9%
[0.01]
1m
5s
[0.3]
limcout
16.50s
[0.1]
29.02s
[0.1]
RS212
0.00k
0.00%
[10.0]
0.00s
[1.0]
0.00x
0.008
[10.0]
0.004
[1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
R6222
0.00x
0.00%
[0.01]
0.00s
[10.0]
0.00%
0.00s
[1.0]
0.004
[1.0]
0.00s
0.00s
[0.01]
0.00s
[0.01]
R5213
0.00%
0.01s
[10.0]
0.01s
[1.0]
0.00%
0.01s
[1.0]
0.01s
[1.0]
0.00s
0.01s
[0.1]
0.0
[0.01]
R8223
0.00%
0.01s
[10.0]
0.01s
[1.0]
0.00s
0.01s
[1.0]
0.01s
[1.0]
0.00s
0.01s
[10.0]
0.0
[0.
33

---

G.3.7
Results for CERT solution concept
Game
Maximize Player I's utility
Maximize Player 2's utility
Maximize social welfare
LP
Ours (DCFR)
Ours (PCFR")
LP Ours (DCFR)
Ours (PCFR")
LP
Ours (DCFR)
Ours (PCFR
B2222
0.00s
0.01s
[1.0]
0,01s
[1.0]
0.00s
0.028
[1.0]
0.02s
[1.0]
0.00s
0.02s
[1.0]
0.03s
[1.0]
B2522
2.00s
1,05s
[1.0]
1.16s
[1.0]
2.00s
1.168
[1.0]
2.29
[1.0]
2.00s
1.24s
[1.0]
1,43s
[1.0]
B2323
40.00%
47.
[10.0]
1m 24
33.00s
58.20%
[1.0]
2m
14s
[0.1]
37.00s
46.51s
[1.00
40.45s
[1.0]
B2324
fimeout
8m 29k
[0.1]
timeout
timeout
timeout
timenut
timenut
6m 14s
[1:0]
timeout
$2122
0.00s
0.02s
[0.1]
0.02s
[1.0]
0.00s
0.02s
0.024
[0.1]
0.00s
0.02s
[1.0]
0.02s
[1.0]
$2125
1.00s
0.19
[0.1]
0.37s
1.00s
0.28s
[1.0]
0.31s
[0.1]
1.00s
0.15s
[1.0]
0.35e
[0.1]
$2133
3.00s
0.968
[1.0]
1.06s
[1.0]
2.00s
1.10s
1.18%
[0.1]
2.00s
0.92s
[0.1]
1.26s
[0.1]
92254
limcout
3m
[0.11
5m
[0:1]
Ummouu
6m
[0.11
[0.1]
timcout
42s
[0.1]
[0.1]
92264
limeout
timeout
timeout
Gmmoou
Emmout
timcout
timcout
timeout
timeout
AS212
0.00%
0.00%
[0.1]
0.00s
[1.0]
0.008
0.008
[10.0]
0.00s
[1.0]
0.00s
0.00s
[0.1]
0.00s
[0.1]
n8222
0.00s
0.00s
[1.0]
0.00s
[10.0]
0.008
0.008
[1.0]
0.00s
[1.0]
0.00s
0.00s
[0.01]
0.00s
[0.01]
R8213
0.00%
0.02s
[10.0]
0.03g
[1.0]
0.00s
0.02s
[1.0]
0.03c
[1.0]
0.00s
0.02s
[10.0]
0.02s
[0.
R8223
1.00%
0.018
[10.0]
0.02g
[1.0]
1.00s
0.028
[1.0]
0.03g
[1.0]
1.00s
0.01s
[0.1]
0.02%
[0.01]
G.4
Detailed breakdown by equilibrium and objective function (three-player games)
For each two-player game, we try three different objective functions: maximizing the utility of Player 1, maximizing the utility of Player 2, and maximizing the utility of Player 3. As in Ap- pendix G.3, for each objective we stop the optimization at the approximation level defined as 1% of the payoff range of the game.
For each game and objective, we report the same information as Appendix G.3.
G.4.1
Results for NFCCE solution concept
Maximize Player
utility
Maximize Player 2's utility
Maximize Player 3's utility
Game
LP Ours (DCFR)
Ours (PCFR) )
LP Ours (DCFR)
Ours (PCFR )
LP Ours (DCFR)
Ours (PCFR !
D32
0.00s
0.01s
[1.0]
0.01s
[1.0]
0.008
0.01s
[1.0]
0.01s
[10]]
0.006
0.01s
[1.0]
0.02s
[1.0]
D33
2m 17%
12.93s
[0.1]
43.45s
[0.1]
2m 8s
16.40s
[0.11
33.57s
[0.1]
2m 23s
17.57%
[0.31
36.55s
[1.0]
GLS
0.008
0.018
[1.0]
0.02s
[1.0]
0.00s
0.018
[1.0]
0.024
[1.0]
0.00s
0.02s
[0.1]
0.02s
[0.1]
X36
49.00k
0.76x
11.01
0.95s
[0.1]
55.00s
0.56x
11.01
1.155
[0.11
55 10:000
0.648
11.01
1.34s
[0.1]
L3132
0.59g
[0.1]
1.09s
24.00s
0.79%
[0.1]
1.28%
[0:1]
24.00s
0.778
[0.1]
1.18s
[0.1]
L3133
38.00
0.948
[0.1]
1,93s
[0:1]
38.00s
[0.1]
2.33s
[0.1]
37.00s
1.11s
[0.1]
1.79s
[0.1]
L3151
limeout
15.12s
[0.11
17.94s
10.11
Gimeout
12.748
[0.11
31.74s
[0.1]
timeout
18.03s
[0.1]
31.69s
[0.1]
L3223
4.00k
0.448
[0.1]
0.92s
[0.1]
4.00k
[0.1]
[0.1]
0.52s
[0.1]
1.26s
[0.1]
L3623
limeout
7%
[0.01]
1m
[0.01]
Limecut
1m 24
[0.01]
1m
[0.01]
timequt
[0.01]
44s
[0.01]
TP3
7.44s
[1.0]
10.71s
[10.0]
mm 40x
7.63%
[1.0]
11.09c
[10.0]
44s
11.45%
[10.0]
11.90s
[10.0]
G.4.2
Results for EFCCE solution concept
Maximize Player I's utility
Maximize Player 2's utility
Maximize Player 3's utility
Game
L.P Ours (DCFR)
Ours (PCFR-)
LP Ours (DCFR)
Ours (PCFR*)
I.P
Ours (DCFR)
Ours (PCFR*)
D32
0.00s
0.02s
[1.0]
0.02s [1.0]
0.00s
0.01s
[1.0]
0.02s [1.0]
0.00s
0.02s
[1.0]
0.03s [1.0]
D33
Emcout
Im 46s
[1.0]
4m 31s [0.1]
timcout
1m 16s
[1.0]
3m 56s
[1.0]
úincout
1m 44s
[1.0]
4m 56s
[1.0]
0L3
1.00
0.024
[1.0]
0.04s
[1.0]
1.00s
0.034
[1.0]
0.04s
[1.0]
1.00s
0.03s
[1.0]
0.04s
[10.0]
K35
46.0 004
0.674
[10.0]
1.69%
[0.
55.00s
0.754
[1.0]
1.69%
[0.1]
$1.00s
0.68s
[1.0]
2.02s
[0.1]
L3132
8m 43%
5.13g
[0.1]
9.57%
[1.0] 9m 17%
6.274
[0.1]
12.37%
[0.1] 9m 44s
7.76s
[0.]]
14.66%
[0.1]
L3133
20m 26s
8.88s
[0.1]
18.30s [0.1]
timevutt
8.19
[1.0]
18.09
[0.1]
23m 15x
10.86s
[1.0]
18.52s
[0.1]
13151
timenut
timenut
timenut
timervtt
timenvt
timenut
timenut
rimeaut
timecut
13223
Im 10s
2.94s
[0.1]
4.85% [0.1]
Im 10s
3.224
[0.1]
4.73%
[0.1]
3.24s
[o.
4.78s
[0.1]
L3523
timeour
timeout
timeout
timeout
timeout
timcout
timcout
timcout
TP3
Limecut
13.768
[10.0]
24.94s [1.0]
15.03s
[10.0]
28.28s
[1.0]
timcout
15.278
[10.0]
27.29s
[1.0]
34

---

G.4.3
Results for EFCE solution concept
Maximize Player I'ss utility
Maximize Player 2's utility
Maximize Player 3's utility
Game
IP
Ours (DCTR)
Ours (PCFR*)
LP| Ours (DCFR) Ours (PCFR*)
LP)
Ours (DCFR)
Ours (PCTR*)
D32
12.00s
0.76s
[1.0]
0.40s [1.0]
11.00s
0.35s
[1.0]
0.85s
[1.0]
10.00s
0.66s
[1.0]
0.80s [1.0]
D33
tmocou
timoout
[-]
timcoat
[-]
timcout
timcout
[-]
timcout
[-]
timcout
timeout
[-]
timcout
[-]
6L3
0.008
0.01s
[1.01
0.02s
[1.0|
0.00s
0.01s
[100]
0.02g
[0.1]
0.00s
0.01s
[1.01
0.02s
[1.0]
K35
57.00s
0.558
[1.0]
1,08s
[0.1]
55.00s
1.038
[1.0]
1.47s
[0.1]
60.00s
1.26s
[1.0]
1.778
[0.1]
L3132
8m 18s
6.108
10.11
7,85%
[0.1]
8m 57s
7.65s
10.11
12.08s
[0.1]
7m 35s
6.78s
[0.11
12.88s
[0.11
L3133
21m 25s
6.84s
[0.1]
12.97s
[0.1]
21m 43s
10.76s
[0.31
18.44s
[0.]]
19m 58s
10.28s
[0.1]
15.69
[0.11
L3161
timeout
timeout
timeout
timevut
ümevat
úmmout
timeout
timevut
timeout
L3223
2m 2%
5.52s
[0.1]
8.74x
[0.1]
Im 50s
6.46s
[0.1]
10.70s
[0.]]
2m
5.94s
[0.1]
10.65s
[0.1]
13523
timenut
timeout
timenut
timerutt
timenut
timenut
timeout
rimeout
timeout
TP3
timcout
13.468
[10.0]
20.25s
[1.0]
timcout
14.25%
[1.0]
22.19s
[10.0]
tincout
14.48s
[10.0]
21.28s
[1.0]
G.4.4
Results for COMM solution concept
Maximize Player I's utility
Maximize Player 2's utility
Maximize Player 3's utility
Game
Ours (DCFR)
Ours (PCFR*)
LP| Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCER*)
D32
0.00s
0.068 [1.0]
[1.0]
0.06s
[1.0]
0.18s [0.1]
1.00s
0.18s
[1.0]
0.178
[1.0]
D33
timeout
4m
[1.0]
9m
[1.0]
31s
[1.0]
[1.0]
Emmout
11.01
3m
[0.1]
limenut
7.72%
[0.1]
11.24k
[0.1]
[1.0]
11.02s
[1.0]
timenut
[1.0]
18.22
[0.1]
X36
1O00
0.03%
[1.01
0.036
10.11
1.00s
0.024
11.01
0.03s
[0.1]
1.00s
0.03s
11.01
0.04s
11.01
L3132
8.00%
3.46%
[0.1]
5.65%
[0.1]
8.00s
3.374
[0.1]
5.89%
[0.1]
7.00s
4.02s
[0.1]
8.38%
[0.1]
13133
12.00%
3.40
[0.1]
7.98%
[0.1]
12.00s
3.54s
[0.1]
7.89s
[0.
11.00s
3.52s
[0.1]
10.52s
[0.1]
13151
timenut
16.73s
[0.1]
18.42s
[0.1]
timenat
15.80
[0.1]
29.51s
[0.
timeour
18.0
18.00s
[0.1]
22.544
[0.1]
L3223
19.00s
18. 19%
[0.1]
29.24s
[0.01]
18.00s
15.30s
[0.1]
27. 27.38s
[0. 1]
21 00s
18:77s
[0.1]
25.91s
[0.01]
L3523
timcout
timcout
timcout
timcout
timcout
timcout
timcour
timcout
timcout
TP3
timenit
timenut
rimeout
timenat
timenat
timenat
timenut
timenut
rimeout
G.4.5
Results for NFCCERT solution concept
Muximize Player
utility Ours (PCFR*)
Maximize Player 2's utility
Maximize Player 3's utility
Game
LP Ours (DCFR)
LP Ours (DCFR)
Ours (PCFR-)
LP
Ours (DCFR)
Ours (PCFR*)
D32
0.00k
0.00k
[10.0]
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.00s [1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
D33
0.00x
0.04s
[1.0]
0.05s
[1.0]
0.00s
0.06s
[1.0]
0.06s [1.0]
0.00s
0.04s
[10.0]
0.05s
[10.0]
G1.3
0.00s
0.00s
[1.0]
0.00s
[1.0]
0.00s
0.008
[1.0]
0.006
[1.0]
0.00s
0.01s
[10.0]
0.00s
[1.0]
K35
0.00s
0.00s
[1.0]
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.004
[1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
L3132
0.00s
0.02s
[0.1]
0.02s
[1.0]
0.00s
0.02s
[0.1]
0.024
[0.1]
0.00s
0.02s
[0.1]
0.02s
[0.
L3133
0.00s
0.02s
[0.1]
0.02s
[0.1]
0.00s
0.02s
[1.0]
0.02s
[0.1]
0.00s
0.02s
[0.1]
0.03g
[1.0]
L3151
0.00s
0.03s
[0.1]
[0.1]
0.00s
[0.1]
[0.1]
0.00s
0.03s
[0.1]
0.04s
[0.1]
L3223
0.00s
0.03s
[0.1]
0.04s
[0.1]
[0.1]
0.00s
0.05s
[0.1]
0.05g
[0.1]
L3523
7.41s
[0.11
14.31s
15.00s
10.11
[0.3]
17.00s
10.60s
[0.01]
13.52x
[0.01]
TP3
47.00k
4.56%
[1.0]
10.06s
[10.0]
48.00%
[10.0]
[1.0]
7.38%
[10.0]
9.40s
[1.0]
35

---

G.4.6
Results for CCERT solution concept
Maximize Player I''s utility
Maximize Player 2's
Maximize Player 3's utility
Game
I.P
Ours (DCFR)
Ours (PCFR*)
T.P
Ours (DCFR)
Ours (PCFR*)
1.P
Ours (DCFR)
Ours (PCFR*)
D32
0.00s
0.00s
[1.0]
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
D33
1.00s
0.208
[1.0]
0.298
[1.0]
1.00s
0.138
[1.0]
[1.0]
1.00s
0.31s
[0.1]
0.19s
[0.1]
013
0.00k
0.01s
[0.11
0.01s
[1.0]
[1.01
0.01s
[1.0]
0.00s
0.01s|
[0.1]
0.01s
[1.0]
X35
0.008
0.008
[1.0]
0.00s
[1.0]
0.008
0.008
10.11
0.00s
[1.0]
0.00s
0.00s
[1.0]
0.00s
[1.0]
L3132
0.00k
0.06x
[0.1]
0.05s
[0:1]
0.008
0.05%
[0.1]
0.07%
[0.1]
0.00s
0.05%
[0.1]
0.06s
[0.1]
L3133
0.00k
0.04k
[0.1]
0.08c
[0.1]
0.00%
0.08%
[0.1]
0.114
[0.1]
0.00s
0.12%
[0.
0.15c
[0.1]
L3151
1.00%
0.12s
[0.1]
0.27c
[0.1]
1.00%
0.166
[0.1]
0.35c
[0.1]
1.00s
0.16s
[0.
0.33s
[0.1]
13223
1 1.00%
0.23%
[0.1]
0.52x
[0.1]
1.00s
0.266
[0.1]
0.43c
[0.1]
1.00s
0.24g
[0.1]
0.41s
[0.01]
13523
timeout
1m 17%
[0.01]
2m
47s
[0.01]
timeour
Im 166
[0.01]
3m
6s
[0.01]
timeout
1m 13s
[0.01]
2m
26s
[0.01]
TP3
tincouu
10.23s
[10.0]
18.00s
[1.0]
Lincouu
10.38s
[10.0]
19,88s
[10.0]
Lincour
11.958
[10.0]
25.89s
[10.0]
G.4.7
Results for CERT solution concept
Muximize Player
ulility
Muximize Player utility
Muximize Player 3's utility
Game
LP Ours (DCFR)
Ours (PCFR*)
LP
Ours (DCFR)
Ours (PCFR*)
LP Ours (DCFR)
Ours (PCFR*)
D32
0.00k
0.01s
[1.0]
0.01s
[1.0]
0.008
0.015
[1.0]
0.01s
[1.0]
0.006
0.01s
[1.0]
0.02s
[1.0]
D33
4.00%
3.14x
[1.0]
6.08s
[1.0]
4.00s
2.028
[1.0]
3.18%
[0.1]
4.00s
2.10%
[1.0]
3.89.
[0.1]
GL3
0.008
0.02s
11.01
0.03s
10.11
0.00s
0.028
11.01
0.036
[1.0]
0.00s
0.03s
10.11
0.03s
[0.1]
K35
0.00s
0.01s
[1.0]
0.01s
[1.0]
0.00s
0.00s
[1.0]
0.014
[0.1]
0.00s
0.00s
[1.0]
0.01s
[0.1]
L3132
1 1.00s
0.158
[0.1]
0.10s
1.00s
0.188
[0.1]
0.224
[0:1]
0.00s
0.18s
[0.1]
0.35s
[0.1]
L3133
1.00s
0.22s
[0.1]
0.42s
[1.0]
1.00s
0.19s
[0.1]
0.33s
[0:1]
1.00s
0.25s
[0.1]
0.38s
[0.1]
L3151
2.00s
0.218
[0.1]
0.42s
2.00s
0.228
[0.1]
0.445
[0.1]
2,00s
0.29%
[0.1]
0.53s
[0.1]
L3223
1.00s
0.61s
[0.1]
1.43s
[0.01]
0.61s
[0.1]
[0.01]
0.68s
[0.1]
0.98s
[0.01]
L3523
Eimeout
2m
[0.01]
timcout
Gimoou
4m
10.01]
dmcout
timeout
55s
[0.01]
dimcou
TPS
timcout
26.70%
[1.0]
40.73s
[1.0]
timcout
25. 28.088
[1.0]
35.99s
[10.0]
timcout
36.36s
[10.0]
1m
[1.0]
H Experimental results for binary search-based Lagrangian
In this section, we compare the performance of our "direct" Lagrangian approach against our binary search-based Lagrangian approach for computing several equilibrium concepts at the approximation level defined as 1 % of the payoff range of the game.
For each solution concept, we identify the same three objectives as Appendix G (maximizing each player's individual utility, and maximizing the social welfare in our two-player general-sum games). For each objective, each of the following tables compares three runtimes:
The time required by the linear program (column 'LP");
The time required by the "direct" (non-binary search-based) Lagrangian approach, taking the fastest between the implementations using DCFR and PCFR as the underlying no- regret algorithms (column 'Lagrangian').
The time required by the binary search- baacch Lagrangian approach, taking the fastest be- tween the implementations using DCFR and PCFR + as the underlying no-regret algorithms (column Searche.
We observe that our two approaches behave similarly in small games. In larger games, especially with three players, the direct Lagrangian tends to be 2-4 times faster.
36

---

H.1
Detailed Breakdown by Equilibrium and Objective Function (Two-Player Games)
H.1.1
Results for NFCCE solution concept
Maximize Pl. utility
Maximize utility LP Lagrangian Bin.Search
Maximize social welfare
Game
LP Lagrangian Bin.Search
LP Lagrangian Bin.Search
B2222
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
B2322
0.00s
0.038
0.048
0.00%
0.04s
0.03s
0.00s
0.01s
0.01s
B2323
7.00s
1.05s
1.67s
6.00s
1.01s
1.23s
6.00s
0.33s
0.17s
B2324
50.00s
15.57s
18.23s
37.00s
20s
11.11s
38.00s
2.73s
1.4ls
92122
0,00s
0.00s
0.00s
0.00s
0.00s
0.00s
0,00s
0.00s
0.00s
$2123
0.00s
0.01s
0.018
0.00s
0.00s
0.01s
0.01s
82133
1.00s
0.02s
0.03s
1 1.00s
0.02s
0.02s
1.00s
0.02s
0. 0.02s
92254
2m Is
6.96s
6.038
Im 14s
10.43s
7.12s
Im 58s
7.43s
3.64s
$2264
3m 368
13.96s
7.648
2m 24s
18.46s
14.57%
43s
11.74s
7.69s
RS212
0,00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
RS213
timeout
34.52s
28.65s
timcout
20. 29:29s
26.25s
timcout
14. 68s
7.44s
RS222
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
RS223
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timoout
timeout
H.1.2
Results for EFCCE solution concept
Maximize PL. I's utility
Maximize PI. 2's utility
Maximize social welfare
Game
LP Lagrangian Sin.Scarch
LP Lagrangian Sen.Search
Lagrangian Bin.Search
B2222
0.00s
0.01s
0.01s
0.00s
0.01s
0.01s
0.00s
0.01s
0.01s
B2322
3.00s
0.41s
0.54s
3.00s
0.69s
0.60s
3,00s
0.69s
0.41s
B2323
mm
9.11s
16.32s
30s
12.
8.62s
21s
14.23s
6.89s
B2324
timcout
Im 53s
2m 5s
timcout
2m 44s
3m 14s
timcout
3m Is
Im 27s
92122
0.00s
0.01s
0.00s
0.00s
0.00s
0.00s
0.00s
0.01s
0.00s
$2123
1.00s
0.038
0.048
1.00s
0.05s
0.04s
1.00s
0.06s
0.03s
$2133
3.00s
0.12s
0.11s
2.00s
0. 20s
0.32s
3.00s
0.1 1s
0.22s
92254
timcout
2s.31s
30.66s
timcout
37.43s
Im
timcout
22.01s
36.62 36.62s
92264
timcout
46.07s
Im 98
timcout
2m
Im 26s
timcout
39.23s
Im 4s
R8212
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
R8213
timeout
28. 80s
36.02s
timeout
31.02
29
timeout
15.54s
9.
RS222
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
RS223
timeout
timeout
timoout
timeout
timeout
timeout
timcout
timcout
timeout
H.1.3
Results for EFCE solution concept
Maximize Pl, I'ss utility
Maximize Pl, 2's utility
Maximize social welfare
Game
LP Lagrangian Sen.Scurch
LP Lagrangian Sen.Search
LP Lagrangian
SearSh
B2222
0.00s
0.01s
0.02s
0.00s
0.05s
0.01s
0.00s
0.02s
0.02s
B2322
9.00s
1.23s
4.49s
9.00s
4.63s
2.04s
9.00s
1.60s
1.57s
B2323
3m 54s
48.40s
Im 44s
4m
Im 27s
40.91s
3m 40s
44.87s
Im 19s
B2324
timeout
9m 38
16m 45s
timeout
10m 21s
13m 15s
timeout
10m 48s
8m 12s
$2122
0.00s
0.01s
0.00s
0.0
0.00s
0.02s
0.01s
$2123
1.00s
0.09s
0.06s
1.00s
0.34s
0.10 10.0s
1.00s
0.15s
0.08s
82133
4.00s
0.52s
0.32s
3.00s
1.31s
0.77%
3.00s
0.49%
0.43s
$2254
timeout
10s
19%
timcout
timeout
4m Is
timeout
3m 34s
2m 10s
S2264
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
RS212
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
R8213
timcout
35.37s
34.00s
timoout
22.49s
36.52s
timcout
23.37s
22. 16s
RS222
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
R8223
timeout
timcout
timeaut
37

---

H.1.4
Results for COMM solution concept
Maximize PL. I's utility LP Lagrangian Bin.Search
Maximize Pl, 2's utility
Maximize social welfare
Game
LP Lagrangian Ben.Search
LP Lagrangian Bin.Search
B2222
2.00s
0.88s
3.39%
2.00s
0.89%
2.70s
2,00s
1.49%
2. 2.80s
B2322
47s
timoout
10m
timeout
4m
7m
82323
timcout
timoout
timeout
tmmout
timeout
timeout
timcout
timcout
timcout
82324
timoout
timeout
timeout
timcout
timcout
timcout
timeout
timcout
timcout
92122
2.00s
0.21s
0.42s
2.00s
0.48s
0.28s
2.00s
0.35s
0.40s
$2123
1m 30s
38, 9.5
Im 368
Im 36s
1m 10s
1m 7s
1m 33s
59.6.3
51.54s
$2133
timcout
4m 26s
10m 23s
tmcout
27s
timcout
12m 1
5m 57s
92254
timcout
timeout
timoout
imoout
timoout
timeout
timcout
timcout
timcout
82264
timeout
timeout
timeout
timeout
timeout
timeout
timeout
tmeout
timeout
R8212
2.00s
0.018
2.00s
2.00s
0.01s
0.00s
R8213
6m 51s
10.24s
18.82s
6m 27s
12.83s
24.61s
6m 25s
8. 8.74s
8. 18s
RS222
3.00s
0.01s
0.01s
3.00s
0.02s
0.02s
3,00s
0.01s
0.01s
RS223
8m
5.79s
9.71s
8m 24s
8.45s
12.948
8m 54s
4.00s
4.54s
H.1.5
Results for NFCCERT solution concept
Maximize Pl. I's utility Maximize Pl. 2's utility
Maximize social welfare
Game
LP Lagrangian Bin.Seurch
LP Lagrangian SearCharch
LP Lagrangian
Sen.Scarch
B2222
0,00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
B2322
0.00s
0.02s
0.03s
0.00s
0.02s
0.02s
0.00s
0.01s
0.00s
B2323
2.00s
0.62s
0.648
1.00s
0.48s
0.51s
2.00s
0.14s
0.08s
B2324
11.00s
4.88s
9.86s
11.00s
5.24s
6.26 26s
10.00s
1.82s
0. 0.70s
92122
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
$2123
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
82133
0.00s
0.01s
0.00s
0.00s
0.01s
0.01s
0.00s
0.01s
0.00s
$2254
25.00s
1.238
0.84s
24.00s
3.02s
2.41s
28.00s
1.32s
0.70s
S2264
56.00s
2.71s
1.72s
42.00s
5.43s
3.81s
50.00s
2.73s
1.24s
0.00s
0.00s
U213
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
U222
0,00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.01s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
H.1.6
Results for CCERT solution concept
Maximize PL I's utility
Maximize PI, 2's utility
Maximize social welfare Lagrangian SenrSh
Game
LP Lagrangian Bin. Ben.Seurch
LP Lagrangian Search
B2222
0,00s
0.00s
0.01s
0.00s
0.01s
0.00s
0.00s
0.01s
0.00s
B2322
0.00s
0.07s
0.1
0.00s
0.15s
0.09s
0.00s
0.22s
0.09s
B2323
7.00s
3.758
3.558
6.00s
4.69%
3.54s
8.00s
5.39s
2.64s
B2324
timeout
54.92s
49.66s
timoout
59.02s
59.88s
timeout
Im 31s
3s
92122
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
52123
0.00s
0.01s
0.02s
0.00s
0.02s
0.02s
0.00s
0.0
0.02s
82133
1.00s
0.04s
0.048
1.00%
0.08s
0.06s
1.00s
0.05s
0.03s
92254
1m 41s
8.61s
11.29s
Im 47s
23.28s
16.40s
3s
8.22s
16.31s
S2264
timcout
20.1
21.42s
timeout
Im 5s
38.76s
timeout
16.50s
20.62s
RS212
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
R8213
0.00s
0.01s
0.00s
0.00s
0.01s
0.01s
0.00s
0.01s
0.00s
R8222
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
RS223
0.00s
0.01s
0.01s
0.00s
0.01s
0.01s
0.00s
0.01s
0.00s
38

---

H.1.7
Results for CERT solution concept
Maximize Pl. I's utility
Maximize Pl. 2's utility
Maximize social welfare
Game
LP Lagrangian Bin.Scarch
I.P Lagrangian Bin.Search
I.P Lagrangian
Ben.Search
B2222
0.00s
0.018
0.00s
0.00s
0.02s
0.02s
B2322
2,00s
1.05s
0.958
2.00s
1.16s
0.66s
2.00s
1.24s
1.20s
B2323
40.00s
47.11s
21.54s
33.00s
58.20s
22.16s
37.00s
40.45s
59.67s
B2324
timeout
29%
38s
timcout
timeout
timeout
6m 14s
4m
82122
0,00s
0.02s
0.01s
0.00s
0.02s
0.01s
0.00s
0.02s
0.01s
82123
1.00s
1.19
0.09s
1.00s
0.28s
0.20s
1.00s
0.15s
0. 0.12s
$2133
3.00s
0.968
0.438
2.00s
1.10s
1s
2.00s
0.92s
0.41s
92254
timcout
3m 268
2m 54s
timcout
6m 15s
4m 14s
timeout
2m 42s
2m 53s
82264
timcout
timcout
timeout
timcout
timcout
timcout
timcout
timcout
RS212
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
R$213
0.00s
0.02s
0.038
0.00s
0.02s
0.04s
0.00s
0.02s
0.01s
R8222
0.00s
0.00s
RS223
1.00s
0.01s
0.02s
1.00s
0.02s
0.02s
1.00s
0.01s
0.01s
H.2
Detailed Breakdown by Equilibrium and Objective Function (Three-Player Games)
H.2.1
Results for NFCCE solution concept
Maximize Pl. utility
Maximize 2's utility
Maximize 3's utility
Game
LP Lagrangian Bin.Search
LP Lagrangian Bin.Search
LP Lagrangian Bin.Search
D32
0.00s
0.018
0.028
0.00s
0.01s
0.02s
0.00s
0.01s
0.02s
D33
2m 17s
12.938
21.468
2m 8s
16.40s
28.63s
2m 23s
17.57s
19.74s
GL3
0.00s
0.01s
0.02s
0.00s
0.01s
0.02s
0.00s
0.02s
0.02s
K35
49.00s
0.76s
1.52%
55.00s
0.56s
1.39%
55,00s
0.64s
1.67s
L3132
26.00s
0.59%
1.728
24.00s
0.79%
1.633
24.00s
0.77s
1.91s
L3133
38.00s
0.94s
1.79s
38.00s
0.89s
1.8.3
37.00s
1.1
1.90s
L3151
timcout
15. 12s
30.01s
timcout
12.74s
35.58s
timcout
18.03s
30.87s
L3223
4.00s
0.44s
0.918
4.00s
0.45s
1.84s
4.00s
0.52s
1.58s
L3623
timeout
1m 7s
4m 21s
timeout
1m 2s
4m 27s
timeaut
1m 9s
4m 35s
TP3
Im
7.44s
8.43s
Im 40s
7.63s
9.41s
44s
11.45s
11.85s
H.2.2
Results for EFCCE solution concept
Maxinize PL. I's utility
Maximize Pl. 2's utility
Maximize Pl. 3's utility
Game
Lagrangian Bin Search
LP Lagrangian Searcha
LP Lagrangian SenrSharch
D32
0.00s
0.02s
0.03s
0.00s
0.01s
0.03s
0.00s
0.02s
0.03s
timeout
46s
2m 32s
timeout
28s
timcout
Im
3m 7s
GL33
1.00s
0.02s
0.04s
L.00s
0.03s
0.05s
1.00s
0.03s
0.05s
K35
46.00s
0.674
2.09s
$5.00s
0.75%
$1.00s
L3133
8m 43s
5.13%
18.75%
9m 17s
6.27%
13.4%s
9m 44%
7.76s
18. 18.47%
L3133
20m
8.88s
19.52s
timeout
8.19s
23.17s
15s
10.86s
27.48s
L3151
timcout
timeout
timeout
timeout
timcout
timcout
timcout
timeout
timecut
L3323
1m 10x
2. 2.944
14.79
1m 10s
3.22s
12.23
1m 2s
3.24%
13.6%%
L3623
timeout
timeout
timeout
timeout
timenut
timeout
timeaut
timeout
timeout
TP3
timeout
13.76s
15.36s
timeout
15.03s
13.64s
timeout
15.27%
15. 10s
39

---

H.2.3
Results for EFCE solution concept
Maximize Pt. I's utility
Maximize Pl. 2's utility
Maximize PL. 3's utility
Game
LP Lagrangian Bin Search
LP Lagrangian Bin.Search
LP Lagrangian Bin.Search
D32
12.00s
0.40s
1.11s
11.00s
0.35s
1.32s
10.0s
0.66x
1.23s
D33
timeout
timenut
GL3
0.00s
0.01s
0.03s
0.00s
0.01s
0.038
0.00s
0.01s
0.06s
K35
57.00s
0.55s
1.50s
55.00s
1.03s
2.37%
60.00s
1.26s
2.22s
L3132
8m 18s
6.10s
14.02s
8m 57s
7.65s
16.25s
7m 35s
6.78s
19.11s
L3133
6.84s
25.8
10.28<
L3151
timenut
timeout
timcout
timeout
timeout
timeout
timenut
timenut
timeout
L3223
2m 2s
5.52s
28. 28.79s
1m 50s
6.46s
29.37s
2m Os
5,94s
17.13s
L3523
timenut
timeout
limenut
TP3
timeout
13.46s
13.78s
timeout
14.25%
13.71s
timeout
14.48s
11.48s
H.2.4
Results for COMM solution concept
Maxinize Pl. I''s utility
Maxinize Pl. 2's utility
Maximize Pl. 3's utility
Game
LP Lagrangian Bin.Scurch
LP Lagrangian Ben.Search
Lagrangian
SearSh
D32
0.00s
0.06s
0.248
1.00s
0.06s
0.21s
1.00s
0.17s
0.32s
37s
5m 35s
imcout
4m
tmoout
2m 38s
5m 21s
GL3
tmcoutt
7.72s
26.48s
timoutt
7.50s
21.91s
timoout
11.42s
25.446
K35
1.00s
0.03s
0.07s
1.00s
0.02s
0.07s
1.00s
0.03s
0.05s
L3332
8.00s
3.468
10.648
8.00s
3.37s
8.44s
7.00s
4.02s
9.57s
L3133
12.00s
3.40s
12.82s
12.00s
3.54s
10.70s
11.00s
3.52s
12.35s
L3151
timcout
16.738
55.5
tmmouu
15,80s
57.66s
timcout
18.00s
56.83s
L33233
19.00s
18. 19h
m 0s
18.00s
15. 30s
1m 17s
21.00s
18.77s
57.1 1s
L3523
timcout
timoout
timoout
timcout
timeout
timoout
timcout
timcout
TP3
timcout
timeout
timeout
timcout
timeout
timeout
timeout
timcout
timcout
H.2.5
Results for NFCCERT solution concept
Maximize PL I's utility LP Lagrangian BeacSharch
Maximize Pl. 2's utility
Maximize PL. 3's utility
Game
LP Lagrangian SearCh
Lagrangian Ben.Search
D32
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
D33
0.00s
0.04s
0.05s
0.00s
0.06s
0.05s
0.00s
0.04s
0.03s
GL.3
0.00s
0.00s
0.01s
0.00s
0.00s
0.01s
0.00s
0.00s
0.01s
K35
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
L3132
0.00s
0.02s
0.03s
0.00s
0.02s
0.02s
0.00s
0.02s
0.03s
L3133
0.00s
0.02s
0.03s
0.00s
0.02s
0.04s
0.00s
0.02s
0.04s
L.3111
0.00s
L32223
0.00s
0.03s
0.06s
0.00s
0.04s
0.05s
0.00s
0.05s
0.08s
L3523
13.00s
7.41s
13.51s
15.00s
8.17s
16.32s
17.00s
10.60s
22.93s
IP3
47.00s
4.56s
4.98s
48.00s
4.97s
8.s
45.00s
7.38s
7.50s
40

---

H.2.6
Results for CCERT solution concept
Maximize Pl. I's utility
Maximize Pl. 2's utility
Maximize Pl. 3's utility
Game
Lagrangian Bin Seurch
LP Lagrangian Ben.Search
Lagrangian Bin.Search
D32
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
D33
1.00s
0.20s
0.27s
1.00s
0.13s
0.32s
1.00s
0.19s
0.25s
G13
0.00s
0.01s
0.02s
0.00s
0.01s
0.02s
0.00s
0.01s
0.01s
K35
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
0.00s
L3132
0.00s
0.05s
0.08s
0.00s
0.05s
0.098
0.00s
0.05s
0.07s
L3133
0.00s
0.04s
0.136
0.00s
0.08s
0.20s
0.00s
0.12s
0.09s
L3151
1.00s
0.12s
0.36s
1.00s
0.16s
0.32s
1.00s
0.16s
0.31s
L3223
1.00s
0.23s
0.72s
1.00s
0,26s
0.58s
1.00s
0.24s
0.67s
L3523
timeout
17s
3m
timcout
timcout
Im 13s
6m
TP3
timcout
10.23s
16.79s
timcout
10.38s
12.96s
timcout
11.958
11.918
H.2.7
Results for CERT solution concept
Maximize Pl. utility
Maxinize 2's utility
Maxinize 3's utility
Game
I.P Lagrangian Bin.Scarch
I.P Lagrangian Ben.Search
I.P Lagrangian Bin.Search
D32
0.00s
0.00s
D33
4.00s
3.14s
7.11s
4.00s
2.02s
2.26s
4.00s
2.10s
9.88s
GL3
0.00s
0.02s
0.048
0.00s
0.02s
0.05s
0.00s
0.03s
0.05s
K36
0.00s
0.01s
0.01s
0.00s
0.00s
0.018
0.00s
0.008
0.01s
L3132
1.00s
1.00s
0.00s
0.18s
L3133
1.00s
0.22s
0.41s
1.00s
0.19
0.44s
1.00s
0.25s
0. 0.30s
L3151
2.00s
0.21s
0.86s
2.00s
0.22s
0.75s
2.00s
0.29s
0.72s
L3223
1.00s
1.00s
0.68%
1.95s
L3523
timeout
2m 58s
timeout
timeout
4m 33s
timeout
timeout
3m 55s
timeout
TP3
timeout
26.70s
34.23s
timcout
25.08s
28.22s
timcout
36.36s
27. 68.
41


Reviews:
[{"review_id": "k0PMkKhkOm", "reviewer": "Reviewer_dPXL", "summary": "This paper presents a novel approach to compute optimal equilibria in multi-player extensive-form games through the use of Lagrangian relaxation as a two-player zero-sum extensive-form game. Building upon the mediator augmentation game framework, the proposed computing approach significantly contributes to the reduction of zero-sum games, thereby holding substantial implications for mechanism design and information design. Furthermore, it plays a pivotal role in fostering a well-balanced hierarchy of concepts.\n\n", "questions": "Why does the space of messages can be restricted by using the revelation principle? I think more details on this are necessary in the paper.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-- The investigation of computing minimax equilibria in extensive-form games is an interesting and well-motivated problem.\n\n-- Most correlation equilibrium notions pose challenges in finding optimal equilibria, whereas the framework presented in this paper offers a learning-based algorithm to compute them.\n\n", "weaknesses": "-- The paper lies heavily on notation that lacks intuitive explanations. To enhance reader understanding, a schematic representation of the mediator-augmented game framework should be included in the main body. \n\n-- The approach proposed in this paper resembles a transformation of the original game into a mediator-led Stackerberg game. It would be beneficial to discuss and compare existing research on equilibrium solutions for zero-sum games in Stackelberg games to provide a contextual background for the paper's contribution. Lack controlled experiments involving additional algorithms for equilibrium solutions in Stackelberg games.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review!\n\n> The paper lies heavily on notation that lacks intuitive explanations. To enhance reader understanding, a schematic representation of the mediator-augmented game framework should be included in the main body.\n\nThank you for the suggestion; we will incorporate this and other clarity recommendations from the other reviews in the final version.\n\n> The approach proposed in this paper resembles a transformation of the original game into a mediator-led Stackerberg game. It would be beneficial to discuss and compare existing research on equilibrium solutions for zero-sum games in Stackelberg games to provide a contextual background for the paper's contribution. Lack controlled experiments involving additional algorithms for equilibrium solutions in Stackelberg games.\n\nStackelberg equilibria in extensive-form games are hard to find in general [1]. Our Stackelberg game has a much nicer form than general Stackelberg games—in particular, we know in advance what the equilibrium strategies will be for the followers (namely, the direct strategies, $d_i$). This observation is what allows the reduction to zero-sum games, sidestepping the need to use Stackleberg-specific technology or solvers. We will expand the discussion about the relationship with Stackelberg games in Appendix B (L722) to include this and make sure it is comprehensive. \n\n[1] J Letchford and V Conitzer “Computing Optimal Strategies to Commit to in Extensive-Form Games”, EC 2010\n\n> Why does the space of messages can be restricted by using the revelation principle? I think more details on this are necessary in the paper.\n\nThe *purpose* of the revelation principle is precisely to reduce the message space: the revelation principle states that, without loss of generality, players in equilibrium will send their true information and obey action recommendations. This allows a reduction of the message space, because then we can assume that messages to the mediator are information reports, and messages from the mediator are action recommendations. We will add a note about this in the final version.\n"}, {"review_id": "sUYU4pZOl3", "reviewer": "Reviewer_c3NQ", "summary": "This paper studies the computation of optimal equilibria in multi-player extensive-form games via no-regret learning algorithms. The key idea is to take the constrained LP formulation of the optimal equilibrium problem proposed by Zhang and Sandholm and consider the saddle point formulation, which can then be solved using no-regret learning algorithms. In order to alleviate the large $\\lambda^*$, a binary-search based algorithm is proposed. Finally, the algorithms are compared with a LP-based method on several tabular games as well as for an auction-design problem.", "questions": "Have the authors tried gradient based methods (such as extra-gradient or gradient descent-ascent) on the saddle-point problem (L1)?", "limitations": "This paper does not have foreseeable negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written. The results presented clearly and the writing is easy to follow.\n\n- The experimental results seem compelling as it has an order of magnitude advantage in wall-clock time over the LP-based method. This advantage is consistent across a set of diverse instances.", "weaknesses": "- I have some concerns about the LP formulation (G). Consider a $N$ player normal form game with $A$ actions per player for instance; it seems that for the correlated equilibrium in such a game, the $\\mu$ in (G) would need to have dimension $A^N$. However, no swap-regret algorithms can find an approximate correlated equilibrium with $\\tilde{O}(NA^2/\\epsilon^2)$ samples. It seems that the LP formulation (G) can lead to suboptimal dependence on the number of players.\n\n- Perhaps related the previous point, while in Line 79 the authors claim that \"Our algorithm significantly outperforms existing LP-based methods\", in the experiments it is only compared against the LP based solution to (G) proposed by Zhagn and Sandholm. Is (G) the only known LP formulation of the optimal equilibrium problem? If not, wouldn't it make sense to compare against those as well?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review!\n\n> I have some concerns about the LP formulation (G).\n\nThere is an important detail that might have been missed here. The cited no-swap-regret dynamics compute one equilibrium, but this paper is concerned with optimizing over the space of equilibria (for example, to compute a social-welfare-maximizing equilibrium). The latter problem is harder than the former, and explains the difference in dependence.\n\n> Perhaps related the previous point, while in Line 79 the authors claim that \"Our algorithm significantly outperforms existing LP-based methods\", in the experiments it is only compared against the LP based solution to (G) proposed by Zhagn and Sandholm. Is (G) the only known LP formulation of the optimal equilibrium problem? If not, wouldn't it make sense to compare against those as well?\n\nYes, the LP of Zhang and Sandholm is, to our knowledge, the only LP formulation of the optimal equilibrium problem in its full generality. That said, for several of the concepts (e.g., mechanism design in single-stage settings [2]), the LP of Zhang and Sandholm is equivalent to previously-known techniques. The paper of Zhang and Sandholm itself contains more details.\n\n[2] V Conitzer and T Sandholm, “Complexity of mechanism design”, UAI 2002\n\n> Have the authors tried gradient based methods (such as extra-gradient or gradient descent-ascent) on the saddle-point problem (L1)?\n\nCFR itself can be viewed as a gradient-based method. Other gradient-based methods, such as those that you mention, certainly can be used to solve any zero-sum game, including (L1). In practice, there is a long line of research (e.g., [3, 4] and references therein) that consistently establishes the CFR variants that we chose as the fastest methods of solving large tabular extensive-form games, so in our experiments we focus on these methods.\n\n[3] G Farina, C Kroer, and T Sandholm, “Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent”, AAAI 2021\n\n[4] N Brown and T Sandholm, “Solving Imperfect-Information Games via Discounted Regret Minimization”, AAAI 2019\n\n"}, {"review_id": "qQlHyC7AlM", "reviewer": "Reviewer_JN1n", "summary": "The paper focuses on addressing the challenge of computing optimal equilibria in extensive-form games. The authors introduce the revelation principle, which transforms the problem into a linear programming (LP) task. \n\nThey propose using Lagrange relaxations to solve the LP, treating the resulting saddle-point problem as a Nash equilibrium in a zero-sum two-player game. The authors explicitly construct such zero-sum game. To efficiently find the solution, the authors employ regret minimization over conic hulls. Additionally, they highlight the flexibility of their approach by showing that other algorithms for zero-sum two-player games can be utilized, offering different convergence rate guarantees or achieving last-iteration convergence. \n\nThe paper concludes with thorough experimental evaluations, demonstrating the effectiveness and scalability of their proposed methods across various simple games.", "questions": "- See the above weakness.\n\n- What does 'optimal direct equilibria' mean in line 162. Moerover, if the revelation principle fails, there's no fixed pure strategy d_i. In this case, how to get a similar problem of (G).\n\n- In the experiment of auction design, to demonstrate scalability, is it possible to conduct an experiment if each bidder's valuation is sampled from uniform distribution in [0,1]. ", "limitations": "The authors have partially addressed the limitations of their work, though there is space for improvement (see the section Weaknesses and Questions).\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses the significant problem of computing optimal equilibria in game theory. By reducing this problem to zero-sum games, the authors provide a framework for finding optimal equilibria. The key contribution lies in the fact that existing algorithms for zero-sum extensive form games can be directly applied to this problem. This reduction greatly enhances the understanding and applicability of the proposed approach.\n\n- The experimental evaluation conducted by the authors is robust and contributes to the strength of their work. They provide evidence of the scalability of their methods through preliminary experiments. This not only showcases the effectiveness of the proposed techniques but also demonstrates their potential for real-world applications. The inclusion of experimental results further reinforces the practical relevance of the research and adds value to the overall paper.", "weaknesses": "My only concern is about the revelation principle. The reduction in the paper relies on the revelation principle, which is a fundamental concept. However, it is not clear regarding the specific conditions under which a fixed pure strategy d_i exists for different players and within which games and equilibria this concept applies.  Additionally, how to effectively find such d_i strategies is also a problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review!\n\n> My only concern is about the revelation principle. The reduction in the paper relies on the revelation principle, which is a fundamental concept. However, it is not clear regarding the specific conditions under which a fixed pure strategy d_i exists for different players and within which games and equilibria this concept applies. Additionally, how to effectively find such d_i strategies is also a problem.\n\nThe revelation principle holds for all the equilibrium concepts referenced in the paper, and indeed in all of those cases, the direct strategy d_i is trivial to define (report honest information and play recommended actions). \n\n> What does 'optimal direct equilibria' mean in line 162. Moerover, if the revelation principle fails, there's no fixed pure strategy d_i. In this case, how to get a similar problem of (G).\n\nThe pure strategy d_i can be defined regardless of whether the revelation principle holds: it is, as above, simply “report honest information and play recommended actions”. An “optimal direct equilibrium” is an equilibrium that is optimal among direct equilibria, that is, equilibria of the form (μ, d). Without the revelation principle, such equilibria can still exist, and our method will still recover the optimal such equilibrium (if one exists). However, without the revelation principle, there would be no guarantee that the optimal direct equilibrium will exist or that it will also be the (overall) optimal equilibrium, as there could be an indirect equilibrium that is better. We leave the problem of generalizing our methods to such cases as an interesting future research direction.\n\n> In the experiment of auction design, to demonstrate scalability, is it possible to conduct an experiment if each bidder's valuation is sampled from uniform distribution in [0,1].\n\nThank you for this experiment idea. While our current paper's scope does not include such extensive experimentation, we agree that this experiment could provide additional evidence for our method being scalable in future work. We believe that our existing methodology adequately supports our findings, but this additional analysis could be a valuable extension in subsequent research that scales our method to much larger games. "}, {"review_id": "HmbSBIpFMk", "reviewer": "Reviewer_dGJ5", "summary": "The authors proposed a learning-based framework to solve for optimal equilibria in n-player general-sum extensive-form games. The key idea is to leverage Lagrangian relaxation and convert such games to 2-player zero-sum extensive-form games which can then be solved using known learning methods that solve for minimax equilibria. ", "questions": "I find the presentation relatively easy to follow. Some minor clarifying questions below: \n\nL42: \"... including information design, and solution concepts such as ....\". This statement appears several times but it is a bit confusing to follow. I can understand the statement after reading the paper in full but consider rephrasing it or splitting it up to make it more readable? \n\nL63 nit: clarify what $T$ stands for. \n\nL145: I find the discussion on the revelation principle interesting but it's not clear how general it would apply to games. Could you comment on this and if the set of benchmark games studied in this work would satisfy this property? \n\nL191: \"All players, ... are constrained to [act/play, missing] according to $d_i$...\" is mediator considered to be included in \"All players\" in this statement? If so, what does playing according to $d_i$ mean for the mediator? Is the mediator limited to deterministic policies in this two-player game? \n\nL192: \"If nature picked ..., the utility is ...\", --> \"the utility [to the mediator] is ...\"?\n", "limitations": "The authors have discussed practical limitations of the method in snippets of the main text.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* significance\nI believe this work could be a significant contribution to the field as it proposes a computationally practical method that solves for optimal equilibria in n-player general-sum games. This is significant as it offers a language to speak about optimality of equilibria in addition to stability and could make game theoretic methods attractive in wider classes of practical applications. \n\n* originality\nI believe the proposed method is novel. \n\n* clarity\nThe paper is well written and relatively easy to follow. \n\n* quality\nThe theoretical derivation of the method appears sound; the empirical results seem extensive though it would be interesting to understanding additional details which I have commented below.  ", "weaknesses": "The presentation of the empirical results seems to be primarily focused on the efficiency and feasibility of converting the problem of solving for optimal equilibria in n-player general-sum EFGs to solving minimax equilibria in two-player zero-sum games. For instance Table 1 presented runtime results of the learning-based method compared to solving LP directly. \n\nWould it be possible to provide additional details on optimality as well especially in general-sum games such as Sheriff where we know the value of max-welfare equilibria (e.g. https://www.cs.cmu.edu/~gfarina/2020/efcce-aaai20/coarse-correlation.aaai20.pdf)? Would the proposed method scale up to these instances of sheriff game? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review!\n\n> Would it be possible to provide additional details on optimality as well especially in general-sum games such as Sheriff where we know the value of max-welfare equilibria (e.g. https://www.cs.cmu.edu/~gfarina/2020/efcce-aaai20/coarse-correlation.aaai20.pdf)?\n\nSheriff games are known to be triangle-free, since they are two-player games with no chance moves. For this class of games, the polytope of all EFCE can be described using a polynomial number of constraints. Both our paper and the paper by Farina et al. that you linked are able to take advantage of this fact and lead to a polynomial-time optimization algorithm. For our algorithm, the majority of the time is spent allocating memory for constructing the internal representation of the set of equilibria used in the learning procedure. We similarly guess that the algorithm by Farina et al. a large fraction of time is spent computing the constraints that define the same set, though expressed as linear constraints passed to the linear programming solver. \n\nAs an example, we run our framework on one of the large Sheriff instances used by Farina et al. In particular, we employed the instance S2-20-5-4 (line 4 of Table 1 in the paper linked). Computing a social-welfare-maximizing NFCCE using our framework requires a learning phase of 110 sec (3 minutes if we consider also the time to construct the representation). The paper by Farina et al. requires around 13min to solve the same instance. On the same instance, we compute a SW-maximizing EFCCE in 99 seconds (6 minutes if we consider the construction of the internal representation), while Farina et al. report an execution time of 1h34min. For both solution concepts, we obtain a final value matching exactly the optimal social welfare reported in Table 1 of Farina et al.\n\nWe will include additional experiments on the exact instances of Farina et al. in the final version.\n\n\n*On the questions raised by the reviewer (several of which are helpful reformulations):*\n\nRe L42: We agree. We will split the sentence into two sentences. The first sentence introduces the solution concepts that we cover, the second information and mechanism design with a separate footnote outlining the construction around L153.\n\nRe L63: We will clarify that this refers to the time horizon, i.e., the number of iterations of the algorithm.\n\nRe L145: The revelation principle depends on an equilibrium/”implementation” concept. Hence, it depends on which equilibrium we consider. In particular, our revelation principle applies to all games we consider with the equilibrium concepts we discuss in L51-54. See also the response to JN1n for more discussion of the revelation principle.\n\nRe L191: According to footnote 1, we refer to the mediator only by “agent”, not “player”. Hence “all players” does not include the mediator.\n\nRe L192: Thank you. This is correct, and we will make this change. \n"}]

Author rebuttal:

Meta-review: A new approach is proposed for computing (correlated, communication, and certification) equilibria in zero-sum extensive-form games. It is proven that the no-regret dynamics converge to equilibrium in both average-iterate and final-iterate senses. The key idea is the mediator-augmented transformation, which gives rise to the saddle-point formulation that can be solved by online learning algorithms. The reduction approach is presented clearly and appears to be novel (although it builds on existing LP formulations). Reviewers reached a consensus on the acceptance.
Decision: Accept (poster)