Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games
Authors: Gabriele Farina
Charilaos Pipis
Venue: NeurIPS 2024 spotlight (2024)
Keywords: equilibrium computation
exact equilibria
extensive-form games
polyhedral games
ellipsoid
phi-equilibria
Primary area: algorithmic_game_theory

Abstract: It is a well-known fact that correlated equilibria can be computed in polynomial time in a large class of concisely represented games using the celebrated Ellipsoid Against Hope algorithm \citep{Papadimitriou2008:Computing, Jiang2015:Polynomial}. However, the landscape of efficiently computable equilibria in sequential (extensive-form) games remains unknown. The Ellipsoid Against Hope does not apply directly to these games, because they do not have the required ``polynomial type'' property. Despite this barrier, \citet{Huang2008:Computing} altered the algorithm to compute exact extensive-form correlated equilibria.

In this paper, we generalize the Ellipsoid Against Hope and develop a simple algorithmic framework for efficiently computing saddle-points in bilinear zero-sum games, even when one of the dimensions is exponentially large. Moreover, the framework only requires a ``good-enough-response'' oracle, which is a weakened notion of a best-response oracle.

Using this machinery, we develop a general algorithmic framework for computing exact linear $\Phi$-equilibria in any polyhedral game (under mild assumptions), including correlated equilibria in normal-form games, and extensive-form correlated equilibria in extensive-form games. This enables us to give the first polynomial-time algorithm for computing exact linear-deviation correlated equilibria in extensive-form games, thus resolving an open question by \citet{Farina2023:Polynomial}. Furthermore, even for the cases for which a polynomial time algorithm for exact equilibria was already known, our framework provides a conceptually simpler solution.

Polynomial-Time Computation of Exact Φ- Q-Equilibria in Polyhedral Games
Gabriele Farina MIT gfarina@mit.cmm edu
Charilaos Pipis
MIT chpipis@mit edu
Abstract
It is well-known fact that correlated equilibria can be computed in polynomial time in large class of concisely represented games using the celebrated Ellipsoid Against Hope algorithm (Papadimitriou and Roughgarden] 2008 Jiang and Leyton- Brown 2015). However, the landscape of efficiently computable equilibria sequential (extensive-form) games remains unknown. The Ellipsoid Against Hope does not apply directly to these games, because they do not have the required "polynomial type" property. Despite this barrier, Huang and von Stengel (2008) altered the algorithm to compute exact extensive- form correlated equilibria.
2000|
In this paper, we generalize the Ellipsoid Against Hope and develop a simple algorithmic framework for efficiently computing saddle-points in bilinear zero-sum games, even when one of the dimensions is exponentially large. Moreover, the framework only requires "good-enough--esponss" oracle, which weakened notion of a best-response oracle.
Using this machinery, we develop general algorithmic framework for computing exact linear -e-quilibbia in any polyhedral game (under mild assumptions), includ- ing correlated equilibria in normal-form games, and extensive-fore correlated equi- libria in extensive-form games. This enables us to give the first polynomial algorithm for computing exact linear-deviation correlated equilibria in extensive- form games, thus resolving an open question by Farina and Pipis 2023). Further- more, even for the cases for which polynomial time algorithm for exact equilibria was already known, our framework provides a conceptually simpler solution.
Introduction
The correlated equilibrium (CE), introduced by Aumann (1974), is one of the most seminal solution concepts in multi-player games. Contrary to the Nash equilibrium, in a correlated equilibrium the players' strategies correlated by fictitious mediator that can recommend (but not enforce) behavior. is then up to this mediator to ensure that the distribution of recommendations does not incentivize any player to deviate from their recommended strategy. It is known that this type of equilibrium naturally emerges from the repeated interaction of learning agents (Hart and Mas-Colell 2000). In practice, this means that can compute e-approximate CEs in normal-form games by implementing suitable decentralized no-re no-regret dynamics, of which several efficient implementations are known (see, e.g., Blum and Mansour (2007) and Anagnostides al. (2022)). However, this approach requires (ppoy(1/E)) iterations to compute an e-approximate equilibrium, making it non-viable choice for high-precise preecpreeision equilibrium computation. In a celebrated result, |Papadimitriou and Roughgarden (2008) (with later refinements by Jiang and Leyton-Brown (2015)) devised an algorithm, called Ellipsoid Against Hope, that can compute an exact CE in a concisely represented normal-form game in polynomial time in the representation of the game. Their algorithm is an algorithmic version the clever reduction of Hart and Schmeidler (1899 that casts the computation of CEs as two-player zero-sum game.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The positive results for normal-form games, however, do not transfer directly to the significantly more involved setting of extensive-fom games. Extensive-form games are games played on a game tree and can model sequential and simultaneous moves, as well as imperfect information. Despite a significant stream of positive results related learning and equilibrium computation extensive-form games, the complexity of computing CEs in extensive-form games remains to this day major open question (Farina and Pipis 2023; yon Stengel and Forges 2008). Due to its conjectured intractability, researchers have resorted to considering the computation of weaker and generalized notions of correlated equilibrium. A key reference point in this space is given by the framework of Gordon et al. (2008), who define generalized notion of CE called o @-equilibria. In @-equilibrium, every player p is endowed with a set pp of behavior transformation functions. The goal of the fictitious mediator is then simply to recommend strategies such that no player could unilaterally benefit from deviating by using any of the functions Φ E 4p. In this language, a CE corresponds to the Ø-equilibrium in which each Φ is the set of all possible functions from the strategy set of the player to itself. However, by considering appropriate subsets of behavior transformations, weaker supersets of CEs can be efficiently computed and learned through uncoupled learning dynamics. Notable examples of such equilibria in extensive-form games include the extensive-form correlated equilibrium (EFCE)
(von Stengel and Forges 2008), the extensive-form coarse-correlated equilibrium (EFCCE) (Farina et 20020, the normal-fome coarse-correlated equilibrium (NFCCE) (Moulin and Vial 1978).
the recently-introdueed linear-deviation correlated equilibrium (LCE) (Farina and Pipis 2023 )
and
others (Morrill et al. 2021).
Huang and von Stengel 2008) proposed specialization of the Ellipsoid Against Hope algorithm to
compute exact EFCE in extensive-form games. Later, |aarina et al. (2022a) showed efficient no-regret dynamics that converge to the EFCE. More recently, there has been iecressed interest in understanding what is the db-qquiiirrum that is the closest to CE while still enabling efficient computation and learning. Farina and Pipis (2023) introduced the linear-deviation correlated equilibrium (LCE) that arises from the set PLIN of all linear-swap deviations in sequence-form strategies and devise efficient no-linear-swap regret dynamics approximate it. The LCE captures all notable notions of equilibrium that were previously known to be efficiently computable (including EFCE, EFCCE, and NFCCE). However, Farina and Pipis (2023) left open the key question as to whether LCEs themselves can also be computed exactly in polynomial time, akin to the generalization of the Ellipsoid Against Hope algorithm by Huang and von Stengel (2008). as opposed to just learned via uncoupled learning dynamics. The approach by Huang and von Stengel (2088) relies heavily on the combinatorial structure of the deviation functions that define EFCE, resulting in rather involved algorithm. This is in stark contrast to the simple framework for constructing ø-regret minimizers championed by Gordon et al. (2008). This begs the natural question:
Can we always construct an efficient algorithm for exactly computing Ø-equilibria, when there exists an efficient no-rbregret minimizer?
In other words, can we create simple and general framework in the spirit of Gordon et al. (2008) that can enable us to construct algorithms for the exact computation of d-equilibria in polyhedral games for any + C PLIN? We answer this question in the affirmative.
Contributions. In this paper, we propose a framework for computing exact d--quilibria in general polyhedral games. Our framework recovers all positive results established by Paaadiimitriu and Roughgarden (2008), and crucially applies to polyhedral games such as extensive-form games. Using our framework, we develop the first polynomial-ting correlated equilibria in extensive-form games, thus resolving an open question by /aarna and Pipis (2023). Furthermore, even for the cases for which polynomial time algorithm for exact equilibria was already known (CEs normal-form games (Papadimitriou and Roughgarden] (0ndddenn[00)))) Diang and Leyton-Brown 2015) and EFCES in extensive-form games (Huang and von Stengel 2008),, our framework provides a conceptually simpler solution.
algorithm for computing exact dinear-deviation
We show that to compute an exact @-equilibrium in polyhedral game, the following three conditions are sufficient:
1. The game satisfies the "polynomial utility gradient property" (Assumption 4.2) which states that given product distribution over the joint strategy space of all n players, we can efficiently compute the expectation of the gradient of any player's utility. This is a natural generalization of the "polynomial expectation property" of Papadiiiirrio and Roughgarden

---

2008). and it is rather low bar to clear (in fact, it is implicitly assumed in every no-regret
learning algorithm).
2. & is set of linear transformations (i.e., of the form d(x) Ba for some matrix B) that map the strategy set to itself. This is a technical requirement so that the expectation operator and the application of the deviation function can commute []] This condition is satisfied by all notions of @-equilibrium mentioned above, including EFCE and LCE in extensive-form games, and CE in normal-form games.
3. The set O of transformations is polytope that admits polynomial-ting separation oracle.
The separation oracle requirement in the third condition is known be equivalent to efficient linear optimization (Grötschel et al.) 1993). In essence, this means that giving a polynomially sized characterization of set of linear transformations for a polyhedral set a sufficient condition to provide both efficient no-regret learning dynamics and an efficient algorithm for computing exact f--qqiiiibii. This exactly what we achieve by applying our result to the set of linear-swap deviations that was recently characterized (Farina and Pipis] 2023 Zhang et al.) (024b) as polytope of polynomially many constraints and was used to prove efficient no-linear-swap regret dynamics. In light of all these considerations, our framework can be thought of as the counterpart of the d-regret minimization framework by Gordon et al. (2008), but for computation of exact equilibria rather than regret minimization.
At the heart of our construction, our main technical tool is a generalization of the methodology of the Ellipsoid Against Hope (Papadimitriou and Roughgarden, 2008 Jiang and general polyhedral bilinear games. In more detail, we give a new constructive proof of the minimax theorem for players with polyhedral strategy sets, by using only a weakened type of best-response oracle that we coin Good-Enough- BeoouuhhRRspoonss (GER) oracle. An interesting property of the GER oracle is that it can be computationally tractable even when the respective best-response oracle is intractable, as we show in Section 4 This algorithmic idea is likely of independent interest and is especially useful when the strategy space of one of the players is very large but there exists an efficient GER oracle that outputs sparse solutions (e.g., vertices of a high-dimensional polytope). This is exactly the type of problem we face when need to compute exact d--quilibria in polyhedral games and we then proceed to apply this machinery to the above question. Interestingly, in order to show the existence of structured good-enough responses in the context of Ø--quilibria, we based on the existence of an efficient fixed-point oracle for each deviation ø E $. Such an ingredient was fundamental (albeit used differently; see Hazan and Kale (2007) for discussion of the role played by fixed-point oracles in the construction of no-gereeree algorithms) also in Gordon et al.) (2008). In our case, it is one of the technical insights that enable to sidestep much of the intricacy encountered by Huang and von Stengel (2008).
2015) to
argument
We defer all proofs of the paper to the appendix.
Related work. We include an extensive discussion of related work in Appendix A
2
Preliminaries
In this section, we introduce some basic concepts and definitions that will be used in developing our framework.
2.1 Polyhedra, polytopes, and convex sets
Definition 2.1 (Rational polyhedron). A rational polyhedron P == fx E R" Ax < b} is the solution set of a system of linear inequalities with rational coefficients. We say that has facet- complexity ip if there exists system of linear inequalities, where each inequality has encoding length at most y, and whose solution set is P. A rational polyhedron that bounded called a rational polytope.
'Note that going beyond linear transformations can introduce several complications. Most notably, in a recent paper. Zhang al. (2024a) observe that computing exact PPAD-hard and they instead introduce a new way to perform regret minimization using "approximate expected fixed-points".
of non-lineat transformations might be
The encoding length of inequality is the total amount of bits required to represent all of its coefficients.
3

---

One important property of rational polytopes that we will use repeatedly throughout the paper is that they can equivalently be written as the convex hull of a finite number of points. We call these points the verfices ((P) of polytope P. Additionally, the vertices of a rational polytope always have rational coordinates and encoding length poly(p) (Grötschel et al. 1993. Lemma 6.2.4).
Since we are interested in constructing algorithms that perform exact computations, any discussion of non-rational numbers not relevant. Thus, from now on, every time we deal with a polytope we will mean a rational polytope.
In our algorithm, we will also make of the concept of conic hull, which is introduced next.
Definition 2.2 (Conic hull). The conic hull of a convex set X' is R4X (t- t 2 0, a X}. Furthermore, if X' is a rational polyhedron, its conic hull is also a rational polyhedron.
2.2 Game theory definitions
We begin by defining polyhedral games, following Gordon et al. 2008). But first, we need to define multi-linear functions.
Definition 2.3 (Multi-linee function). Let V1...., Vn be vector spaces. A functin V1 X Vn + R is said to be multi Maltt--imear&aa for each E [ni] and fixed v-p E V-p the function f U-p) is linear in Vp Vp In other words, if V f(v-p) is the gradient of f f(pp, U-p) with respect vy when p-p is fixed, then [(pp, 0-p) = Up (f(v=p).
Definition 2.4 (Polyhedral game). In a polyhedral game with n players, every player p E [n] has a polytope strategy set Ap C Rd and a multi-linear utility function up : Ai X x An +
Some notable examples of polyhedral games are: normal-form games, where every player has probability simplex as their strategy set, and extensive-form games, where the strategy sets of the players are the sets of sequence- form strategies (Romanovskij 1962, Koller al. 1996 von Stengel 1996). We will refer to the encoding length of the game as the size of the game. In games of interest this is usually much smaller than holding the full utility function; for example, extensive-form games are encoded using game tree and different classes of normal-fore foomml games can have other succinct descriptions (Papadimitriou and Roughgarden 2008).
sub-class of polyhedral games that will be particularly useful in our paper is that of bilinear zero-sum games, which is defined below.
Definition 2.5 (Bilinear zero-sum game). Let X' RM,, y C R.N be two rational polytopes. A bilinear zero-sum game is a game between two players with strategy sets X and y such that the utility of the X-player is in (xx, y) x. Ay, for some A QMN,, and the utility the Y-player is u2(2s y) = u1 (x. y)
We can now define the notion of a (--quiiibrium, which generalizes the correlated equilibrium for arbitrary n-player polyhedral games and sets of strategy transformations 4. Before do that, first need to define the corner game I(G of a polyhedral game G, following Gordon et al. (2008); Marks (2008) This is the game that arises if we let the action sets of every player p be equal to the vertices ((Ap) of the polytope strategy set of that player. Note that since Ap is a polytope, it will have finite number of vertices. The utilities of this game for player p E [m] and pure strategy profile s E ((Ai) x ... x ((AA) are simply given by us,(s). In this paper, we will denote the vertices of every strategy set in a polyhedral game as II, (Ap). We are now ready define the @-equilibrium.
Definition 2.6 (#-equilibrium). Let G be a polyhedral game o players and D, be a set of strategy transformations 6, : Ap + Ap for each player p E [n]. A { -qquilibrium for G joint distribution μ E (II,, x ... x IIn) on the pure strategy profiles of [(),, such that for every player p E [n] and deviation o E Dp it holds
E [mp(())] gmp
E [l)p((((pp) 8-p)]. a~p
That is, no player p has an incentive to unilaterally deviate from the recommended joint strategy using any transformation & E 4p
Despite their name, polyhedral games have strategy sets that are polytopes, that is, bounded polyhedra.

---

A simple framework for computing equilibria in bilinear zero-sum games using rood-enough-rspponee (GER) oracles
We begin by introducing simple algorithmic framework (Theorem 3.1 for computing min-max equilibria in bilinear zero-sum games. As mentioned before, it relies on the idea of good-enough- responses. The motivation behind this that sometimes a best-response oracle is not known, even NP-hard to construct (as we prove in Theorem 4.7p. On the contrary, good-enough-responss might be a readily available primitive. For example, oracle materializes through the use of fxed-poin oracles for transformations ø E 4 and this enables us devise polynomial time algorithms for computing exact D-equilibria in polyhedral games.
will in Section that good-enough-respone
Let us assume that we have a bilinear zero-sum game (,X,),),, where the strategy sets X' C RM, , C [R are rational polytopes. We typically assume that M > N. Additionally, let
OPT = max min x Ay. =E yEy
be the value of the game at equilibrium, which is known to us. In the rest of the puper we assume that OPT O. This without loss of generality because otherwise, is possible to create new game with this property by augmenting the vectors with an extra dimension as follows:
x
1
0
OPT
x Ay OPT.
Our framework is a formalization of the following observation. The statement (S1) Given any E y we can find some æ = ary) E X' such that x Ay 2 0.
implies the following
(S2) There exists xx E X' such that (x*) Ay 2 for all E V.
This follows from the minimax theorem (Neumann) 1928) as the first statement (S1) is equivalent to miny max, x: Ay O, while the second statement (S2) is equivalent max, miny x: Ay 2 0.
We are interested in the following question: "Is there an efficient algorithm that when given access to an oracle for (S1), it constructs a solution x" for (S2) represented as mixture of a small number of oracle responses?".
3.1 Good-Enough- -ets--ooou----eossse (GER) oracle
We begin by formally defining the oracle we presented previously, which we coin a Good- Good-Enought Response (GER) oracle. It defined as follows:
GER (y) return (x, x AA) E X' QN s.t. x T Ay > OPT 0
where y y R N, and OPT 0 was discussed earlier. Note that this is not best-response oracle, because it does not return an x E X' that maximizes the utility of the max-player. Rather, suffices to return "good enough response", hence the name.
In fact, our algorithms will often need to query a GER oracle for y E R., and not just vectors in V. This however is not problem because it suffices to find any v'/a for some a >> 0 and e y and then query GER(y) instead. To find such a efficiently we can again, without loss of generality, assume that all vectors y y are augmented with extra dimension (call it y(e)) such that y/ø] y [
for all y E y. Then we can find the desired scaling factor immediately because if and only if y' az for y V.
In addition for the polytope ), which can be easily converted to separation oracle for R, by the same "augmenting" argument as before. Combining these two, we can make the final separation oracle (Algorithm 2) that is needed to execute the ellipsoid method on i as presented later. Specifically, if & 47 then we simply return separating hyperplane via SEP y, else we return good-enough- response from GER.
good-enough-responss oracle, our algorithm also requires a separation oracle SEPy
5

---

3.2 The framework
Our goal is to compute an a E X that is an optimal (min-max, strategy for the max-player. Equiva- lently, we seek to find a solution to the following linear program
find E X
S.t. min x: Ay 2 0 yEy
This is an LP with M variables which is typically assumed to be much greater (even super- exponentially greater) than N. When faced with this situation, one might want to attempt to directly solve the dual of (P) using the ellipsoid method. However, this would require a proper separation oracle for the dual problem, which corresponds to linear optimization oracle, or at least a best-response oracle. But as we explained, the oracle access we have is weaker.
Instead, we focus on the below linear program. Note that for any y E R.Y. GER should always return an z E X' such that (x y 2 0, which is a violated constraint of (D). Thus, we can combine GER and separation oracle for R. (as in Algorithm to make separation oracle for this LP.
2
find y E R+Y
s.t. max x Ay S -1 mEX
(D)
By the Generalized Farkas lemma (Lemmaa B.2) and the fact that (P) is feasible, it immediately follows that (D) must be infeasible. Despite the infeasibility, and following the "Against Hope" step of ofPPapddiiirriou and Roughgarden (2008), we execute the ellipsoid method on (7) using Algorithm 2 as a separation oracle. The ellipsoid method will run for number L = poly (N) of steps and then conclude that (D) is infeasible. Let #1..... 2 be the response vectors returned by GER during this process. We now consider "compressed" version of the previous LP that only uses vectors æ from the convex hull co of these responses.
find R.y S.I.
max 2 T Ay S -1 (mp.
(D'
We argue that this LP must also be infeasible; the ellipsoid method is a deterministic algorithm and if we execute on (D'p it will go through the same sequence of candidate points yk. to which we can respond with the same sequence of separating hyperplanes before. These hyperplanes will still be valid for (D) because all of the response vectors we used previously exist in co(2x).
Now, using Generalized Farkas lemma (Lemma B.2 again and the fact that D' is infeasible, it follows that the LP shown below must be feasible.
find æ E co(
min x T Ay 2
(P')
yEy
This is a ''compressed" version of (P). because now every vector æ E co(zx} can be represented as a vector of size L that corresponds to a convex combination of the response vectors Ti.... LL Finally, since (P') is an LP with only polynomial number of variables. we can solve it in polynomial time using any LP algorithm. This will clearly be feasible solution for our initial LP (?). because cofork] [xk] X. The full algorithm is shown below, in Algorithm I Note that reality we only use the LPs D and P The rest were used as intermediate steps for the presentation of the algorithm.
Algorithm 1: Ellipsoid Against Hope for bilinear zero-sum games
Input: Separation oracle , y for R.Y, and a good-enouuh--responee oracle GER. Output: A sparse solution x=" of (P) represented as mixture of GER oracle responses. Execute the ellipsoid method on (D). using Algorithm 2 as a separation oracle;
Create P
using the response vectors and compute a teasible solution x";
Theorem 3.1. the following hold
1. X C M y c R are rational polytopes and y has facet-complextty at most 4
2. we have access to separation oracle SEPy for y and a mood-enough-respooee oracle GER,
3. the encoding length of x: A is at most 4p for all GER oracle responses and all vertices of X,
then Algorithm 7 runs in poly (N, up) time, performs L poly(N, (N, sp) oracle calls, and computes an exact solution x. of (P) that a mixture of at most N oracle responses. In particular, the encoding length of x² depends polynomially the encoding length of the GER oracle responses.

---

Note that since we have assumed that M > N, it would not make sense for the final solution x" to have encoding length poly(M), as this would invalidate the whole algorithm. In order for the solution to make sense, the GER oracle must only give responses with low encoding length. This is exactly the case in Section where M is a doubly-exponential quantity in the size of the problem, while the CER responses are vectors with only one non-zero entry.
4 Computing linear @-equilibria in polynomial time
We have seen in Section 3 how one can compute exact min-max max equilibria using good-enough- response (GER) oracles. Now it is time to apply this machinery in the problem of computing exact d-equilibria in polyhedral games. Crucially, the factor that enables us utilize the framework of Section B is the existence of an efficient GER oracle, which effectively boils down to constructing product distribution consisting of fixed seed-points for the strategies of every player of the game.
Let G be any polyhedral game (Definition 2.4) with n players and strategy sets Ap C R for p E [n]] In this section we apply the framework we developed previously to construct an algorithm that computes an exact Ø-equílibrium of G in polynomial time when + is a polytope containing valid linear transformations from polyhedral strategies to polyhedral strategies. Notable examples of sets with these properties are the trigger deviations used for EFCE (Farina et al. (022a), and the linear-swap deviations used for LCE (Farina and Pipis 2023) in extensive-form games.
The general idea of our construction is that of the existence proof by Hart and Schmeidler (9899 that casts the problem of (-eqqilibriimm computation as of computing min-max equilibrium in a two-player zero-sum meta-gand meet--game between a "Correlator", who acts upon the simplex of all pure strategy profiles, and "Deviator", whose actions correspond to deviations for every player. We call this a Correlator-Devitte game.
To make this idea applicable to polyhedral games, we generalize it as follows. We define a bilinear zero-sum meta- peet--game with strategy sets X. for the two players, where X is the set of all joint distributions over strategy profiles, X' (11, x ..... x II,) (hence, polytope) and y is the Cartesian product of p for all players p. y = 2 ... x 2n which is a convex set and in our case, a polytope.
We remark here that linear transformations op can be represented using matrix B, such that (x,,,) = B, Thus, when we say that Φ, is a polytope, it means that there exists a system of inequalities that can describe the entries of the corresponding matrix B, for every Op E pp. For notational convenience, we will interchangeably use Φ, to denote either the set of transformation functions, or a polytope describing the vectors (flattened B, matrices) that correspond to transforma- tions. In any event, it should not matter which of the two representations we have, because they are completely equivalent.
The utility matrix U of the Correlator in the meta-game is shown below. Specifically, it has one row for each pure strategy profile E II, x .... II, and one column for each tuple j = (p. o, b), where a. E [dp] are used as indices over strategy vectors 8p E Ap. Additionally, we always want the final expression have quantity (Ep Es Es>a(upps)) that is independent of the value of y. To achieve this we can use trick similar to the one used to make OPT 0 in Section By augmenting vectors E y with an extra dimension Ø such that y y/2) = always holds. Then we have
U.j {
E, Us),,
j Ø
sp s.p.spp).. otherwise
where 1, denotes the vector having all O, apart from index b, which is 1. Note that the number of rows of U might be doubly-ea eaabl--epponential (exponential both in the number of players and the dimension of the polyhedral strategies), which is in contrast to the original Ellipsoid Against Hope algorithm that only allowed a number of rows exponential in the number of players.
Lemma 4.1. Let G be polyhedral game with pure strategy set IIp for every player p E [n]. Additionally, let D be a set of linear transformations for every p E [n]. If E x= A[Il x.. xII)
and y (ØI..... )n) E y ②1 ... x D,, then
x U
E [up(s) upl -
'We are slightly abusing the notation here and up (1,, s-p) instead of 1s Vup(s-p).
7

---

It is now evident that our goal is to compute joint distribution that is solution to the following T linear program: find æ E X s.t. mingey x Uy 2 0.
Observe that this is slightly different from the required non-negativity in Definition 2.6 there we want the individual (per-player) expectations be non-negative, while here it suffices for the minimum of the sum of expectations to be non-negative. However, we can assume without loss of generality that the identity transformation is always a valid transformatior Then, every LP solution E & will satisfy æ Uy 2 0 for all y E y, including = (Ø1, Lo.,,...., I), (I, 02 ,2...,,, I).... that correspond to to the individual expectations.
The previous LP respects exactly the structure of (P) that our min-max framework can handle. The only remaining component get a polynomial-timg time algorithm is to have an efficient good-enough- response oracle GER. Specifically, for any valid y E Y, we need to respond with an æ such that Uy 2 0. The important insight that allows us construct efficient oracle and uncover sparse solutions is that we can always find such an æ that is a product distribution - similar to the original Ellipsoid Against Hope algorithm (Papadimitriou and Roughgarden 2008) that was based on the observation by Hart and Schmeidler (1989). Note that we can always represent a product distribution by simply specifying its marginals and those, in turn, can always be represented as polyhedral strategies. Thus, representing the product distribution æ only requires linear space in the game size.
Next, we define an important property that game must have to enable the efficient implementation of the GER oracle we propose (Lemmal) D.I for our algorithm.
Assumption 4.2 (Polynomial utility gradient property). Given a product distribution E AIII X x I,), it is possible to compute the value of
gp(x=p)= P-5~~ (V,((
for all players p E [n] in polynomial time in the encoding length of and the size of the game.
This assumption generalizes the polynomial expectation property defined in Papadimitriou and Roughgarden (2008) to more general, polyhedral games. In particular, if we have a normal-form game, the polynomial expectation property amounts computing 9p (2c (p(x=p)) Fp for product distribution æ. Moreover, as we stated in the introduction, this assumption is very natural for one more reason; it implicitly assumed in every no-regret learning algorithm.
Remark 4.3. Papadimitriou and Roughgarden (2008) also defined a second property that is required for efficient computation, called the "polynomial type" property. Even though our algorithum does not require this property, a variant of it is implicit in the fact that the complexity of the algorithm depends polynomially in the number of players and the dimension of every player's 's strategy set Ag However, this relaxation is what allows our algorithm to handle much broader classes of games, such as the extensive- form games that do not have the polynomial type property.
Theorem 4.4. Let G be a polyhedral game (Definition 2.4 of n players and {0t)) be a collection of polytopes corresponding to sets of linear strategy transformations that map every strategy Ap to itself. Additionally, let N = E, dy. Assume that
there exist polynomial-time -ime separation oracles for Ap and Tp.
G satisfies the polynomial utility gradient property (Assumption 4.2%
sa is an upper bound on the facet-complexty of every Ap and 4p.
log is the maximum encoding length of the utilities of G.
Then there exists an algorithm that computes an exact { of G in time (N,y log u, 1) and performs poly(N, N, log u, v)) number of calls to all the separation oracles. Additionally, the equilibrium represented as a convex combination of at most N pure strategy profiles.
As first application of this framework, we argue that it can be applied to normal-form games that satisfy the polynomial type and the polynomial expectation property, defined Papadimitriou and Roughgarden (2008).
'Otherwise we can replace each Φ, with co J (1)} which remains a rational polytope and admits a separation oracle when 2p has separation oracle.
8

---

Corollary 4.5 (Exact CE in normal foomm games). If normal-fort game G has the polynomial rype and the polynomial expectation property, defined P'apadinitroou and Roughgarden (2008), then our algorithm computes an exact correlated equilibrium of G and runs in polynomial time in the size of the game.
As we have discussed, very notable example of polyhedral games is that of extensive-form games. Next, we apply Theorem 4.4 to this class of games, and specifically to the set of all linear-swap deviations, recently defined in Farina and Pipis| (2023). ) In particular, this set contains all trigger deviations and thus, our algorithm also produces an extensive-form correlated equilibrium (EFCE) in a conceptually simpler manner than in the early work of Huang and von Stengel (2008).
Corollary 4.6 (Exact LCE computation). There exists algorithm that runs in poly log u) time and computes an exact linear-deiattin correlated equilibrium (LCE) in an extensive-form game.
Finally, we prove in Theorem 4.7 that, least in the case of computing é-equilibria in polyhedral games, the use of GER over a best-response oracle is not just more elegant, but it is also necessary because constructing best-response oracle is NP-hard. At the heart of our hardness result lies a reduction from SAT to equilibrium computation in extensive-form games that has also been used in the past to prove the hardness of cquilibrium selection for EFCE and LCE (von Stengel and Forges 2008 Farina and Pipis. 2023). In sense, constructing best-response oracle is as hard as the equilibrium selection problem, while constructing a good-enough -repoos oracle amounts to computing fixed-points of strategy transformation functions. This further highlights the importance of having framework akin to the one presented in Section 3 for designing new algorithms; the hardness result rules out solutions that require responses competitive against any threshold, but sometimes it is sufficient to only compete with a particular good-enough threshold.
Theorem 4.7 (Hardness of BR oracle). It is NP-hard construct a best-response oracle for the Correlator in the Correlator-Deviatorr game.
5 Discussion and Future Work
In this paper, we devise polynomial-ting -ime algorithm for computing min-max equilibria in bilinear zero-sum games, by utilizing a good-enough response oracle. We use this machinery to develop a simple general framework for the exact computation of Ø-equilibria in polyhedral games for sets of linear strategy transformations. This framework parallels that of Gordon et al.) (2008) on no-regret dynamics, but for exact equilibrium computation. Applying this to extensive-form games, we construct the first polynomial-time algorithm for computing exact linear-deviation correlated equilibria in extensive-form games question that had been left open by Farina and Pipis (2023).
cnouuhhrespoonse
We believe that having a simple framework to use as a mental model to guide algorithm design is of paramount importance for the advancement of the field. The d-regret minimization framework of Gordon et al. (2008) is indicative of this fact, because it has been key to many interesting results over the years (Morrill et al. 2021 Farina et al. 2022a Anagnostides et al. 2022: Farina and Pipis 2023).
Compared to no-regret learning, the problem of exact equilibrium computation has been much less studied (basically only in Papadimitriou and Roughgarden (2008); Diang and Leyton-Brown Brown 2015); Huang and von Stengel (2008)) and we hope that offering simplified framework will give new insights to advance this front, perhaps aiding in the discovery of new, more practical, algorithms.
Several key questions remain underinvestigated.
Despite its great theoretical importance, our framework (based on the ellipsoid algorithm) has a polynomial time complexity rather large degree. Could one devise a more practical alternative while retaining similar level of generality?
Can our framework be easily generalized to convex strategy spaces (instead of polytopes)?
Is there similar algorithmic framework to compute exact d-equilibria in extensive-fore games for non-linear transformations &? In recent work, Zhang et al. (2024a) give param- eterized algorithms for minimizing Ø--rereet when & is the set of all degree-k polynomial swap deviations. Can similar guarantees be achieved for high-precision computation of these d-cquilibria?
Can ideas similar to those presented in this paper be applied to Markov games?

---

References
AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghh Hajiaghayi. Brendan Lucier, Hamid Mahini, and Saeed Seddighin. 2019. From Duels to Battlefields: Computing Equilibria of Blotto and Other Games. Mathematics of Operations Research 44, (2019), 1304-1325.
loannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. 2022. Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games. In ACM Symposium on Theory of Computing.
Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, and Maxwell K. Fishelson. 2023, Online Learning and Solving Infinite Games with an ERM Oracle. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India (Proceedings of Machine Learning Research, Vol. 195), Gergely Neu and Lorenzo Rosasco (Eds.). PMLR, 274-324
Robert J Aumann. 1974. Subjectivity and correlation in randomized strategies. Journal of mathemati- cal Economics 1, (1974), 67-96.
Avrim Blum and Yishay Mansour. 2007. From External to Internal Regret. J. Mach. Learn. Res. (2007).
G.W. Brown. 1951. Iterative Solutions of Games by Fictitious Play. In Activity Analysis of Production and Allocation, T. C. Koopmans (Ed.). Wiley, New York.
Darshan Chakrabarti, Gabriele Farina, and Christian Kroer. 2024. Efficient Learning in Polyhedral Games via Best Response Oracles. In AAAI Conference on Artificial Intelligence (AAAI).
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. 2024. From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces (STOC 2024). Association for Computing Machinery, New York, NY, USA, 1216-1222.
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. 2009. The complexity of computing a Nash equilibrium. Commun. ACM 52, 2 (feb 2009), 89-97.
FAIR, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mojtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts, Adithya Renduchintala, Stephen Roller, Dirk Rowe, Weiyan Shi, Joe Spisak, Alexander Wei, David Wu, Hugh Zhang, and Markus Zijlstra. 2022. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 378, 6624 (2022), 1067-1074.
Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm. 2020. Coarse Correlation in Extensive- Form Games. In AAAI Conference on Artificial Intelligence.
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. 2022a. Simple Uncoupled No-regret Learning Dynamics for Extensive-form Correlated Equilibrium. J. ACM 69, 6 (2022).
Gabriele Farina, Chung- Wei Lee, Haipeng Luo, and Christian Kroer. 2022b. Kernelized Multiplicative Weights for O/l-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games. In International Conference Machine Learning.
Gabriele Farina and Charilaos Pipis. 2023. Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games. In seirtty Conference on Neural Information Processing Systems.
Ian Gemp, Yoram Bachrach, Mare Lanctot, Roma Patel, Vibhavari Dasagi, Luke Marris, Georgios Piliouras, Siqi Liu, and Karl Tuyls. 2024. States as Strings as Strategies: Steering Language Models with Game-Theoree Solvers. arXiv:2402.01704 [cs.CL]
Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. 2017. Frank-Wolfe Algorithms for Saddle Point Problems. In Proceedings of the 20th International Conference Artificial Intelligence and Statisties (Proceedings of Machine Learning Research, Vol. 54), Aarti Singh and Jerry Zhu (Eds.). PMLR, 362-371.
10

---

Paul W. Goldberg and Francisco J. Marmolejo-Cossio. 2021. Learning Convex Partitions and Com- puting
Equilibria from Best-response Queries. ACM Transactions on Economics and Computation 9, (2021), 3:1-3:36.
Geoffrey Gordon, Amy Greenwald, and Casey Marks. 2008. No-regret in convex games. In International Conference on Machine learning. 360-367.
Martin Grötschel, László Lovász, and Alexander Schrijver. 1993, Geomelric Algorithms and Combi- natorial Optimization. Springer Berlin, Heidelberg.
Sergiu Hart and Andreu Mas-Colell. 2000. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica 68, (2000), 1127-1150.
Sergiu Hart and David Schmeidler. 1989. Existence of Correlated Equilibria. Mathematics of Operations Research 14, 1 (1989), 18-25.
Elad Hazan and Satyen Kale. 2007. Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria. In Advances in Neural Information Processing Systems, Platt, D. Koller, Y. Singer, and Roweis (Eds.), Vol. 20. Curran Associates, Inc.
Wan Huang and Bernhard von Stengel. 2008. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics. Springer, 506-513.
Albert Xin Jiang and Kevin Leyton-Brown. 2015. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior 91 (2015), 347-359.
Christopher Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ordóñez, and Milind Tambe. 2009. Computing optimal randomized resource allocations for massive security games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems- Volume / (Budapest, Hungary) (AAMAS '09). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 689-696.
Daphne Koller, Nimrod Megiddo, and Bernhard Stengel. 1996. Efficient Computation of Equilibria for Extensive Two-Person Games. Games and Economic Behavior 14, 2 (1996), 247-259.
Wouter M Koolen, Manfred K Warmuth, Jyrki Kivinen, et al. 2010. Hedging Structured Concepts. In COLT. Citeseer, 93-105.
Mare Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. 2017. A Unified Theoreehe Approach to Multiagent Reinforcement Learning. Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 4190-4203.
C. Marks. 2008. No-regret learning and game-theoretic equilibria. Ph. D. Dissertation. Brown University, Providence, RI.
Dustin Morrill, Ryan D'Orazio, Mare Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. 2021. Efficient Deviation Types and Learning for Hindsight Rationality in Extensive- Form Games. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (Proceedings of Machine Learning Research, Vol. 139). PMLR, 7818-7828
H. Moulin and J. P. Vial. 1978. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. Int. J. Game Theory 7, 3-4 (sep 1978), 201-221.
J. von Neumann. 1928. Zur Theorie der Gesellschaftsssiele. Math. Ann. 100, (1928), 295-320.
Christos Papadimitriou and Tim Roughgarden. 2008. Computing Correlated Equilibria Multi- Player Games. J. ACM 55, 3 (2008).

---

Binghui Peng and Aviad Rubinstein. 2024. Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (Vancouver, BC, Canada) (STOC 2024). Association for Computing Machinery, New York, NY, USA, 1223-1234.
I. Romanovskii. 1962. Mathematics 3 (1962).
Reduction of Game with Complete Memory to Matrix Game Sovier
Aviad Rubinstein. 2015. Inapproximability of Nash Equilibrium. In Proceedings of the Forty- Seventh Annual ACM Symposium on Theory of Computing (Portland, Oregon, USA) (STOC (1)). Association for Computing Machinery, New York, NY, USA, 409-418.
Aviad Rubinstein. 2016. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 258-265. 265.
Eiji Takimoto and Manfred K Warmuth. 2003. Path kemnlss and multiplicative updates. The Journal of Machine Learning Research 4 (2003), 773-818.
Bernhard von Stengel. 1996. Efficient Computation of Behavior Strategies. Games and Economic Behavior 14, 2 (1996), 220-246.
B. von Stengel and F. Forges. 2008. Extensive-form correlated equilibrium: Definition and computa- tional complexity. Mathematics of Operations Research 33, (2008), 1002-1022.
Haifeng Xu. 2016. The Mysteries of Security Games: Equilibrium Computation Becomes Com- binatorial Algorithm Design. In Proceedings of the 2016 ACM Conference on Economics and Computation (Maastricht, The Netherlands) (EC 16). Association for Computing Machinery, New York, NY, USA, 497-514.
Haifeng Xu, Fei Fang, Albert Jiang, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. 2014. Solving Zero-Sum Security Games in Discretized Spatio- Temporal Domains. Proceedings of the AAAI Conference on Artificial Intelligence 28, (Jun. 2014).
Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. 2024a. Effi- cient &-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games. arXiv:2402.0967 097777007777 [cs.GT]
Brian H. Zhang, Gabriele Farina, and Tuomas Sandholm. 2024b. Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games, The Twelfth International Conference on Learning Representations.
A Related work
Algorithms for computing equilibria can be classified broadly into three categories:
Polynomial-time time algorithmss compute exact equilibrium in time polynomial in the input game size. Note that exact equilibria only make sense when the game has rational utilities, otherwise we settle for c-approximate equilibria in time polynomial in log(1/c) and the size of the game. Fully polynomial-inne approximation schemes (FPTASs) compute e-approximate equilibria in time polynomial in 1 /e and the size of the input game.
Polynomial-time approximation schemes (PTASs) compute e-approximate equilibria in time that is polynomial in the size of the input game, for every fixed > 0 however, they might in general have an exponential dependence on L/e.
Nash equilibria are known to be PPAD-complete, thus ruling out any polynomial-time algorithm for them (Daskalakis et al. 2009). Additionally, approximating a Nash equilibrium, even for a constant is known also be PPAD-complete for n-player games (Rubinstein, 2015) and to require quasi-polynomial time for 2-player games, assuming ETH for PPAD (Rubinstein 2016),, thus ruling any PTAS FPTAS algorithm.
The complexity landscape significantly more favorable for the case correlated equilibrium (CE). Specifically, Hart and Mas-Colel] (2000); Blum and Mansour (2007) gave efficient no-regret
12

---

dynamics (minimizing the so-called internal regret) that, if used by all players in a game, can be used compute an c-approximate CE in normal-form games in time polynomial in the size of the game and c/c. This constitutes the first FPTAS for the computation of CEs. Finally, Papadimitriou and Roughgarden (2008) gave a centralized algorithm that exactly computes CE concisely represented normal- game in polynomial time in the size of the game. This was the first polynomial-time algorithm for CEs.
The complexity of CE is not settled for extensive-form games (EFGs), and its determination remains a major unresolved question in the field (von Stengel and Forges 2008: Farina and Pipis 2023). An advance in this direction was provided very recently by the breakthrough results from two concurrent works of Dagan et al. (2024) and Peng and Rubinstein (2024), which provide PTAS for CE in extensive- formii games, though it remains unclear whether a myyoomlll-imme algorithm or even an FPTAS exist.
Due to the conjectured intractability of computing a normal-form CE in EFGs, researchers have come up with other notions of equilibrium (von Stengel and Forges 2008 Morrill et al. [202]] Farina and Pipis 2023 Zhhagg et al. (2024b) that lie on a spectrum of Q-equilibria. D-equilibria provide generalization of CE that ranges from least hindsight-rational (coarse correlated equilibria), to maximum hindsight rational (CE), depending on the size of the set of behavior transformation & considered by the players. One of the most notable and natural notions of sequential rationality is that of the extensive-fore formi correlated equilibrium (EFCE) (von Stengel and Forges 22088. The EFCE was shown to be efficiently computable exactly (Huang and von Stengel| (008) using method similar to the Ellipsoid Against Hope of |Papadimitriou and Roughgarden (2008). Additionally, it was shown that there exist efficient regret dynamics (minimizing the so called trigger regret) that can be used to compute an c-approximate equilibrium by Farina et al. (2022a). This also gives an FPTAS for EFCE.
Currently, the highest notion of rationality that admits an FPTAS is the recently defined linear- deviation correlated equilibrium (LCE) (Farina and Pipis, 2023). which subsumes previous equilib- rium notions such as EFCE. Farina and Pipis (2023) proved that there exist efficient regret dynamics (minimizing linear-swap swap regret) that can converge to an LCE; the polynomial complexity was then later improved by Zhang et al. (2024b). They however left open the question as to whether there exists a polynomial time algorithm that can compute an exact LCE. We resolve this open question in this paper, showing that the exact computability of equilibria in EFGs extends up to the linear-deviation correlated equilibrium.
Relationship with work on combinatorially-stuutue games. Our algorithmic framework in Section 3 can be used to compute exact min-max equilibria in bilinear games when one of the players has an exponentially large action space and we can only use a good-enough-respone oracle- a weaker notion than the best-response oracle.
In light of applications related to Machine Learning and Deep Learning, there has recently been increased renewed interest in games having exponential (or even infinite) action spaces. For example, Assos et al. (2023) propose regret dynamics that can converge to approximate coarse correlated equilibria in infinite (nonparametric) games when a suitable notion of dimension of the game (Littlestone and fat-threshold) is bounded. Dagan et al. (2024) generalize this result even further proving that there also exist regret-dynamics in these cases that converge in approximate correlated equilibria. Interestingly, recent breakthroughs in Large Language Models have inspired work on "language-basee based" games that typically have an enormous number of strategies (FAIR et al. 2022 Gemp et al. 2024).
However, the interest in games involving large strategy spaces is by no means recent phenomenon. For instance, the community of security games has traditionally been interested in the problem of computing Stackelberg equilibria for games where one player (the leader) can possibly have exponentially many strategies (Kickintveld et al. 2009; Xu 2016). Another notable example is that of the Colonel Blotto game, which involves exponentially ly large strategy sets in both players (Ahmadinejad et al. 2019). Finally, work on learning in combinatorially-sstuuae
games has found applications to online optimization combinatorial domains such as EFG strategy spaces and flow polytopes (Farina et al., 20226] Koolen et al. 2010 Takimoto and Warmuth (003).
Even though our framework for computing min-max equilibria might have some resemblance to some of the methods in these papers, to the best of our knowledge, in all of the past cases the algorithms cleverly exploit the special combinatorial structure inherent in security games and usually involve
13

---

reducing the dimensionality of the strategy space as first step. Our framework on the other hand, might allow for applications where the large decision set of player is not amenable some kind of smaller-dimensional representation.
Finally, remark that interesting recurring theme in games with large strategy spaces is that they often assume some kind of best-response oracle access.
Relationship with work based on best-response oracle access to games Using best-response oracles is a ubiquitous technique for learning in games or equilibrium computation, starting from the foundational method of fictitious play (Brown 1951 where players apply best-response oracle every round to respond to the empirical frequency of play of their opponent. Best-response oracles (or variants thereof) have additionally been used in security games (Ahmadinejad et al. 2019 Xu et al. 2014), in bilinear games (Gidel et al. 2017). in efficient learning on polytopes (Chakrabarti et al.
2024), in the computation of well-supported equilibria in bilinear games (Goldberg and Marmolejo- Cossio 202T). in the PSRO for Reinforcement Learning (Lanctol et al. (017). in infinite games (Assos al. 2023: Dagan al. 2024). We remark however that this paper we do not best-response oracle in our algorithms. Rather, we use weaker notion that we coin "Good- -noughE Response" (GER) oracle. In certain cases (such as the computation of o -e-quiiiirra in Section 4 is critical to relax the requirement for best-response oracle because no such oracle can be constructed unless = NP (Theorem
B Further preliminaries on linear programs
Here, we introduce some more specialized Lemmas that will be useful for proving the main results of Section 3 The first one concerns feasibility sets of the form we use in our main I.Ss and shows that they are, fact, polytopes and that their facet-complexity is properly bounded.
Lemma B.1. Let A be a matrix and
P u E
max q T Au S soj QEΩ
If the following conditions hold
U be rational polyhedron with fucet-complexity most yp
Q be the convex hull of set of finitely many points V(Q) = (Âi.... qR}.
the inequality (q Aju S has encoding length most up for all vertices & E (Q)..
Then the set P is a rational polytope with facet-complexity at most s.
Proof. First we show that P PP, where
="==uu Eu (
is the polytope defined by finitely many inequality constraints, corresponding to the vertices of Q. Combining this with the assumption that each such inequality has encoding length at most ip, the result follows immediately. It remains prove the desired set equality:
Case P PCP C':
u P = u u U max q qEo
Au S = ueu, (q AJu SCV V(2),
where the last implication follows from the fact that for all & E v(Q)
(q A
A)u v S max q Au S.
qEQ
Case P P2 P': By definition, any point Q can be written as the convex combination of
all vertices q = Σ. Xaq. Thus, we have
u P' uuu, (q Aju S c Vq vQQ) E 4 max q
Au S cc
Q
14

---

where the last implication holds because for any Q
K
K
Au AuAu= N. Au S
Σ Apc.
This concludes the proof.
We also mention a result in the spirit of the classical Farkas lemma. We use this result in to prove our main Theorem Section
Lemma B.2 (Generalized Farkas lemma). Let X RM, C R be convex compact sets. Then exactly one of the following two statements is true.
There exists x: E X such that min x: yEy
Ay 2
2. There exists y E IR such that max
Ay S -1.
sEx
Proof. 1) We first show that (1) and (2) cannot be true simultaneously. Assume otherwise and let
X. y E R y. be values that satisfy (1) and (2) respectively. Since ý belongs to the conic hull of )' it must be ÿ ky for some & >> 0 and y' E 3. Thus,
1
max x FEX
S
max x mEX
Ay S
k
Additionally, it holds
0 S min & T Ay S a Ay' S
max x Ay S TEA
yEy
K
which is contradiction. Thus, the statements (1) and (2) cannot be simultaneously.
II) We now proceed to prove that when (2) is false then (1) must true. We begin by showing
that (2) being false implies that for any 0 there does not exist any E R.,. such that
max x Ay < -7. Suppose otherwise; then y' yy/ is multiple of an element of RR,.) and thus xx
y' R. Furthermore,
max x T Ay' XEX
max x T Ay S -1, 7 #E
which is contradiction because we have assumed that (2) is false. It directly follows that
min max x T Ay 2 0. MEY #ex
By the minimax theorem it also holds
max min x T Ag 20 = #EX wEy
Fee: min Ay 2 yEy
and thus, statement (1) is true.
III) Finally, need to prove the inverse direction: when (1) is false then (2) must be true. This trivial because (2) was false, then by II) we would have that (1) is true, which contradicts the assumption.
C Omitted proofs from Section 3
Theorem 3.1. If the following hold
1. X' c R y R rational polytopes and y has fucet-complexity at most yp
2. have access separation oracle SEPy for y and good-enough-responn oracle GER,
3. the encoding length of x A is most up for all GER oracle responses and all vertices of X.
15

---

Algorithm 2: Separation oracle for the ellipsoid method on (D)
Input:
Separation oracle SEPR, y for R,Y, and good-enough-response oracle GER. Output:
A separating hyperplane e for y in (D). and corresponding vector æ: from GER, if exists.
if' SEPR.y deems that is in R4,3/ then Set (z, c) to the output (x, A x)) of GER(Y);
else
Set c to the separating hyperplane output by SEP SEPR.y:
= 23;
end
then Algorithm runs poly(N, :p) time, performs L poly(N, sp) oracle calls, and computes an exact solution x of (P) that is a mixture of at most N oracle responses. In particular, the encoding length of x² depends polynomially on the encoding length of the GER oracle responses.
Proof. First, we can assume without loss of generality that there exists dimension Ø in all y E y such that y|ø] = 1. Otherwise, it is always possible to augment these vectors with an extra dimension before applying the next steps of the algorithm. This allows to convert the given separation oracle SEPy into a new separation oracle SEPR, for R.y. that we can then use to construct the general oracle of Algorithm 2
The first step of the algorithm is execute the ellipsoid method on (D). Using the assumptions of the theorem in Lemma B.I with 1 = R and Q = X, it follows that (2) is polytope and has facel-complexity at most yp. Additionally, by the fact that (P) feasible (it has an equilibrium with OPT = 0) and by Lemma B.2 it follows that (7) must be infeasible.
To execute the ellipsoid method to solve the Strong Nonemptiness Problem for (D) using the strong separation oracle of A Algorithm 2 To this end, we use the algorithm from Theorem 6.4.1 Grötschel al. (1993). This algorithm works for any polyhedron, even if it is not bounded or full-dimensional, as might be the case here. To do that, it might execute the central-cut ellipsoid method more than once, but never more than N times. In our case, we already know that (D) is infeasible and thus, the algorithm terminates after N executions of the central-cut ellipsoid and concludes that (D) is infcasible.
would then mean, the language of Grötschel al, 1993
Since the central-cut ellipsoid method is an oracle-polynomial algorithm that executed N times in polyhedra of facet-complexity most yo, the whole process in polynomial time and performs polynomial number of separation oracle calls. To calculate the exact number L of oracle calls, we note that the algorithm in Grötschel al. [1993 Theorem 6.4.1) initializes the central-cut ellipsoid method with
R R= 2= ((N22p) and 2 2-2-0(
while the central-cut method terminates in O(N log log(1/e) + N log R) iterations (Grötschel et al. 1993 Theorem 3.2.1). Combining these with the fact that the central-cut ellipsoid method is repeated N times, we get that the number oracle calls is L O(N7
is comprised of constraints coming from GER oracle responses, which by Lemma B. gives that the facet-complexity D must also be at most sp. By going through the same process before, the algorithm will reach the same conclusion after executing the central-cut ellipsoid method N times; D is infeasible.
Next, note that
Finally, by the infcasibility of D' and Lemma equivalent way to express P is
B.2 it follows that P must be feasible. An
find a
s.t. min a yey
T (X
A)y 2 0
a A
where 4 is the T-dimenniionl simplex and X [m)) responses as its columns.
xr.. is matrix with the GER oracle
16

---

Applying Lemma B.1 for U A and Q = y we conclude that P describes a polytope
p = a E A
min a (x A)u 2 wEy
of encoding length most L poly(p)) This is because, for any vertex E V()),, the inequality a' (X A) 2 0 has L coefficients, each of which having encoding length poly(p). This can be solved in polynomial time by any known linear programming method. Even better, possible to compute a basic feasible solution of this LP, which will have at most N non-zero entries and thus the final solution x' * = Xa will be a mixture of at most oracle responses.
D Omitted proofs from Section
Lemma 4.1. Let G be polyhedral game with pure strategy set 11, for every player p [n]. Additionally, let p be set of linear transformations for every E [n]. If E & A(Th x..
and y (01,.... 2n) ())) E y $1
D, then
x U Σ Elpls) up up((p((8))
Proof. As we discussed, each linear transformation dp can be viewed as dp x dp transformation matrix Bg. We denote the matrix entries with Bylb, a]. In particular, if s) 0p(sp), have
sy [b] = E. Bylb, a]sp/a]. Then for any E X' and y (d1....,, Qn) E y we have
x
Tu =
Σ
3s
Ux(s)
E
Σ
Bplb, alsplclup((1. 8-p)
8
p
aE|d,] bE(d,]
Σ Σ
up(() - up Σ
1a Σ
Us
B
bEldp)
aE|dp]
ΣΣ
Up(s) Up
165 s-p
F
bEldp)
Σ (up(s) up((r((p), 8-p))
E (up(s) un (s,) s
where in the second equality we have used the multi- celti-iinneaityy the utilities.
Now we are ready present the good-enough-respon responss oracle that will allow develop an efficient algorithm for computing exact Øh-qqilibria in polyhedral games. As general backbone, this Lemma follows the constructive proof that Papadimitriou and Roughgarden (2008) did for the CE existence result Hart and Schmeidler (1989) and, crucially, it produces pure strategies using the idea of Jiang and Seyyton-rrowy (2015).
Lemma D.1 (GER oracle for @-equilibria), For every y E = - x x... DT, there exists a pure strategy profile s E II x x II, such that Uy 2 O. Furthermore, such strategy profile alongside with the vector 13 U can be computed efficiently, provided that the game satisfies the polynomial utility gradient property (Assumption 4.2 and there exists polynomial-time separation oracle for every Ap-
Proof. As we have discussed, we can denote all linear transformations o, using a matrix B,, such that (1r)) Bp
First note that there always exists fixed- point of any linear strategy transformation op: this follows from Brouwer's fixed-point theorem and the fact that these transformations continuous maps of
17

---

Algorithm 3: Purified GER oracle
Input: Polyhedral game G of n players, y y 41 x .n. separation oracles SEP A, for all p E [rz].
Output: A pure strategy profile E II x x... x II such that Uy 2 0.
Compute a product distribution æ s.t. a: Uy by finding fixed points xpp = 0p (20p) for all
p
[n]:
for p E [n] do
Find a set of k 2 dp + 1 vertices 8
(k) Sp
V(Ap) s.t. 2p = -E \.
Set 8p the vertex 8 that satisfies (p-
Uy 2
Set æ to be (zr-ra))
end
Finally, æ must correspond to pure strategy profile
compact convex set Ap itself. Additionally, since the transformations linear always efficiently compute a fixed-point of any transformation by solving the following LP:
find Fp
s.t. Bp Ip pp E Ap
that can be solved in polynomial time using the ellipsoid method with the given separation oracle for Ap.
Next, let restrict our attention only to product distributions æ E ( will be (p)pp)pp) for all pure strategy profiles s, which gives
II,). In this case
Uy ΣΣ
Σ
z-p(s -=p((-p)=p(()) [up Sp. s-p) up(0p(sp).
p 8-p ET
ΣΣ x=p(( u) (1x, - (p((p)) s-p)
[gp(x= (xp (p(p))
(1)
where Up E Ap is the marginal distribution for player p represented point of the polyhedral strategy set. In the second equality we have used the multi-linearity of 8.(8.pp)) and the linearity of the transformations; E,, Tp (sp)))p (sp) (xp)) It directly follows from the last equality that
we set each marginal distribution equal to the corresponding fixed-point x.p = (2pp). we get product distribution æ such that x Uy=
Now, it remains to find a way to extract the desired pure strategy profile from this product distribution. We follow a similar procedure to the purification technique used by Jiang and Leyton Brown (0015). Similar to their algorithm, we define & (p-+a,) for a product distribution æ to be the product distribution which player p plays pure action sp Ap and all other players act according to x x-pp Additionally, note that since Ap is polytope, it must hold
Ip =
Σ
Xo
VpEV(Ap)
for some convex combination (Ne, 2 0 E,p As = 1}. By the product distribution structure, is
easy to see that for every player p [n].
UU
T p Uy|
Xay
(AAp)
The algorithm of Jiang and Leyton-Brown (0055) iterates over all players and for each player p they search over all its pure strategies and find one, sy for which x (pp-ry)) Uy 2 0. Such a pure
18

---

strategy must always exist because 2 represents a convex combination over all vertices (a.k.a. pure strategies). However. in our case we cannot iterate over all pure strategies for player because they might be exponentially many.
To make this procedure general for all polyhedral games, we observe that by Carathéodory's theorem there must always exist subset that satisfy
{ (((1) (8y
(k)
(Ap)) of at most & S dp + vertices of Ap
k Pp =
8 (i)
1=1
for some convex combination represented with A....., As- Thus, we can follow the same procedure before but this time only search over k vertices instead of all (possibly exponentially many) vertices of Ap. The complete algorithm is shown in Algorithm 3
This be implemented in polynomial time because: (a) there exists algorithmic version of Carathéodory's 's theorem Grötschel et al. (1993 Theorem 6.5.11) that only requires access to a
separation oracle for Ap. and (b) Assumption 4.2 allows us compute a (pp-a Uy in polynomial time for any product distribution ()))>s))> as is evident from
Theorem 4.4. Let G be polyhedral game (Desinition 2.4 of players and {8p) be a collection of polytopes corresponding to sets of linear strategy transJormations that map every strategy set Ap to itself. Additionally, let N= Ep dy. Assume that
there exist polynomial-time time separation oracles for Ap and dp.
G satisfies the polynomial utility gradient property (Assumption 4.2
db is an upper bound on the facet-complextty of every An and Dp.
log u the maximum encoding length of the utilities of G.
Then there exists algorithm that computes exact {quuieqquliirimm of G in time (N,y(N, log u, and performs poly(N, log u, t) number of calls to all the separation oracles. Additionally, the equilibrium is represented convex combination of at most N pure strategy profiles.
Proof. The set = A[II x II,) is trivially a rational polytope and the set y' 11 x.. 2 C RN is the Cartesian product of rational polytopes, hence a rational polytope. Furthermore, we can directly construct a polynomial-time separation oracle for y by calling the separation oracles for each one of the sets p. Additionally, every row of the U matrix has N entries, each with encoding length at most 2 log u. Using the enough-respons
oracle from Lemma D.I each response (æx, U) E X x Q corresponds to pair of a pure strategy profile (vertex of X') and row of U. Thus, each response has encoding length at most 2.V log u. Set o max log u. vb).
Now, we can apply Theorem 3.1 which gives us an algorithm running in poly(N,sp) time and performing poly(M sp) oracle calls. Combining this with Lemma D.I follows that the total time complexity is poly(N, (p) = poly NN, log u, v²). Finally, the optimal solution x will be comprised of a mixture of N oracle responses. In other words, x" will be an exact dequl-uqulirrium for the game G with probability mass on at most N pure strategy profiles.
Corollary 4.5 (Exact CE in normal games). If normal-sorm form game G has the polynomial type and the polynomial expectation property, defined in Papadimitriou and Roughgarden (2008), then our algorithm computes an exact correlated equilibrium of G and runs in polynomial time in the size of the game.
Proof. A normal-foo form game is a polyhedral game where every strategy set is probability simplex. Additionally, the set & all linear transformations normal-form games is that of swap-deviations which is equivalent to the set of all stochastic matrices (Gordon et al.) 2008). Both the sets of strategies and the sets of stochastic matrices can easily be represented as pol ptopss of bounded facet- complexity having polynomially many constraints. Finally, the polynomial utility gradient property
19

---

reduces to the polynomial expectation property in succinct normal- games and the polynomial type property implicitly satisfied (see Remark 4.3). Thus, all requirements of Theorem 4.4 are satisfied and we conclude that there exists a polynomial time algorithm for computing CEs normal-form games.
(Assumption 4.2)
Corollary 4.6 (Exact LCE computation). There exists algorithun that runs in poly log u) time and computes an exact linear-deviation correlated equilibrium (LCCE in an extensive-form game.
Proof. We apply Theorem 4.4 for the set of linear-swap deviations. Specifically, in Farina and Pipis 22033
Theorem 3.1) it is proved that:
The set LIN of linear-swap deviations for a player is a rational polytope.
This polytope can be described using a polynomial number of equality constraints, which immediately implies the existence of an efficient separation oracle.
Every constraint of the characterization has at most | coefficients, each belonging to {0, 1.1. Thus, the compl-cyyyyy of L must be ab |Epl
Finally, since the number non-zero utilities are at most equal to the game tree size, it trivially follows that extensive-form games satisfy the polynomial utility gradient property (Assumption follows that there exists a polynomial time algorithm for computing LCEs.
Theorem 4.7 (Hardness of BR oracle), It is NP-hard construct a best-response oracle for the Correlator in the Correlator-evviat game.
Proof. A best-response oracle for the Correlator in the Correlator-Deviator game must respond with the optimal æ E X' = A x .... x I1,) for any given y E y = 4i x ... x on. More precisely, we have to be able to compute
x² = arg max (I Uy) = arg max ZEX
EE (up(s) up(ōp(8p),
xEN
for all y E V.
To prove that this process is intractable it suffices to find a game and an equilibrium concept such that is NP-hard to compute x" for least one y E y. For the solution concept we choose the coarse-correlaed equilibrium, in which the sets Φp consist of all constant (or external) deviations that output a fixed strategy 0p (xp) = 5, E IIp no matter the input strategy Tp. For the game, we choose the SAT-game that was also used to prove the hardness of equilibrium selection for EFCE and LCE in extensive-form games (von Stengel and Forges 2008 Farina and Pipis, 2023). The exact details are not important for our purposes, but will only the fact that any SAT instance can be encoded in a 2-player extensive-fore formm game using a polynomial-timg
reduction. In this game, any pure strategy profile II, X x II, with social welfare (sum of players' utilities) equal to corresponds to satisfying assignment for the SAT instance, while any other strategy profile has social welfare at most 2(1 1 1/... Thus, there exists Nash equilibrium (and hence, CCE) corresponding a pure strategy profile that has maximum social welfare.
Before we proceed, we augment the SAT-game by adding extra decision point for both players at the beginning of the game that asks whether they want to play. If both players respond "Yes" then the game continues normal, otherwise -if at least one player responds "No"- the game ends and both players get a payoff. We denote the pure strategy of the "No" answer from player with s and the "No" answer from player with "
Now, to prove the desired result consider a Correlator-Deviant game applied to the computation of CCE in the above augmented SAT-game. Assume that there exists a polynomial-time best-response oracle for this game that returns a solution of polynomial size the representation of the game (and hence, the size of the SAT instance). Then, use it to best-respond to y (Φ1, Φ2) for
20

---

( = s/ and (22))) = s² Specifically, we have
x² arg max øE
E [p(()) up(0p(8p)) 8 8ppppp
arg max
E [sp[
Σ swa
E (up( spp)
Σ E swap [u]]
arg max ØEN
In other words, the BR oracle returns in this case a distribution x" over pure strategy profiles with maximum social welfare. Since the BR oracle computes polynomially-sizee x² in polynomial-time, we can uncover pure strategy profile of maximum social welfare that corresponds, by construction of the SAT-game, to a satisfying assignment of the SAT instance. We conclude that constructing best-response oracle in the Corvelator-Deviatoo game corresponding to the compution of a CCE in extensive-form games NP-hard.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We include our contributions in the abstract as well as in the "Contributions" paragraph of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We include discussion of the limitations in the final section of the paper, alongside with list of related open problems.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: All theorems, lemmas and corollaries of the paper explicitly mention the set of assumptions needed. Additionally, all complete proofs are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Since this a purely theoretical paper, exploring the tractability of computing high-precision equilibria in games (and giving polynomial-time algorithm of rather high complexity), it does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. htcp//blcc/gudeeeeeeeeeeieeeeeee
ssiobbiiiisiooccccyc. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaarrr...c.oaaaaaccccccea
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper theoretical investigation of the tractability of computing high- precision equilibria in polyhedral games and does not suggest a way to deploy new tech- nologies. Thus, it does not have any immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper concerns theoretical results of equilibrium computation in games and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "UVK1C4R0kz", "reviewer": "Reviewer_Ht5B", "summary": "The paper, titled \"Polynomial-Time Computation of Exact $\\Phi$-Equilibria in Polyhedral Games,\" proposes a novel algorithmic framework to compute saddle-points in bilinear zero-sum games, particularly when one dimension is exponentially large. This framework extends the Ellipsoid Against Hope algorithm and introduces a \"good-enough-response\" oracle to compute exact linear ε-equilibria in polyhedral games efficiently. The authors claim that this new approach resolves an open question by providing the first polynomial-time algorithm for computing exact linear-deviation correlated equilibria in extensive-form games.", "questions": "The paper makes a substantial theoretical contribution to the field of game theory and computational algorithms. Given its innovative approach and resolution of a significant open problem, it is a strong candidate for acceptance at NeurIPS. However, the authors should consider including empirical results and a more detailed comparative analysis to strengthen the practical relevance and impact of their work. \n\nPersonally, I have tried multiple times to parse again and again section 4 to understand how GER does really work efficiently. Could you please explain more the reduction to the Correlator-Deviator game.\nAdditionally, can you explain how you go from summation inequality of lemma 4.1 to the individual parts' inequality. To be honest, I need elicit explanations for each paragraph between lines 297 and 326, which are the crucial part to make the algorithm works.\n\nWhat is the limit to apply non-linear transformation?\nIn order to get a Nash equilibrium, which kind of transformation family do you really need?\n\nAdditionally, improving the clarity and accessibility of the paper could broaden its appeal and understanding among the NeurIPS community.", "limitations": "n/a", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Strengths\n\n1. **Innovative Framework**: The paper presents a significant extension of the Ellipsoid Against Hope algorithm, applying it to a broader class of games, including extensive-form games.\n   \n2. **Polynomial-Time Algorithm**: The proposed algorithm offers a polynomial-time solution for computing exact $\\Phi$-equilibria, which is a notable advancement in game theory and computational complexity.\n\n3. **Generality and Simplicity**: The framework is described as conceptually simpler than existing methods while being general enough to handle various types of equilibria, such as correlated equilibria and extensive-form correlated equilibria.\n\n4. **Resolution of Open Problem**: The paper addresses and resolves an open question posed by Farina and Pipis (2023) regarding the polynomial-time computation of linear-deviation correlated equilibria.\n\n5. **Technical Depth**: The theoretical foundations and technical depth are robust, with clear definitions, assumptions, and a well-structured algorithmic framework.", "weaknesses": "### Weaknesses\n\n1. **Complexity and Practicality**: While the algorithm is polynomial-time, the degree of the polynomial may be high, potentially limiting practical applicability for very large games.\n\n2. **Empirical Validation**: The paper lacks empirical validation or experimental results demonstrating the practical performance of the proposed algorithm on real-world or benchmark datasets.\n\n3. **Assumptions and Limitations**: The framework relies on specific assumptions, such as the polynomial utility gradient property, which may not hold for all types of games or real-world scenarios.\n\n4. **Clarity and Accessibility**: The paper is highly technical, which might make it less accessible to a broader audience without a strong background in game theory and computational complexity.\n\n5. **Comparative Analysis**: There is limited discussion on how the proposed method compares with other state-of-the-art algorithms in terms of computational efficiency and accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and your comments on the paper. We respond below to the raised weaknesses and questions.\n\n* > [Weakness] Complexity and Practicality\n>\nIndeed, the degree of the polynomial in our algorithm's time complexity is extremely high, rendering it impractical. However, it is a first step in the direction of understanding what classes of equilibria can be computed exactly and efficiently. Currently, in the literature there are no exact-equilibrium algorithms with practical applicability that applies to large classes of games. Our hope is that our simplified algorithmic framework will offer an avenue for future research that will lead to other, more practical such algorithms.\n\n* > [Weakness] Empirical Validation\n>\nThe main contribution of our paper is theoretical; we propose the first polynomial-time algorithm for computing exact $\\Phi$-equilibria in polyhedral games (including extensive-form games, which was a previous open question). Our algorithm includes several nested executions of the ellipsoid method, which has an unwieldy time complexity and is tricky to implement right in practice. We have thus left this as one of the problems for future work.\n\n* > [Weakness] Assumptions and Limitations\n>\nThe polynomial utility gradient assumption is standard and satisfied by many classes of games. Among others, it is satisfied by extensive-form games and by succinct normal-form games [1], which include graphical games, anonymous games, polymatrix games, congestion games, scheduling games, and local effect games. Additionally, as we mention in our paper, this assumption is implicitly made in all no-regret learning algorithms, which are the gold standard for computing equilibria in large games in practice. It is also worth mentioning that if we had no assumption on the access of the game's utilities, the task at hand would be inherently impossible, as any algorithm would have to know all entries of the exponentially-sized utility tensor for the game.\n\n* > [Weakness] Comparative Analysis\n>\nAs we mention in Line 130, we include an extensive discussion of related work in Appendix A. The main body only contains the few most directly related papers that concern the exact computation of correlated equilibria in games. Finally, since our algorithm provides the first polynomial-time algorithm to exactly compute several classes of equilibria in games (such as linear-deviation correlated equilibria in extensive-form games), there is no direct benchmark we could compare to for these cases.\n\n* > [Question] Correlator-Deviator game\n>\nThis is a two-player zero-sum meta-game we define, in which the strategy spaces are: the space of all joint distributions for the first meta-player (Correlator), and the Cartesian product of all sets of deviations for the second meta-player (Deviator). The matrix giving the Correlator's utility is given in lines 302-303.\n\n* > [Question] can you explain how you go from summation inequality of lemma 4.1 to the individual parts' inequality\n>\nWe refer to lines 312-318. In a nutshell, if we assume (without loss of generality) that the identity is always a valid deviation $\\mathbf{I} \\in \\Phi_p$, then a feasible solution $\\mathbf{x}$ of the LP in line 311 will guarantee that $\\mathbf{x}^\\top \\mathbf{U} \\mathbf{y} \\geq 0$ for all $\\mathbf{y} \\in \\mathcal{Y}$. Thus, this inequality will also hold for $\\mathbf{y} = (\\phi_1, \\mathbf{I}, \\dots, \\mathbf{I}), (\\mathbf{I}, \\phi_2, \\dots, \\mathbf{I}), \\dots$, which correspond to the individual parts' inequalities.\n\n* > [Question] how GER does really work efficiently\n>\nIntuitively, our algorithm casts the problem of $\\Phi$-equilibrium computation as one of computing a min-max solution of the Correlator-Deviator bilinear zero-sum game. A min-max solution for the Correlator in this game corresponds to a valid $\\Phi$-equilibrium in the original game. Thus, the GER in our case receives a tuple $\\mathbf{y} = (\\phi_1, \\phi_2, \\dots, \\phi_n)$ of deviations for all players (aka., a Deviator's strategy) and outputs a good-enough strategy $\\mathbf{x} \\in \\Delta(\\Pi_1 \\times \\dots \\times \\Pi_n)$ for the Correlator. One of the crucial ideas for the efficient computation of such a strategy is to notice that we can always compute a product distribution that is good-enough, owing to the existence of fixed points for linear transformation functions. Then, combining the probabilistic method with techniques for decomposing a point of a polytope into a small number of vertices (such as the Caratheodory theorem), it is possible to extract a single pure joint strategy from this product distribution. For more details, we refer to Lemma D.1 and Algorithm 3 in Lines 719-760 of the Appendix.\n\n* > [Question] To be honest, I need elicit explanations for each paragraph between lines 297 and 326, which are the crucial part to make the algorithm works.\n>\nThank you for the recommendation. We will edit the final version of the paper to include the more intuitive explanation we provided for paragraph 312-318 and also slightly improve the language in the rest of these lines.\n\n* > [Question] What is the limit to apply non-linear transformation? In order to get a Nash equilibrium, which kind of transformation family do you really need?\n>\nThe Nash equilibrium is basically defined as a coarse-correlated equilibrium (ie., using external deviations) with the additional constraint that the joint distribution is a product distribution. If we want to apply no-regret dynamics for the computation of Nash equilibria, we know that this is generally only possible in two-player zero-sum games, where it suffices to compute any coarse-correlated equilibrium of the game. In general, there do not exist any uncoupled dynamics that guarantee convergence to Nash equilibria.\n\n### References\n\n[1] Christos H. Papadimitriou and Tim Roughgarden. 2008. Computing Correlated Equilibria in Multi-Player Games. JACM", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DUDPb1Kcci", "reviewer": "Reviewer_2L7d", "summary": "This paper studies the problem of computing phi-equilibria in a general class of games called polyhedral games. Phi-equilibria are a class of game-theoretic equilibria where each player has low regret with respect to some class Phi of linear transformation functions (e.g. this captures various notions of correlated equilibria). Polyhedral games are games where each player has a convex polyhedral action set and where the payoffs are given by multilinear functions (also capturing cases of interest such as normal-form games, Bayesian games, extensive-form games, ...).\n\nIn 2008, Papadimitriou and Roughgarden introduced the Ellipsoid Against Hope (EAH) algorithm which showed how to efficiently compute succinctly representable correlated equilibria in some classes of multiplayer games (including games where writing down a generic correlated equilibrium might take exponential time). This paper generalizes this algorithm to the above much broader set of equilibria and games. In particular, the authors introduce an algorithm which efficiently constructs a Phi-equilibrium in an n-player polyhedral game, with the only requirement being that the class Phi of linear transformation functions has an efficient separation oracle (along with some other mild constraints). \n\nAs with the EAH algorithm, the main technical ingredient is to show that there exists such a correlated equilibrium which can be expressed as a convex combination of a small number of product distributions. To do this, the authors generalize the original technique used in the EAH paper to the problem of computing equilibria in two-player bilinear zero-sum games. In particular, they show how to efficiently compute a minimax equilibrium for one player (in time polynomial in the dimension of their action set) even if the other player has an extremely high-dimensional action set. The idea here is that as long as you can find “good enough responses” to actions of the other player (responses that guarantee you the minimax equilibrium), you can use this find a low dimensional subspace of the opponent’s high-dimensional action space in which a minimax equilibrium must be supported, and finally solve the resulting problem explicitly.", "questions": "Feel free to reply to any element of the review.", "limitations": "Limitations adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Evaluation\n\nUnderstanding the computational complexity of computing various types of game-theoretic equilibria is one of the fundamental questions in the area of learning in games. Recently, there has a been a surge of interest in understanding how to compute various types of correlated equilibria in general-sum games (e.g. recent improvements to the best known swap regret bounds). This paper fits into this line of work, answering a question of the complexity of computing exact forms of correlated equilbria in “large” games (e.g. extensive-form games) by providing a very natural set of conditions for when this is possible.\n\nIn some sense, it is accurate to describe this paper as a mostly straightforward generalization of the EAH algorithm to these more general settings -- the main technical observation (i.e., the reason why the EAH algorithm does not work “out of the box”) being that for linear swap transformations, the complexity of the solution should only depend on the dimensionality of your action space, not on the number of pure strategies (number of extreme points). But I think this is still a valuable observation, and the consequences of this (that you can exactly compute these equilibria for reasonable classes of phi) are not a priori obvious and would be of interest to NeurIPS researchers in this area. \n\nI also very much enjoyed the presentation of this paper. I think it is nice how this paper abstracts out the fundamental problem that the EAH technique solves (find a minimax strategy in an unbalanced two-player game, given only a “good enough response” oracle); I think this gave me a better understanding of the original EAH algorithm, and I would not be surprised if this rephrasing of the subproblem ends up useful elsewhere.", "weaknesses": "See above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review. You are right that in our generalization of the EAH, it is critical that the time complexity depends on the dimensionality of the action space and not on the number of pure strategies (which might be exponentially many in the dimensionality of the action space, as is the case in extensive-form games). This goes beyond the standard Ellipsoid Against Hope algorithm's requirement for the \"polynomial type\" property. We believe that the simplicity and generality of our framework for computing exact $\\Phi$-equilibria is especially nice, as it greatly simplifies the algorithm of [1] for EFCE, while at the same time providing the first polynomial-time algorithm for computing the very general linear correlated equilibria in extensive-form games [2]. Finally, we completely agree that the framework for computing equilibria in bilinear zero-sum games using GERs should be of independent interest, beyond computing $\\Phi$-equilibria in games.\n\n### References\n\n[1] Wan Huang and Bernhard von Stengel. 2008. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics\n\n[2] Gabriele Farina and Charilaos Pipis. 2023. Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games. In Thirty-seventh Conference on Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2wPod0LBYU", "reviewer": "Reviewer_r2xR", "summary": "This paper gives an algorithm for computing exact $\\Phi$-equilibria in polyhedral games. The algorithm follows the general framework of the \"Ellipsoid Against Hope\" method for computing exact correlated equilibria in succinctly represented normal form games. The paper generalizes this method to computing linear $\\Phi$-equilibria (i.e. correlated equilibria where each player's allowed set of deviations are encoded by $\\Phi$), in polyhedral games. The set $\\Phi$ of allowed individual player deviations is required to consist of linear transformations on the player's strategy set. This model captures previously studied variants of correlated equilibria, most notably linear-deviation correlated equilibria, where $\\Phi$ is the set of all linear-swap deviations on sequence-form strategies. Thus the results in this paper give the first polynomial time algorithm for exact computation of linear-deviation correlated equilibria in extensive-form games.\n\nThe key modification needed to the \"Ellipsoid Against Hope\" method is to allow for the use of something weaker than a best-response oracle as a subroutine in solving the two-player meta-game induced by the original polyhedral game. The authors show that for exact linear $\\Phi$-equilibrium computation, it is NP-hard to compute a best-response oracle, but it is tractable to compute a \"good enough\"-response oracle. The method then needs to be modified to use the \"good-enough\"-response oracle to efficiently compute an exact equilibrium. The notion of \"good-enough\" response here means that the response need only achieve utility equal to that at equilibrium in the two-player meta-game.", "questions": "Is there an example of game where exact computation of a linear-$\\Phi$ equilibrium has a natural interpretation that is somehow better than an approximate equilibrium, and where $\\Phi$ naturally should consist of linear functions?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The key insight that only a good-enough response oracle is sufficient for using the \"ellipsoid against hope\" method is simple yet powerful. It gives a more straightforward analysis of prior results on exact computation of correlated equilibria, and solves an open problem on exact computation of linear-swap correlated equilibria.\n\n- The proof that it is NP-hard to compute a best-response oracle demonstrates the necessity of using good-enough response oracles as introduced in this paper, and thus suggests that these techniques could be useful for exact computation of equilibria in other settings.\n\n- The paper is well-written and easy to follow.", "weaknesses": "- A possible weakness is that most of the techniques in the paper (including those that yield the good-enough response oracle) are straight-forward modifications of the \"ellipsoid against hope\" method. I don't necessarily view this as much of a weakness, because the primary insight of the paper is that one does not actually need a best response oracle for this method, and that good-enough response oracles can be constructed using standard techniques.\n\n- Another possible weakness is in the specificity of the problem studied: exact computation of linear-swap correlated equilibria in polyhedral games. Equilibrium computation results are known for approximate equilibria, for exact equilibria in normal form games, and for extensive form correlated equilibria (which are a special case of linear-swap correlated equilibria).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and observations on our paper. We respond to the weaknesses and questions you raised.\n\n* > [Weakness] straightforward modifications of the ellipsoid against hope method\n>\nOur framework balances generality with simplicity, as it greatly simplifies the algorithm of [1] for EFCE, while at the same time providing the first polynomial-time algorithm for computing the very general linear correlated equilibria in extensive-form games [2] (thus, going beyond the standard \"polynomial type\" property of the ellipsoid against hope).\\\nDespite the apparent simplicity of our framework, we do agree that it offers insightful ideas for algorithm design, including the good-enough-response oracles. Finally, as we argue in the Discussion section, we believe that offering simplified algorithmic frameworks can greatly aid algorithm development in the general area.\n\n\n* > [Weakness] specificity of the problem studied\n>\nOur paper gives the first polynomial-time algorithm for computing exact linear-deviation correlated equilibria in extensive-form games, thus capturing the largest yet known set of equilibria in these games that can be computed exactly. Regarding exact equilibria, our work subsumes all previous results in normal-form games, as well as the exact computation of EFCE for extensive-form games (with EFCE being a strictly weaker solution concept than linear equilibria). Finally, we give sufficient conditions that can allow for computing exact linear equilibria in any general polyhedral game.\n\n* > [Question] Is there an example of game where exact computation of a linear-Phi equilibrium has a natural interpretation that is somehow better than an approximate equilibrium, and where \nPhi naturally should consist of linear functions?\n>\nIn this paper we show for the first time that we can compute linear correlated equilibria in polyhedral games in polynomial time. While our focus is exact equilibria, if we stop the ellipsoid iteration earlier, we can also compute $\\epsilon$-approximate equilibria in $\\text{polylog}(1 / \\epsilon)$ steps. This is exponentially better than no-regret dynamics that, instead, require $\\text{poly}(1/\\epsilon)$ steps. Thus, in theory, it is possible to compute equilibria in much higher precision than by using no-regret dynamics.\n\n### References\n\n[1] Wan Huang and Bernhard von Stengel. 2008. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics\n\n[2] Gabriele Farina and Charilaos Pipis. 2023. Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games. In Thirty-seventh Conference on Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "prdP9zlmyf", "reviewer": "Reviewer_un2H", "summary": "The authors this generalize the Ellipsoid Against Hope and develop a simple algorithmic framework for efficiently computing saddle-points in bilinear zero-sum games, even when one of the dimensions is exponentially large.", "questions": "Page 1:\nCan you please give some more details about multi-player games?\n\nPage 2:\nI do not understand Lines 52 -- 58. What do you mean by uncoupled learning dynamics?\n\nPage 3:\nCan you please elaborate on the technicalities behind Item 2?\n\nPage 4:\nCan you please explain a bit more the definition of $\\Phi$-equilibrium?\n\nPage 5:\nLine 218:\nHow do you exactly find the scaling factor?\n\nPage 6:\nI got confused by ($D'$).\n\nHow do you combine the GER responses to represent $x^*$?\n\nPage 7:\nLine 302:\nI do not understand this math display.\n\nPage 8:\nAssumption 4.2 needs to be motivated better :)\n\nPage 9:\nCan you please elaborate on the future work, especially on the bullet regarding Markov games? Thank you!", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength of this work is the significance of the problem considered.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and for helping us improve the presentation of our paper. We will incorporate your suggestions in the final version. We respond to your questions below:\n\n* Page 1: Here, with \"multi-player games\" we refer to games with any number $n$ of players.\n\n* Page 2: Uncoupled learning dynamics refer to no-regret learning dynamics that can be followed by all players in a decentralized manner. The example equilibria that we give in these lines constitute equilibria that can be approximated with known efficient no-regret dynamics.\n\n* Page 3: The requirement for linear transformations $\\phi \\in \\Phi$ implies that $\\mathbb{E}[\\phi(x)] = \\phi(\\mathbb{E}[x])$. For example, this property is used in Lemma 4.1, which is a crucial component of our characterization of exact $\\Phi$-equilibrium computation as a bilinear zero-sum game.\n\n* Page 4: Intuitively, a $\\{ \\Phi_p \\}$-equilibrium is a distribution $\\mu$ over the joint strategy profiles such that, on expectation, no player $p$ has an incentive to unilaterally deviate from the recommended joint strategy $\\mathbf{s} \\sim \\mu$ using any transformation $\\phi \\in \\Phi_p$. Please see Line 181 for a formal definition. We will also incorporate this intuitive description in the final version of our paper. \n\n* Page 5: Since $\\mathbf{y}' = \\alpha \\mathbf{y}$ it should hold that $\\mathbf{y}'[\\emptyset] = \\alpha$. Thus, to find the scaling factor $\\alpha$ we simply need to look at the value of $\\mathbf{y}'$ in the extra dimension.\n\n* Page 6: If we let $x_1, \\dots, x_L$ be the GER response vectors, then (D') is basically identical to (D) but replacing $\\mathcal{X}$ with the convex hull $\\text{co}\\{ x_k \\}$ of the response vectors. Then, to compute the final feasible solution $x^*$ it suffices to solve the linear program (P'). Any valid solution of that LP belongs to $\\text{co}\\{ x_k \\}$ and thus, it is a convex combination of the GER response vectors.\n\n* Page 7: In this math display, we set the values for the meta-game utility matrix $\\mathbf{U}$. Specifically, for the column corresponding to the extra augmented dimension $j = \\emptyset$, the value of $U_{s j}$ is the sum of all players' utilities for the current joint strategy profile. In all other columns $j = (p, a, b)$ we have that $U_{s j}$ is the product of $-\\mathbf{s}_p[a]$ (the $a$-th component of player $p$'s strategy vector $\\mathbf{s}_p$) and $ u_p(  \\mathbf{1}\\_b , s\\_{ -p } ) $ (the utility of player $p$ in strategy profile $s$ under the strategy vector $\\mathbf{1}_b$).\n\n* Page 8: We believe that this assumption is very natural because (a) in normal-form games, it is equivalent to the natural polynomial expectation property that Papadimitriou and Roughgarden have defined in their Ellipsoid Against Hope algorithm and (b) as we have stated in page 2 of the introduction, it is already implicitly assumed in every no-regret learning algorithm. We will also add this short motivation in page 8 as well, thanks!\n\n* Page 9: The open question related to Markov Games would be to investigate whether it is possible to compute exact equilibria of some kind in Markov Games. Note that this is an important class of games that do not directly fall under the category of polyhedral games, so our framework cannot be applied directly. To the best of our knowledge, the question of computing exact correlated equilibria in Markov Games has not been generally studied in the past.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a strong submission that gives new algorithms for exact Phi-equilibria in several settings.
I recommend accepting for spotlight. 


*******************************************

Two writing comments (or really questions to the authors that I wished I had asked earlier):

1. It would be good to elaborate on your second condition that requires the class \Phi to contain only linear transformations.
E.g. explain in more detail what you mean and give a natural example where it doesn't hold.

1-a. You should change l.96 to say that \Phi contains **only** valid linear transformations. 
As written it doesn't really make sense because I can always add the linear transformations to \Phi.

2. Given the NP-hardness result for BR, I find it surprising that finding a response with value greater than 0 is easy. For most NP-hard optimization problems, if you ask whether you can beat some threshold that's also NP-hard. It would be nice to elaborate a bit on why GER is still tractable in some settings.
Decision: Accept (spotlight)