2023/12/18 by Hanyu Li, Wenhan Huang, Li, Hanyu +11 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Algorithm #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Best response #Computation #Computational economics #Computer Science and Game Theory (cs.GT) #Computer science #Data Structures and Algorithms (cs.DS) #Economics #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Applications #Game Theory and Voting Systems #Game theory #Implementation #Machine Learning (cs.LG) #Mathematical economics #Mathematical optimization #Mathematics #Nash equilibrium #Series (stratigraphy) #Theoretical Economics (econ.TH) #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2312.11063
openalex publication_date 2023/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nash equilibrium is one of the most influential solution concepts in game theory. With the development of computer science and artificial intelligence, there is an increasing demand on Nash equilibrium computation, especially for Internet economics and multi-agent learning. This paper reviews various algorithms computing the Nash equilibrium and its approximation solutions in finite normal-form games from both theoretical and empirical perspectives. For the theoretical part, we classify algorithms in the literature and present basic ideas on algorithm design and analysis. For the empirical part, we present a comprehensive comparison on the algorithms in the literature over different kinds of games. Based on these results, we provide practical suggestions on implementations and uses of these algorithms. Finally, we present a series of open problems from both theoretical and practical considerations.