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

Endre Boros (), Khaled Elbassioni (), Vladimir Gurvich (), Kazuhisa Makino () and Vladimir Oudalov ()
Additional contact information
Endre Boros: Rutgers University
Khaled Elbassioni: Masdar Institute of Science and Technology
Vladimir Gurvich: Rutgers University
Kazuhisa Makino: Kyoto University
Vladimir Oudalov: Salient Management Company

International Journal of Game Theory, 2016, vol. 45, issue 4, No 16, 1131 pages

Abstract: Abstract In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its $$2 \times 2$$ 2 × 2 submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every $$2 \times 2$$ 2 × 2 subgame has one. Nevertheless, Shapley’s claim can be extended to bimatrix games as follows. We partition all $$2 \times 2$$ 2 × 2 bimatrix games into fifteen classes $$C = \{c_1, \ldots , c_{15}\}$$ C = { c 1 , … , c 15 } depending only on the preferences of two players. A subset $$t \subseteq C$$ t ⊆ 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”.

Keywords: Matrix and bimatrix games; Saddle point; Nash equilibrium; Nash-solvability; Dual hypergraphs; Transversal hypergraphs; Dualization (search for similar items in EconPapers)
JEL-codes: C02 C62 C65 C72 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00182-015-0513-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:45:y:2016:i:4:d:10.1007_s00182-015-0513-7

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-015-0513-7

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().