Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games

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:

• Page 1: Here, with "multi-player games" we refer to games with any number $n$ of players.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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$).

• 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!

• 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.

Thank you for your review and observations on our paper. We respond to the weaknesses and questions you raised.

• [Weakness] straightforward modifications of the ellipsoid against hope method

Our 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).
Despite 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.

• [Weakness] specificity of the problem studied

Our 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.

• [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 Phi naturally should consist of linear functions?

In 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.

References

[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

[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.

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.

References

[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

[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.

Thank you for your thorough review and your comments on the paper. We respond below to the raised weaknesses and questions.

• [Weakness] Complexity and Practicality

Indeed, 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.

• [Weakness] Empirical Validation

The 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.

• [Weakness] Assumptions and Limitations

The 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.

• [Weakness] Comparative Analysis

As 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.

• [Question] Correlator-Deviator game

This 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.

• [Question] can you explain how you go from summation inequality of lemma 4.1 to the individual parts' inequality

We 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.

• [Question] how GER does really work efficiently

Intuitively, 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.

• [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.

Thank 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.

• [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?

The 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.

References

[1] Christos H. Papadimitriou and Tim Roughgarden. 2008. Computing Correlated Equilibria in Multi-Player Games. JACM