Enumeration of Nash equilibria for two-player games
Enumeration of Nash equilibria for two-player games
复制标题
DOI：
10.1007/s00199-009-0449-x
复制
发表时间：
2010-01-01
期刊：
影响因子：
1.3
通讯作者：
von Stengel, Bernhard
中科院分区：
文献类型：
--
作者：
Avis, David;Rosenberg, Gabriel D.;von Stengel, Bernhard
本文描述了寻找策略形式的两人博弈的所有纳什均衡的算法。我们提出了两个算法，扩展早期的工作。我们的演示文稿是自包含的，并解释了两种方法在一个统一的框架中使用的最佳响应多面体的面。第一种方法lrsnash基于已知的顶点枚举程序lrs，用于“字典式反向搜索”。它只枚举一个最佳反应多面体的顶点，以及另一个多面体中与这些顶点对应的互补面的顶点（如果它们不为空）。第二种方法是对已知的极值平衡点枚举算法的改进。我们还描述了第二个，但尚未实现，是空间效率的变体。我们讨论的lrsnash和lrsnash的实现细节，并报告的计算实验，比较这两种算法，这表明两者都有自己的优点和缺点。
This paper describes algorithms for finding all Nash equilibria of a two-player game in strategic form. We present two algorithms that extend earlier work. Our presentation is self-contained, and explains the two methods in a unified framework using faces of best-response polyhedra. The first method lrsnash is based on the known vertex enumeration program lrs, for "lexicographic reverse search". It enumerates the vertices of only one best-response polytope, and the vertices of the complementary faces that correspond to these vertices (if they are not empty) in the other polytope. The second method is a modification of the known EEE algorithm, for "enumeration of extreme equilibria". We also describe a second, as yet not implemented, variant that is space efficient. We discuss details of implementations of lrsnash and EEE, and report on computational experiments that compare the two algorithms, which show that both have their strengths and weaknesses.