Deterministic Graphical Games Revisited

Daniel Andersson; Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre Sørensen

doi:10.1007/978-3-540-69407-6_1

Deterministic Graphical Games Revisited

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review

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.

Original language	English
Book series	Lecture Notes in Computer Science
Volume	5028
Pages (from-to)	1-10
Number of pages	11
ISSN	0302-9743
DOIs	https://doi.org/10.1007/978-3-540-69407-6_1
Publication status	Published - 2008
Event	Conference on Computability in Europe, CiE 2008. - Athen, Greece Duration: 15 Jun 2008 → 20 Jun 2008 Conference number: 4

Conference

Conference	Conference on Computability in Europe, CiE 2008.
Number	4
Country/Territory	Greece
City	Athen
Period	15/06/2008 → 20/06/2008

Access to Document

10.1007/978-3-540-69407-6_1

Cite this

@inproceedings{0afac4601cf311ddbe51000ea68e967b,

title = "Deterministic Graphical Games Revisited",

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.",

author = "Daniel Andersson and Hansen, {Kristoffer Arnsfelt} and Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

note = "Title of the vol.: Logic and Theory of Algorithms. Proceedings. / Arnold Beckmann, Costas Dimitracopoulos and Benedikt L{\"o}we (eds.) ISBN: 978-3-540-69405-2; Conference on Computability in Europe, CiE 2008. ; Conference date: 15-06-2008 Through 20-06-2008",

year = "2008",

doi = "10.1007/978-3-540-69407-6_1",

language = "English",

volume = "5028",

pages = "1--10",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - Deterministic Graphical Games Revisited

AU - Andersson, Daniel

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 4

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-69407-6_1

DO - 10.1007/978-3-540-69407-6_1

M3 - Conference article

SN - 0302-9743

VL - 5028

SP - 1

EP - 10

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Conference on Computability in Europe, CiE 2008.

Y2 - 15 June 2008 through 20 June 2008

ER -

Deterministic Graphical Games Revisited

Abstract

Conference

Access to Document

Fingerprint

Cite this