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”.