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

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 07:14:13

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.

Main paper: 
  
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: ### Weaknesses

1. **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.

2. **Empirical Validation**: The paper lacks empirical validation or experimental results demonstrating the practical performance of the proposed algorithm on real-world or benchmark datasets.

3. **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.

4. **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.

5. **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.
questions: 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. 

Personally, 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.
Additionally, 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.

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?

Additionally, improving the clarity and accessibility of the paper could broaden its appeal and understanding among the NeurIPS community.
limitations: limitations: n/a
paper_summary: paper_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, ...).

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

As 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.
strength_weakness: strength_weakness: See above
questions: questions: Feel free to reply to any element of the review.
limitations: limitations: Limitations adequately addressed.
paper_summary: paper_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.

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

- 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).
questions: 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: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: See questions below.
questions: questions: Page 1:
Can you please give some more details about multi-player games?

Page 2:
I do not understand Lines 52 -- 58. What do you mean by uncoupled learning dynamics?

Page 3:
Can you please elaborate on the technicalities behind Item 2?

Page 4:
Can you please explain a bit more the definition of $\Phi$-equilibrium?

Page 5:
Line 218:
How do you exactly find the scaling factor?

Page 6:
I got confused by ($D'$).

How do you combine the GER responses to represent $x^*$?

Page 7:
Line 302:
I do not understand this math display.

Page 8:
Assumption 4.2 needs to be motivated better :)

Page 9:
Can you please elaborate on the future work, especially on the bullet regarding Markov games? Thank you!
limitations: limitations: None.

Comments: comment: Thanks for the response! I have read your rebuttal and the other reviews and will increase my score to 7.
Thank you for your response. I have read through the other reviews/responses and maintain my positive evaluation of this paper.
Thank you! :)