A Computer-aided Approach for Approximate Nash Equilibria

author: Dongchen Li, Hanyu Li, Xiaotie Deng

Abstract: Since the landmark PPAD-completeness result for Nash equilibria in two-player normal-form games, significant research has focused on developing polynomial-time algorithms to compute $\epsilon$-approximate Nash equilibria ($\epsilon$-NE). The challenge of establishing the optimal approximation guarantee in polynomial time remains pivotal. While advancements have been made for two-player games, progress in multi-player games has been limited. The current best algorithm for three-player games achieves a $(0.6+\delta)$-NE by extending the two-player algorithm. Difficulties arise due to the increased sophistication of multi-player games and the lack of tools for analyzing approximation bounds. This paper introduces a computer-aided method for approximation analysis using a domain-specific language called LegoNE. Based on LegoNE, we are able to turn high-level intuitions into an algorithm. Then, LegoNE can automatically discover lower-level properties and prove an approximation bound. Using LegoNE, we design a new algorithm for three-player games that achieves a $(0.56+\delta)$-NE, improving the previous best bound. This shows that combining human intelligence with computer-aided methods allows us to obtain higher-level understandings and better results.