2009-09: On acyclicity of games with cycles

DIMACS TR: 2009-09

On acyclicity of games with cycles

Authors: Daniel Anderson, Vladimir Gurvich and Thomas Dueholm Hansen

ABSTRACT
We study restricted improvement cycles (ri-cycles) in nite positional n-person games with perfect information modeled by directed graphs (digraphs) that may contain directed cycles (di-cycles). We obtain criteria of restricted improvement acyclicity (ri-acyclicity) in two cases: for n = 2 and for acyclic digraphs. We also provide several examples that outline the limits of these criteria and show that, essentially, there are no other ri-acyclic cases. We also discuss connections between ri-acyclicity and some open problems related to Nash-solvability.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-09.pdf

DIMACS Home Page