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

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Konferenceartikel › Forskning › 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.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Vol/bind	5028
Sider (fra-til)	1-10
Antal sider	11
ISSN	0302-9743
DOI	https://doi.org/10.1007/978-3-540-69407-6_1
Status	Udgivet - 2008
Begivenhed	Conference on Computability in Europe, CiE 2008. - Athen, Grækenland Varighed: 15 jun. 2008 → 20 jun. 2008 Konferencens nummer: 4

Konference

Konference	Conference on Computability in Europe, CiE 2008.
Nummer	4
Land/Område	Grækenland
By	Athen
Periode	15/06/2008 → 20/06/2008

Adgang til dokumentet

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

Citationsformater

@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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater