Notice: Undefined offset: -25 in /srv/www/htdocs-cs/cie08/print-abs.php on line 7
CiE 2008 -
Computability in Europe 2006
Logical Approaches to Computational Barriers



Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117

Special Session Talk:
Deterministic Graphical Games Revisited



Notice: Undefined index: cancelled in /srv/www/htdocs-cs/cie08/conf-code.php on line 530

Notice: Undefined variable: del in /srv/www/htdocs-cs/cie08/conf-code.php on line 552
Speaker: Troels Bjerre Sørensen
Author(s): Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Abstract

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
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 579
2008-01-04