Ex ante coordination and collusion in zero-sum multi-player extensive-form games
Recent milestones in equilibrium computation, such as the success of Libratus, show that it is possible to compute strong solutions to two-player zero-sum games in theory and practice. This is not the case for games with more than two players, which remain one of the main open challenges in computational game theory. This paper focuses on zero-sum games where a team of players faces an opponent, as is the case, for example, in Bridge, collusion in poker, and many non-recreational applications such as war, where the colluders do not have time or means of communicating during battle, collusion in bidding, where communication during the auction is illegal, and coordinated swindling in public. The possibility for the team members to communicate before game play-that is, coordinate their strategies ex ante-makes the use of behavioral strategies unsatisfactory. The reasons for this are closely related to the fact that the team can be represented as a single player with imperfect recall. We propose a new game representation, the realization form, that generalizes the sequence form but can also be applied to imperfect-recall games. Then, we use it to derive an auxiliary game that is equivalent to the original one. It provides a sound way to map the problem of finding an optimal ex-antecoordinated strategy for the team to the well-understood Nash equilibrium-finding problem in a (larger) two-player zero-sum perfect-recall game. By reasoning over the auxiliary game, we devise an anytime algorithm, fictitious team-play, that is guaranteed to converge to an optimal coordinated strategy for the team against an optimal opponent, and that is dramatically faster than the prior state-of-the-art algorithm for this problem.
The paper studies the problem of multi-player extensive-form games where players form teams. Within a team, players share the common payoff and the paper focuses on the zero-sum setting in the sense that two teams of players are playing against each other and the sum of utilities of both teams equals zero for each terminal state. Solving such games is challenging since they can be either modeled as multi player games with perfect recall, or as a two player game but with imperfect recall.   The authors argue that within such setting, it is reasonable to consider solution concepts where the players of a team are able to correlate their strategies -- i.e., to agree in a advance on a probability distribution from which they sample their pure strategies. Under this assumption, the authors show that the range of expected utilities can be represented as a convex set and an auxiliary perfect recall game of an exponential size can be constructed, solving which leads to the solution of the original game.   The authors propose a novel algorithm based on Fictitious Play in extensive-form games and experimentally demonstrate the performance on Kuhn and Leduc poker games with varying number of cards.   Overall, the idea and the technical results seem interesting, however, I had quite some difficulties to understand why the realization form is not a straightforward consequence of the choice of the authors focus on normal-form strategies -- I would suggest to include a more complex example instead of Figure 1, namely one, where restricting to normal-form strategies does not directly lead to a perfect recall game.  There are two concerns about the paper. First, it is difficult to agree with the statement that correlated strategies are the right choice for team games, especially due to the necessity of correlating before each game (or sampling the correlated strategies several times in advance, once for each play of 1 game). On the other hand, if you assume correlation via some actions during the play, then it is assumed that players have observable actions which limits the applicability (and can actually simplify the technical results). Such a correlation can make sense in other multi-agent adversarial scenarios (a team is fighting adversarial team). However, even in these tactical scenarios, the correlation with respect to receiving signals in each information set (instead of receiving one signal) seems more natural as argued by von Stengel and Forges when introducing Extensive-Form Correlated Equilibrium. Could the authors comment of that? Is it truly reasonable to focus on computing correlation over pure strategies in these games? And if so, do authors actually compute a correlated equilibrium in these games? How does TMECor differ from standard correlated equilibrium (not EFCE) in these games?  Second, the authors omit the recent algorithms for computing behavioral strategies in imperfect recall games (namely works by Cermak et al. "Combining Incremental Strategy Generation and Branch and Bound Search for Computing Maxmin Strategies in Imperfect Recall Games" and "Approximating maxmin strategies in imperfect recall games using A-loss recall property"). These works are computing optimal strategies in behavioral strategies in imperfect recall games -- that, as the authors state, leads to a non-linear, non-convex optimization problem. At the same time, the scalability of the existing algorithms reported in these prior works outperforms the running time of the algorithm in this paper by several orders of magnitude (number of sequences is 10^6 and higher solvable within hours in the works by Cermak et al., compared to 10^2 in this submission). Since one of the positive results of this submission is to simplify the strategy space and offer better and more scalable algorithms, it seems that current experimental results do not strongly support this claim. A natural question arises -- can the techniques and algorithms for computing behavioral strategies in imperfect recall developed by Cermak et al. be adopted for computing the solution concept the authors propose (technically, it is a bilinear mathematical program, so it actually can be simplified)? If not, why?  After rebuttal:  I am not that satisfied with the response of the authors since several questions were left unanswered.   1. I am aware that ex-ante correlation does not lead to a perfect recall game. I was merely suggesting the authors to use a more complex example in the paper so that it is clearly stated in the paper.  2. I am not convinced that ex-ante correlation is the right choice, however, this my subjective opinion and I admit that ex-ante correlation has its place in the literature/research.  The authors did not respond to my question regarding TMECor -- it seems to me that TMECor is a combination of two standard correlated equilibria played within the members of a team, joined in a zero-sum competition. If this is true, I am wondering whether there is some connection to the property that the realization form is a convex polyhedron -- e.g., does this mean that any CE in an imperfect recall game can be represented using the same strategy space?  3. The problem with scalability is as follows -- the authors suggest that they use TME for conceptual simplicity that should be positively reflected in the scalability. However, this is not currently the case, since the cited papers are able to solve larger games in behavioral strategies (that have all the negative aspects the authors state -- non-existence of Nash equilibria, non-linearity, non-convexity, etc.) compared to the current experiments in the submission. My question was, whether the advanced techniques that lead to this better scalability in the more complex strategy space can be modified to the proposed solution concept (i.e., not to directly apply cited algorithms -- which is what the authors responded to).    Overall, there are some concerns over the significance of the paper (connections to the standard solution concepts, scalability), however, there is some contribution and I can imagine that the paper can be helpful for other researchers in a follow-up work.