Computing Optimal Nash Equilibria in Multiplayer Games
Authors: Youzhi Zhang
Bo An
Venkatramanan Siva Subrahmanian
Venue: NeurIPS 2023 poster (2023)
Keywords: Algorithmic game theory
Optimal Nash equilibrium

Abstract: Designing efficient algorithms to compute a Nash Equilibrium (NE) in multiplayer games is still an open challenge. In this paper, we focus on computing an NE that optimizes a given objective function. For example, when there is a team of players independently playing against an adversary in a game (e.g., several groups in a forest trying to interdict illegal loggers in green security games), these team members may need to find an NE minimizing the adversary’s utility. Finding an optimal NE in multiplayer games can be formulated as a mixed-integer bilinear program by introducing auxiliary variables to represent bilinear terms, leading to a huge number of bilinear terms, making it hard to solve. To overcome this challenge, we first propose a general framework for this formulation based on a set of correlation plans. We then develop a novel algorithm called CRM based on this framework, which uses correlation plans with their relations to strictly reduce the feasible solution space after the convex relaxation of bilinear terms while minimizing the number of correlation plans to significantly reduce the number of bilinear terms. We show that our techniques can significantly reduce the time complexity and CRM can be several orders of magnitude faster than the state-of-the-art baseline.

Computing Optimal Nash Equilibria in Multiplayer Games
Youzhi Zhang
Bo An School of Computer Science and Engineering Nanyang Technological University Singnapore boanêntu. edu.ttuueddu...
Centre for Artificial Intelligence and Robotics Hong Kong Institute of Science & Innovation Chinese Academy of Sciences
youzhi changacair--aeee org
S.S. Subrahmanian Department of Computer Science
Northwestern University Evanston, USA vss ves@nozthhwettern.cc
Abstract
Designing efficient algorithms to compute a Nash Equilibrium (NE) in multiplayer games still an open challenge. this paper. we focus on computing an NE that optimizes given objective function. For example, when there is a team of players independently playing against an adversary in a game (e-g., several groups in a forest trying to interdict illegal loggers in green security games), these team members may need to find an NE minimizing the adversary's utility. Finding an optimal NE in multiplayer games can be formulated as a mixed-integer bilinear program by introducing auxiliary variables to represent bilinear terms, leading huge number of bilinear terms, making it hard to solve. To overcome this challenge, we first propose a general framework for this formulation based on a set of correlation plans. We then develop novel algorithm called CRM based on this framework, which uses Correlation plans with their Relations to restrict the feasible solution space after the convex relaxation of bilinear terms while Minimizing the number correlation plans to reduce the number of bilinear terms. We show that our techniques significantly reduce the time complexity, and CRM can be several orders of magnitude faster than the state-of-the-art baseline.
Introduction
One of the important problems in artificial intelligence is the design of algorithms for agents make decisions in interactive environments [33]. To this day, many results have been achieved in two-player non-cooperative environments, for example, security games 39] the game of Go (38), and poker games (6] One of the most important solution concepts behind these results the well-known Nash Equilibrium (NE) (30). Indeed, there are many efficient algorithms, e.g., algorithms based
on linear programs 42 43 37 47 48) or counterfactual regret minimization [56] [5) to compute Nash equílibria (NEs) in two-player zero-sum games. However, there fewer results efficient algorithms for NES with theoretical guarantees in multiplayer games (see the discussion in 4 ) and most of these results are for games with particular structures (e.g.. polymatrix games 7 ) The main reason is that finding NEs in multiplayer games is hard - it is PPAD-comples even for zero-sum three-player games [8] Designing efficient algorithms compute NEs in multiplayer games is thus still an open challenge.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we focus on computing an optimal NE that optimizes a specific objective over the space of NEs. In the real world, we may need optimize our objective over the space of NEs [34]. Possible objectives [9] could be maximizing social welfare (the sum of the players' expected utilities), maximizing the expected utilities of one player or several players, maximizing the minimum utility among players, minimizing the support sizes of the NE strategies, and so on. In addition, when there is a team of players in a game, team members need to consider finding an equilibrium that optimizes some objective [45 [1]. For example, in green security games where several heterogeneous groups (e.g., local police, the Madagascar National Parks, NGOs, and community volunteers) try to protect forests from illegal logging (26], the groups involved may need to find an NE that minimizes the
adversary's is utility
Unfortunately, the problems mentioned above are NP-hard 14 9 In two-player games, finding an optimal NE can be formulated as a mixed-integer linear program [34.. this formulation, finding an optimal solution means optimizing an objective over the space of NEs, and this space is modeled as the feasible solution space of the mixed-in -nttegerre linear program. We can directly extend this two-player formulation to find an optimal NE in multiplayer games by representing the space of NEs as the feasible solution space of a mixed-integer bilinear program transformed from a multilinear program by using auxiliary variables to represent bilinear terms. Then finding optimal NE requires solving a non-convex program. Unfortunately, such a formulation is not efficient because there exponentially many bilinear terms in the program. There are other approaches (e.g.. 4 that guarantee finding an NE in multiplayer games. However, these approaches need to enumerate all NEs to find an optimal NE, which is very inefficient 34 (sce our experimental results) because there can be exponentially many NEs
To tackle this challenge, we first propose general framework for transforming multilinear program for computing optimal NEs into a bilinear program based on a set of correlation plans, where each correlation plan (i.e.. probability distribution over joint actions) corresponds to set of auxiliary variables representing a set of bilinear terms. We then develop a novel algorithm called CRM based on this framework, which uses Correlation plans with their Relations to strictly reduce the feasible solution space after the convex relaxation of bilinear terms while Minimizing the number of correlation plans to reduce the number of bilinear terms. We show that our techniques can significantly reduce the time complexity, and CRM can be several orders of magnitude faster than the state-of-the the-art baseline. To our best knowledge, CRM is the first algorithm to use minimum set of correlation plans to reformulate the program for computing optimal NEs in multiplayer games.
2 Preliminaries
Consider normal-fome game G -N, A, 37|. We denote the set of players as N = [l,.....]; the set of all players' joint actions is A XieN A,, where A, the finite set of player i's pure strategies (actions) with o; E A; and the set of all players' payoff functions is u = (#1,.... Un), where u; A + R is player i's payoff function. Let Umaz = m m (a) and Unin = minjeN m (a). In addition, the set of (joint) mixed strategy profies X = Xxex X,, where X, = A(A.) (i.e., the set of probability distributions over A,) is the set of mixed strategies of player i, and zz,(a)) is the probability that any action o; E A, is played. Let i be the set of all players excluding player i, i.e.. -i = \ {i), and A_; be x XJeNVH A.. Generally, given N' C N, the action of player i E N' in the joint action ox For example, if ax = (01, a3. as) with N' = (1,3,5), axx = 0g. If N = N, we ignore the subscript, i.e. a an and A AN. For each x E X. player i's expected payoff is:
aN AN = XieN' A,, axx
(x(x)
Σ (a(a) II (a(())
aEA
JEN
and, if player i plays az:
(i x-1)=
Σ E.A:
u, a-i) II xy(a=;()) je-i
'Here, if all team members play strategies according to an NE minimizing the adversary's utility, the adversary cannot deviate from the equilibrium strategy obtain higher utility.
"Our methods mostly apply to normal- fermal-frm games including green security games mentioned in Section Extensive- form games can be first converted to normal-form form games to be solved, and exploiting their game structure is the future work.
2

---

In this paper, we consider multiplayer games, i.e., n 2.
A Nash Equilibrium (NE, and NEs for Nash Equilibria) 30 is stable strategy profile in which no player has an incentive to change her strategy given other players' strategies and always exists. Formally, a strategy profile x² is NE if, for each player i, x is best response x= i.e., un ux(2), +f,, 2 u.(Ii, <".,, Vr; E X,, which is equivalent to uz x-;)) 2 u,(a,, Va; E A,.
With the above condition of NEs, we could use multilinear program to represent the space of NEs, but it will involve the product of strategies in u, (I), whose degree is n and is higher than the product of strategies in u,(a,, x-1). To reduce the degree of the program representing the space of NEs from n to n - (i.e., only the product of strategies in u, u, 2--) is required), in two-player games, the previous work [4 exploited the following NE's property, which can be used in multiplayer games as well. For each strategy profile x E X, the regret of an action a; is the difference in player i's expected utility between playing 3; in and playing ds i.e., uz(x)) uz(as, x-.). Obviously, strategy profile x E X is an NE and only if every action either has the regret O, or is played with the probability 0 in æ. Then the space of NEs of game can be formulated as the feasible solution space of mixed-integer program by using a binary variable ba. to represent that any action a, either has the regret 0, or is played with the probability 0:
04(0;,,=i)
= Σ
ui(a;, a-i) II ay(a=;(i) Vi,a; E A, JE-i
(1a)
a
Σ x1(aa== =1 ViEN a
(lb)
1 bu. 2 x1(1,) ViE E. A,
(Ic)
(x)) (000) Vi ViE A,
(Id)
(x) (((a,,=))) S (Umaz - Umin) ViE V,E E An 4, E [Umin Umax], ux(z) E mUmin Umau] vi N. A., xx(a,)= E [0, ba, E 10, E, E A,,
(Ie)
(1f)
(Ig)
where we use the notations of utility functions (x(x)) and u.(a; to represent the corresponding variables in the program. Eq.4ic) ensures that binary variable 6s, is set to 0 when x; (a,) > 0 and can be
only when (a.) = 0; and Eq.(Te) ensures that the regret of action a; equals 0 (i.e., (z) = u, (a, x -)),, unless ba. = 1 where the constraint (z(z) un (a,, =) S (Umar Umin) always holds.
An optimal NE is an NE optimizing an objective function g(x) over the space of NEs, where g(x) is linear objective functior[] and could be maximizing social welfare, maximizing the expected utilities of one player or several players, maximizing the minimum utility among players, minimizing the support sizes of the NE strategies, and on. Unfortunately, finding an optimal NE optimizing the above objectives is NP-hard [9].
3 Computing Optimal Nash Equilibria
The problem of finding an optimal NE in multiplayer games requires optimizing an objective over the space of NEs. This space is represented by [T. which involves nonlinear terms in Eq. to represent the strategies of players in -i, which bilinear when n and is multilinear when 2 4. The multilinear program is usually transformed into a bilinear program to make the program solvable using global optimization solvers, e.g., Gurobi [19]. Here, we propose a general framework for this transformation based on set of correlation plans for any binary collection of subsets of players, where each set this collection is divided into two disjoint sets, and each correlation plan corresponds to set of auxiliary variables representing set of bilinear terms. However, there are two challenges for solving this bilinear program: 1) this bilinear program usually involves a large number of bilinear terms, and 2) an important step used by state-of-the-ar algorithms to solve such bilinear programs is to use convex relaxation to replace each bilinear term in the program [15] 18) which significantly enlarges the feasible solution space. To overcome these challenges, we develop novel algorithm called CRM that uses Correlation plans with their Relations to strictly reduce the feasible
'If g(x) is nonlinear, we can use variable (i.e., a linear function) as the new objective with the constraint such that g(x).
3

---

solution space after the convex relaxation while Minimizing the number of correlation plans to reduce the number of bilinear terms. Section s.4 that our techniques can significantly reduce the time complexity. The procedure of CRM is shown in Algorithm 2, which is illustrated in Appendix A
3.1 A General Transformation Framework
A correlation plan is probability distribution over the joint action space of a subset of players, and we focus on correlation plans for certain special collections subsets of players, which can be used to transform multilinear program for computing optimal NEs into bilinear program.
Definition 1. A collection N of subsets of players is binary collection if:
1. {-iliENy NW;
2. for each N' N, N' C. N.N with (N' 2 2: and
3. for each N' E N,, there are two disjoint children Ni and N; in {() l N] U. such that N/ NN; = and N' = N2 U N, i.e., N' is divided into two disjoint sets.
Let Ni and N be the left child and the right child of N E N, respectively. For each N' in any hinary collection N, correlation plan of N' is probability distribution xx over Ag:: given nN xN((aN)) E (0, (Vax' E AN', N' EN,
Σ (N)( =1 YN' AyrEANr
For simplification, let i be equivalent to {i} for each E N. That is, is special correlation plan TG) (i.e.. 2, = (.)).. a, E A, special joint action ( E App) (i.e., a, = a(i)). Each element N' in a binary collection A has the binary division, i.e., it is divided into two disjoint sets Nj and NÝ. Based on this binary division, any joint action aN Ay can be divided into two sub-joint actions aN; AN; and aN; E Av; such that aN (aNg, aN;). Then we can use this binary division to ensure that [L 2a(a (i)) = IN (ax)) for the correlation plan IN,, as shown Example [
21, 4), (1.3, 4), 3, 4), {1. (1.3), (2, [1,4], {3, 4), {2, (2, 4} is a binary collection for a four-player game. For N' (1,2,3) in this collection with N2 = {1.2] (having two children (1} and (2)) and N; (3), have ax (a1, (a1,02,03) = (a(1.)) as) E Ax and aq1.2} (2),02) E A Then can have a chain of bilinear constraints (equalities): x (ax)) = (112)) (4(1,2) (z(())) and (112))((1.2)) = (1(0))=2(00)
Example 1.
which guarantees that xN'(ax' = I x1(a))as (22)2aa( In other words, we use 2(1.2) (Q(1.2)) and (ax) as the auxiliary variables to represent bilinear terms 21 (21))2((02) and x (1.2) (0 )=)())))) respectively.
This property of correlation plans of a binary collection can be used to transform multilinear Program (I) into a bilinear program. First, we use the binary division of each element N' in N to connect correlation plans, i.e., for any N' E N with its children Nj and NZ:
xN NN (aw; ( (oN(( VaN- aNY) E AN
(3a)
(aN)) E [0 VaN E AN..
(3b)
Second, replace Π Fz (a((((()) in Eq. lab with ra)(a
Uz (a(
Σ
a
Vi NEEN
(4)
R-.EA_;
In the above transformation, each correlation plan corresponds to set of auxiliary variables (e.g.. xN (ax:)) representing a set of bilinear terms (e.g., nN; (a)))))) (ax;)). Eq. guarantees that II Z (aw (j)) = xNx (a and then the feasible solution space of Eqs. Ig (3) and represents the space of NEs.
Theorem 1. The feasible solution space of mixed strategies (i.e. I; (as) ) for each i N, ag E A&) in
Eqs. 1b
33, and (4) is the space of NEs. (Proofs are in Appendix B)

---

We can then compute optimal NE by solving the following mixed mixed-integer bilinear program according to any binary collection A
max ((x)
(5a)
s.t. Eqs. 16
1y
(5b)
It is straightforward to solve Program ( by using the vanilla binary collection A that includes all non-singleton proper subsets of N, i..., N {N' | c NN 2 2}. where, for each N E N, N2 is N \\ {i} and NF is (j- m i}. Example provides an example of N.
3.2 Exploit Correlation Plans with Their Relations
In this section, we use correlation plans with their relations to restrict the feasible solution space after the convex relaxation. The common convex relaxation technique 27
35 [8] before searching for the
optimal solution is: each bilinear term vv (ax') y/ 1/2 with yı, U2 E [0, 1] represented by the following constraints including four linear constraints:
m y1 + 1/2 - 1} S (v((an) S min V23.
(6)
which significantly enlarges the feasible solution space. We now show the motivation to use correlation plans with their relations to reduce this feasible solution space.
Example 2. Given N' {2, 43 N with actions for each player (i.e., A; = {ai, d33 in a game
G. by Eq bilinear terms (e.g., EN (a2, a1) = I2 (z((a))za(aa) are relaxed according to E e.g.. max 0, 22 (2) + x1s) 1} < EN (a2, a1) < <min(x2(a2)) (4 (a(a)). With additional constraints by Eq. lb (e.g., z4(01) + xa ( = 1), the following assignment could be a feasible solution:
x (a2, 04) xx (ag. 01) xxv (4) = (ay a')
=x2( xz (12) (04) ==(( = 0.5.
IN (a2, 04) is not equal to (=(aa))aa(aa) In fact, based on Eq. 2 we have: Obviously, in Eq.
NN (a2. a1) + N (022 01) + (x, d'a) + xN (azz d'a) = 1,
(8)
which will make the solution Eq. (7) infeasible. Moreover, the following assignment is a feasible solution after the relaxation and satisfies Eq. 8
IN'' (a2, 01) = xN (ay 04) = IN a')) 0.2, IN (a a()) 0.4, (02) = x (a1) = 0.5.
(9)
However, in Eq. N (a2, a1) still not equal to x2(22) (a1). Actually, we have:
x (a2, a4) + x (a2 a1) (a1),,
(10)
nN (02, d44) + xN (ag- d/4) = (d4),,
which will make the solution in Eq. 9 infeasible.
This above example shows that can use the definition of correlation plan (i.e., Eq. and the relation correlation plans to reduce the feasible solution space after the relaxation.
Each element N' in any binary collection N is defined by N/ and N'. which actually defines
relations between correlation plans for elements in {fi} | i e N} U.. In Example 2 (0 actually represents relation between the correlation plan xx and the mixed strategy 34 (i.e., the special correlation plan x TAa)). Formally, for any N' E N and i N':
Σ
(aN)) (a Va, A
(11)
axy Ex Ey.EANNaay
where a (i) is the action of player i E N' in the joint action ax. Similarly, let (x=(N") be the sub-joint action of player N" c CN' in the joint action ay. Then, for any N' e W with its children Ni and NÝ. and N E NA):
Σ
(ax)) IN"((N") VaNu E AxD
(12)
ag E ( (a
5

---

Algorithm 1 Generate A
1: Build full binary tree T_n with the height [log2 (n 1)] for -n with the set of internal nodes Nr.,. and WN =
2: for each i in (1,....
-11 } do
3: Search T-n to replace i with each node including to form a binary tree T-, with the set of internal nodes Nr_,
4: end for
5: N + UieNNT
where we could add |N'| > ensure that Eq. 11 and Eq. 12 do not generate the same constraints. Appendix A shows some examples of these constraints. Eq. represents the relation between the correlation plan zyy and the mixed strategy z; (i.c., the special correlation plan z(()) ) for each e NN, and Eq. 12 represents the relation between the correlation plan N and the correlation plan n IN.. Equivalently, Eqs. 2). (IT) and (I2) represent the marginalization constraints that independent probability distributions ought to obey, where EN is the joint distribution (represented by (2. of independent distributions a; for all i E N' (represented by Eq. or independent distributions VNy and Ny; (represented by Eq. T22)
We now show the effectiveness of our correlation plans by showing our method strictly reduces the feasible solution space after the relaxation. Reducing the feasible solution space will make the program efficiently solvable, as shown in the experiments. Let M be the original feasible solution space for the original multilinear program that is transformed into bilinear program according to N, i.c., M is particularly constrained by Eqs.q (3a). and (3b). We define the convex relaxation space R using Eq.46) to represent each bilinear term in Eq.(3a). i.e., R. is particularly constrained by Eqs.(Ib) (6), and (3b). We define our tight relaxation space 7 based on our correlation plans, i.e., T particularly constrained by (Ib). (2). (II). (12). and (3b). (Proofs
in Appendix B
Theorem 2. M c T R,, T is strictly smaller than R but still includes M.
The property M CCTC C R means that: i) we can use T to strictly reduce the feasible solution space after the relaxation, and restricting the feasible solution space to does not reduce the space of NEs and then guarantees optimality for the original program. We now explicitly restrict the feasible
solution space to T by adding Eqs. (2.. (TT). and (12) Program (5) for any binary collection N
max g(x)
(13a)
S.t. Eqs. 1b
1g
(13b)
Theorem 3. The optimal solution of Program
13 maximizes g(z) over the space of NEs.
Using the bilinear constraint Eq. Bap
Program is necessary for computing an optimal NE by solving Program (13) because MM T. Appendix Cshowss that, after removing (q.(Ba) in Program (13). the inefficiency can be arbitrarily large, and the resulting strategy profile may be an NE.
3.3 Minimum-Height Binary Trees
we need add set of linear constraints and bilinear constraints for each correlation plan corresponding to each element in any binary collection A. The size of the vanilla binary collection N is 2n (n + 2), which grows exponentially with the number of players. this section, we propose building minimum-height binary trees to obtain a minimum binary collection. Our binary collection gives us a minimum set of correlation plans, which requires significantly fewer bilinear terms than N.
In Program 13
There are different ways to divide a subset of players, which determines different binary collections. For example, N' 2,, 3, 4) can be divided into {1, and (3, 4) or {1} and (2,3, 4). which will lead to different binary collections. Therefore, for obtaining a minimum binary collection N,, the challenge how to effectively divide each element in N.

---

Algorithm 2 CRM
1: Input: A game G = (N, A, u) and an objective function g(x)
2: A binary collection NV < The output of Algorithm |
3: Create Eqs. (T))
4: Create Eqs. 3). 2
and (12 according to .NV
5: x² An optimal solution by solving Program 13 based on M, i.., max. g(x) s.t. Eqs. 16
Lgl.
12
6: Output: An optimal NET
To overcome this challenge, we propose building minimun-height binary tree for each element in {-i i E N) and ensuring that the number of internal nodes in these binary trees is the min- imum. The binary division for each element in a binary collection / creates a binary tree for each element in {-i i E J). For example, Figure a a binary tree for -5 = {1, 2, 2,3,4) and Figure bb) is binary tree for -3 {1, 2, 5, 4} in five-player games. Each binary tree for - is full binary tree, i.e., each internal node has two children, with n 2 internal nodes and n leaf nodes, where the height is the number of internal nodes on the longest path from the root leaf (e.g., the height in Figure a is 2). Details for these binary trees are shown in Appendix D We can then build full binary tree T-n with the minimum height [log2 1)] for -n and then replace i with in the 1]. That creates n full binary trees for {-i N). This procedure shown in Algorithm 1 (details are shown in Appendix D). generating our minimum binary collection N' including all internal nodes in these trees. For example, Figure aa) builds binary tree 7-5. and Figure (b) obtains T-3 by replacing 3 with 5 in T- Generally, we only need to create at most [log, (n 1) new internal nodes to build a minimum-heige binary tree for each- -i with i n. Then |M] is at most n + (n 1) logg (n 1)7, i.e., O(n log n)) Theorem 4. N generated by Algorithm is binary collection, and On log n) for the size of N is the minimum size of all binary collections of a game G. (Proofs are in Appendix
(1,2334]
(1.2354)
11.2]
(3,4]
11.21
[9.4]
[2)
(3/
(4]
(2)
(5)
(4)
(a)
(h)
Figure I: Binary trees for -5 and
nodes of T- n. to obtain T-; for each i E - = (1,...,77
| only grows sub-quadratically with n and is much smaller than J 2" - (n + 2) for N. Then N requires fewer bilinear terms than N when n > 3. For example, in a seven-player game with two actions for each player, by using A with | -11 correlation plans, the number of bilinear terms is 564, which is much smaller than 2044 by using NV with [W] 119 correlation plans. Table Jof Appendix G shows more examples. Note that Algorithm cannot reduce the number of internal nodes when = 3 because each element in {-i | i N) includes only two players in three- thrce-player games. Our algorithm, CRM, is solving Program 13) based on N, which is shown in Algorithm and is illustrated in Appendix A
3.4 Complexity
The problem of finding an optimal NE is NP-hard (9) and our algorithm, CRM, i.e., Program 13)
based on N generated by Algorithm 1, is mixed-integer bilinear program. whose scalability is mainly affected by the number of bilinear terms and integer variables. Generally, the problem of solving a linear integer program is NP-hard, and the time complexity is (( where is the number of integer variables, E is the number of constraints containing integer variables, and C is the maximum value among constants and the range of integer variables in these constraints. Theoretically, each bilinear term can be represented by a -ixeee-itteger linear program by introducing new set of constraints and binary integer variables [21]. Suppose each bilínear term introduces l' integer variables and E' constraints, and each player has m actions. Program (5) based on N has mn binary integer variables with mn constraints and the following number of bilinear terms:
[32].
Σ
II |A, < (2 n - 2)m"~1 < mm
NEN
Then the time complexity for solving the Program 5 based on N is O(T{(F) C2)2E.+3) where
I 2-1p + mn and E, n-1 E mn. Program 13 based on N has mn binary
7

---

Table I: Part of experimental results (more results are in Tables and 5 of Appendix H). The format is: Average Runtime + 95% Confidence Interval (Pencentage of Games not Solved within the Time Limit) (Utility Gap). Note that the unit the runtime second, the case that all games have been solved with the time limit should be (0%) and is omitted, we only need to care about the utility gap (a larger gap means losing more) for EXCLUSION, and the utility gap represents EXCLUSION cannot return a solution within the time limit.
Random Game
Runtime i 95% Confidence Interval (Percentage of Games not Solved) (Utility Gap)
Vary
(n, m.
CRM
MIBP
ENUMPOLY
EXCLUSIIN
(3, 2)
0.01 1
0.02 0
0.03 0.01
31 + 41 (gap:15%))
n
(5, 2)
0.2 + 0.1
0,5
+ 0.4
11 + 4
753 + 148 (73%) (44):64%)
(7, 2)
25
+ 17
429 + 131 (20%)
1000 + 0 (97%)
835 + 119 (80%) (gap:53%)
(3, 5)
0.2 + 0.03
0.3 =0.1
1000 = (100%)
1000 = 0 (I00%) (g4p:67 %%)
(3, 8)
4 + 3
247 = 140 (17%)
1000 + (100%)
1000 + 0 (100%) (gap:oo)
(3, 10)
9
+ 9
334 = 167 (30%)
1000 - 0 (100%)
1000 + O (100%) (gap:oc)
(3, 13)
38
+ 21
342 = 151 (27%)
1000 + 0 (100%)
1000 + 0 (100%) (gap:oc)
GAMUT Game
CRM
MIBP
ENUMPOLY
EXCLUSION
Random LEG
2 +1
1000 + (100%)
1000 (100%)
986
27 (97%) (gap: 1 1%)
Random graphical
0.1 + 0.1
803 + 140 (83%)
50 30
971
+ 55 (97%) (gap:32%)
Uniform LEG
2.2 1
1000 + 0 (100%)
1000 + 0 (100%)
986 + 26 (97%) (gap:1 1%)
Table 2: Ablation study (more results are Tf Appendix H Note that (in CR and C) and A CRM.
CM, and M) result in the same hilinear terms in three-player games because each element in {-i i E {1, 2, 3}} includes only two players such that A Algorithm 1 cannot reduce the number of internal nodes to reduce the number of bilinear terms, and then CR and CRM (or C and CM) have the same performance. The unit of the runtime is second.
Runtime 95% Confidence Interval (Percentage of Games not Solved)
Game
CRM
CR
CM
M
(8, 2)
156+ 83 (3%)
612+ 129 (33%)
190 + 102 (7%)
763 + 120 (60%)
1000 (100%)
(7,2)
25 + 17
89 + 51
36 + 28
408 + 157 (30%)
488
+ 111 (10%)
(3, 15)
167.1 86 (3%)
167 i: 86 (3%)
317 :: 137 (17%)
317 : 137 (17%)
558
1 (40%)
(3, Random graphical
231+122 (10%)
231 +122 (10%)
326 134 (20%)
326 134 (20%)
784
102 (53%)
0.1 0.1
0.4 + 0.1
0.2 + 0.1
0.6 + 0.4
814
+ 134 (80%)
Uniform LEG
2.2 1: 1
5 44
2.5 2
5 4:5
999 + 2 (97%)
integer variables with mn constraints and the following number of biliear terms:
Σ II | < [mm"-1
NE
i... log n n)m"-1) bilinear terms (this size is the minimum because O(n log n) is the min- imum size of binary collections by Theorem 4 and Then the time complexity for solv- ing Program (13) based on A is (I2 23) where I2 (n log n n + mn and E2 (n log n n=mm" E' + mn, and thus On log n) of Algorithm can be ignored. Therefore, CRM dramatically reduces the time complexity (i.e., the term 2n in I and E₁ is changed to the term n log n in 12 and E2).
4 Experiments
Following prior work for NEs 34 (3). we evaluate our approach on two sets of games: randomly generated games (i.e., mn) with n players and m actions for each player) and six-player three- action games that are generated by GAMUT (31]. Payoffs are generated from the interval between 0 and 100 (other ranges (e-g-. [0, 1)) do not affect the result). Details are shown Appendix We show the game size in terms of the number of bilinear terms and integer variables in Appendix G e.g., the number of bilinear terms in the game (9, 2) is 19152 based on N but is 2512 based on A.
We compare our CRM shown in Algorithm 2, i.e., solving Program 13 based N, to the state-of ofee-----teeeaa art algorithms: i) MIBP (34 [3] the equivalent of solving Program (5) based on Ni; ii) EXCLUSION 4 the first implemented algorithm guarantees to converge to an NE by using tree-search based method by splitting the continuous probability space of the solution; and ii) ENUMPOLY (28): an algorithm in the well-known game-solving package Gambit which
Baselines:
*Codes are available at

---

tries to find all NEs by enumerating all the supports which could be the support of an NE and then searching for an equilibrium on that support. They represent upproaches solving a nonlinear program, finding an NE, and enumerating all Nash equilibria, respectively. There are some other algorithms in Gambit (28) for finding an NE in a multiplayer game, including: i) GNM [6] a global
Newton method approach; ii) IPA [7] an iterated polymatrix approximation approach: iii) LIAP: a function minimization approach; iv) SIMPDIV [4]]: a simplicial subdivision approach; and v) LOGIT 229 40 quantal response method. However, they cannot guarantee finding NE [4]. Therefore, they are not suitable for finding an optimal NE. In fact, we show in Appendix that all of them fail to solve many games and even run significantly slower than CRM in many games. Note that these Gambit algorithms only achieve some NE if the game is solved, which may not be optimal.
We set time limit of 1000 seconds for each case unless stated Algorithm Setting and Metric:
otherwise. Our optimality gap for EXCLUSION is significantly smaller than 0.001 in [4] (we verified that, with the same optimality gap, our result for EXCLUSION is almost the same as the one in (4). We mainly use the runtime and the percentage of games that are not solved within the time limit to measure the performance of our approach. Details are shown in Appendix (also caption of Table
Result: Part of results are shown in Table I1 and more results are in Tables f and 5 of Appendix
They show that the runtime of our CRM steadily increases with the game size. Note that the
runtime of CRM includes the runtime for our Algorithm I, which extremely small (see Appendix Moreover, CRM is sigmificantly faster than the baselines and is two or three orders of magnitude Faster than the state-of-art baselines MIBP, ENUMPOLY, and EXCLUSION in most games. The reasons are that: 1) MIBP with too many bilinear terms and large feasible solution space after the relaxation cannot perform well without CRM's novel techniques in Section 3 where each of these techniques significantly boosts the performance (see the ablation study); and 2) the exponentially many NEs and the large search space caused by splitting the continuous probability space make ENUMPOLY and EXCLUSION, respectively, hard to scale up. EXCLUSION always has large utility gaps, which means that we will lose large utilities we use EXCLUSION for our problem. The result that CRM runs significantly faster than EXCLUSION means that CRM is faster algorithm not only for computing an optimal NE but also for just computing an NE. Furthermore, the gap between CRM and any of the baselines increases with the number of players or actions. In games with a large gap between CRM and baselines, the real gap should be larger because these baselines have not solved all of them within the time limit, while CRM solved all of them. Overall, CRM significantly overcomes the limitation of baselines.
Ablation Study: We evaluate each component of CRM by using the following variants: i) CR: solving Program (13) based on NV ii) CM: solving Program (13) based on 'N without the relation constraints Eqs. b and 12); iii) C: solving Program 13) based on N without the relation constraints Eqs. (1T and (12); and iv) M: solving Program (5) based on A. Part of results are in Table and more
results are in Table of Appendix H We can see that each component of our approach significantly
boosts its performance.
Related Work
Existing works define correlation plan as a probability distribution over the joint action space of all players, and use it to formulate constraints for a correlated equilibrium [37 I.. However, the constraints for the space of correlated equilibria cannot be used in our program due to the following two reasons. First, there are no correlation plans for coordinating all players in our program after the convex relaxation because our formulation based on [44] has reduced the degree of the multilinear program for the space of NEs in order to significantly reduce the number of bilincar terms. Second, our correlation plans are different from the correlation plan for correlated equilibria because correlation plans are only for subsets of the players. Recently, the correlation plan 49 based on a decomposition of the extensive-form game into public states has been used to compute correlated equilibria. However, their approach is not suitable for our problem because our game is not extensive- form and then does not have the property of their problem. Then our approach exploiting the relations of correlation plans and minimizing the number of correlation plans is novel.
Several recent efforts have developed relatively efficient algorithms to find an NE that maximizes 51
the utility of a team of players in zero-sum games 45 algorithms cannot be used in games where team members have different utility functions. Existing
50
52
24 53). However, these

---

works transforming multilinear terms into bilinear terms only focus on special cases. For example, the transformation in [3] is equivalent to our transformation based on N. which is only a special case of our transformation framework. They [13] then directly solves the bilinear program based on this special transformation for finding an NE, which is equivalent to our baseline MIBP. Experiments show that our approach with novel techniques in Section 3 significantly outperforms 1
Similar to
the formulation in [34), there are other formulations 2 3 for finding an optimal NE for two players under the problem of computing a Seader-follower (Stackelberg) equilibrium for a single leader and two followers after a mixed strategy is committed by the leader. These formulations are different from ours because of the difference between the NE and the Stackelberg equilibrium. For example, the leader will commit a strategy to the followers in Stackelberg equilibrium, i.e., the followers know the leader's strategy, but this cannot happen in an NE as all players move simultaneously. Moreover, after dropping the dependences of the followers to the leader's s strategies in these bilinear programming formulations, the problem boils down to computing an optimal NE in two-player games because they only consider two followers in their formulations, which results in the same two-player formulation of
For the existing general optimization techniques, e.g., Reformulationn-Lnearzzzzttt Linearization Technique (RLT) [35 25 36]. they add linear constraints by multiplying linear constraints with a single variable to reduce the feasible solution space of the convex relaxation and the number of bilinear terms if they can be represented by linear constraints (i.e., variants of original linear constraints). However, these operations are not very effective for our problem because the bilinear terms cannot be represented by those linear constraints (i.e., variants of original linear constraints), and simply multiplying linear constraints with a single variable cannot effectively represent the relation between auxiliary variables and nonlinear terms. Indeed, RLT is implemented in Gurobi [8] [9], but its performance (see MIBP in Table ID is not good enough for large games in experiments. Moreover, our approach significantly outperforms the state-of- thrt optimization solver Gurobi (see results for CRM versus MIBP in Table 1 in experiments.
6 Limitations
Similarly to the previous literature [3), to efficiently evaluate the algorithms, we set a time limit of 1000 seconds for each case unless stated otherwise. It means that may need 30,000 seconds (almost 8 hours) to run an algorithm for each game setting (e.g.. the game (6,3) with 30 cases. We totally run 13 algorithms for 21 different game settings, whose total runtime is more than 2,000 hours if each algorithm needs 30,000 seconds for each game setting. A higher time limit means more runtime. For example, if the time limit is 10,000s, we may need 20, 000 hours (more than 800 days), which is not reasonable for a personal computer. Increasing the game size will cause a similar problem as well. Our goal is only to show that our proposed algorithm runs faster than baselines. Therefore, as a proof of concept, our time limit and game size are reasonable and practical.
Our algorithm CRM is significantly faster than the state-of-the-arr baseline, and it solve many real-world games: e.g., (1) multiplayer hand games using only the hands of the players (https) wwkipeedi..or//iikiiiiii
game), including the pock-paper-scissoorss games, Morra games, and their variants; and (2) the matching pennies game with several players and only two actions for each player. However, cannot handle extremely large games now because we handling very hard problem, and then it is unrealistic to expect that our exact algorithm CRM could run very fast in large games. Our algorithm is an attempt to make this computation of optimal NEs feasible, and our algorithm framework can be built on by further innovative heuristics to improve the computation of optimal NEs. That is, for games with more players or actions, we can exploit the auxiliary speed-up up techniques: the multiagent learning framework Poliic--Spaceeeee
Response Oracles (PSRO) [22 154 55 51 46 (33, the abstraction techniques [47] or only considering approximate NEs. Specifically, our algorithm CRM could be used as the meta-solver in PSRO.
7
Conclusion
This paper proposes a novel algorithm (CRM) for computing optimal NEs based on our transformation framework. CRM uses correlation plans with their relations to strictly reduce the feasible solution space after the convex relaxation while minimizing the number of correlation plans to significantly reduce the number of bilinear terms. Experiments show that CRM significantly outperforms baselines.
10

---

Acknowledgments and Disclosure of Funding
This research is supported by the InnoHK Fund, ONR grants N00014-18-1-2670, and N00014-20- 1 1-2407. Bo An is supported by the National Research Foundation, Singapore under its Industry Alignment Fund Pre-positioning (IAF-PP) Funding Initiative. Any opinions, findings and conclu- sions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
References
[1] Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of mathemati- cal Economics, 1(1):67-96, 1974.
[2] Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel programming ap- proaches to the computation of optimistic and pessimistic wew.--eeder-mlti-fllllee equilibria.
In SEA, volume 75, pages 1-14, 2017.
[3] Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel programming methods for computing single-leader-mun wwweimmllliiiliiii multi-follower equilibria in normal-form and polymatrix games. EURO Journal on Computational Optimization, 8(1):3-31, 2020.
[4] Kimmo Berg and Tuomas Sandholm. Exclusion method for finding Nash equilibrium in multiplayer games. In AAAI, pages 383-389, 2017.
[5] Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect- information games. In NeurlPS, 2017.
[6] Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 4224)44444144422000 2018.
[7] Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In SODA, pages 217-234, 2011.
[8] Xi Chen and Xiaotie Deng. 3-Nash PPAD-complete. In Electronic Colloquium on Computa- tional Complexity, volume 134, pages 2-29, 2005.
[9] Vincent Conitzer and Tuomas Sandholm. Complexity results about Nash equilibria. In IJCAI, pages 765-771, 2003.
[10] Hélène Fargier, Paul Jourdan, and Régis Sabbadin. A path-following polynomial equations systems approach for computing Nash equilibria. In AAMAS, pages 418 118.426,777 2022.
[11] Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Connecting optimal ex-ante collusion in teams extensive-form correlation: Faster algorithms and positive complexity results. In ICML, pages 3164-3173. PMLR, 2021.
[12] Jiarui Gan, Edith Elkind, Sarit Kraus, and Michael Wooldridge. Mechanism design for defense coordination in security games. AAMAS, pages 402-410, 2020.
[13] Sam Ganzfried. Fast complete algorithm for multiplayer Nash equilibrium. arXiv preprint arXhv:2002.04734 2021.
[14] Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-95) 99, 1989.
[15] Ambros M Gleixner, Timo Berthold, Benjamin Müller, and Stefan Weltge. Three enhancements for optimization- bound tightening. Journal of Global Optimization, 67(4):731-757, 2017.
[16] Srihari Govindan and Robert Wilson. A global Newton method to compute Nash equilibria. Journal of Economic Theory, 110(1):5--86, 2003.
[17] Srihari Govindan and Robert Wilson. Computing Nash equilibria by iterated polymatrix approximation. Journal of Economic Dynamics and Control, -227),129-1124, 2004,

---

[18] Gurobi. Non-conven quadratic http://wwww.../.oooooooooooooo/o
2020-01-14
20Wehinar.pdjj 2020. Accessed: 2021-09--2
[19] Gurobi. Gurobi optimizer reference manual. http://wwww..uuu..ccoom/oomumnnn refman/innexxcc httll 2021. Accessed: 2021 1021-09-20.
[20] Donald E Knuth. The Art of Computer Programming. Fundamental Algorithms, 3rd edition, volume 1, 1997.
[21] Scott Kolodziej. Pedro M Castro, and Ignacio E Grossmann. Global optimization of bilinear programs with a multiparametric disaggregation technique. Journal of Global Optimization, (1<4):1039-1063, 2013.
[22] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic theoretic approach to multiagent reinforcement learning. In NeurlPS, pages +19004200, 2017.
[23] Shuxin Li, Xinrun Wang, Youzhi Zhang, Wanqi Xue, Jakub Černý, and Bo An. Solving large-scale pursuit-evasion games using pre-trained strategies. In AAAI, volume 37, pages 11586-11594, 2023.
[24] Shuxin Li, Youzhi Zhang, Xinrun Wang, Wanqi Xue, and Bo An. CFR-MIX: Solving imperfect information extensive-form games with combinatorial action space. In IJCAI, pages 1663-3669, 2021.
[25] Leo Liberti. Linearity embedded in nonconvex programs. Journal of Global Optimization, 33(2):157-196, 2005.
[26] Sara Marie McCarthy, Milind Tambe, Christopher Kiekintveld, Meredith L. Gore, and Alex Killion. Preventing illegal logging: Simultaneous optimization of resource teams and tactics for security. In AAAI, pages 3880-3886, 2016.
[27] Garth P McCormick. Computability of global solutions factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical Programming, 10(1):147-175, 1976.
[28] Richard D. McKelvey, Andrew M. McLennan, and Theodore L. Turocy. Gambit: Software tools for game theory, version 16.0.1. http://www..ammbiippjjee...ooo 2014.
[29] Richard D McKelvey and Thomas Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6-38, 1995.
[30] John Nash. Non-cooperative games. Annals of Mathematics, pages 286-295, 1951.
[31] Eugene Nudelman, Jennifer Wortman, Yoav Shoham, and Kevin Leyton-Brown. Run the GAMUT: comprehensive approach to evaluating game-theoreti, algorithms. In AAMAS, volume 4, pages 180-887, 2004.
[32] Christos H Papadimitriou. On the complexity of integer programming. Journal of the ACM (JACM), 28(4):765 768, 1981.
[33] Stuart J Russell and Peter Norvig. Artificial Intelligence: Modern Approach. Malaysia; Pearson Education Limited, 2016.
[34] Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer. Mixed Mixed-integer programming methods for finding Nash equilibria. In AAAI, pages 495-501, 2005.
[35] Hanif D Sherali and Amine Alameddine. new eeformulationllneeazzaaoooon technique for bilinear programming problems. Journal of Global Optimizution, 2(4):379-410, 1992.
linearization
[36] Hanif D Sherali, Evrim Dalkiran, and Leo Liberti. Reduced RLT representations for nonconvex polynomial programming problems. Journal of Global Optimization, 52(3):447-469, 2012.
[37] Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008.
12

---

[38] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of Go without human knowledge. Nature, 550(7676):3543385 359,, 2017.
[39] Arunesh Sinha, Fei Fang. Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond a decade of success. In ICAA, pages
2018.
[40] Theodore L Turocy. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51(2):243325 263, 2005.
[41] Gerard van der Laan, AJJ Talman, and L Van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on product of unit simplices using a general labelling. Mathematics of Operations Research, 12(3):377-397, 1987.
[42] John Von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1953.
[43] Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-244 246, 1996.
[44] Bernhard Von Stengel. Rank-1 I games with exponentially many Nash equilibria. arXiv preprint
arXiv:1211.2405 2012.
[45] Bernhard von Stengel and Daphne Koller. Team- maxmin equilibria. Games and Economic Behavior, 21(1-2):309-322 1997.
[46] Wanqi Xue, bf Youzhi Zhang, Shuxin Li, Xinrun Wang, Bo An, and Chai Kiat Yeo. Solving large-scale extensive-form network security games via neural fictitious self-play. In IJCAI, pages 3713-3720 2021.
[47] Brian Zhang and Tuomas Sandholm. Small Nash equilibrium certificates in very large games. In NeurlPS, 2020.
[48] Brian Zhang and Tuomas Sandholm. Sparsified linear programming for zero-sum equilibrium finding. In ICML, pages 11266-11267 2020.
[49] 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 celumn-generation
Fixed-parameter EC, pages 1119-1120. 2022.
[50] Youzhi Zhang and Bo An. Computing team-maxmin equilibria in zero-sum multiplayer extensive-form games. In AAAI, pages 2318-2325, 2020.
[51] Youzhi Zhang and Bo An. Converging team-maxmin equilibria in zero-sum multiplayer games. In ICML, pages 11033-11043, 2020.
[52] Youzhi Zhang, Bo An, and Jakub Cerny. Computing ante coordinated team maxmin equilibria in zero-sum multiplayer extensive-fome games. In AAAI, volume 35, pages 5813-5821, 2021.
[53] Youzhi Zhang, Bo An, and V.S. Subrahmanian. Correlation-based algorithm for team-maxmin equilibrium in multiplayer extensive-form games. In IJCAI, pages 606-612, 2022.
[54] Youzhi Zhang, Bo An, Long Tran- ThanT,han,, Zhen Wang, Jiarui Gan, and Nicholas R Jennings. Optimal escape interdiction on transportation networks. In IJCAI, pages 3936-3944, 2017.
[55] Youzhi Zhang, Qingyu Guo, Bo An, Long Tran-Thame Thanh, and Nicholas R Jennings. Optimal interdiction of urban criminals with the aid real-time information. In AAAI, volume 33, pages 1262-1269, 2019.
[56] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini- mization in games with incomplete information. In NeurlPS, pages 1729-17366 2008
13

---

Appendix
A Illustration of CRM
In four-player games,
N = ((1,2,3), (1, (1,44)))),, (2.3.4), (2,)) (3.4),
By Algorithm 1 in CRM, we have:
N = (11,2,3), (4,2.3), (1,43,),11,2,444 (1, (1.2), (1,4))
ie.,
-1, 2. -1,22,33,,11 (2,4), To obtain this set, we first have a full binary
NT 4. we replace 1 with 4 to obtain Nr = [14, (4,2)); Then, for each element in 2 with 4 to obtain N (1,4,3), [1,4]]; and replace with obtain NT = -(1,2, (1, Then N NT U Nr. UWT UNT
tree T_4 with the set of internal nodes NT_, = (f1,2,3){1112)) (1,2)}-
In three-player games, Algorithm 1 cannot reduce the number internal nodes because each element in (-i (1,2,3) includes only players. Then .N A {(1,2), (1,3), 3)) which means that N and N will result in the same of bilinear terms in three-player games.
To be simplified, we show how to formulate the program according to Algorithm 2 (i.e., CRM) in a three-player game G = (N, A, u) with N = (1, 2, 3). A, = {az, af) first. In three-player games, -1 (2,3), and N = {-1, -2, -3 = ((2,3), (1,3)
(1,2])
Note that A- 2 = A2 x As {a2, 03), (a2, dz), (a as), (ag, a44) with N' = -1 = {2. (2, {2), NY (3). We show the constraints related player here: We first show player I's constraints in the Nash equilibria space based on Eqs.(1b-11
x (ai) + xi (a1) = (based on Eqs. 1b
1- bmj 2 x (ai), 1 - bug 2 æ1 (af) (based on (cc)
x-- 11 (x) 2 un (a1, (-,, un (x) - un (01, Dog (Umaz Umia) (based on Eqs. (ds and (Ie)
"1 (x) 2 un (d) 111,, un (x)
(a', x-1) bo; (Umaz Umin) (based on Eqs. 1dd and (Ie)
The above constraints include player I's expected utility variables uy (1(11, x-1) and in (af x-1). which are represented by the following constraints based on Eq 4p:
ii x-) = in (a), a2, (2)) + w (a), 02 ag)) x (a2, m/))
+ ui (a), (01,0 + w (a), 222 a1) ) (a dg) (based on Eq.(4)
U1 u1(d),0-1) = un
(a 02 0/3 x - (22 a's)
+ mi (d).
(a/ a/2, a1) ) (a/, a's) (based on Eq.(4)
where the correlation plan _- of over 4 based Eq. 2 is defined by:
x- 1 (a2, d3) + 1 4/4 + -
+ + 0/) = 1 (the plan of -1 based on Eq.
In the above correlation plan 1- x-1 0z). -ー 20, 04), x (agy az). x (a aa)) represent the following four bilinear terms (constraints):
x- ( da) = 22(a2)ra(a3) (the bilinear constraint based on Eq. with a_1 (a2, 03) (aN7. aN; ). aN. (a2), aN; (a3)
x_1 ab)) = (22))=3)(()) (ab) (the bilinear constraint based on Fq. with
a- (a2, a/g) (aN7, aN; ). ANz
(22),a;; = (ag)
x x-1(ab, = 2z 22 ) (ay) (the bilinear constraint based on Eq. with
a = (azz 03) (ax; aN: ONς = (al), aN; = (as)
x_1(6b,dg) = 22(a6) (the bilinear constraint based on Eq. (3)) with
a- = (dz, o/g) = (aN;, aN.) ON; = (ab), aN; = (db);
14

---

where, based on the binary division in N,, any joint action av E AN can be divided into two sub-joint actions aN; E AN; and ax; E AN; such that a, = xa, ax;).. Note that 22 and zg are special correlation plans with that 2 is set to be equivalent to {2} and 3 is set to be equivalent to {3) for simplification. Correlation plans x-1 1 and z2 (or 2z)) have the following relation:
x-1 x=1(02, 03) + x- x=1(a2, dgz = x2((2) (the relation of correlation plans x= and 22 based on Eq.11]
VaN' E {(02. a3), (a2, o5)) - a. (2) d2. i.e. 02 player 2's action in oN
x-1 x-1 03) + x- +x_ (dly d'y) x2(dg) (the relation of correlation plans x-1 and at based on Eq.
VaN {(o2, 0z), (a2, 04)) C _ (2) a22. i.e, ag is player 2's action in ON
x-1 (02, 03) + x- (d 03) 13 (a3) (the relation of correlation plans . and zy based on Eq. VaN' E { az). (02, as)) C ax (3) 03. i.e., 03 is player 3's action in ON
x-1 d2y) + + db4) I3 (3(44) (the relation of correlation plans x_ and z3 based on Eq. VaN' E {(02, dg), (a2, d5)) C ax (3) = a'z. i.e., d' is player 3's action in ON
Constraints related to other players are created similarly. As shown in Algorithm 2 (i.e., CRM), after creating all of these constraints in the bilinear program for the Nash equilibria space, we can solve the program to optimize an objective function by using global optimization solver, e.g., Gurobi.
In three-player games, x-1(a-1) 1) just represents a bilinear term, and then a chain of bilinear con- straints (equalities) to transform multilinear term into bilinear terms is not explicit. In four four-player games, a chain of bilinear constraints (equalities) to transform a multilinear term into bilinear terms more explicit. For example, in a game G = (N, A, u) with N {1, 3, 4), A, {a,, " and (- -1 1, 22 - 3, (1. 2), (2, 4) (1, 4) based on (a). we have:
x-1( 0z 04) 22,2 a. (23 22,4 (02, a4) 22 (22) a (aa) chain of bilinear constraints),
where N = -1 = (2, = (2. 4) and N = {3} based on A. That is, a-1 = (ag. ag a1) = (ax;, with aN; (az, 04); AN; (aa) (i.e., joint action a-1 is divided into two sub-joint actions aN; and aN: such that a-1 = (ax; ax:)) based on N, and then we can have the above chain of bilinear constraints for it. Each joint action in A-1 A2 Ag x A AN X AN ((a2, 03, (a).(a2, 03 o4), (a2, az. (4),(a2. d2. (a) 03 (a) 03, d dzg a4). (a), dg. d is divided into two disjoint sets similarly, and then we can have a chain of bilinear constraints for it.
In three-player games, each element in {-i i E {1,2,3]} includes only two players, and then the resulting program does not include the constraints for the relation of correlation plans based on 12). To show the constraints based on Eq. we consider four-player games. The following constraints are player I's constraints based on Eq. 12) for solving a game G = (N, A, u) with N 2,, 4). A, = {a,, d.}:
x-1 03, a1) - 1 d'y 01) = 12 01) (based on Eq. 12 with aN; = (a2, as),
VaN' E ((22, 0z, at), ) (a2, a'g, at)} C an,,av(( = (a2, az),
i.e., (a2, a4) is N/'s sub-joint action in ax""
F. 1-1((a (az, 0z, d/) + x (a2 dg. a4) = ==2, (22, o4) (based on Eq. 12) with axy = (az, d'i);
VaN' E {(02, 0z d'y), (az, n'g, a'3) S aN,, (a2, d').
i.e., (a2, a1) is N/'s jub-joint action in ax"
F. x-1 1 0z, a2) - x Mag dg. 04) = =I= ( 04) (based on Eq. 12) with aNy = (agz as);
VaN' E ((ag, as au), (d2. agg, a4)} C A-1,aN((N)) (a2, aa),
i.e,, (a2, a4) is N sub-joint action in ax
I- I-1 az, d') - -------dd (l2y dg. a4)) =I2 a4) (based on Eq. 12 with aNy = (dg, o'),
VaN' E {(ab, 0z d'y), (dg, ang, a4)} S. (N)) (ah, d')..
iee, (a2. )4) is N/'s sub-joint action in aN'
where N' = -- (2.3, 4) N/- (2,4) and N (3} based on N. The we can divide the joint actions in A_1, e.g., a_ = (az, 4z. a.) (ax7, ) with axy = (az, da), an. = (az). For elements in (NV, we only consider constraints based on Eq. 12) for N because |N/| = 2 > 1
15

---

and N = 1. We could use Eq. to generate constraints for Nº {3} for the relation between F-1 and I3, e.g., for ag E A3,
x-2 43, a4) + x-1 43, aa) + x=1(az, 43, d44 + z 1 d4) = rz((s)) where, for each aN {(a2, 03, aa), (42 03, a4); (a2, 03, d44, (d2. 03 d4)) C A-1, 03. i.e. 0g is player 3's action in aN
Other constraints for four-player games are created similarly the above creation of constraints for three-player games.
B
Proofs
Theorem 1. The feasible solution space of mixed strategies (i.e., x;(0s) for each i E N, as E A,) in
Eqs. Ib 1g 3). and (4) is the space of NEs.
Proof. [ describing the space of NEs and Eqs. 1b
and (4) both include Eqs. g
which describe the condition of NEs. Then we only need to show that Eq. is equivalent Eqq lap. That is, we need to show I
(a-());) for each i E N and a-; E A-j. To
achieve this result, we show II Je Zy (ax=
zN (ax²) for each N' V and av E Axv. We show that this statement holds by induction. For any N' E A with |N' = we obviously have IiE Iy (j))
(ax') ) for each aN E AN by Eq. 3). Suppose, for any N' E V with [N'] = k 2 2, the statement holds. Now for any N' E N with N' k + 1 and its two children Nj and NW. we have: for any aN E AN'.
N (ax') (ON
II m:(ax; (i)) II zy(an;(i)
AENY
JEN;
II (a)x
JEN
where the second "=" is based on the assumption that, for any N' E N with [N'| k 2, the statement holds. Then I[ 2z (ax (j) = ZN (ax) for each N' e N and ax E Ay. Therefore, the theorem holds.
Theorem 2. Mc R, i.e,, i is strictly smaller than R but still includes M.
Proof. (i) We first show that T c R. Given any ((i,)(aa,, aj) = x,(a;)x((a))) in T, we have T(a2) (a);a) I min(x;(a;;) 22 (a:)) according [1). Suppose x=(a:) + 2,(a,) 1 >
T(i. (a, az). According to Eqs. 11 and (Tb), have the Tollowing contradiction:
(a:)
Σ (((s)(a;aa)) dyEA,
< (as)) + +zz((;)) -1 -
Σ af
S <x,(as) - -1 + Σ وz(0;)
a,EA,
(a,))
where the first "=" is according Eq. "<" is according the assumption, "<" according to Eq. [T]. and the last "=" is according to Eq. Ibp. This contradiction implics that xa,)))= max (a, + (a,)) - 1} S I(is)) (a;, az). Similarly, for any av (aN+) = .NN (aN; NY (ax;) with two children NY and N of N', in T, we have:
Iz(a,) - Z((,)) (a;, az), ie., i..,
max(#N; <axi((N-))
(aN;)) 1, 0}
minfaNy (aN;))) LN (aN:))
16

---

Therefore, T R.
Given any x(s.)} (2) xn (22(2)))))))))))))()))) and (iss 0z) in (d))))((a2) by Eq. we can have a feasible solution such that:
[i,)((n, 02) (an)
m[os](a 02) (a) x2
Then (i.j) 02) + (1.5) 02) > x2((2) when < x2( min(z((a), < 1. However, in T,
((35) a2) + (a.)) 02) - (2))
Then R $ T. Therefore, T C R. i... is strictly smaller than R.
(ii) Now we show that M T. In M. for each aN E AN' N' E A with two children Nú and N of N there is a bilinear constraint z (axv) zN; (aN; Nz (ax;) based on ax (aNy aN;).
where IN (ax)) Iz (a,) for N' {i}. We first show M C for Eq. by induction. For any N = (i,5) E N, by M, we have:
Σ
((,))(a,)))=
E x((as) Σ agEd,
2z(a,)
(o.,,))EA(Rs)
a,E,;
Suppose, for any N' with
with |N' = k and &s 2 2,
Σ
(ax)) =
Exyr
Now for any N' W with [N' l 1, with two children N/ and NÝ of N by M and the assumption of Ng, we have:
(N((a
Σ
INz(aN;)
Σ
(aNt))
EAN
ExTEAN
aNy EANy
Therefore, ( is implied by M. Similarly, for each NO C N, we have Eaw (xx(a)) 1.
For any N' = (i,j) NN by M, we have: for any E Ai,
Σ A,EA,
(a;, = x;;a;) Σ ==(a,)==((11) a,EA,
and for any aj Aj. (p.) (a; a,) = 2z((az) Ener, I;(a;) = 2z(a;). For any N' e En
with IN' > 2, by M, we have: for any E N', and a; Ai, with N₂ N' (i).
Σ
(aN) (:((s)
Σ (aNa)
axy ExyEr axy (f==;
aN2 ENNz
= =xi(ai)-
Therefore, Eq. is implied by M.
Now for any N' E N, with two children Nj and Nº of N', by M, for each aN; E ANy, we have:
Σ
(aN))
ag (2)
= = any EAN;
Σ
NNy (aN:)
=xN((aN));
17

---

where the condition ax = (axy, Ax represents that aw E ENv. (N(( =x,, For each aNe E ANy we have:
Σ
(aN(aN))
oN' (
= =xN((ax;) aNEEN
E
INZ(aN;)
=IN((aN;).
Therefore, Iq. is implied by M. Then M CT.
Given any four bilinear terms:
(112)((1,00 02) = x ((1)(2(((2)
(1,2)((1,02) (1()(22((2))
(1,2)((1,06) =1(())(2(a)) ((12)(((1,5)) =r
The following solution is in T:
F(1.2) 02) = 0
"(1,2](0],0) 02) = 2/3
"(1,2](01,5) d2) = 1/3
"(1.2](0(, =0
21 = 1/3, 21 = 2/3
x2(22) = 2/3, 22 (22)))1133 =1/3.
However, the above solution not in .M because: x (a1) = 1/3 and x2 = 2/3 imply that
T(22) (2) 2/9, which contradicts 2(1.2) (01, a2) T g M. That is, MC
the above solution. Therefore.
Theorem 3. The optimal solution of Program
13 maximizes g(x) over the space of NEs.
Proof. By Theorem T includes M, i.e. T does not reduce the space of NEs. Program 13 is obtained after we explicitly restrict the feasible solution space by adding Eqs. 2.. and 12) to Program (5). The optimization solver will search this feasible solution space after the relaxation to find the optimal solution for the original bilinear program. Therefore, by solving Program (13). we obtain an optimal NE.
Theorem 4. N generated by Algorithm 1 is binary collection, and O(n n) for the size of N is the minimum size of all binary collections of a game G.
Proof. First, is clear that N generated by Algorithm a binary collection G. Then {-é N) N.
The number of internal nodes in each binary tree with n leaves of - for each E N is n 20 To obtain the minimum number of internal nodes in these binary trees for { (-i i E N). we can minimize the difference between binary trees. Given binary tree T_, for -n and a binary tree T-; for -i with i E -n, the difference between T-,, and T-; least includes the path from the root to the node {i} in T_,,, and the path from the root to the node [n) in T-,. Then the number of different internal nodes (i.e., nodes that are not in T-,)) in these binary trees for {-i E N is at least equal to the total path length in T-n- Algorithm ensures that the number of different internal nodes in these binary trees for {-i i E N} is equal to the total path length in T_ and the total 1)1. Given a binary tree with l: 1
path length in T-,, by Algorithm is at most (n - 1) [og, internal nodes, the minimum total path length is O log k) 200 Therefore, (n log n) for the size of N is the minimum size of all binary collections of G.
18

---

Algorithm 3 Generate N: full details of Algorithm
1: Build(-n)
2: for each i (1...., 1] do
3: -i: replace with n. in -n
4: N'
5:
A Nu {-i}
6:
while [N' > 2 do
7:
(N1, N2) Ch(N))) with i N1
8:
N replace with n in N : replace i with in N1
9:
10:
Ch(N") < N2)
11:
if |N| > 1 then
12:
N < NO (N)
13: end if
14: N' + N1
end while
16:
end for
C The Necessity of Eq. (3a) in Program (13)
B We denote Program T the resulting program after removing (3) in Program (13). We use the optimization gap between the optimal objective value 9 in Program 13) and the objective value g obtained from the players' strategies after solving Program T (i.e., iS the real objective value after playing the strategies obtained from solving Program T) to measure the inefficiency of Program T, i.e., g" g. Note that, by Theorem 2 the optimal objective value of Program T is just an upper bound of the optimal objective value of Program (3). which may not be achieved by playing the strategies obtained from solving Program
Now show the necessity of (q.(3a) in Program
T. The following theorem shows that g can be arbitrarily large, i.e., Program T is not suitable to be used for computing optimal NEs. In addition, the resulting strategy profile by solving Program T may not be an [
Theorem 5. g" can be arbitrarily large, and the resulting strategy profile x' by solving Program T may not be an NE.
Proof. Consider game with three players, A₁ {ai, a A2 {az, ab) and As {as, a/g ag) and the following utility function for three players, respectively, with k 2 1:
(u1, 12, Ug) (a1, 02 a3)) (0.5k, 0.5k, k);
(u1, U2 ug):
(a a22 a3))
(0.5k, 0.5k, -k);
u (u1, 122 Ug):
(21,022 03) + (0.125k: 0.125kk - -0.25k);
u (u1, 02, Ua): (a1, 022 a4)) (0.125k: 0.125k, - 0.25k));
u (u1, u3) (a1, d2y a²) - (0.1k, 0.15k, -0.25k);
u (11. U2 Ug) otheer joint actions > (0,0.0).
The objective function is g = Uj (I) 22, x3) + (z, By solving Program T, we obtain 1/3, x'y with (a2) 1/3 and xa(a4) 2/3, and z with x'g (aa) = 1/2 = (((()) and 2y (aa) = O. If players and 2 play oi and zzy. respectively, us(21, 2/2, 03) k/3 us(a1 L/z dg), and us (=1,1222 ag) k/9. That is, player 3 will play the pure strategy a" to respond to 2 and 2z which will result in g = k/9. Then the resulting strategy profile x' is not an NE,
oi with 2 (a1) 2/3 and 2 (a
'To find an optimal NE, this paper only considers programs guaranteeing exact NEs, and designing programs with approximate NEs is the future work.
19

---

It is clear that (zf 22 2z) with =,
- and z; (33) = is an NE, which also is an output of solving Program (33 with the objective value g" = k/4.
Therefore, 9" 5k/36, which is arbitrarily large when is arbitrarily large.
Algorithm 4 (N') Build minimum-height binary for N'
1: h + [lo
2: if 2 N then
3: Lower set N < {{i} i N
4: for k (1..... ( do
5:
Upper set N2 0
6:
for j E (1, "II...,,M.. 1/2)
7:
N1 < N x 2 - UNN x 2/: the union of the (j x 2 1)-th element and the (jx 2) element N
8:
22 t Ch(NN) + (N' 11 x NI, 2|} end for
9:
10:
set, No NN22 12: N "Y-UUND
11: Lower set
13:
end for
14:
else
15:
NY [N [N
N222h-1}}
16:
NO N' N
17:
3 2h <= N then
18:
Lower set N t {(A) E N
19:
for l E {1, {1...., [log([>[D)]} do
20:
Repeat Lines 5-12.
21:
end for Build( N3)
22:
23:
N. MU (N')
24:
Ch(N) -
else
26:
Lower set set 1 + {ii} | N
for ls E {1,..., [oo 1) do
28:
Repeat Lines 5-12. end for (uild
30:
31:
N1 + N" U
32:
A < K-NU N
Ch(NG) + (W" 22, N3
34:
A- (N'
35:
Ch(N') (N" [1)
36:
end if
37:
end if
D Binary Trees and Details of Algorithm 1
We consider special binary tree (full binary tree), which includes two kinds of nodes: nodes with two children (internal nodes) and nodes without children (leaf nodes). A binary tree Tyx of N' C N with [N' > is that: 1) its root is N'; 2) its nodes are {N" N" C N'); 3) each of its leaf nodes is a singleton; and 4) each of its internal nodes N has two children No and N with N n N" = and N N U N" i.e., N is divided into two disjoint sets. Let Ch(N") (N", N be the set of A children Tw,, and Ch(N") = if N a singleton. Let No be the set internal nodes in Ty.
Our binary tree for -i full binary tree, i.e., each internal node has two children, which has internal nodes if there are & Ieaf nodes (20). For example, Figure I has internal nodes and 4 leaf
20

---

nodes. The length of the path from the root to leaf is the number of internal nodes on this path in binary tree. The height of binary tree the maximum path length, and the total path length the sum of the lengths of the paths from the root to each leaf node in a binary tree. For example, the path length from the root to each leaf node in Figure Ta) 2, the height is 2, and the total path length is 2 x 4 8.
To obtain the minimum number of internal nodes in these binary trees for {-i I i E N). we can minimize the difference between binary trees. Given the binary tree T'nn for -n and the binary tree T-; for -i with i E -n, the difference between T-n and T-; at least includes the path from the root to the leaf node {i} in T-n and the path from the root to the leaf node {n} in T- Then the number of different internal nodes (i.e., internal nodes that are not in T-,)) in these binary trees for {-ili i E N} is at least equal to the total path length in T-,,. Now we propose an algorithm ensuring that the number of different internal nodes in these binary trees for {-i E N) is equal to the total path length in T-n. which is the minimum total path length. To do that, we first build a binary tree for -n with the minimum height (a full binary tree with the minimum height may not be balanced). Note that there are at most 2 leaf nodes in binary tree with the height h, and there are n 1 leaf nodes and n - 2 internal nodes in a binary tree for -n. Then we can build a full binary tree T-n with the height [log, (n 1)] for -n and then replace i with in the nodes of T-n to obtain T-, for each i E -n = (1...., n 13. That creates 72 full binary trees for { E N). This procedure is shown in Algorithm 1, generating our minimum binary collection A.. Figure T a) builds binary tree T-s. and Figure a obtains T-3 by replacing 3 with 5 in T-5-
The full details of Algorithm 1 are shown in Algorithm 3 Line 1 builds a binary tree with the height [log,(1 - 1)] for -n = f n - 1). whose details are shown in Algorithm 4 At Lines 2-16, for each in (1.... n }}. we search the binary tree for -n from the root and replace i with in each node including i to form a new tree for -i. And we only need to add new internal nodes to N.
Algorithm builds a binary tree with the height [log2 ((VV'))] for N'. If the size of N' is (logg(NN')) (note that each element in N' corresponds tree with the height h), then we can build a complete binary tree, where all leaf nodes are at the lowest level. That is, combine two nodes the lower level to form node the upper level, as shown at
leaf node, and there are most 2 leaf nodes in binary
Lines 3-12. If the size of N' is not 2 [ogg2 and is larger than 3 2 [ogg2(AV D1-2 then build a complete binary tree for the subset N (Line 15) with the height [log2(1A)) ([D [[ogg ((NV')) 1 (Lines 18-20) and then build a binary tree for the remaining subset (Line 22). Finally, we combine both binary trees together to form a binary tree for N' (Line 24). If the size of N' is not [1o'1( we build a complete binary tree for the subset Ní (Line 28) 1. However, at the last step of building the binary tree for Ni. we do not combine two nodes to form a root. We keep both two nodes within Nj by setting k S (N)) - = [lgg(/\'))] - 2 at Line 26. Then we build a binary tree for the remaining subset N (Line 30). After that, we combine the root of the binary tree for N2 and two nodes in A to form binary tree for N' (Line 31-35). This step is to try to reduce the total path length because the number of nodes in the binary tree for N₂ is less than the number of nodes of the binary tree for any node in NY. and we can reduce the total path length by combining the root of the binary tree for N2 and any node in N to form a node first.
and it is less than 3 x (I with the height [1 = [log (1 (IN'))
E Runtime for Algorithm 1
Table shows the runtime of Algorithm 1, which is extremely small and then can be ignored, compared to the runtime of CRM shown in Tables and
F Experiment Setting
Games:
we evaluate our approach on two sets of games: randomly generated games and games that are generated by GAMUT BI) Payoffs are generated from the interval between 0 and 100 (other ranges (e.g., [0, 1D do not affect the result). We vary the number of players (i.e., n) and the number of actions (i.e., m) for each player for random games (i.e., (n. m)). For GAMUT games, we use the variants with six players and three actions (i.e., the game 3). which are much larger than the
three-player three-action games (i.e., the game (3, 3)) used prior work 4 13. We show the game
size in terms of the number of bilinear terms and integer variables in Appendix G e.g., the number of
21

---

Table 3: Game size and runtime of Algorithm 1.
Integer variables
Bilinear terms
Correlation Plans
Algorithm
nn. m)
Size
Based on N
Based on N
[
[
Runtime
6
12
12
3
<0.0001s
(5, 2)
10
200
104
25
11
0.0001s
(7, 2)
14
2044
564
119
21
0.0002s
(3, 3)
9
27
27
3
3
<0.0001s
(4.3)
12
162
135
<0.0001s
(5
15
765
459
25
11
0.0001s
(4, 2)
8
56
44
10
7
<0.0001s
(4,3)
12
162
135
10
7
<0.0001s
(4, 4)
16
352
304
10
7
<0.0001s
(4,
20
650
575
10
<0.0001s
(3
15
75
75
3
3
<0.0001s
(3.8)
24
24
24
3
~0.0001s
(3, 10)
30
300
300
3
3
<0.0001s
(3, 13)
39
507
507
3
<0.0001s
(3, 15)
45
675
675
3
<0.0001s
(3. 17)
51
867
867
3
3
<0.0001s
(6, 3)
18
3348
T620
56
16
0000015
(8, 2)
16
6288
1172
246
26
0.0003s
(9, 2)
18
19152
2512
501
31
0.00033"
Table 4: Results for random games: (n. represents the game with players and m [A.] actions for each player. The format for each result is: Average Runtime 95% Confidence Interval (Percentage of Games Solved within the Time Limit) (Utility Gap). Note that unit games have been solved with the time limit should be (0%) and is omitted, we only need to care about the utility for EXCLUSION, and the utility gap represents EXCLUSION cannot return solution within the time limit. For example, for the random games (7, 2). CRM solves 100% of them by using 25s with 95% interval solved by EXCLUSION within the time limit, and EXCLUSION has utility gap
runtime second, and the case that all
17s, but 80% of them 53%.
Runtime = 93% Confidence Interval (Percentage of Games not Solved) (Uillity Gap)
Vary
(n, m)
CRM
MIBP
ENUMPOLY
EXCLUSION
(3, 2)
0.01 +
+
0.03 0.01
+ 41 (gap:15%%
T
(5, 2)
0.2 0.1
0,5 + 0.4
11 +
753 + 148 (73%) (gap:64%)
(7,2)
25 +7
429 + 131 (20%)
1000 (97%)
835 + 119 (80%) (gap:53%)
(3.3)
00.1 10
0.1 10-
-59
252 Σ [40 (20% (gap:345)
(4,
0.3 0.1
+.3
1000 (100%)
773 + 125 (67%) (gap:58%)
(5.
19
239
1 (7%)
1000 (100%)
1 (97%) (gap:62%)
(4.2)
0.1 1 0.01
0.1
1.00
0.2 1.1
246 1 126 (13%) (gap:235)
(4.3)
0.3 101
1
103
1000 1 (100%)
773 1 125 (67%) (gap:58
(4, 4)
2.8 +1
42
- 12
1000 = (100%)
1000 = (100%) (gap:73%)
5)
64
1 42
862
91 (77%)
1 (100%)
1000 1 (100%) (5%p:75%)
(3,5)
0,2
1 0.03
FO.1
1000 = O (100%) (gap:67%)
m
(3, 8)
4
13
247
+ 140 (17%)
1000 + (100%)
1000 + (100%) (gap:oo)
(3, 10)
9
19
334
+ 167 (30%)
1000 + (100%)
1000 = O (100%) (gap:0o)
(3, 13)
38
+
21
342 + 151 (27%)
1000 + (100%)
1000 + O (100%) (gap:oo)
bilinear terms in the game (9, 2) is 19152 based on N but 2512 based on N. For each setting, we generated 30 games MacBook Pro, where the seeds are i E {l..... 30) for the GAMUT games and 20201125 + 10 for random games. Results in this section are hence averaged over 30 cases.
Algorithm Setting: The objective function used in the experiments maximizes the expected utility of player n. We verified that results for optimizing other objectives (e.g., maximizing social welfare) are similar. We use the non-convex solver of Gurobi 9.5 to solve all mixed-integer bilinear programs with optimality gap set to 0.0001 (the default setting). EXCLUSION uses this optimality gap as well, which is significantly smaller than 0.001 in 4 (we verified that, with the same optimality gap, our result for EXCLUSION is almost the same as the one in 4)). Experiments are run on an eight-core Intel Core 19 machine at 2.3 GHz with 16GB of RAM. Similarly to the previous literature 34 4 13.
22

---

Table 5: Results for six-player three-action GAMUT games.
Runtime
95% Confidence Interval (Percentage of Games not Solved) (Utlitt Gap)
Game
CRM
MIBP
ENUMPOLY
EXCLUSION
Bidirectional LEG
1.6 + 1
972 + 54 (97%)
1000 = (100%)
1000 = 0 (100%) (gap: 133%)
Collaboration
i 0.2
967 63 (97%)
1000 0 (100%)
1000 = 0 (100%) (gap:81%)
Covariant r 0.5
6
1000 = 0 (100%)
1000 (100%)
963 = 59 (93%) (gap:73%)
PolyMatrix
194 + 74 (3%)
867 116 (87%)
1000 + (100%) (gap:17%%
Random LEG
2 + 1
1000 + (100%)
1000 = 0 (100%)
986 + 27 (97%) (gap: (19):
Random graphical
0.1
+: 0.1
803 + 140(83%)
50
30
971
+ 55 (97%) (gap:32%)
Uniform LEG
2.2 + 1
1000 + (100%)
1000 O (100)
986 + 26 (97%) (gap: 16)
Table 6: Ablation study, No time limit for CRM, CR, and CM in games (8, 2). We can see that each component of our approach significantly bonsts its performance. Note that N (in CR, C, and MIBP) and W (in CRM, CM, and M) result in the same bilinear terms in three-player games hecause each element in {-i includes only two elements such that Algorithm 1 cannot reduce the number of internal nodes reduce the number of bilinear terms, where CR CRM (or and CM, or MIBP and M) have same performance. For one case in the game (9, 2). which CRM and CM cannot solve within 1000s, after removing the time limit for it, CRM solves it by using 1188, but CM solves it by using 12751s. The unit of the runtime is second.
{1, 2,3
Runtine + 95% Confidence Interval (Pereentage of Games not Solved)
Game
19, 2)
658 128 (50%)
988
1. (974)
782 (63%)
10001 0 (0123)
1000 1 (110%%
1000 1 (1100)))
2)
166::
278
(60%)
(100%)
1000
(7, 2)
25 = 17
89 +151
36 28
408 + 157 (30%)
488 = 111 (10%)
429
+ 131 (20%)
15)
167: 86 (3%)
167
+: 86 (3%)
317H 137 (17%)
317
+ 137 (17%)
558
150 (40%)
558
155 (40%)
(3. 17)
231=122 (10%)
231 +:22 (10%)
3262 134 (20%)
326
+ 134 (20%)
784
102 (53%)
784
(53%)
Bidirectional LEG
1.6 =
5.4
14
2.2 2
86
1:3
991 = 18 (97%)
972
1 54 (97%)
Collaboration
0.2
2
0.2
0.4
(87%)
(97%)
Covariant y = 0.5
5 6
12 + 10
5 +
18
+
1000 D (100%)
1000 (100%)
PolyMatrix
26 44
25
36 = (3%)
17
+1
267 97 (10%)
194 74 (3R)
Random
6
25+2
+5
1000 (100%)
1000 (100%)
Random graphical
0.1 = 0.1
0.4 1.01
0.1
0.6
1.4
814 134(80%)
803 140(83%)
Uniform LEG
2
5
25
#5
999 (97%)
1000 (100%)
to efficiently evaluate the algorithms, we set time limit of 1000 seconds for each case unless stated otherwise.
Metric: We use the runtime and the percentage of games that are not solved within the time limit to measure the performance of our approach. In addition to the average runtime, we show a 95% confidence interval. CRM and MIBP guarantee finding an optimal NE. For algorithms that can enumerate all NEs, can choose an optimal NE from the output for all NEs. We then compare ENUMPOLY to our approach only in the runtime. For algorithms that only guarantee to converge to an NE, we may need use them enumerate all NEs. However, it is unclear whether algorithms like EXCLUSION can enumerate all NEs. Therefore, we compare EXCLUSION to our approach in the runtime and the utility gap. The utility gap is the relative distance between the optimal objective value (g") ) in our problem (returned by CRM) and the objective value (go) in the Nash equilibrium returned by EXCLUSION, i.e., و goll / 100%. In some cases, solution returned even if it has not reached the given accuracy within the time limit, which is still used as solution of EXCLUSION. larger gap means that we will lose more while using EXCLUSION.
G Game Size
Table T shows the number of integer variables, bilinear terms, and correlation plans for the games we used experiments. Note that the used GAMUT games have six players and three actions. Also, note that we do not reduce the number of bilinear terms and correlation plans games with only three players.
H Details of Experimental Results
The details of experimental results are Tables and
Specially, CR is solving Program (33) based on NV, and CRM is solving Program 13 based on A. We discussed the difference between. N and M in Section 3.3. Basically, N and N are the same in
23

---

Table 7: Results on more Gambit algorithms for random games. The format for each result is: Average Runtime 95% Confidence Interval (Percentage of Games Solved within the Time Limit). Note that, these Gambit algorithmms only achieve some NE the game solved, which may not be optimal. Even so, these algorithms fail to solve many games, and even run significantly slower than our CRM (see T in many games.
Runtime + 95% Confidence Interval (Percentage of Games not Solved)
12, m
GNM
TPA
LIAP
SIMPDIV
LOGIT
(3. 2)
0.03 = 0.02
567 = 177 (57%)
0.06 = 0.02 (77%)
0.07 = 0.06
0.04 = 0.02 (100%)
(5
0.04 0.01 (3%)
867 = 122 (87%)
0.45 0.04 (100%)
1000 + 0 (100%)
0.02 = 0 (100%)
(7,
333 169 (53%)
400 (37%)
+ 0.4 (1005)
79.4 + 78.6
0.05 0.05 (100%)
3)
0.03 (33%)
933 89 (93%)
0.16 2 (100%)
300 E Т63 (30%)
00.04 20.02 (100%)
(4.3)
0.11 (3%)
500
179 (50%)
0.76 1 0.08 (100%)
500 1 179 (50%)
0.02 1 0 (100%)
(5.3)
0.15 0.03 (30%)
773
158 (73%)
6.3 + 0.3 (100%)
900
+ 107 (90%)
0.02 = 0.01 (100%) )
(4.2)
0.03 0.01 (3%)
667
= 169 (63%)
0.13 I 0.02 (97%)
733
E 158 (73%)
0.02 :: O (TOD%E)
(4.3)
0.11 (3%)
500 1 179 (50%)
0.76 1 0.08 (100%)
500
1 179 (50%)
0.02 1 0 (100%)
(4, 4)
800 + 143 (80%)
367 172 (33%)
4.9 + 0.4 (100%)
867
+ 121 (87%)
0.07 + 0.07 (100%)
(4,5)
0.33 + 0.07 (37%)
833
(83%)
16
(100%)
900
+ 107 (90%)
0.04 0.03 (100%)
(3.5)
600 1175 (63%)
767 = 15I (77%)
133 0.1 (100%)
933 4 (9(93%)
0.00 = 0.09 (100%)
(3.8)
0.76 + 0.26 (17%)
506 177 (50%)
11
+ 0.7 (100%)
867 + 122 (87%)
0.02 = 0 (100%)
(3, 10)
334 + 168 (53%)
767 + 153 (77%)
37 +3 (100%)
867 + 121 (87%)
0.02 + O (100%)
(3. 13)
3.8 + 1.1 (47%)
1000 = 0 (100%)
132 # 11 (100%)
805
+ 140 (80%)
0.03 = 0 (100%)
Table 8: Results on more Gambit algorithms for six- six-player three-action GAMUT games. The format for each
result is: Average Runtime = 95% Confidence Interval (Percentage of Games not Solved within the Time Limit). Note that, these Gambit algorithms only achieve some NE if the game is solved, which may not be optimal. Even so, these algorithms fail solve many games, and even run significantly slower than our CRM (see Table
5 in many games.
Runtime 1 95% Confidence Interval (Porcentage of Games not Solved)
Game
GNM
IPA
LIAP
SIMPDIV
LOGIT
Hidirectional LBG
167 4 (63%)
8 0.6 (100%)
667
169 (67%)
0.03 (100%)
Collaborstion
34
+ 64 (3%)
0.03 =
24 : 2 (100%)
0.03 + 0
0.03 : 0 (100%)
Covariant = 0.5
100 + 107 (17%)
0.04 00
21
+ 2 (100%)
367 + 172 (37%)
0.04 + 0.03 (100%)
PolyMatrix
0.13 +:
(7%)
8.3 8
9 + 0.8 (100%)
24
+ 0.05 (100%)
Random LEG
0.19 + 0.04 (47%)
0.04 + 0
7.5 : 0.6 (100%)
777 + 146 (77%)
0.03 : 0 (100%)
Random graphical
0.05 : 0 (3%)
1000 : 0 (100%)
9 1 1 (100%)
0.05 + 0.03
0.04 + 0.02 (100%)
Uniform LEG
0.16 -: 0.04 (47%)
0.04 +
7.3 + 0.6 (100%)
776
146 (77%)
0.02 :: (100%)
3-player games, so CR and CRM have the same performance in 3-player games shown in Table 6 When the number of players increases, the size of N is larger and larger than N, and then CRM's advantage over CR is more significant. This statement is verified by our result: game (7, 2): CRM with 25 + 17 and CR with 89 + 51; and game (8, 2): CRM with 156 + 83 (3%) and CR with 612 + 129 (33%) (see Table 2 However, from the game (7, 2) to the game (8. 2), the trend that CRM's advantage over CR is more significant is not very clear based on the above data due to the time limit in the game (8, 2). To show this trend clearly. we remove the time limit for CRM and CR in the game (8, 2) and obtain: CRM with 166 + 97 and CR with 2334 1742 which is shown in Table Then from the game 2). where CRM is about times faster than CR, to the game (8. 2), where CRM is about 13 times faster than CR, we can clearly see the trend that CRM's s ad over CR is more significant when the number of players increases. The difference between N and A also explains that CR is slower than CM in the game (8. 2).
I Results on More Gambit Algorithms
Results in Tables and 8 show that Gambit algorithms, i.e., GNM, IPA, LIAP, SIMPDIV, and LOGIT, cannot guarantee finding an NE, i.e., fail to solve many games, and even run significantly slower than our CRM (see Tables 4 and 5) in many games:
GNM fails to solve many large games: GNM stops without output in some of these cases, and cannot stop within the time limit in other cases. GNM runs significantly slower than our CRM in many games, e.g., random games (7,2), (4, 4), (3,5), (3, 10), and GAMUT games Bidirecttional LEG, Collaboration, Covariant
* IPA fails to solve many large games: IPA cannot stop within the time limit in most of these games. IPA runs significantly slower than our CRM in most random games, and the GAMUT game Random graphical.
24

---

LIAP can only solve several games in small random games (3. 2) and (4, 2), and fails to solve all of the other games: LIAP stops without output in these games. Even so, LIAP runs significantly slower than our CRM in most games.
SIMPDIV fails to solve many large games: SIMPDIV cannot stop within the time limit in almost all of these games. SIMPDIV runs significantly slower than CRM in most games.
LOGIT fails to solve all of these games: LOGIT stops without output in all these games. LOGIT may not work properly in this latest GAMBIT version. Even LOGIT runs significantly slower than our CRM the random game (3, 2).
25


Reviews:
[{"review_id": "rrajIdUWvA", "reviewer": "Reviewer_WEGb", "summary": "The paper attempts an improvement to existing approaches to tackling the problem of optimal Nash equilibrium (NE) computation. In general, the problem is NP-hard.\n\nUsually, a common approach in computing the optimal NE is to formulate it as the solution of a constrained mathematical program whose objective function assesses the optimality of a given NE while the feasibility set describes the set of all NE's. The solution space is nonconvex; commonly, the constraint set is relaxed to a convex one based on the set of correlation plans. The authors devise a a way to shrink the size of the underlying trees and shave-off a term that is exponential to the number of players $n$ from the running time complexity of solving a mixed integer bilinear program.", "questions": "* Is the improvement on the term $2^n$ that crucial?", "limitations": "The limitations are adequately discussed in my opinion.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The analysis seems self-contained, and the previous work is well demonstrated.\n* The paper is complemented with a good chunk of experiments.", "weaknesses": "* The improvement in the complexity manages to get rid of a term $2^n$ for a term $n \\log n$. Still though, in both cases, these terms are multiplied with a term $m^n$ (the number of actions $m$ to the power of the number $n$ of agents). For a game to be nontrivial, $m>1$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments.\n\n**Q**: Is the improvement on the term $2^n$ that crucial?\\\n**Answer**: Yes. Based on our general transformation framework, the straightforward approach is using the vanilla binary collection, but our CRM can generate a minimum binary collection to reduce time complexity. The improvement on the term $2^n$ is crucial because:\\\n1.\tTheoretically, it means that our proposed algorithm is significantly faster than the straightforward one. The reason is that our proposed algorithm requires significantly fewer bilinear terms than the straightforward one.\\\n2.\tExperimentally, our proposed algorithm is significantly faster than the baselines including the straightforward one, which validates our theoretical results. For example, for solving the GAMUT game called Random graphical shown in Table 1, our algorithm (i.e., CRM) used about 0.1 seconds, but the straightforward algorithm (i.e., MIBP) used more than 800 seconds. \\\n3.\tAs we mentioned in the limitation section, we are handling a very hard problem, and it is unrealistic to expect that we could remove all exponential terms to obtain an extremely fast algorithm. Our algorithm is an attempt to make the computation of optimal NEs feasible, and our algorithmic framework can be built on by further innovative heuristics to improve the computation of optimal NEs. For example, as shown in our additional experiment results (see our response to Reviewer PoVn), our algorithm CRM can solve large-scale real-world games with the aid of the PSRO framework, even when we cannot enumerate all actions due to the memory constraint.\n"}, {"review_id": "nJXT4kUzN5", "reviewer": "Reviewer_PoVn", "summary": "This paper tackles the challenge of computing a NE that optimizes some objective (e.g, social welfare). They present an algorithm that avoids the naive exponential blowup that occurs when trying to extend the two-player MILP for optimal NE to multiplayer optimal NE, by using relations between correlation plans to prune the feasible space that results after convex relaxation and reduce the number of bilinear terms. They present empirical evidence of the benefit of this approach.", "questions": "As mentioned above, it would be good to have some experiments combining this algorithm with other techniques to see how it can be used to solve larger scale games.\n\nIt is slightly confusing to me the use of “left” and “right” in line 126 to order the children in some sense of the binary collection. While it is common to refer to “left child” and “right child” of a binary tree, it doesn’t seem especially relevant (could you point out where the ordering of “left” and “right” gets used) to future discussion.\n\nI have read the rebuttal and my concerns have been sufficiently addressed.", "limitations": "Yes, the limitations have been addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well-written and the contributions made easy to understand.\n2. The paper presents a state-of-the-art algorithm for computation of optimal NE in multiplayer games. This is an important problem to consider because it helps operationalize game theory in the real world (most multi-agent settings are not two-player zero-sum).\n3. The paper contributes to a growing literature on cooperative AI (e.g., it might be useful to be able to compute an optimal equilibrium so that agents may be steered towards it).", "weaknesses": "1.\tWould be good to have shown a couple experiments using CRM as the meta-solver for PSRO (as the authors themselves suggest), and maybe compare using other meta-solvers for PSRO, just to see how the performances compared in those settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments.\n\n**Q**: About experiments combining this algorithm with other techniques to see how it can be used to solve larger scale games.\\\n**Answer**: We conducted experiments on real-world network security games (Jain et al., 2011). In these games, the attacker begins at a source node and traverses by choosing path to one of his targets. The action space of the attacker thus consists of all possible paths. The police officers move independently, each occupying one of the edges of the network in an attempt to apprehend the attacker before he reaches his target. There are three players in these games. The edges of the network with L x W nodes are randomly generated. It is estimated that in a fully connected network with 20 nodes and 190 edges, the number of possible attacker paths is approximately $6.6^{18}$ (Jain et al., 2011).\n\nOur experimental results show that: in games on the network with the 6 x 6 nodes, CRM fails to output the result as it is running out of memory, but our CRM with the aid of the PSRO framework (CRM is used as the meta solver) can solve these games within about 10 seconds. In significantly larger games on the network with 10 x 10 nodes, our CRM, with the aid of the PSRO framework, can solve these games within about 100 seconds. Therefore, our CRM can solve large-scale real-world games with the aid of the PSRO framework, even when we cannot enumerate all actions due to the memory constraint. \n\nJain, M., Korzhyk, D., Vaněk, O., Conitzer, V., Pěchouček, M. and Tambe, M., 2011, May. A double oracle algorithm for zero-sum security games on graphs. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 1 (pp. 327-334).\n\n**Q**: About the usage of the ordering of “left” and “right”\\\n**Answer**: In Line 126, we mentioned: “Let $N'_l$ and $N'_r$ be the left child and the right child of $N'\\in \\mathcal{N}$, respectively”, which means that each element $N'$ in a binary collection $\\mathcal{N}$ has the binary division, i.e., it is divided into two disjoint sets $N'_l$ and $N'_r$. Based on this binary division, any joint action can be divided into two sub-joint actions, as mentioned in Line 132. Therefore, it is used when we divide any joint action into two sub-joint actions, e.g., in Example 1 and Eq.(3a).\n"}, {"review_id": "X01haGxlDZ", "reviewer": "Reviewer_CmiG", "summary": "This papers studies computing Nash equilibrium in multiplayer games that optimizes a given objective function. The designed solving framework first transform the corresponding multilinear program into a bilinear program by introducing auxiliary variables representing probability distribution over players' joint actions. Then the feasible solution space after the convex relaxation of bilinear terms can be reduced. Time complexity of the proposed algorithm is shown to be reduced then SOTA both theoretically and numerically.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The design of correlation plan to reduce the feasible solution space after relaxation is interesting.\n2. The proposed approach is shown to be effectively by both concrete thereotical proofs and numerically experiments.", "weaknesses": "1. Although the time complexity of solving the optimal Nash is reduced, it is stiil exponential-time, which is not surprised.\n2. The notations related to the correlation plan is complicated. Although the examples provide quite clear intuition, it would be better there is any way to simplify the notations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your helpful comments.\n\n**Q**: About “Although the time complexity of solving the optimal Nash is reduced, it is stiil exponential-time, which is not surprised.”\\\n**Answer**: Based on our general transformation framework, the straightforward approach is using the vanilla binary collection, but our CRM can generate a minimum binary collection to reduce time complexity. The improvement on the term $2^n$ is crucial because:\\\n1.\tTheoretically, it means that our proposed algorithm is significantly faster than the straightforward one. The reason is that our proposed algorithm requires significantly fewer bilinear terms than the straightforward one.\\\n2.\tExperimentally, our proposed algorithm is significantly faster than the baselines including the straightforward one, which validates our theoretical results. For example, for solving the GAMUT game called Random graphical shown in Table 1, our algorithm (i.e., CRM) used about 0.1 seconds, but the straightforward algorithm (i.e., MIBP) used more than 800 seconds. \\\n3.\tAs we mentioned in the limitation section, we are handling a very hard problem, and it is unrealistic to expect that we could remove all exponential terms to obtain an extremely fast algorithm. Our algorithm is an attempt to make the computation of optimal NEs feasible, and our algorithmic framework can be built on by further innovative heuristics to improve the computation of optimal NEs. For example, as shown in our additional experiment results (see our response to Reviewer PoVn), our algorithm CRM can solve large-scale real-world games with the aid of the PSRO framework, even when we cannot enumerate all actions due to the memory constraint.\n"}, {"review_id": "Bw5oy4vL3j", "reviewer": "Reviewer_oqCe", "summary": "This paper addresses the problem of computing optimal Nash Equilibria in multi-player games. The authors present an optimization algorithm that uses a correlation plan-based formulation with a suitable convex relaxation in order to compute an optimal NE. At its core, the algorithm relies on a binary-tree structure of the correlation plans that enables the adoption of bilinear constraints to represent the set of NE. Finally, the authors experimentally evaluate their algorithm against different baselines for computing optimal NE. ", "questions": "I would like the authors to address my concerns on the significance of the paper.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main strength of this work is that the experimental evaluation shows promising results with respect to the state-of-the-art algorithms evaluated by the authors. \nMoreover, for what concerns me, the theoretical claims are sound. ", "weaknesses": "The aspect of this paper that concerns me the most is the contribution and significance of the presented results. I do not find it surprising that you can use correlation plans to compute a NE, and the algorithm formulation seems to me quite straightforward. \nFurthermore, while the experimental evaluation shows that in the benchmarks used, the algorithm outperforms existent baselines, I find the games used as benchmarks quite small. This, in my opinion, contributes to limiting the significance of the present paper. \n\nOverall, I don't think that at its current state, this work is suitable for a venue like NeurIPS", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments.\n\n**Q**: About the contribution, significance, and small benchmarks \n\n**Answer**: 1. To our knowledge, as we discussed in the related work section, the approach of breaking the strategy space into bilinear correlation plans based on a binary-tree structure and then heuristically reducing the feasible space, as a path to computing optimal NEs using bilinear programming is novel. We believe the heuristics that are applied over this structure are also good original contributions: There are no existing works that compute optimal NEs in multiplayer games by exploiting correlation plans with their relations based on a binary-tree structure to strictly reduce the feasible solution space after the convex relaxation while minimizing the number of correlation plans to reduce the number of bilinear terms.\\\n2. Based on our general transformation framework, the straightforward approach is using the vanilla binary collection, but our CRM can generate a minimum binary collection, which dramatically reduces time complexity, i.e., getting rid of a term $2^n$ for a term n log n. The improvement on the term $2^n$ in complexity is significant because, theoretically, it means that our proposed algorithm is significantly faster than the straightforward one. The reason is that our proposed algorithm requires significantly fewer bilinear terms than the straightforward one.\\\n3. Our experiment shows that our proposed algorithm is significantly faster than the baselines. For example, for solving the GAMUT game called Random graphical shown in Table 1, our algorithm (i.e., CRM) used about 0.1 seconds, but the straightforward algorithm (i.e., MIBP) used more than 800 seconds.\\\n4. As we mentioned in the limitation section, we cannot handle extremely large games now because we are handling a very hard problem, and then it is unrealistic to expect that our exact algorithm CRM could run very fast in large games. Our algorithm is an attempt to make this computation of optimal NEs feasible. \\\n5. Our algorithmic framework can be built on by further innovative heuristics to improve the computation of optimal NEs. For example, as shown in our additional experiment results (see our response to Reviewer PoVn), our algorithm CRM can solve large-scale real-world games with the aid of the PSRO framework, even when we cannot enumerate all actions due to the memory constraint. \n\n"}]

Author rebuttal:

Meta-review: Clear accept with unanimous support from all reviewers. The authors are encouraged to address the comments of the reviewers as well as include clarifications emerged during the discussion phase in improving the final version of their paper.
Decision: Accept (poster)