Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

Summary

The authors proposed a learning-based framework to solve for optimal equilibria in n-player general-sum extensive-form games. The key idea is to leverage Lagrangian relaxation and convert such games to 2-player zero-sum extensive-form games which can then be solved using known learning methods that solve for minimax equilibria.

Strengths

* significance I believe this work could be a significant contribution to the field as it proposes a computationally practical method that solves for optimal equilibria in n-player general-sum games. This is significant as it offers a language to speak about optimality of equilibria in addition to stability and could make game theoretic methods attractive in wider classes of practical applications. * originality I believe the proposed method is novel. * clarity The paper is well written and relatively easy to follow. * quality The theoretical derivation of the method appears sound; the empirical results seem extensive though it would be interesting to understanding additional details which I have commented below.

Weaknesses

The presentation of the empirical results seems to be primarily focused on the efficiency and feasibility of converting the problem of solving for optimal equilibria in n-player general-sum EFGs to solving minimax equilibria in two-player zero-sum games. For instance Table 1 presented runtime results of the learning-based method compared to solving LP directly. Would it be possible to provide additional details on optimality as well especially in general-sum games such as Sheriff where we know the value of max-welfare equilibria (e.g. https://www.cs.cmu.edu/~gfarina/2020/efcce-aaai20/coarse-correlation.aaai20.pdf)? Would the proposed method scale up to these instances of sheriff game?

Questions

I find the presentation relatively easy to follow. Some minor clarifying questions below: L42: "... including information design, and solution concepts such as ....". This statement appears several times but it is a bit confusing to follow. I can understand the statement after reading the paper in full but consider rephrasing it or splitting it up to make it more readable? L63 nit: clarify what $T$ stands for. L145: I find the discussion on the revelation principle interesting but it's not clear how general it would apply to games. Could you comment on this and if the set of benchmark games studied in this work would satisfy this property? L191: "All players, ... are constrained to [act/play, missing] according to $d_i$..." is mediator considered to be included in "All players" in this statement? If so, what does playing according to $d_i$ mean for the mediator? Is the mediator limited to deterministic policies in this two-player game? L192: "If nature picked ..., the utility is ...", --> "the utility [to the mediator] is ..."?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have discussed practical limitations of the method in snippets of the main text.

Summary

The paper focuses on addressing the challenge of computing optimal equilibria in extensive-form games. The authors introduce the revelation principle, which transforms the problem into a linear programming (LP) task. They propose using Lagrange relaxations to solve the LP, treating the resulting saddle-point problem as a Nash equilibrium in a zero-sum two-player game. The authors explicitly construct such zero-sum game. To efficiently find the solution, the authors employ regret minimization over conic hulls. Additionally, they highlight the flexibility of their approach by showing that other algorithms for zero-sum two-player games can be utilized, offering different convergence rate guarantees or achieving last-iteration convergence. The paper concludes with thorough experimental evaluations, demonstrating the effectiveness and scalability of their proposed methods across various simple games.

Strengths

- The paper addresses the significant problem of computing optimal equilibria in game theory. By reducing this problem to zero-sum games, the authors provide a framework for finding optimal equilibria. The key contribution lies in the fact that existing algorithms for zero-sum extensive form games can be directly applied to this problem. This reduction greatly enhances the understanding and applicability of the proposed approach. - The experimental evaluation conducted by the authors is robust and contributes to the strength of their work. They provide evidence of the scalability of their methods through preliminary experiments. This not only showcases the effectiveness of the proposed techniques but also demonstrates their potential for real-world applications. The inclusion of experimental results further reinforces the practical relevance of the research and adds value to the overall paper.

Weaknesses

My only concern is about the revelation principle. The reduction in the paper relies on the revelation principle, which is a fundamental concept. However, it is not clear regarding the specific conditions under which a fixed pure strategy d_i exists for different players and within which games and equilibria this concept applies. Additionally, how to effectively find such d_i strategies is also a problem.

Questions

- See the above weakness. - What does 'optimal direct equilibria' mean in line 162. Moerover, if the revelation principle fails, there's no fixed pure strategy d_i. In this case, how to get a similar problem of (G). - In the experiment of auction design, to demonstrate scalability, is it possible to conduct an experiment if each bidder's valuation is sampled from uniform distribution in [0,1].

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have partially addressed the limitations of their work, though there is space for improvement (see the section Weaknesses and Questions).

Summary

This paper studies the computation of optimal equilibria in multi-player extensive-form games via no-regret learning algorithms. The key idea is to take the constrained LP formulation of the optimal equilibrium problem proposed by Zhang and Sandholm and consider the saddle point formulation, which can then be solved using no-regret learning algorithms. In order to alleviate the large $\lambda^*$, a binary-search based algorithm is proposed. Finally, the algorithms are compared with a LP-based method on several tabular games as well as for an auction-design problem.

Strengths

- The paper is well-written. The results presented clearly and the writing is easy to follow. - The experimental results seem compelling as it has an order of magnitude advantage in wall-clock time over the LP-based method. This advantage is consistent across a set of diverse instances.

Weaknesses

- I have some concerns about the LP formulation (G). Consider a $N$ player normal form game with $A$ actions per player for instance; it seems that for the correlated equilibrium in such a game, the $\mu$ in (G) would need to have dimension $A^N$. However, no swap-regret algorithms can find an approximate correlated equilibrium with $\tilde{O}(NA^2/\epsilon^2)$ samples. It seems that the LP formulation (G) can lead to suboptimal dependence on the number of players. - Perhaps related the previous point, while in Line 79 the authors claim that "Our algorithm significantly outperforms existing LP-based methods", in the experiments it is only compared against the LP based solution to (G) proposed by Zhagn and Sandholm. Is (G) the only known LP formulation of the optimal equilibrium problem? If not, wouldn't it make sense to compare against those as well?

Questions

Have the authors tried gradient based methods (such as extra-gradient or gradient descent-ascent) on the saddle-point problem (L1)?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This paper does not have foreseeable negative societal impact.

Summary

This paper presents a novel approach to compute optimal equilibria in multi-player extensive-form games through the use of Lagrangian relaxation as a two-player zero-sum extensive-form game. Building upon the mediator augmentation game framework, the proposed computing approach significantly contributes to the reduction of zero-sum games, thereby holding substantial implications for mechanism design and information design. Furthermore, it plays a pivotal role in fostering a well-balanced hierarchy of concepts.

Strengths

-- The investigation of computing minimax equilibria in extensive-form games is an interesting and well-motivated problem. -- Most correlation equilibrium notions pose challenges in finding optimal equilibria, whereas the framework presented in this paper offers a learning-based algorithm to compute them.

Weaknesses

-- The paper lies heavily on notation that lacks intuitive explanations. To enhance reader understanding, a schematic representation of the mediator-augmented game framework should be included in the main body. -- The approach proposed in this paper resembles a transformation of the original game into a mediator-led Stackerberg game. It would be beneficial to discuss and compare existing research on equilibrium solutions for zero-sum games in Stackelberg games to provide a contextual background for the paper's contribution. Lack controlled experiments involving additional algorithms for equilibrium solutions in Stackelberg games.

Questions

Why does the space of messages can be restricted by using the revelation principle? I think more details on this are necessary in the paper.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A