Finding Optimal Nash Equilibria in Multiplayer Games via Correlation Plans

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. 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 propose a novel algorithm called CRM based on a novel mixedinteger bilinear program with correlation plans for some subsets of players, 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. Experimental results show that our algorithm can be several orders of magnitude faster than the state-of-the-art baseline.

Authors

• Youzhi Zhang CAIR, Hong Kong Institute of Science & Innovation, CAS
• Bo An Nanyang Technological University
• V. S. Subrahmanian Northwestern University

Keywords

• Nash equilibrium
• Multiplayer game
• Bilinear program