标题： 有限正常形式博弈中纳什均衡算法的综述 显示英文标题

标题： A survey on algorithms for Nash equilibria in finite normal-form games

摘要： 纳什均衡是博弈论中最具有影响力的一种解概念。随着计算机科学和人工智能的发展，对纳什均衡计算的需求不断增加，尤其是在互联网经济学和多智能体学习领域。本文从理论和实证两个角度回顾了各种计算有限正规形式博弈中纳什均衡及其近似解的算法。在理论部分，我们对文献中的算法进行了分类，并介绍了算法设计与分析的基本思想。在实证部分，我们对文献中的算法在不同类型的博弈中进行了全面比较。基于这些结果，我们提供了这些算法实现和使用的实际建议。最后，我们从理论和实践的角度提出了一系列开放性问题。 显示英文摘要

摘要： 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.