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