Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games
Authors: Brian Hu Zhang
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)

Abstract: For common notions of correlated equilibrium in extensive-form games, computing an optimal (e.g., welfare-maximizing) equilibrium is NP-hard. Other equilibrium notions---communication and certification equilibria---augment the game with a mediator that has the power to both send and receive messages to and from the players---and, in particular, to remember the messages. In this paper, we investigate both notions in extensive-form games from a computational lens. We show that optimal equilibria in both notions can be computed in polynomial time, the latter under a natural additional assumption known in the literature. Our proof works by constructing a {\em mediator-augmented game} of polynomial size that explicitly represents the mediator's decisions and actions. Our framework allows us to define an entire family of equilibria by varying the mediator's information partition, the players' ability to lie, and the players' ability to deviate. From this perspective, we show that other notions of equilibrium, such as extensive-form correlated equilibrium, correspond to the mediator having imperfect recall. This shows that, at least among all these equilibrium notions, the hardness of computation is driven by the mediator's imperfect recall. As special cases of our general construction, we recover the polynomial-time algorithm of Conitzer & Sandholm [2004] for automated mechanism design in Bayes-Nash equilibria, and the correlation DAG algorithm of Zhang et al [2022] for optimal correlation. Our algorithm is especially scalable when the equilibrium notion is what we define as the full-certification equilibrium, where players cannot lie about their information but they can be silent. We back up our theoretical claims with experiments on a suite of standard benchmark games. 

Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games
Brian Hu Zhang
Tuomas Sandholm Computer Science Department, CMU Strategic Machine, Inc. Strategy Robot, Inc.
Computer Science Department Carnegie Mellon University bhzhang@cs. cmu. edu
Optimized Markets, Inc. sandholm@cs, cmu edu
Abstract
For common notions of correlated equilibrium in extensive-foon games, comput- ing optimal (e.g., welfare-manse maximizing)) equilibrium is NP-hard. Other equi- [11] and certification [12] equilibria aqulibriaaaugment augment the game with mediator that has the power to both send and receive messages and from the players-and, in particular, to remember the messages. this paper, we investigate both notions in extensive-form games from computational lens. We show that optimal equilibria in both notions can be computed in polynomial time, the latter under natural additional assumption known the literature. Our proof works by constructing a rrediator-augment explicitly represents the mediator's decisions and actions. Our framework allows to define an entire family of equilibria by varying the mediator's 's information partition, the players' ability to lie, and the players' ability deviate. From this perspective, we show that other notions of equilibrium, such as extensive-form correlated equilibrium, correspond to the mediator having imperfect recall. This shows that, at least among all these equilibrium notions, the hardness of compu- tation is driven by the mediator's imperfect recall. As special cases of our general construction, recover 1) the polynomial-time algorithm of Conitzer and Sand- holm [8] for automated mechanism design Bayes-Nash equilibria and 2) the correlation DAG algorithm of Zhang al. [31] for optimal correlation. Our algo- rithm is especially scalable when the equilibrium notion is what we define as the call-certification equilibrium, where players cannot lie about their information but they can be silent. We back up our theoretical claims with experiments on a suite of standard benchmark games.
librium
game of polynomial size that
Introduction
Various equilibrium notions in general-sum extensive-form games are used to describe situations where the players have access to a trusted third-party mediator, who can communicate with the players. Depending on the power of the mediator and the form of communication, these notions include the normal-form [1] and extensive-form correlated equilibrium (NFCE and EFCE) [29], the normal-form [25] and extensive-form [10] coarse coarse-correlated equilibrium (NFCCE and EFCCE), the communication equilibrium [11], and the certification equilibrium [12].
Several of these notions, in particular the EFCE and EFCCE, were defined for mainly computa- tional reasons: the EFCE computationallly-rassnii a computationally-rasonbbbll relaxation of EFCE. When the goal is to compute a single correlated equilibrium, these relaxations are helpful: there are polynomial-time algorithms for computing an EFCE [16]. However, from the perspective of computing optimal equilibria that is, equilibria that
relaxation NFCE, and the EFCCE as
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

