zbMATH — the first resource for mathematics

A complete characterization of Nash-solvability of bimatrix games in terms of the exclusion of certain \(2\times 2\) subgames. (English) Zbl 1143.91308
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 99-109 (2008).
Summary: In 1964 Shapley observed that a matrix has a saddle point whenever every \(2 \times 2\) submatrix of it has one. In contrast, a bimatrix game may have no Nash equilibrium (NE) even when every \(2 \times 2\) subgame of it has one. Nevertheless, Shapley’s claim can be generalized for bimatrix games in many ways as follows. We partition all \(2 \times 2\) bimatrix games into fifteen classes \(C = \{c _{1}, \dots , c _{15}\}\) depending on the preference pre-orders of the 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 general method for getting 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) minimal NE-theorems.
For the entire collection see [Zbl 1136.68005].

91A05 2-person games
PDF BibTeX Cite
Full Text: DOI