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

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.

Strengths

The main strength of this work is the significance of the problem considered.

Weaknesses

See questions below.

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!

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

None.

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.

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

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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

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.

Strengths

Evaluation Understanding 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. In 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. I 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

Questions

Feel free to reply to any element of the review.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

2

Limitations

Limitations adequately addressed.

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.

Strengths

### Strengths 1. **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. 2. **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. 3. **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. 4. **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. 5. **Technical Depth**: The theoretical foundations and technical depth are robust, with clear definitions, assumptions, and a well-structured algorithmic framework.

Weaknesses

### 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

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.

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

n/a