A survey on algorithms for Nash equilibria in finite normal-form games
Hanyu Li Wenhan Huang Zhijian Duan David Henry Mguni Kun Shao Jun Wang Xiaotie Deng
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.