Aarhus University Seal / Aarhus Universitets segl

Deterministic Graphical Games Revisited

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume5028
Pages (from-to)1-10
Number of pages11
ISSN0302-9743
DOIs
Publication statusPublished - 2008
EventConference on Computability in Europe, CiE 2008. - Athen, Greece
Duration: 15 Jun 200820 Jun 2008
Conference number: 4

Conference

ConferenceConference on Computability in Europe, CiE 2008.
Number4
CountryGreece
CityAthen
Period15/06/200820/06/2008

Bibliographical note

Title of the vol.: Logic and Theory of Algorithms. Proceedings. / Arnold Beckmann, Costas Dimitracopoulos and Benedikt Löwe (eds.)
ISBN: 978-3-540-69405-2

See relations at Aarhus University Citationformats

ID: 11264651