# 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].

##### MSC:
 91A05 2-person games
Full Text: