DIMACS TR: 2008-09

Minimal and local minimal games and game forms



Authors: Endre Boros, Vladimir GurvichVl and Kazuhisa Makino

ABSTRACT

By Shapley's (1964) theorem, a matrix game has a saddle point whenever each of its 2*2 subgames have one. In other words, all minimal saddle point free (SP-free) matrices are of size 2*2. We strengthen this result and show that all locally minimal SP-free matrices are of size 2* 2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column, then A is of size 2*2. Furthermore, we generalize this result and characterize the minimal and locally minimal Nash equilibrium free (NE-free) bimatrix games. Let us recall that a two-person game form is Nash-solvable if and only if it is tight (Gurvich, 1975). We show that all (locally) minimal non tight game forms are of size 2*2. In contrast, it seems dicult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sucient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex

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