DIMACS TR: 2008-11

Criteria or solvability of bimatrix games based on excluding certain 2*2 subgames



Authors: Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Khaled Elbassioni and Vladimir Oudalov

ABSTRACT

In 1964 Shapley noticed that a matrix M has a saddle point whenever every its 2*2 submatrix has one. In this paper we strengthen this claim. For example, we show that M not only has a saddle point but, moreover, it is dominance-solvable and it has no strict improvement cycles, as it was recently conjectured by Kukushkin [?]. We also extend Shap- ley's claim to bimatrix games for which we consider the following five concepts of solution: Nash equlibrium, domination (or sophisticated) equilibrium, and acyclicity, that is, absence of weak, semi-weak, or strict improvement cycles. Although the naive generalization fails: a 3*3 bimatrix game might have no Nash equilibrium even if every its 2*2 subgame has one (see Example 1 in [GL90] or in [BGM07]), yet, we prove that a bimatrix game with no ties is dominance-solvable and it has no strict improvement cycles whenever every its 2*2 sub- game is dominance-solvable. This statement was also conjectured by Kukushkin (private communications), however, we had to add the \no tie" assumption, which is crucial. We also obtain many similar results for games with possible ties, however, in this case more 2*2 subgames must be forbidden. Moreover, we develop a general technique for deriving all criteria of this type. Our method is based on joint generation of dual hypergraphs given by a special oracle.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-11.pdf
DIMACS Home Page