Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $2 \times 2$ subgames
In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its (Formula presented.) submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every (Formula presented.) subgame has one. Nevertheless, Shapley’s claim can be extended to bimatrix games as follows. We partition all (Formula presented.) bimatrix games into fifteen classes (Formula presented.) depending only on the preferences of two players. A subset (Formula presented.) 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”.