--- title: "Correlation-Based Algorithm for Team-Maxmin Equilibrium in Multiplayer Extensive-Form Games" authors: - "Youzhi Zhang" - "Bo An" - "V. S. Subrahmanian" doi: "10.24963/ijcai.2022/86" url: "https://ijcai.org/proceedings/2022/86" pdf: "https://ijcai.org/proceedings/2022/0086.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "606-612" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Cooperative Games" - "Agent-based and Multi-agent Systems: Noncooperative Games" --- # Correlation-Based Algorithm for Team-Maxmin Equilibrium in Multiplayer Extensive-Form Games Youzhi Zhang, Bo An, V. S. Subrahmanian *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 606-612. DOI: [10.24963/ijcai.2022/86](https://doi.org/10.24963/ijcai.2022/86) ## Abstract Efficient algorithms computing a Nash equilibrium have been successfully applied to large zero- sum two-player extensive-form games (e.g., poker). However, in multiplayer games, computing a Nash equilibrium is generally hard, and the equilibria are not exchangeable, which makes players face the problem of selecting one of many different Nash equilibria. In this paper, we focus on an alternative solution concept in zero-sum multiplayer extensive-form games called Team-Maxmin Equilibrium (TME). It is a Nash equilibrium that maximizes each team member’s utility. As TME is unique in general, it avoids the equilibrium selection problem. However, it is still difficult (FNP- hard) to find a TME. Computing it can be formulated as a non-convex program, but existing algorithms are capable of solving this program for only very small games. In this paper, we first refine the complexity result for computing a TME by using a correlation plan to show that a TME can be found in polynomial time in a specific class of games according to our boundary for complexity. Second, we propose an efficient correlation-based algorithm to solve the non-convex program for TME in games not belonging to this class. The algorithm combines two special correlation plans based on McCormick envelopes for convex relaxation and von Stengel-Forges polytope for correlated equilibria. We show that restricting the feasible solution space to von Stengel-Forges polytope will strictly reduce the feasible solution space after convex re- laxation of nonlinear terms. Finally, experiments show that our algorithm is about four orders of magnitude faster than the prior state of the art and can solve many previously unsolvable games. ## Full text ## 1 Introduction Designing efficient algorithms by which agents can make decisions in complex, interactive environmnets is an important part of AI [Russell and Norvig, 2016]. Much recent work on the computational study of non-cooperative environments has focused on computing a Nash equilibrium [Nash, 1951] for large zero-sum two-player Extensive-Form Games (EFGs) [Zinkevich et al., 2008; Zhang and Sandholm, 2020; Brown and Sandholm, 2017]. In theory, a Nash equilibrium can be computed by a polynomial-time (in the size of the game) algorithm in zero-sum two-player EFGs [von Stengel, 1996; Shoham and Leyton-Brown, 2008]. In practice, the agents based on algorithms for computing a Nash equilibrium in large zero-sum two-player EFGs have defeated top human players in the heads-up limit Texas hold'em poker game [Bowling et al., 2015] and the heads-up nolimit Texas hold'em poker game [Moravˇc´ık et al., 2017; Brown and Sandholm, 2018]. Therefore, in both theory and practice, the problem of computing a Nash equilibrium in zero-sum two-player EFGs is well understood. However, this problem is more complicated in zero-sum multiplayer games, and there are relatively few results. Computing a Nash equilibrium in these games is generally hard [Chen and Deng, 2005], and the strategies between different Nash equilibria are not exchangeable, which impedes players from independently selecting strategies to make them form a Nash equilibrium (i.e., having the equilibrium selection problem among different Nash equilibria) [Brown and Sandholm, 2019]. In this paper, we focus on an alternative solution concept in zero-sum multiplayer EFGs, Team-Maxmin Equilibrium (TME) [von Stengel and Koller, 1997; Basilico et al., 2017; Celli and Gatti, 2018; Zhang and An, 2020a], which is for the situation where several players with the same utility function form a team but take actions against an adversary independently. TME has some nice properties: (i) a TME is a Nash equilibrium that maximizes the utility of each team member among all Nash equilibria, and (ii) TME always exists and is unique and hence avoids the aforementioned equilibrium selection problem. Moreover, TME can capture many strategic interaction scenarios in the real world. For example, in poker games, several players may form a team and play against the target player, i.e., they have the same goal but take actions independently because communications are not allowed in general poker games [Brown and Sandholm, 2019]. In Bridge, two defenders, form a team but play cards independently due to the rules. In the three-player card game DouDizhu (i.e., Fighting the Landlord) [Zha et al., 2021], two peasants form a team to fight against the Landlord. Moreover, in security games, different security departments independently protect major ports such as the New York port [Jiang et al., 2013]. However, it is still very hard (FNP-hard [Celli and Gatti, 2018]) to compute a TME in EFGs. Computing a TME in EFGs can be formulated as a non-convex program. The previous state-of-the-art algorithm for solving this program is IARAMDT [Zhang and An, 2020a], which is based on a global optimization technique - the Multiparametric Disaggregation Technique (MDT) [Kolodziej et al., 2013; Andrade et al., 2019]. The MDT-based algorithms use a digit-wise discretization of continuous variables to approximate nonlinear terms and then add a large number of constraints and integer variables to the program. Our experiments show that MDTbased algorithms are inefficient to compute a close approximation of a TME in large games because they add too many constraints and integer variables to the program. To counter this inefficiency, a correlated variant of TME [Basilico et al., 2017; Zhang et al., 2021] where team players correlate their strategies was proposed as an approximation of TME, because the team's correlated strategy can be transformed into a mixed strategy profile [Basilico et al., 2017]. Correlated TME is relatively easier to compute, but the transformed profile may not form a TME, resulting in an arbitrarily large loss for the team both in theory and practice [Basilico et al., 2017; Zhang and An, 2020a; Zhang and An, 2020b]. Contributions. Our contributions are threefold. First, we refine the computational complexity of TME by proposing to use a correlation plan to represent the team's strategy to show that a TME can be found in polynomial time in a specific class of EFGs according to our boundary for complexity. Second, we propose an efficient correlation-based algorithm to solve the non-convex program for a TME in other EFGs by combining two special correlation plans based on the wellknown McCormick envelope [McCormick, 1976] for convex relaxation and the well-known von Stengel-Forges Polytope [Von Stengel and Forges, 2008] for correlated equilibria: 1) We explore the relation between the proposed correlation plan and both special plans to show that our proposed correlation plan cannot be replaced by them in these EFGs. 2) We show that restricting the feasible solution space to von Stengel-Forges Polytope will strictly reduce the feasible solution space after convex relaxation of nonlinear terms. Finally, our experimental results show that our algorithm is about four orders of magnitude faster than baselines and can solve many previously unsolvable games. ## 2 Preliminaries The Extensive-Form Game (EFG) [Shoham and LeytonBrown, 2008; Von Stengel and Forges, 2008; Farina and Sandholm, 2020] is a standard model for games played on game trees (e.g., game trees in Figure 1), which can capture simultaneous and sequential moves. The imperfectinformation EFG can also capture private information. An EFG includes a set of players N = {1, . . . , n}, and n ≥ 3 for multiplayer games. Each node in the game tree belongs to one player except for chance nodes that are used to model stochastic events in the game (e.g., drawing cards in poker). The edges leaving a node represent actions that the player at that node can take, and each player i has a set of actions Ai. Hi is a set of nonterminal nodes (i.e., nodes having outgoing edges) for player i. ψi : Hi → 2Ai is the action function assigning a set of possible actions to each nonterminal node of player i. Nodes without outgoing edges are terminal nodes (also called leaves) that represent the end states of a game, and Z is a set of these terminal nodes. Each player i's utility function ui : Z → R assigns a utility to each leaf. As customary in related works, we focus on perfect-recall games where all players remember the information gained earlier in the game, i.e., for each player i and each Ii ∈ Ii, nodes in Ii have the same sequence of player i's moves on the paths from the root to these nodes. A sequence σi of moves of player i, defined for each node h ∈ H ∪ Z of the game tree, is the ordered set of actions of player i that lie on the path from the root to h. We use seqi (Ii) to represent the sequence of player i leading to Ii and use σi = seqi (Ii)ai to denote that sequence σi's last move is ai taken in information set Ii. In this case, we say σi belongs to Ii. Σi = {seqi (Ii)ai | Ii ∈ Ii, ai ∈ ψi(Ii)} defines the set of sequences of player i. ΣN ′ = ×i∈N ′⊆NΣi defines the combinations of sequences of players in N ′ , and σN ′ (j) represents the sequence of player j in σN ′ ∈ ΣN ′ . We write σ = σN and Σ = ΣN. Each node h ∈ H ∪ Z corresponds to a joint sequences σN ∈ ΣN of players, denoted as seqN (h), and seqN ′(h) is the joint sequence of players in N ′ ⊆ N leading to node h. For example, in Figure 1(a), seq{1,2}(D) = (a, c). We use ΣN ′(Ii) to denote the set of joint sequences of players in N ′ reaching Ii. ϕ denotes the empty sequence corresponding to the root. A realization plan ri : Σi → [0, 1] is a function assigning a probability to each sequence to be played, which satisfies: Information sets, partitions of nonterminal nodes, represent private information. Specifically, player i's collection Ii of non-empty subsets of Hi is a partition of Hi: Each Ii ∈ Ii is a set of nodes that player i cannot distinguish, given what they have observed while playing the game. Formally, if hi, h′i ∈ Ii, then ψi(h1) = ψi(h2), i.e., the nodes in Ii have the same set of actions. Let ψi(Ii) = ψi(hi) for any hi ∈ Ii denote the set of available actions in Ii. Without loss of generality, we assume that for each action ai ∈ Ai there is a unique Ii ∈ Ii such that ai ∈ ψi(Ii). These constraints enforce the property of probability flow for ri at each information set Ii. Let Ri be the set of all realization plans, and RN ′ = ×i∈N ′⊆NRi define the space of joint realization plans over N ′ . A behavioral strategy βi of player i defines a probability distribution over ψi(Ii) for each information set Ii ∈ Ii. Every realization plan gives rise to a behavioral strategy by setting: ∀ai ∈ ψi(Ii), βi(Ii, ai) = ri(seqi (Ii)ai) ri(seqi (Ii)) if ri(seqi (Ii)) > 0; otherwise βi(Ii, ai) could be an arbitrary value in [0, 1]. A behavioral strategy defines a realization plan as well, i.e., ri(σi) = ∏(Ii,ai)∈σi βi(Ii, ai), where {(Ii, ai) ∈ σi} represents all information sets and actions along the path (sequence) σi of player i. Figure 1: Examples of EFGs with three players. In each example, uppercase letters (i.e., A,B, · · · ) represent nodes, lowercase letters represent actions, Ii represents the information set of player i, numbers represents leaves, and players 1, 2 (and 3) form a team. For example, in Figure (a), player 1 acts in information set I1 with node A and two actions a and b, player 2 acts in information set I2 with nodes B and C and two actions c and d, and the adversary acts in the information set with nodes D-G. ![Image](https://ijcai.org/proceedings/2022/fulltext/86/image_000000_a04925a1bad9b495d2b8459d17f86340383a7cce1a84c5521b049dfa37b265a3.png) Given player i and player j, Ii ⇌ Ij with Ii ∈ Ii and Ij ∈ Ij denotes that Ii and Ij are connected, i.e., there exist hi ∈ Ii and hj ∈ Ij such that the path from the root of the game tree to hi passes through hj or vice versa. For example, I1 ⇌ I2 in Figure 1(a), but I ′1 and I2 are not connected in Figure 1(b). Two sequences are relevant if any of them is the empty sequence or if both of them belong to connected information sets. That is, given any σi = seqi (Ii)ai ∈ Σi and σj = seqj (Ij)aj ∈ Σj, if either σi or σj is ϕ, or if Ii ⇌ Ij, then σi and σj are relevant, denoted as σi ▷◁ σj. A joint sequence σN ′ is relevant if any two sequences σN ′(i) and σN ′(j) in σN ′ are relevant. The set of relevant joint sequences is Σ▷◁ N ′ for N ′ ⊆ N. For example, in Figure 1(a), a ▷◁ c, and the joint sequence σ{1,2} = (a, c) is relevant. Given any player i and a subset of players N ′ (i /∈ N ′ ), we say that σN ′ ∈ ΣN ′ is relevant for Ii ∈ Ii, denoted as Ii ▷◁ σN ′ , if seqi (Ii) ▷◁ σN ′ (j) for each j ∈ N ′ , and there is at least one node hi ∈ Ii such that the joint sequence seqN (hi) includes the sequences of seqi (Ii) and σN ′ . For example, in Figure 1(a), the joint sequence σ{1,2} = (a, c) of players 1 and 2 is relevant for the adversary's unique information set because seqN (D) = (a, c, ϕ) includes σ{1,2} and ϕ for the adversary to reach this information set. Team-Maxmin Equilibrium (TME) [von Stengel and Koller, 1997; Celli and Gatti, 2018; Zhang and An, 2020a] captures scenarios where a team of players T = {1, . . . , n - 1} play against the adversary n with ui(z) = uj(z)(∀i, j ∈ T) and un(z) = -uT (z) = - ∑i∈T ui(z) for each terminal node z, and team members take actions independently in a zero-sum multiplayer EFG. Here, UT is the team's utility with UT (σ) = ∑z∈Z′ uT (z)c(z) if a nonempty subset of terminal nodes Z ′ ⊆ Z are reached by the joint plan σ of all players with the chance c(z) determined by chance nodes, and UT (σ) = 0 otherwise. A TME is a Nash equilibrium maximizing each team member's utility and thus always exists and is unique in general [von Stengel and Koller, 1997]. We denote the TME value as the utility of the team under a TME. In an ϵ-TME, both the adversary and the team cannot gain more than ϵ if any of the players deviates from his strategy, and the difference between the TME value and the ϵ-TME value is not larger than ϵ. The team's strategy profile in a TME is defined as arg maxr1,...,rn-1 minrn∑σ=×i∈N σi ,σ∈ΣUT (σ)∏ni=1 ri(σi) and can be computed by a non-convex maxmin program [Celli and Gatti, 2018], whose objective maximizes the team's utility at the root of the game tree and constraints ensure that the adversary chooses the action minimizing the team's utility (i.e., maximizing the adversary's utility) in each information set of the game tree, similar to the case in two-player games [Shoham and Leyton-Brown, 2008]: where In(σn) denotes the information set where player n takes the last action in sequence σn except for In(ϕ) = ϕ representing the root, free variable vector v : In → R where v(In) is the team's expected utility in information set In except that v(ϕ) represents the team's expected utility in this EFG. By using the computed strategy profile of the team in a TME, the adversary strategy in a TME can be computed by a linear program through minimizing the team's utility [von Stengel and Koller, 1997; Zhang and An, 2020b]. For simplification, we say a TME is computed by Program (2). ## 3 Using Correlation Plan to Represent Joint Plan We now propose an efficient algorithm to compute a TME using a correlation plan of the team to represent the combination of independent plans of team members. By using this representation, we show that a TME can be computed by a linear program with a polynomial number of variables. In a TME, team members take actions independently, which results in using the non-convex Program (2) to compute the TME. In Eq.(2b), there is a multilinear term ∏i∈T ri(σT (i)). rT is a joint realization plan of team members, i.e., the combination of independent realization plans of team members. Motivated by the extensive-form correlation plan in two-player games [Von Stengel and Forges, 2008], we propose our multilinear correlation plan x : Σ▷◁ T → [0, 1] to represent the joint plan σT of the team such that: We use X to denote the space of multilinear correlation plans x. Given a correlation plan x, we can obtain a joint realization plan for all team members as well. To do so, we first obtain a behavior strategy from x. That is, for each teammember i, for each Ii ∈ Ii with seqi(Ii) = σi and each ai ∈ ψi(Ii), and given any σT and σ′T with σT (i) = σi, σ′T (i) = σiai, and σT (j) = σ′T (j) for i ̸= j, We can then obtain the corresponding equivalent realization plan ri from this behavioral strategy βi obtained from x. Therefore, the correlation plan space is equivalent to the joint realization plan space: for each joint realization plan, there is an equivalent correlation plan and vice versa. Similar to Program (2), the team's strategy in a TME can be defined as: Through the dual linear program of the inner problem over rn, we can show that a TME can be computed by a linear program with a polynomial number of variables. Proposition 1. A correlation plan x is the team's strategy in a TME if and only if it is a solution of the following linear program: (All proofs are in Supplementary Appendix 1 ) Program (5) is a linear program whose number of variables is polynomial in the game size. If we can use a polynomialsized set of linear constraints to represent X, then we can have a polynomial-time algorithm to compute a TME. However, this is impossible in general cases unless P = NP because computing a TME is FNP-hard [Celli and Gatti, 2018]. ## 4 Correlation Plans with Polynomial-Sized Set of Linear Constraints The preceding section argued that finding a polynomial-sized set of linear constraints to represent X in Program (5) would lead to a polynomial-time algorithm to compute a TME. In this section, we introduce two special correlation plans that do have a such a polynomial-sized representation. Based on the first special correlation plan, we obtain a boundary between polynomial and FNP instances of games with respect to TME. That is, we provide the first positive result (i.e., a polynomial-time algorithm) for complexity on computing a TME in some games. Moreover, we develop an efficient algorithm to compute a TME in other games by combining both special correlation plans. [1 https://github.com/Youzhi333/TMEEFG](https://github.com/Youzhi333/TMEEFG) Figure 2: The relation between correlation plan spaces: (a) X ⊂M in any EFG; (b) X ⊂ Y in any EFG satisfying the non-uniquepath property; (c) X = Y in any EFG satisfying the unique-path property; and (d) X ⊂ (M∩ Y) ⊂ M in any EFG satisfying the non-unique-path property. ![Image](https://ijcai.org/proceedings/2022/fulltext/86/image_000001_68cbc8f2939b7a2ff574b9582378721f972ba492f982dadabccc2db6e9e7d9a7.png) ## 4.1 A Boundary for Complexity We now show a boundary between the existence and nonexistence of a polynomial-time algorithm to compute a TME based on the von Stengel-Forges Polytope [Von Stengel and Forges, 2008] 2 . We propose a special von Stengel-Forges correlation plan with a polynomial-sized set of linear constraints as y : Σ▷◁ T → [0, 1] that assigns a probability for each relevant joint sequence in multiplayer games. That is, the team's correlation plan satisfies: These constraints will give y the property of the probability flow at each information set: starting with probability 1 at the root (Eq.(6b)), Eq.(6c) ensures that the incoming probability is equal to the outgoing probability at each information set. We denote the space of these plans as Y. We now explore the relation between X and Y, and find that Y includes X in any EFG. ## Proposition 2. X ⊆ Y in any EFG. We now show the boundary between X = Y and X ⊂ Y. Note that ΣT (Ii) is the set of joint sequences of team members reaching Ii, which are paths of the team from the root to Ii. We first define the unique-path property of an information set of a team member as: there is only one path for the team from the root to this information set, or there is only one action in this information set. Formally, Ii of teammember i is unique-path if |ΣT (Ii)| = 1 or |ψi(Ii)| = 1. Conversely, the non-unique-path property of an information set of a teammember is: there are at least two paths for the team from the root to this information set, and this information set has at least two actions. Formally, Ii of teammember i is nonunique-path if |ΣT (Ii)| ≥ 2 and |ψi(Ii)| ≥ 2. A game satisfies the unique-path property if each information set of each team member satisfies the unique-path property, and a game satisfies the non-unique-path property if at least one information set of any teammember satisfies the non-unique-path property. For example, the EFG in Figure 1(a) satisfies the non-unique-path property because ΣT (I2) = {(a, ϕ), (b, ϕ)} and ψ2(I2) = {c, d}; and the game in 1(b) satisfies the nonunique-path property because of the non-unique-path property of I ′2 . However, the EFG in Figure 1(c) satisfies the unique-path property because ΣT (I1) = {(ϕ, ϕ)}, ΣT (I2) = {(c, ϕ)} = ΣT (I ′′ 2 ), ΣT (I ′2 ) = {(d, ϕ)} = ΣT (I ′′′ 2 ), and so on. These properties define the boundary between X ⊂ Y and X = Y shown in Figure 2(b) and 2(c). 2 In two-player EFGs either without chance nodes [Von Stengel and Forges, 2008] or with public chance nodes [Farina and Sandholm, 2020], the von Stengel-Forges Polytope gives rise to a polynomial-time algorithm for correlated equilibrium. However, these results cannot be extended to TME because (as we show later) using the von Stengel-Forges Polytope does not lead to a polynomial-time algorithm for TME even in games without chance nodes, e.g., the game in Figure 1(a) or 1(b). Proposition 3. In any EFG satisfying the non-unique-path property, X is a strict subset of Y, i.e., X ⊂ Y. We now provide a positive result for some EFGs. Proposition 4. In any EFG satisfying the unique-path property, X = Y. Note that the assumption of the unique-path property can be easily verified in any EFG in linear time in the size of the game by checking each information set. The above results define the boundary between the existence and nonexistence of a polynomial-time algorithm for TME. That is, we have the following positive complexity result. Theorem1. In any EFG satisfying the unique-path property, a TME can be computed in polynomial time. The EFGs satisfying the unique-path property can model many scenarios. For example, in poker, including any games using cards, a team of players may share card information with each other (at least, according to some movies such as 21 (https://en.wikipedia.org/wiki/21 (2008 film)). More specifically, in an online variant of DouDizhu [Zha et al., 2021], friends can see the information of cards held by friends on the screen to fight against the adversary. Other examples include some variants of real-world security games [Wang et al., 2019; Zhang et al., 2019], where defenders have real-time location information about other players, e.g., through GPS. Such information enables the player to consider how other defenders try to interdict the adversary (e.g. the poacher in the forest or the criminal in the city) on the path. In these games, the unique-path property holds, and team members may use a polynomial-time Program (5) to compute a TME strategy by replacing X with Y and then transform it into independent realization plans for team members using Eq.(4). We understand that the EFGs satisfying the unique-path property are relatively rare, and the EFGs satisfying the nonunique-path property are common. Therefore, we still need efficient algorithms to compute a TME in general EFGs. However, the significance of a boundary between the existence and nonexistence of a polynomial-time algorithm is: 1) it helps us understand the complexity of computing a TME better, i.e., knowing which case is easy and which case is hard; and 2) it helps us develop an efficient algorithm to compute a TME for general EFGs and understand the reason why the algorithm works, which is discussed in Section 4.2. ## 4.2 Solving General EFGs By Proposition 3, there are some EFGs where we cannot use Y to replace X , i.e., we still need to use a global optimization solver to solve the nonlinear program for a TME. To make the nonlinear program efficiently solvable, we propose our correlation-based algorithm by combining Y and a special correlation plan space implicitly used as the feasible solution space in the global optimization solver. We then theoretically show the efficiency of our correlation-based algorithm by proving that this combination will strictly reduce the feasible solution space in these EFGs. We now present the special correlation plan based on the well-known McCormick envelopes [McCormick, 1976] for convex relaxation of nonlinear programs. The McCormick envelope is usually used as a basic technique to solve a bilinear program in state-of-the-art non-convex optimization solvers, e.g. Gurobi [Gurobi, 2020]. The McCormick correlation plan m : Σ▷◁ T → [0, 1] has a polynomial-sized set of linear constraints and assigns a probability for each relevant joint sequence. The team's plan satisfies the following a polynomial-sized set of linear constraints with T = {1, 2}: That is, the McCormick correlation plan is bounded according to the realization plan, and Eqs.(7a)-(7d) represent inequalities r1(σ1)r2(σ2) ≥ 0, (1 - r1(σ1))(1 - r2(σ2)) ≥ 0, r1(σ1)(1 - r2(σ2)) ≥ 0, and r1(σ1)(1 - r2(σ2)) ≥ 0, respectively, where r1(σ1)r2(σ2) is replaced by m(σ1, σ2). We denote this McCormick correlation plan space as M. For multilinear programs, the recursive McCormick relaxation recursively transforms each multilinear term into bilinear terms 3 . Therefore, we only present the McCormick correlation plan for two players as it is easy to extend to the multiplayer setting by recursive McCormick relaxation. We now show that M strictly includes X , as illustrated in Figure 2(a). Therefore, M is strictly larger than X, and we cannot use Eq.(7) as the constraints of X, i.e., we cannot have a polynomial-time algorithm for computing a TME in any EFG based on the McCormick correlation plan. However, when we use a global optimization solver, e.g., Gurobi, to solve a nonlinear program, the solver implicitly restricts the feasible solution space after convex relaxation toMand then searches for the optimal solution. We now propose our correlationbased algorithm for computing a TME to explicitly restrict the feasible solution space to Y and use nonlinear constraints to represent X in Program (5): ## Proposition 5. X ⊂M in any EFG. That is, Program (8) is a nonlinear program because of constraints (1a)-(1c) and (3) that represent the correlation plan space X . In addition, we restrict the feasible solution space to Y through Eq.(6) (the variable y is changed to x when Eq.(6) is inserted into Program (8)) in addition to the implicit feasible solution spaceM. Our experiments show that these constraints will make our program efficiently solvable. We now theoretically show why restricting the feasible solution space to Y can achieve this good result by showing that this step will strictly reduce the space of M, i.e., the implicit feasible solution space after convex relaxation of nonlinear terms, as shown in Figure 2(d). 3 E.g., the term m1 = r1(σ1)r2(σ2)r3(σ3) is transformed into two bilinear terms m1 = m2r3(σ3) and m2 = r1(σ1)r2(σ2). Table 1: The runtime for algorithms in different games: |B| represents the number of nonlinear terms, |Σi| represents the number of sequences of each player in a game, and '>10h' indicates that an algorithm did not reach the given optimization gap within 10 hours. No algorithms can reach the gap 0.0001 within 10h in games with ∗ (i.e., 4K6, 3L2-3, and 3L3-2), where the runtime for the gap 0.3 is reported. | | EFG | 3K4 | 3K6 | 3K8 | 3K10 | 3K12 | 3K13 | 4K5 | 4K6∗ | 3L2-3∗ | 3L3-2∗ | |-----------|-----------------|-------|-------|-------|--------|--------|--------|-------|--------|----------|----------| | Size | |B| | 132 | 330 | 616 | 990 | 1452 | 1716 | 2200 | 4170 | 572 | 1707 | | Size | |Σi | | 33 | 49 | 65 | 81 | 97 | 105 | 81 | 97 | 209 | 457 | | | CNLP | 0.1s | 0.3s | 37s | 47s | 273s | 1.5h | 146s | 1303s | 20s | 141s | | Algorithm | NLP | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | | Algorithm | IARAMDT | 0.2s | 4.3h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | | Algorithm | MDT | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | >10h | Table 2: The runtime to reach the gap from 0.1 to 0.0001 in 3K6 and 3K8: Rows 1-4 represent CNLP, NLP, IARAMDT, and MDT, respectively, and 10h represents >10h. | | 1 10 | 1 102 | 1 103 | 1 104 | 1 10 | 1 102 | 1 103 | 1 104 | |----|--------|---------|---------|---------|--------|---------|---------|---------| | 1 | 0.3s | 0.3s | 0.3s | 0.3s | 8s | 25s | 35s | 37s | | 2 | 10h | 10h | 10h | 10h | 10h | 10h | 10h | 10h | | 3 | 15s | 68s | 1.4h | 4.3h | 10h | 10h | 10h | 10h | | 4 | 10h | 10h | 10h | 10h | 10h | 10h | 10h | 10h | Proposition 6. In any EFG satisfying the non-unique-path property, X ⊂ (M∩ Y) ⊂ M. X ⊂ (M∩ Y) ⊂Mmeans that: 1) we cannot simply use (M∩ Y) to replace X in Program (5) to compute a TME, i.e., Program (8) with nonlinear constraints to represent X is necessary; and 2) restricting the feasible solution space to Y will strictly reduce the space of M, i.e., the feasible solution space after convex relaxation of nonlinear terms. By Propositions 4 and 5, X = (M∩ Y), i.e., Program (8) after the convex relaxation is still a polynomial-time algorithm to solve EFGs satisfying the unique-path property. Therefore, Program (8) is efficient to solve general EFGs for TMEs. ## 5 Experimental Evaluation We now evaluate the correlation-based Program (8) proposed above. All experiments ran on a machine with an 8-core 2.3GHz CPU and 16GB of RAM. All programs were solved by Gurobi 9.1. 4 We used the default optimization gap in Gurobi, i.e., |U-u| |u| = 0.0001, where U is the upper bound, and u is the lower bound of the objective function produced by the solver while searching for the optimal solution, unless stated otherwise. Codes are available at Footnote 1. 4 For games with multilinear terms, we use the recursive method mentioned in Section 4.2 to transform them into bilinear terms. We tested our algorithm on benchmark multiplayer poker games [Zhang et al., 2021]: Kuhn poker and Leduc poker, which satisfy the non-unique-path property. We use nKc to represent an n-player Kuhn game with c different cards and nLk-c to represent an n-player Leduc game with k ranks and c cards for each rank. Generally, the team is formed by players 1 to n - 1. We use CNLP to represent our correlationbased algorithm (i.e., Program (8)). We evaluate our CNLP against three baselines: 1) NLP: we use Gurobi to solve the nonlinear Program (2) as a baseline; 2) IARAMDT: the prior state-of-the-art algorithm for computing a TME [Zhang and An, 2020a] based on MDT; and 3) MDT: the original MDT algorithm for global optimization [Andrade et al., 2019; Kolodziej et al., 2013]. Note that NLP is equivalent to solving Program (8) within M that is implicitly used in Gurobi. Table 1 shows the runtime to compute a TME in different games, while Table 2 provides additional details about the convergence in games 3K6 and 3K8 (similar results were achieved in other games shown in Table 1 as well). Results in Tables 1 and 2 verify that: 1) Our algorithm CNLP dramatically outperforms the baselines. 2) Our algorithm CNLP still significantly outperforms the baselines even when the optimization gap is relaxed, as shown in Table 2. 3) Our algorithm CNLP could be four or five orders faster than the prior state-of-the-art algorithm IARAMDT (see the result for 3K6 in Table 1). 4) Our algorithm CNLP can solve many games (e.g., games 3K8-3K13) that IARAMDT cannot solve. 5) Our algorithm CNLP dramatically outperforms NLP, which highlights the importance of restricting the feasible solution space to Y. 6) IARAMDT dramatically outperforms MDT, which is consistent with previous results [Zhang and An, 2020a]. ## 6 Conclusions In this paper, we focus on computing a TME in zero-sum multiplayer EFGs. We first propose to use a correlation plan to represent the team's strategy to show that a TME can be found in polynomial time in specific EFGs according to our boundary for complexity. Second, we propose an efficient correlation-based algorithm for TME in other EFGs by combining two special correlation plans for smaller feasible solution space after relaxation. Finally, experimental results show that our algorithm significantly outperforms baselines. ## Acknowledgments We gratefully acknowledge support from ONR grant N00014-20-1-2407. Bo An is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-RP-2019-0013). ## References 1. [Andrade et al., 2019] Tiago Andrade, Fabricio Oliveira, Sil- vio Hamacher, and Andrew Eberhard. Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming. Journal of Global Optimization, 73(4):701-722, 2019. 2. [Basilico et al., 2017] Nicola Basilico, Andrea Celli, Giuseppe De Nittis, and Nicola Gatti. Team-maxmin equilibrium: Efficiency bounds and algorithms. In AAAI, pages 356-362, 2017. 3. [Bowling et al., 2015] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 347(6218):145-149, 2015. 4. [Brown and Sandholm, 2017] Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect-information games. In NeurIPS, 2017. 5. [Brown and Sandholm, 2018] Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418- 424, 2018. 6. [Brown and Sandholm, 2019] Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Sci- ence, 365(6456):885-890, 2019. 7. [Celli and Gatti, 2018] Andrea Celli and Nicola Gatti. Com- putational results for extensive-form adversarial team games. In AAAI, pages 965-972, 2018. 8. [Chen and Deng, 2005] Xi Chen and Xiaotie Deng. 3-Nash is PPAD-complete. In Electronic Colloquium on Compu- tational Complexity, volume 134, pages 2-29, 2005. 9. [Farina and Sandholm, 2020] G Farina and T Sandholm. Polynomial-time computation of optimal correlated equi- libria in two-player extensive-form games with public chance moves and beyond. In NeurIPS, 2020. [Gurobi, 2020] Gurobi. Non-convex quadratic opti- mization. https://pages.gurobi.com/rs/181-ZYS-005/ images/2020-01-14 Non%20Convex%20Quadratic% 20Optimization%20in%20Gurobi%209.0%20Webinar. pdf, 2020. Accessed: 2021-08-02. 10. [Jiang et al., 2013] Albert Xin Jiang, Ariel D Procaccia, Yundi Qian, Nisarg Shah, and Milind Tambe. Defender (mis)coordination in security games. In IJCAI, pages 220- 226, 2013. 11. [Kolodziej et al., 2013] Scott Kolodziej, Pedro M Castro, and Ignacio E Grossmann. Global optimization of bilin- ear programs with a multiparametric disaggregation tech- nique. Journal of Global Optimization, 57(4):1039-1063, 2013. 12. [McCormick, 1976] Garth P McCormick. Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical Pro- gramming, 10(1):147-175, 1976. 13. [Moravčík et al., 2017] Matěj Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. DeepStack: Expert-level artificial in- telligence in no-limit poker. Science, 356:508-513, 2017. 14. [Nash, 1951] John Nash. Non-cooperative games. Annals of Mathematics, pages 286-295, 1951. 15. [Russell and Norvig, 2016] Stuart J Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Malaysia; Pearson Education Limited, 2016. 16. [Shoham and Leyton-Brown, 2008] Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008. 17. [Von Stengel and Forges, 2008] Bernhard Von Stengel and Franc ¸oise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4):1002-1022, 2008. 18. [von Stengel and Koller, 1997] Bernhard von Stengel and Daphne Koller. Team-maxmin equilibria. Games and Eco- nomic Behavior, 21(1-2):309-321, 1997. 19. [von Stengel, 1996] Bernhard von Stengel. Efficient compu- tation of behavior strategies. Games and Economic Behav- ior, 14(2):220-246, 1996. 20. [Wang et al., 2019] Yufei Wang, Zheyuan Ryan Shi, Lantao Yu, Yi Wu, Rohit Singh, Lucas Joppa, and Fei Fang. Deep reinforcement learning for green security games with real- time information. In AAAI, volume 33, pages 1401-1408, 2019. 21. [Zha et al., 2021] Daochen Zha, Jingru Xie, Wenye Ma, Sheng Zhang, Xiangru Lian, Xia Hu, and Ji Liu. DouZero: Mastering DouDizhu with self-play deep reinforcement learning. In ICML, 2021. 22. [Zhang and An, 2020a] Youzhi Zhang and Bo An. Com- puting team-maxmin equilibria in zero-sum multiplayer extensive-form games. In AAAI, volume 34, pages 2318- 2325, 2020. 23. [Zhang and An, 2020b] Youzhi Zhang and Bo An. Converg- ing to team-maxmin equilibria in zero-sum multiplayer games. In ICML, pages 11033-11043, 2020. 24. [Zhang and Sandholm, 2020] Brian Zhang and Tuomas Sandholm. Sparsified linear programming for zero-sum equilibrium finding. In ICML, pages 11256-11267, 2020. 25. [Zhang et al., 2019] Youzhi Zhang, Qingyu Guo, Bo An, Long Tran-Thanh, and Nicholas R Jennings. Optimal in- terdiction of urban criminals with the aid of real-time in- formation. In AAAI, volume 33, pages 1262-1269, 2019. 26. [Zhang et al., 2021] Youzhi Zhang, Bo An, and Jakub Černỳ. Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. In AAAI, vol- ume 35, pages 5813-5821, 2021. 27. [Zinkevich et al., 2008] Martin Zinkevich, Michael Johan- son, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In NeurIPS, pages 1729-1736, 2008.