Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
Deterministic Graphical Games Revisited

Speaker: Troels Bjerre Sørensen
Author(s): Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen


We revisit the deterministic graphical games of Washburn.  A deterministic
graphical game can be described as a simple stochastic game (a notion due to
Anne Condon), except that we allow arbitrary real payoffs but disallow moves of
chance. We study the complexity of solving deterministic graphical games and
obtain an almost-linear time comparison-based algorithm for computing an
equilibrium of such a game. The existence of a linear time comparison-based
algorithm remains an open problem.

websites: Arnold Beckmann 2008-01-04