Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the complexity of correlated equilibrium in extensive form games with mediator communication, knowns as the communication or certification equilibria. The main result is a polynomial-time algorithm, specifically a linear program formulation, for computing optimal communication and certification equilibria. To prove this result, the paper define a mediator-augmented games, which basically includes the mediator as an additional player. The new game has  polynomial size and can describe several equilibrium notions.

strengths_and_weaknesses: Strengths: 

-- the study of communication in extensive-form game seems an interesting and well-motivated problem.

-- the fact that for most correlation equilibrium notions, the optimal equilibrium is hard whereas this paper identifies polynomial time algorithm for CE with mediator is interesting.

Weakness:

-- The paper is very notation heavy without much illusion about the intuition of the model. For instance, I was hoping the paper could instantiate their model in one of the listed three applications (i.e., Crowdsourcing and ridesharing, persuasion or automated MD), to familiarize the audience with the setup and the motivation of the mediator.  

-- the techniques of the work appears somewhat standard. It is not clear what the novelty is. Frankly speaking, I spent more time to understand the notations in Section 2 than to understand the proof of the main theorem, which is a natural conversion of the original game to a Stackelberg game with the mediator as the leader. 

-- This is purely an equilibrium optimization paper without any aspect of learning. So it does not seem a good fit to NeurIPS.   

questions: "The infinite family of constraints can be made polynomial-sized by taking a dual of the inner optimization" at the end of Section 3.1 --- would you elaborate on how to achieve this, or is this a known result? 


limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Many papers were dedicated to the study of correlated equilibrium in sequential games in recent years. In this work, the authors argue that focusing on (variants of) correlated equilibrium is too restrictive, as the inherent NP-hardness of finding optimal equilibria precludes them from being used in real-world applications. Because the root of the problem appears to be the imperfect recall of the mediator, i.e. the correlation device, they suggest studying a more general class of mediators, capable of not just sending messages to players, but also receiving them, effectively broadcasting some information. The main result presented in this paper claims that under the assumption that a certain property of signal sets holds, computing an optimal certification equilibrium in sequential games is a polynomial-time problem. As an intermediate result the authors obtain also an analogue of the revelation principle in their setting. Next, the authors introduce two special cases of the certification equilibria, allowing for faster computation (in case of the full-certification equilibria) or incorporation of the mediator’s own observations into their decision-making process (in case of the (S,M)-certification equilibrium). After a short section dedicated to a construction of the entire family of solution concepts based on the mediator’s recall and observations and the players’ abilities to lie and deviate, recovering several correlated equilibria as special cases, the authors move to the empirical evaluation. The main outcome of the empirical evaluation appears to be that when the mediator seeks to maximize social welfare, in the three classes of games examined by the authors, the algorithm computing the certification equilibria provides higher-quality solutions (in general) in a shorter time than the correlated equilibria. 
strengths_and_weaknesses: The idea this paper examines seems extremely intriguing to me. The motivation is clear, and the connections the authors make between different solution concepts and the argumentation about their application validity and computability presents an interesting point of view which I am inclined to mostly agree with. As far as I can tell, after going through the appendix as well, the results seem to be original and correct. The experiments further corroborate the claims, letting the reader compare both the optimal values and the computational times, and the way how the authors visualize the results is coherent and easily comprehensible. 

My main concern relates to this work’s overall exposition, though. The field of algorithmic game theory, and sequential games in particular, often requires a careful buildup, patiently guiding the reader through all the introduced concepts, because of their inherent complexity and an abundance of notation. Especially when discussing multiple types of equilibria. The authors certainly do not seem to be at fault here, but NeurIPS’ space limit does not appear to provide enough space for it. Because of that, even as someone fairly acquainted with the field, I had to reread several parts multiple times to understand what the authors are perhaps trying to say and how do the individual solution concepts they discuss relate. The absence of any examples besides the briefly described Fig1 further confuses the reader. For example, it took me a while to understand even why Theorem 3.2 immediately implies the polynomial computability of optimal communication equilibrium when it speaks about certification equilibria. Or, why program (1) is indeed linear. If I understand it well the players’ optimal strategies are basically projections from the mediator’s pure strategy space, is that correct? Many details are missing also from the experimental section, e.g., not explaining even informally which domains were employed and why mediator concepts make sense in those situations, literally referring the reader not even to the appendix, but to a completely different work. 

To sum up, I feel like this work puts me in a difficult position: on one hand, I enjoyed the ideas the authors are presenting, but on the other it may be more suitable for a conference with a more generous space limit, or some journal. I vote to accept it as I believe that more examples and discussions could be put in the appendix (even though it is not optimal), and I look forward to further discussing these issues with the authors and fellow reviewers in the next reviewing phase.

questions: To strengthen the intuition about the presented concepts, could the authors give an example of some related setting (besides the case of imperfect recall of the mediator) that could NOT be modeled using a polynomially-computable certification equilibrium, e.g., because the NRC does not hold?

How robust are the results with respect to the optimized function? For example, do the certification equilibria perform well even when the mediator optimizes their own (let’s say) random utility?

How large are the games used in the experiments, i.e. with how many information sets?

How do the algorithms scale with the number of players? Could, e.g., the full-certification equilibrium be computed even in some moderately-sized game with four or five players?

limitations: I could not think of any other limitation not addressed already by the authors.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies extensive-form games augmented with a mediator that receives and sends messages from and to the agents involved in the game. In the particular case in which only the mediator can send messages and these can be interpreted as action recommendations, such an extended game resembles the one in the definition of correlated equilibria. At the same time, allowing for messages from the agents to the mediator allows to capture different notions of equilibrium, such as the communication equilibrium and the certification equilibrium. By leveraging such an augmented representation, the paper provides a linear programming formulation for finding optimal communication/certification equilibria in n-player extensive-form games in polynomial time. The theoretical results are complemented with an extensive experimental evaluation on a standard testbed of games.

strengths_and_weaknesses: ORIGINALITY

(+) The paper studies equilibrium concepts (communication and certification equilibria) that have never been addressed before by the algorithmic game theory community.

(-) The techniques employed by the authors are fairly standard, since they consist in a simple linear programming formulation.

QUALITY

(+) As far as I am concerned the results are sound.

(-) I think that more formalism in proving the technical results is needed. There are only two propositions in the paper, whose proofs given in the appendix are not sufficiently formalized in mathematical terms. Moreover, I think a proof is also need in order to shows the correctness of the linear programming formulation.

CLARITY

(+) Overall, the paper is well written and easy to follow.

(-) There are only some minor problems that I list in the following:

	(*) Line 28: Cite [24] after “extensive-form”.

	(*) In paragraph “Applications and related work.”: You should cite the recent works on learning dynamics converging to correlated equilibria in extensive-form games, such as: “No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium” (NeurIPS 2020), “Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games” (ICML 2021), and “Hindsight and Sequential Rationality of Correlated Play” (AAAI 2021), and others.

	(*) Line 95: Remove “player”.

	(*) Line 106: “We also will” is “We will also”.

	(*) Adding an example of extended game would help.

	(*) The terms used in the caption of Table 1 do not appear in the table.


SIGNIFICANCE

(+) The results could be of interest for the part of the NeurIPS community interested in algorithmic game theory.

(-) I have some concerns of the significance of the experimental results. It seems to me that the linear programming formulation does not scale well on large games, especially that one for communication equilibrium (which I think is the most interesting solution concept).

questions: 1) Can you provide more details as to why you can restrict the space of messages by using the revelation principle (see footnote 3)? I think more details on this are need in the paper.

2) It is not clear to me what you mean by “truthful EFCE” and other “truthful” concepts. Can you provide some more details on this.
limitations: Yes.
review_title: null

final_score: 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.
review_content: summary: This paper studies the problem of computing optimal equilibria in extensive-form games. Standard equilibrium notions are hard (i.e., NP-hard) to optimize (e.g., for revenue or social welfare) in extensive-form games. The authors study communication and certification equilibria, showing that they can be optimized in polynomial time. These arise when a mediator is present who can send and receive messages from the players. They build additional results on top of this main result, namely:
- A class of equilibria where the players cannot reveal false information, leading to a linear size linear program (scales better than other notions).
- They consider the integration of payments, allowing the mediator a more expressive way to modify the outcome in settings where they are permitted.
- They define a family of equilibria from the main result that correspond to different tweaks to the setting, e.g., imperfect recall for moderator. They recover existing algorithms for equilibrium computation as special cases of their general method.
strengths_and_weaknesses: Originality:
- They are the first to show that communication and certification equilibria can be optimized in polynomial time for extensive-form games.
- The paper lays out a map of equilibrium concepts and shows that many can be computed through the same meta-algorithm.
- Coverage of related work seems adequate.

Quality:
- There is a substantial amount of math I did not check, but the work appears technically sound.
- It's a theory paper, so not a lot of attention is spent on thinking about potentially real systems. I found myself wondering at some points wishing for a more direct discussion of motivation.
- There is not a lot of discussion of weaknesses.
- The authors' claims seem well supported.

Clarity:
- It's math-heavy. The notation was explained pretty clearly and a substantial chunk of the paper is spent doing so. I would prefer more pictures or examples to help explain (perhaps in the appendix due to space constraints).
- The authors say they will not release code, which I don't understand.

Significance:
- The results seem like they could be useful in some real-world contexts. In any case, it is good to know that such tractable families of equilibria exist.
- The generalization of past algorithms provides a bit of interesting big picture structure.
questions: N/A
limitations: Negative social impact is not a concern here, in my opinion. There is little explicit discussion of limitatins.
review_title: null

Meta-review: metareview: Executive summary:

Motivated by the potential hardness of computing optimal corrrelated equilibria, this paper looks at variants of correlated equilibria -- communication and certification equilibria --- where the mediator has additional power. The main result of the paper is a poly-time algorithm for computing optimal such equilibria, which embeds the mediator into the original game in the fashion of a two-player Stackelberg game and shows that the resulting game can be solved optimally via linear programming. The paper implies certain existing poly-time algorithm as special cases.

Discussion:

Overall this paper struck me as rather original, and the main result is rather general and encouraging. I think it may motivate follow-up motivation, and variants of it may even have practical use cases.

Accept.
confidence: Certain
Decision: Accept