2008-10: Acyclic or totally tight, two-person game forms; characterization and main properties

DIMACS TR: 2008-10

Acyclic or totally tight, two-person game forms; characterization and main properties

Authors: Endre Boros, Vladimir Gurvich, Kazuhisa Makino and David Papp

ABSTRACT
It is known that a two-person game form g is Nash-solvable if and only if it is tight [12, 13]. We strengthen the concept of tightness as follows: game form is called totally tight if every its 2*2 subform is tight. (It is easy to show that in this case all, not only 2*2, subforms are tight.) We characterize totally tight game forms and derive from this characterization that they are tight, Nash- solvable, dominance-solvable, acyclic, and assignable. In particular, total tightness and acyclicity are equivalent properties of two-person game forms.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-10.pdf

DIMACS Home Page