maximize the expected value of a given function, such as the social welfare evenn ations fall short: for all of the correlation notions above, computing an optimal equilibrium of an extensive-form game is NP-hard [29, 10].
even these relax-
On the other hand, notions of equilibrium involving communication in games have arisen. These dif- fer from the notions of correlation in that the mediator can receive and remember information from the players, and therefore pass information between players as necessary to back up their sugges- tions. Certification equilibria [12] further strengthen communication equilibria by allowing players to prove certain information to the mediator. To our knowledge, the computational complexity of op- timal communication or certification equilibria has never been studied. We do so in this paper. The main technical result of our paper is polynomial-tims algorithm for computing optimal communi- cation and certification equilibria (the latter under a certain natural condition about what messages the players can send). This stands in stark contrast to the notions of correlation discussed above.
To prove our main result, we define a general class of mediator-augmentt games, each having polynomial size, that is sufficient to describe all of the above notions of equilibrium except the NFCE We also build on this main result in several ways.
1. We define the full-certification equilibrium, which is the special case in which players cannot lie to the mediator (but can opt out of revealing their information). In this case, the algorithm is linear program whose size is almost linear in the size of the original game. As such, this special case scales extremely well compared to all of the other notions.
2. We formalize notions for incorporating paymenls in the language of our augmented game. By using payments, mediators can incentivize players to play differently than they other- wise would, possibly to the benefit of the mediator's utility function.
3. We define entire family of equílibria using our augmented game, that includes as spe- cial cases the communication equilibrium, certification equilibrium, NFCCE, EFCCE, and EFCE. From this perspective, show that other notions of equilibrium, such extensive- form correlated equilibrium, correspond to the mediator having imperfect recall. This shows that, at least among all these equilibrium notions, the hardness of computation is driven by the mediator's imperfect recall. We argue that, for this reason, many stated practical applications of correlated equilibria should actually be using communication or certification equilibria instead, which are both easier to compute (in theory, at least) and better modelling the decision-making process of a rational mediator.
4. We empirically verify the above claims via experiments on a standard set of game instances.
Applications and related work. Correlated and communication equilibria have various applications that have been well-documented. Here, we discuss just a few of them, as motivation for our paper. For further discussion of related work, especially relating automated dynamic mechanism design and persuasion, see Appendix F.
Bargaining, negotiation, and conflict resolution [4, 9]. Two parties with asymmetric information wish to arrive at an agreement, say, the price of an item. A mediator, such as a central third-party marketplace, does not know the players' information but can communicate with the players.
Crowdsoureing and ridesharing [13, 22, 31]. A group of players each has individual goals (e.g., to make money by serving customers at specific locations). The players are coordinated by a central party (e.g., a ridesharing company) that has more information than any one of the players, but the players are free to ignore recommendations if they so choose.
Persuasion in games [17, 3, 23, 14,30) 30]. The mediator (in that literature, usually "sender") has more information than the players ("receivers"). and wishes to tell information to the receivers so as to persuade them to act in a certain way.
Automated mechanism design [6, 8, 33, 35, 26, 34, 18, 19]. Players have private information un- known to the mediator. The mediator wishes to commit to strategy- -that is, set a mechanism- such that players are incentivized to honestly reveal their information. In fact, in Appendix E we will see that recover the polynomial-time Bayes-Nash randomized mechanism design algorithm of (6, 8] as a special case of our main result.
We do not consider the NFCE, because it breaks our paradigm, which enforces that the mediator's recom- mendation be single action. In whether it is possible to even find one NFCE in polynomial time, not to mention optimal one.
NFCE, the whole strategy needs to be revealed upfront. It is an open question

---

Some of the above examples are often used to motivate correlated equilibria. However, when the mediator a rational agent with the ability to remember information that it is told and pass the infor- mation between players as necessary, we will argue that communication or certification equilibrium should be the notion of choice, for both conceptual and computational reasons.
Preliminaries
In this section, we discuss background correlation in extensive-form games.
Extensive-form games. An extensive-form game T with n players consists of the following.
1. A directed tree of nodes or histories H. whose root is denoted Ø. The depth of the tree will be denoted T. The edges out of nodes are labeled with actions, and the set of such actions will be denoted Ax. Given a node h E H and action a at h, the child reached by following action a node h is denoted ha. The set of terminal (leaf) nodes in H is denoted Z. Terminal nodes will always be denoted 2 throughout the paper.
2. A partition H.', \ Z = Hc L 74, L... .... H.p of nodes, where Mi is the set of all nodes at which player plays and player Hc is the set of chance nodes.
3. For each player i, a partition I; of player i's decision nodes, H4 into information sets or
infosets. Every node in a given information set I must have the same set of actions, denoted
A₁. We will call the partition I I1 L .... L LIn,, the players' information partition.
4. For each player i, ulility vector u. E [0. 1)2, where u; [=] denotes the utility achieved by player at terminal node z.
5. For each chance node h Hc. a probability distribution p(- (b) over the children of h.
The sequence (y) is the list of infosets reached by player i, and actions taken by the player at those infosets, on the Ø + h path, not including the infoset at h itself (if any). We will assume that each player has perfect recall-thar that is, for each infoset 7, the sequence of the player acting at T should be the same for each node in I. We will denote this sequence (T). In perfect-recall games, nonempty sequences will be identified by the last infoset-action pair Ia in them.
We also will assume that games are timeable and fixed-turn-order, that is, information sets do not span multiple levels of the tree, and all nodes in the same layer of the tree belong to the same player".
We will use the following notation. The relation 3 denotes the natural precedence order induced by the tree H: we write 3 h' means that h is an ancestor of h' (or h = h'), and for sets S,S', we say S I S" if there are some h E S, h e S' such that h = h', The binary operation A denotes the lowest common ancestor: h A h/' is the lowest node u such that u 3 h, h'.
For sequences, (h) = (o1 (h)....,, on (h)) denotes the joint sequence of all players at node h. ((a) denotes the set of possible next infosets following sequence a, that is, N(o)) = [I : oTT)=
r). The set Σ; denotes the set of sequences of player i, and Σ denotes the set of all sequences across all players (i.e., Σ E,).)
pure strategy for a player is selection of one action for each information set 7 E I4. pure profile is tuple of pure strategies. A correlated profile is a distribution over pure profiles.
We will generally work with strategies in realization form (see e.g., Koller et al. [20]). Given a pure strategy x, we say that æ plays to z E Z if æ plays every action on the 2 + path. We will call the vector E {0, 1] 2 the realization form of x. The realization form of mixed strategy is the appropriate convex combination. The set of mixed strategies forms convex subset of IR that, so long as the player has perfect recall, can be expressed using linearly many constraints and variables.
We will occasionally need to discuss changing information partitions of r. If J = Ti U.... Jn is another valid information partition, we will use r to denote the game I' with its information partition replaced by J. We will also occasionally need to talk about multiple games simultancously; where this the case, we will mark attributes of the game the same as the game itself. For example, H is the node set of game f.
Timeability is not without loss of generality, but any game for which the precedence order < is partial order over infosets can be converted to a timeable game by adding dummy nodes. Given timeability, fixed-ture order is without loss of generality, also by adding dummy nodes
3

---

Communication and certification equilibria. Here, we review definitions related to communica- tion equilibria, following Forges [11] and later related papers.
Definition 2.1. Let S be a space of possible messages. A pure mediator strategy is a map d S S, where S denotes the set of sequences in S of length most T. A randomized mediator strategy (hereafter simply mediator strategy) is distribution over pure mediator strategies.
We will assume that the space of possible messages is large, but not exponentially so. In particular, we will assume that {1} UZ U Un A, S S (i.e., messages can at least be nothing, information, or actions)' and that |S] S poly will give algorithms that need S as an input that wish to run in time poly((?!))
The latter assumption is mostly for cleanliness in stating results:
mediator strategy augments game as follows. If the strategy randomized, first samples a pure strategy d, which is hidden from the players. At each timestep i, player reaches a history at which she must act, and observes the infoset I 3 h. She sends a message 8; E to the mediator. The mediator then sends a response d(s1,..... 8,), which depends on the message as well as the messages sent by all other players prior to timestep L. Then, the player chooses her action E An. We will call the sequence of messages sent and received between the mediator and player i, the transcript with player i. A communication equilibrium" / is a Nash equilibrium of the game I' augmented with a mediator strategy. The mediator is allowed to perform arbitrary communication with the players. In particular, the mediator is allowed to pass information from one player another. Further, the players are free send whatever messages they wish to the mediator, including false or empty messages. These two factors distinguish communication equilibria from notions of correlated equilibria. In Section 3.4 will discuss this comparison in greater detail.
A useful property the literature on communication equilibria the revelation principle (e.g., [I].. Informally, the revelation principle states that any outcome achievable by an arbitrary strategy profile can also be achieved by a direct strategy profile, in which the players tell the mediator all their information and are subsequently directly told by the mediator which action to play. In order to be a communication equilibrium, the players still must not have any incentive to deviate from the protocol. That is, the equilibrium must be robust to all messages that player may attempt to send to the mediator, even if in equilibrium the player always sends the honest message.
Forges and Koessler [12] further introduced a form of equilibrium for Bayesian games which they called certification equilibria. In certification equilibria, the messages that a player may legally send are dependent on their information; as such, some messages that player can send are verifiable. At each information set I E I, let S S S denote the set of messages that the player at infoset / may send to the mediator. We will always assume that / E S, and 1 E S, for all I. That is, all players always have the options of revealing their true information or revealing nothing.
3 Extensive-form S-certification equilibria
The central notion of interest in this paper is a generalization of the notion of certification equilibria [12] to extensive-fomm games.
Definition 3.1. Given an extensive-form game and a family of valid message sets = (S, : I e Z). an S-certification equilibrium is Nash equilibrium of the game augmented by randomized mediator, which each player at each information set / is restricted to sending a message & E S₁.
The existence of S-certification equilibria follows from the existence of Nash equilibria, which are the special case where the mediator does nothing.
We will need one extra condition on the message sets, which is known as the nested range condition (NRC) [15]: if I Sr, then S, C Sp. That is, if player with information I' can lie by pretending to have information I, then that player can also emulate any other message she would have been
'A priori, although the messages are given these names, they carry no semantic meaning. The revelation principle is used to assign natural meaning to the messages.
*Previous models of communication in games [11, 12] usually worked with model in which players send messages, receive messages, and play moves simdtaneously, rather than sequence as in the extensive-gat game model that we use. The simultaneous-moo move model is easy to recreate in extensive form: by adding further "dummy nodes" at which players learn information but only have one legal action, we can effectively re-order when players ought to communicate their information to the mediator.

---

able to send at I. Equivalently, the honest message I should be the most certifiable message that a player can send infoset I. Our main result the following.
Theorem 3.2. Let uM E R2 be an arbitrary wilityy vector for the mediator. Then there is a polynomial-time algorithm that, given a game T and message set family S satisfying the nested range condition, computes an optimal S-certification equilibrium, that is, one that maximizes Eg uM[z] where the expectation over playouts of the game under equilibrium.
In particular, by setting S, = for all I, Theorem 3.2 implies that optimal communication equilibria can be computed in polynomial time.
The rest of the paper is organized follows. First, we will prove our main theorem. Along the way, we will demonstrate form of revelation principle for S-certification equilibria. We will then discuss comparisons to other known forms of equilibrium, including the extensive-form correlated equilibrium [29], and several other natural extensions of our model. Finally, we will show exper- imental results that compare the computational efficiency and social welfare of various notions of equilibrium on some experimental game instances.
3.1 Proof of Theorem 3.2: The single-deviator mediator-augmmented game
In this section, we construct game f. with n + players, that describes the game I where the mediator has been added as an explicit player. This game has similar structure to the one used by Forges [11, Corollary 2]. but, critically, has size polynomial in [7]. This is due to two critical differences. First, the players are assumed to either send I. or send messages that mediator cannot immediately prove to be off-equilibrium. In particular, if the player's last message was / and the mediator recommended action a at 1, the player must send a message I' with o ((') = Ia. If this will assume that S₁ consists of
impossible, the player must send 1. Therefore, in particular, only 1 and information sets at the same level as I. Second, only one player is allowed to deviate. Therefore, the strategy of the mediator is not defined in cases where two more players deviate.
We now formalize I' Nodes in I' will be identified by tuples (h, r. where h E H. is history in I, T = (Ti...., Tw) is the collection transcripts with all players, and r E {REV, REC, ACT] is stage marker that denotes whether the current state is one in which player should be revealing information (REV), the mediator should be recommending a move (REC), or the player should be selecting an action (ACT). The progression of I' is then defined as follows. We will use the notation [i-s] to denote appending message to тІ-
The root node of I' is (Ø, (Ø...., Ø), REV).
Nodes (z, REV) for = E Z are also terminal in I'. The mediator gets utility uu[z], where u is the mediator's utility function as in Theorem 3.2. All other players i get utility u, [z].
Nodes (h, REV) for non-terminal h are decision nodes for the player i who acts h.
1. If i is chance, there is one valid transition, to (h, ACT).
2. If some other player j # has already deviated (i.e., (h) * T2)), there is one valid transition, to (h, rii-7]. REC) where / h.
3. If player has deviated
one has deviated, then player i observes the infoset 7 3 h. and selects a legal message I' E ((L) to send to the mediator Transition to (h, - (i-7"') REV).
At (h, T, REC) where h E Hi, the mediator observes the transcript and makes a recom- mendation a. If 7. contains any 1 messages, then L. Otherwise, a is legal action a E A,, where I is the most recent message in T.. Transition to (h, ACT)..
Nodes (h, T, ACT) for non-terminal are decision nodes for the player who acts h. 1. If is chance, then chance samples a random action ~ p(-1h). Transition to (ha, T, REV).
2. If some other player j * has already deviated, there is one valid transition, to (ha, T, REC), where a is the action sent by the mediator.
If contains any 1 messages, then take (T))
5

---

then the mediator replies with an action 3. If player i has deviated or no one has deviated, then player observes the transcript Ti and selects an action a' An. Transition to (ha', T, REV). The action a' need not be the recommended action.
Since at most one player can ever deviate by construction, and the length of the transcripts are fixed because turn order is common knowledge, the transcripts T can be identified with sequences as of the deviated player, if any. We will make this identification: we will use the shorthand ht to denote the history (h, (a_ o,), REV). and h for (h, (h), REV) (i.e., no one has deviated yet). Therefore, in particular, this game has at most ((HH[[=)) histories.
For each non-mediator player, there is well-defined direct strategy # for that player: always report her true information 3 h, and always play the action recommended by the mediator. The goal of the mediator is to find strategy EM for itself that maximizes its expected utility, subject to the constraint that each player's direct strategy is a best response-thal is, find oy such that (dM: , ( is (strong) Stackelberg equilibrium of f.
We claim that finding a mediator strategy ZM that is a strong Stackelberg equilibrium in I' is equiv- alent to finding an optimal S-certification equilibrium in I. We prove this in two parts. First, we prove a version of the revelation principle for S-certification equilibria.
Definition 3.3. An S-certification equilibrium is direct if it satisfies the following two properties.
1. (Mediator directness) If the transcript тr of a player is exactly some sequence of player i, and player i sends an infoset I with (1)
a E A₁. Otherwise the mediator replies
2. (Player directness) In equilibrium, players always send their true information I, and, upon receiving an action a E A1, always play that action.
Proposition 3.4 (Revelation principle for S-certification equílibria under NRC). Assume that S satisfies the nested range condition. For any S-certification equilibrium, there is realization- equivalent direct equilibrium.
Omitted proofs can be found in the appendix. Since direct mediator strategies are exactly the me- diator strategies in f', and the player strategies only limited versions of what they allowed to do in S S-certification equilibrium, this implies that, for any S-certification equilibrium, there is a mediator strategy iM in such that (&M: ,f....,f") is a Stackelberg equilibrium. We will also need the converse of this statement.
Proposition 3.5. Let Es be strategy for the mediator in f such that, the strategy profile (Ew, ......, ,,)), every nt for i + M is best response. Then there is an direct S-certification equilibrium that is sulizaation-qquivler
(ā ""....,,"")
Therefore, we have shown that the mediator strategies Pu in I for which (dM, Hi. x") a Stackelberg equilibrium in I correspond exactly to optimal S-certification equilibria of r. Such a Stackelberg equilibrium can be found by solving the following program:
max #M EM
Σ [M
[+
2
AE [m]
max #3 ajEXi 22
$)(=)
II + < O
Vj ejell [n]
where X; is the sequence-form strategy space [20] of player i in I.
The only variables in the program are c for each player and the mediator. In particular, the direct strategies á are constants. Therefore, the objective is a linear function, and the inner maximization constraints are bilinear in ZM and 2,. Therefore, this program can be converted to linear program by dualizing the inner optimizations. For more details on this conversion, see Appendix B. The result a linear program of size O(n)p()) = (())) We have thus proved Theorem 3.2.
'This condition is necessary because, if the mediator does not know what infoset the player is in, the mediator may not be able to send the player valid action, because action sets may differ by infoset.

---

3.2 Extensions and special cases
In this section, we describe several extensions and interesting special cases of our main result.
Full-certification equilibria. One particular special case of S-certification equilibria which is par- ticularly useful. We define full-certification equilibrium as an S-certification equilibrium where Sy (J. Intuitively, this means that players cannot lie to the mediator, but they may withhold information. We will call such an equilibrium full-certification. Removing valid messages from the players only reduces their ability to deviate and thus increases the space of possible equilibrium strategies. As such, the full-certification equilibria are the largest class of S-certification equilibria.
For full-certification equilibria, the size of game I' reduces dramatically. Indeed, in all histories h/" of I. we must have I 3 h. Therefore, we have [H] S | BD where B is the maximum branching factor and D is the depth of the game tree, i.e., the size of f' goes from essentially quadratic to essentially quasilinear in H.. The mediator's 's decision points in I for a full-certification equilibrium the trigger histories used by Zhang et al. [31] in their analysis of various notions of correlated equilibria. Later, we will draw further connections between full certification and correlation.
Changing the mediator's information. In certain cases, the mediator, in addition to messages that it sent by the players, also has its own observations about the world. These are trivial to incorporate into our model: simply change the information partition of the mediator in I' as needed. Alternatively, one can imagine adding "player", with no rewards (hence no incentive to deviate), whose sole purpose is to observe information and pass it to the mediator. For purposes of keeping the game small, it is easier to adopt the former method. To this end, consider any refinement partition M of the mediator infosets in f and consider the game F'M created by replacing the mediator's information partition in I with M. Then we make the following definition.
Definition 3.6. An (S, M)certificattn equilibrium of I' is mediator strategy iM in I'M such that, in the strategy profile (iM, "i,..., (,,), every xi for i + M is best response.
MS)MMMccriiiiittii equilibria may not exist: indeed, if M is coarser than the mediator's original information partition in I', then the mediator may not have enough information provide good recommendations under the restrictions of f. This can be remedied by allowing payments (see Appendix E), or by making the assumption that the mediator at least knows the transcript of the player whom she is making any nontrivial recommendation:
Definition 3.7. mediator partition M is direct if, every mediator decision point (h, t, RFC). so long as |A, > 1, the mediator knows the transcript of the player acting at h. M is strongly direct if the mediator also observes the transcript when |Apl = 1.
The condition |Ax| > 1 in the definition allows the mediator to possibly not observe the full in- formation of player if she does not need make nontrivial recommendation that player. In particular, this allows players to sometimes have information that they only partially reveal to the mediator, so long as the player does not immediately need act on such information.
Coarseness. In literature on correlation, coarseness refers to the restriction that a player must obey any recommendation that she receives (but may choose deviate by requesting recommenda- tion and instead playing any other action). Normal-form coarseness further adds the restriction that players can only choose deviate at the start of the game the mediator essentially takes over and plays the game on behalf of non-deviating players. These notions can easily be expressed in terms of our augmented game, therefore also allowing to express coarse versions of our equilibrium notions as augmented games.
3.3 The gap between polynomial and not polynomial
If players cannot send messages to the mediator at all, and the mediator has other way of gaining any information, we recover the notion of autonomous correlated equilibrium (ACE). It is hardard to compute optimal ACE, even in Bayesian games (see e.g., von Stengel and Forges [29]).
When M is direct and perfect recall, computing an optimal direct (S, -)eetffficaato equilibrium can be done in polynomial time using our framework. When S obeys NRC and M satisfies
7

---

stronger condition', , the proof of the revelation principle (Propositions 3.4 and 3.5) works, and the resulting equilibrium is guaranteed to be optimal over all possible equilibria including those that may not be direct.
If NRC does not hold, one can still solve the program (1), and the solution is still guaranteed to be an optimal direct equilibrium by Proposition 3.5. However, it is not guaranteed to be optimal over all possible communication structures. Indeed, Green and Laffont [15, Theorem 1] give an instance in which, without NRC, there can be an outcome distribution that is not implementable by direct mediator. Our program cannot find such an outcome distribution. The counterexample does not preclude the possibility of efficient algorithms for finding optimal certification equilibria in more general cases, but does give intuition for why NRC is crucial to our construction.
We could also consider changing the mediator's s information partition so that the mediator does not have perfect recall. This transformation allows to recover notions of correlation in games. In- deed, we start from the full-certification equilibrium and only allow the mediator to remember the transcript with the player she is currently talking to, we recover EFCE. Adding coarseness simi- larly recovers EFCCE and NFCCE. In this setting, the inability to represent the strategy space of an imperfect-recall player may result in the loss of efficient algorithms.
3.4 A family of equilibria
By varying 1) what the mediator observes, 2) whether the mediator has perfect recall, 3) whether the players can lie or only withhold information, and 4) when and how players can deviate from the mediator's recommended actions, we can use our framework to define a family consisting of 16 conceptually different equilibrium notions. More can be generated by considering other variations in this design space, but we focus on the extreme cases in the table. Some of these were already defined in the literature; the remaining names are ours. The result is Table 1. An inclusion diagram for these notions can be found in Appendix G.
In the table, ex ante means that players have only binary choice between deviating (in which case they can play whatever they want) and playing (in which case they must always be direct and obey recommendations). With ex ante deviations, it does not matter whether lying is allowed because we can never get to that stage: either the player deviates immediately and never communicates with the mediator, the player is direct. If the mediator only remembers the current active player's information, and players cannot lie, withholding and coarsely deviating are the same.
Mediator information advantage means that the mediator always learns the infoset of the current active player, and therefore requires no messages from the players. This is equivalent to forcing players to truthfully report information. A mediator with information advantage may still not have perfect information for example, it will not know whether a player (or nature) has played an action until some other player observes the action. In this setting, the mediator may also have extra private information (known to none of the players), leading to the setting of Bayesian persuasion [17]. In extensive-form games, there are two different reasonable notions of persuasion: one that stems from extending correlated equilibria, and one that stems from extending communication equilibria. The distinction is that, in the former, the mediator has imperfect recall. For more in-depth discussion of Bayesian persuasion, see Appendix F.
Our framework allows optimal equilibria for all notions in the table to be computed. For perfect- recall mediators, this possible in polynomial time via the sequence form; for imperfect-reett recall mediators, the problem is NP-hard, in general, but the team belief DAG of Zhang et al. [32] can be used to recover fixed- prrdmmarrmeter algorithms. For the notions of correlated equilibrium, this method results in basically the same I.P as the correlation DAG of Zhang et al. [31]. We do not claim that all of these notions easy motivate. For example, correlated equilib- ria are usually arrived at in the "truth known, imperfect recall" setting; the correlated equilibrium notions where lying is allowed are more difficult to motivate in this respect. Further, even the fixed- parameter algorithms of Zhang et al. [31] would fail in this setting, because "public states" can no longer be treated as public due to the possibility of lying players. We leave to future research the problem of finding a motivation for the notions that we do not reference elsewhere in the paper.
'Roughly speaking, this condition is that players should not be able to cause the mediator to gain infor- mation apart from their own messages by sending messages. It holds for all notions we discuss in this paper. Formalizing the general case beyond the scope of this paper.
8

---

Table 1: A whole family of equilibria. See Section 3.4 for an explanation of the terms used in the table. NF, EF, and IR stand for normal-form, extensive-form and imperfect-recat respectively.
when cun play ers deviale?
ante
ex interim
course
course
mediator remeembrrs current player's transcript
lying possible
NICCE (25)
trutffull EPOCE
tuthful EPCE
wilhholding only
EFCCE (10)
EFCE [29]
mediator information advaniage
NF cosmne IR persunsion [3]
course IR persuasion
IR penamsion
lying possible
NF coarse full-eertt
coarse comnm
comme [11]
("mediatted" [24]]
mediator perfect recall
withholding only
coarse full-ecrt
full-cest [12]
mediator information advantage
NF counse persussion
course persuasion
persussio
4 Experiments
We ran our algorithm for communication and full-certification equilibria on various two-player games, and compared the results to those given by notions of optimal correlation in games. The games used in the experiments are given in Appendix D. All experiments were allocated four CPU cores and 64 GB of RAM. Linear programs were solved with Gurobi 9.5. When payments are used, the allowable payment range is [0, M] where M is the reward range of the game. Experimental results can be found in Table 2.
In the battleship and sheriff instances, there is not significant difference in performance be- tween finding full-certification equilibria and finding optimal correlated equilibria in terms of performance- is because, unlike in the general case, optimal correlated equilibria in two-player games without chance can be found in polynomial time [29] anyway. In the ridesharing instances,
Table 2: Table of experimental results. Values are the optimal social welfare given the type of equi- librium. Values and timings for optimal correlated equilibria were taken from Zhang et al. [31] and are included here for purposes of comparison. When payments before making the payment of whether the player was honest, and the optimization objective the social welfare of the original terminal state, minus any payments made. "oom" is out of memory.
used, the mediator is informed
(2)
This
game
121
NFCCE EFCCE
EFCE
Cerl
Cerl
pay
psy
no pay
pay
n0 pay
pay
no pay
pay
B222
1072
value
0,000
40,525
00525
0.000
0.000
<0.525
40.333
-0.525
-0.453
40750
-0.520
time
0.00s
0.05%
0.174
0.01%
0.014
0.024
0.07%
0.06g
0.17%
3.80%
4.05%
19116
Value
8.000
-0.317
30.317
-0.000
0.000
-0.17
-0.300
-0.317
-0.226
0.215
1.386
5.83s
0.286
4,05g
B323
191916
Value
8,000
-0.375
.0.375
0.000
0.000
.0.375
-0.250
-0.375
00m
00m
o0m
time
2,52s
32.84s
1m 55g
0.32%
2.42s
2.77
16.50s
22.59
00m
00m
oom
5122
396
value
13,636
9.565
9.078
50,000
50.000
10.000
42,000
10,000
42,000
0.820
42.000
time
0.03s
0.004
0.044
0.014
0.016
0.026
0.11s
0.008
0.20s
0.855
1.74g
9123
2376
Value
13636
10.000
10.000
50.000
50,000
10.000
42,000
10.000
42.000
0.820
time
0.04s
0.23s
0.65s
0.12s
0.25s
0.46s
1.04s
5133
5632
Value
18.182
15.000
15.000
30,000
50,000
15,000
43,000
15,000
43,000
0.820
com
time
0.046
1,51
2.46s
0.06x
0.124
0.31s
0.65s
1.78s
2.89s
17m 7s
com
RS12
value
6.010
6.010
6.173
6.173
6.173
0.02s
0.01s
0.01s
0.00s
0.01s
0.00s
0.01s
0.01s
0.04s
0.91s
1.37s
RS13
4356
value
9,308
9.385
9.367
9.622
9.622
9.022
9.622
9.622
9.622
9.592
9.592
time
2,80s
1m 28s
12m 31s
0.03%
0.11s
0.07s
0.19
0.16s
0.55s
3m 9g
6m 42s
229888
value
10.500
10.500
10.500
10.500
10,500
10,500
time
0.300
1,414
0.665
3.97
2.34k
12,04x
R522
484
value
7.188
7.176
7.176
7.594
7.594
7.594
7.594
7.594
7,594
7.594
7.594
time
0.30s
0.20%
0.164
0.014
0.014
0.014
0.044
0.90s
RS23
4096
value
10.961
10.820
10.791
11,516
11.516
11.513
11.513
11,485
11.485
11. 464
11.464
time
3.12s
36m
31s
6m 35s
0.336
0.10&
0.06s
0.186
0.19%
0.663
Vin 43s
12m Is

---

batlleship222
sheriff122 22
rideshare22
4.092
1.887
49.016
4.010
0.533
13.315
3.928
Flayer I's uillty
0.637
$7.215
Player I's uilkit
3.846
0,422
31.311
3,764
-0.263
-0.487
7.705
3.437
-0.713
1,803
3.350
-0.938
-4.098
3.276
2.195
1,003
11556
-1253
-0.95
10
-3.30
5,000
0,323
0.633
9.00
0,170
1.10
4.24
$239
6.99
7,11
6337
33351
3,421
5.995
350
5.55
S777
$919
1009
2'ayer''s utility
Player uttility
Player utullyy
NFCCE
EFCCE
EFCE
NF coarse full-cert
Coarse full-cert
Full-certification
(*) Communication
Figure 1: Payoff spaces for various games and notions of equilibrium. The symbol indicates that
the set of communication equilibrium payoff's for that game is (at least, modulo numerical precision) that single point. In the battleship instance, many of the notions overlap.
computing optimal correlated equilibria is much more computationally intensive because the game contains non-public chance actions. Computing optimal full-certification equilibria is comparably easy, and this difference is clearly seen in the timing results.
Finding optimal communication equilibria is much more intensive than finding optimal full- certification equilibria, owing to the quadratic size of the augmented game for communication equi- libria. This often causes communication equilibria be the hardest of the notions compute in practice, despite optimal correlation being NP-hard.
In Figure 1, have plotted the payoff spaces of some representative instances. The plots show how the polytopes of communication and full-certification equilibria behave relative to correlated equilibria. In the buttleship and sheriff' instances, the space of communication equilibrium payoffs a single point, which implies that the space of NFCE (and hence Nash) equilibrium payoff's is also that single point. Unfortunately, that point is the Pareto-least-optmmal point in the space of EFCEs. In the ridesharing instances, communication allows higher payoffs. This is because the mediator is allowed "leak" information between players.
Conclusions and future research
We have shown that optimal communication and certification equilibria in extensive-form games can be computed via linear programs of polynomial size, almost-linear size in the full-certification case. We have used our machinery derive entire family of equilibrium concepts which we hope to be of use
future.
Possible future directions include the following.
1. Are there efficient online learning dynamics, in any reasonable sense of that term, that converge to certification or communication equilibrium?
2. Is there a better-than saatter-hhan-uudaattii---- -uadratic-sizze linear program for communication equilibria?
3. Is it possible extend our augmented game construction also cover normal-form corre- lated equilibria while maintaining efficiency?
4. Investigate further the comparison between communication and correlation in games. For example, when and why do communication equilibria achieve higher social welfare than extensive-form correlated equilibria?
Acknowledgements
This material is based work supported by the National Science Foundation under grants IIS-1900 1901403 and CCF-1733556, and the ARO under award 191
10

---

References
[1] Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathemat- ical Economics, 1:67-96, 1974.
[2] Dirk Bergemann and Stephen Morris. Information design: A unified perspective. Journal of Economic Literature, 57(1):44-95, 2019.
[3] Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private Bayesian persuasion with sequential games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1886-1893, 2020.
[4] Michal Chalamish and Sarit Kraus. Automed: automated mediator for multi-issue bilateral negotiations. Autonomous Agents and Multi-Agent Systems, 24(3):536-564, 2012.
[5] Wolfram Conen and Tuomas Sandholm. Preference elicitation in combinatorial auctions: Ex- tended abstract. ACM Conference on Electronic Commerce (ACM-EC), pages 256-259, Tampa, FL, 2001. More detailed description of algorithmic aspects in IJCAI-01 Workshop on Economic Agents, Models, and Mechanisms, pp. 71-80.
[6] Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 103-110, Edmonton, Canada, 2002.
[7] Vincent Conitzer and Tuomas Sandholm. Vote elicitation: Complexity and strategy In National Conference Artificial Intelligence (AAAI), pages 392-397, Edmonton, Canada, 2002.
[8] Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. ACM Conference on Electronic Commerce (ACM-EC), pages 132-141, New York, NY, 2004.
[9] Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive- form games: Saddle-point formulation and benchmarks. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
[10] Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm. Coarse correlation in extensive- form games. In AAAI Conference on Artificial Intelligence, 2020.
[11] Francoise Forges. An approach to communication equilibria. Econometrica: Journal of the Econometric Society, pages 1375-1385, 1986.
[12] Françoise Forges and Frédéric Koessler. Communication equilibria with partially verifiable types. Journal of Mathematical Economics, 41(7):793-88) 811, 2005.
[13] Masabumi Furuhata, Maged Dessouky, Fernando Ordóñez, Mare-Etienne Brunet, Xiaoqing Wang, and Sven Koenig. Ridesharing: The state-of tiitee-ff-hheee art of-the-art and future directions. Transporta- tion Research Part Methodological, 57:28 46, 2013.
[14] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential socision-making In AAAI Conference Artificial Intelligence (AAAI), volume 36, pages 5025 5025-5033, 2022.
[15] J Green and J-J Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427 438, 1977.
[16] Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics, pages 506-513, Springer, 2008
[17] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 10166):2500-211, 2011.
[18] Andrew Kephart and Vincent Conitzer. Complexity of mechanism design with signaling costs.
In Autonomous Agents and Multi-Agent Systems, pages 357-365, 2015.

---

[19] Andrew Kephart and Vincent Conitzer. The revelation principle for mechanism design with signaling costs. ACM Transaction on Economics and Computation (TEAC), 9(1):1-35, 2021.
[20] Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Fast algorithms for finding ran- domized strategies in game trees. In ACM Symposium on Theory of Computing (STOC), 1994.
[21] Kate Larson and Tuomas Sandholm. Mechanism design and deliberative agents. In Interna- tional Conference on Autonomous Agents and Multi--gent Systems (AAMAS), pages 650-656, Utrecht, The Netherlands, 2005.
[22] Hongyao Ma, Fei Fang, and David C Parkes. Spatio-temporal pricing for ridesharing platforms. Operations Research, 2021.
[23] Yishay Mansour, Alex Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration in bayesian games. Operations Research, 70(2):100--111 105--1277 2022.
[24] Dov Monderer and Moshe Tennenholtz. Strong mediated equilibrium. Artificial Intelligence, 173(1):180-19,, 2009.
[25] H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4): 201-221, 1978.
[26] Christos Papadimitriou, George Pierrakos, Alexandros Psomas, and Aviad Rubinstein. On the complexity of dynamic mechanism design. Games and Economic Behavior, 2022.
[27] Tuomas Sandholm and Craig Boutilier. Preference elicitation in combinatorial auctions. In Peter Cramton, Yoav Shoham, and Richard Steinberg, editors, Combinatorial Auctions, pages 233-263. MIT Press, 2006. Chapter 10.
[28] Tuomas Sandholm, Vincent Conitzer, and Craig Boutilier. Automated design of multistage mechanisms. Twentieth International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, 2007.
[29] Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 1002)1100- 2008.
[30] Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient rein- forcement learning. In ACM Conference on Economics and Computation (EC), 2022.
[31] Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Optimal correlated equilibria in general-sum extensive-form games: Fixed-parameter algorithms, hardness, and two-sided column-generation. arXiv preprint arXiv:2203.07188, 2022.
[32] Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief dag form: A concise representation for team-correlated game-theoretic decision making. arXiv preprint arXiv:2202.00789, 2022.
[33] Hanrui Zhang and Vincent Conitzer. Automated dynamic mechanism design. Conference on Neural Information Processing Systems (NeurIPS), 34:27785-27797, 2021.
[34] Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Automated mechanism design for classifica- tion with partial verification. In AAAI Conference on Artificial Intelligence (AAAI), volume 35, pages 5789-5796. 2021.
[35] Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Planning with participation constraints. In
AAAI Conference Artificial Intelligence (AAAI), 2022.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] in appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [N/A] Experiments were deterministic.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nktFBm8R68Q", "reviewer": "Reviewer_Xqpy", "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.\n", "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.\n\n2) 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.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "ORIGINALITY\n\n(+) The paper studies equilibrium concepts (communication and certification equilibria) that have never been addressed before by the algorithmic game theory community.\n\n(-) The techniques employed by the authors are fairly standard, since they consist in a simple linear programming formulation.\n\nQUALITY\n\n(+) As far as I am concerned the results are sound.\n\n(-) 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.\n\nCLARITY\n\n(+) Overall, the paper is well written and easy to follow.\n\n(-) There are only some minor problems that I list in the following:\n\n\t(*) Line 28: Cite [24] after “extensive-form”.\n\n\t(*) 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.\n\n\t(*) Line 95: Remove “player”.\n\n\t(*) Line 106: “We also will” is “We will also”.\n\n\t(*) Adding an example of extended game would help.\n\n\t(*) The terms used in the caption of Table 1 do not appear in the table.\n\n\nSIGNIFICANCE\n\n(+) The results could be of interest for the part of the NeurIPS community interested in algorithmic game theory.\n\n(-) 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).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eMhr4beQk9A", "reviewer": "Reviewer_GECr", "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:\n- A class of equilibria where the players cannot reveal false information, leading to a linear size linear program (scales better than other notions).\n- They consider the integration of payments, allowing the mediator a more expressive way to modify the outcome in settings where they are permitted.\n- 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.", "questions": "N/A", "limitations": "Negative social impact is not a concern here, in my opinion. There is little explicit discussion of limitatins.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n- They are the first to show that communication and certification equilibria can be optimized in polynomial time for extensive-form games.\n- The paper lays out a map of equilibrium concepts and shows that many can be computed through the same meta-algorithm.\n- Coverage of related work seems adequate.\n\nQuality:\n- There is a substantial amount of math I did not check, but the work appears technically sound.\n- 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.\n- There is not a lot of discussion of weaknesses.\n- The authors' claims seem well supported.\n\nClarity:\n- 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).\n- The authors say they will not release code, which I don't understand.\n\nSignificance:\n- 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.\n- The generalization of past algorithms provides a bit of interesting big picture structure.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VCJWAn2tU6Z", "reviewer": "Reviewer_TwPw", "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.\n", "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? \n\n", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n-- the study of communication in extensive-form game seems an interesting and well-motivated problem.\n\n-- 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.\n\nWeakness:\n\n-- 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.  \n\n-- 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. \n\n-- This is purely an equilibrium optimization paper without any aspect of learning. So it does not seem a good fit to NeurIPS.   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6OwjjRksfo6", "reviewer": "Reviewer_ZsGj", "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. ", "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?\n\nHow 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?\n\nHow large are the games used in the experiments, i.e. with how many information sets?\n\nHow 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?\n", "limitations": "I could not think of any other limitation not addressed already by the authors.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nMy 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. \n\nTo 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept