Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden \(2 \times 2\) subgames

详细信息    查看全文

• 作者：Endre Boros ; Khaled Elbassioni ; Vladimir Gurvich…
• 关键词：Matrix and bimatrix games ; Saddle point ; Nash equilibrium ; Nash ; solvability ; Dual hypergraphs ; Transversal hypergraphs ; Dualization
• 刊名：International Journal of Game Theory
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：45
• 期：4
• 页码：1111-1131
• 全文大小：
• 刊物主题：Economic Theory/Quantitative Economics/Mathematical Methods; Game Theory, Economics, Social and Behav. Sciences; Behavioral/Experimental Economics; Operation Research/Decision Theory;
• 出版者：Springer Berlin Heidelberg
• ISSN：1432-1270
• 卷排序：45

文摘

In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its \(2 \times 2\) submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every \(2 \times 2\) subgame has one. Nevertheless, Shapley’s claim can be extended to bimatrix games as follows. We partition all \(2 \times 2\) bimatrix games into fifteen classes \(C = \{c_1, \ldots , c_{15}\}\) depending only on the preferences of two players. A subset \(t \subseteq C\) is called a NE-theorem if a bimatrix game has a NE whenever it contains no subgame from t. We suggest a method to construct all minimal (that is, strongest) NE-theorems based on the procedure of joint generation of transversal hypergraphs given by a special oracle. By this method we obtain all (six) strongest NE-theorems. Let us remark that the suggested approach, which may be called “math-pattern recognition”, is very general: it allows to characterize completely an arbitrary “target” in terms of arbitrary “attributes”.