Computing Optimal Nash Equilibria in Multiplayer Games

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