Deterministic graphical games revisited

被引：10

作者：

Andersson, Daniel ^{[1
]}

Hansen, Kristoffer Arnsfelt ^{[1
]}

Miltersen, Peter Bro ^{[1
]}

Sorensen, Troels Bjerre ^{[1
]}

机构：

[1] Univ Aarhus, Datalogisk Inst, DK-8200 Aarhus, Denmark

来源：

LOGIC AND THEORY OF ALGORITHMS | 2008年 / 5028卷

关键词：

D O I：

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

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1 / 10

页数：10

共 17 条

[1]

Ajtai M., 1983, P 15 ANN ACM S THEOR

[2]

[Anonymous], SCALABLE SEARCH COMP

[3] Presidential address [J].

Aumann, RJ .

GAMES AND ECONOMIC BEHAVIOR, 2003, 45 (01) :2-14

[4]

BLUM M, 1972, P 4 ANN ACM S THEOR, P119

[5] THE COMPLEXITY OF STOCHASTIC GAMES [J].

CONDON, A .

INFORMATION AND COMPUTATION, 1992, 96 (02) :203-224

[6] On model checking for the μ-calculus and its fragments [J].

Emerson, EA ;

Jutla, CS ;

Sistla, AP .

THEORETICAL COMPUTER SCIENCE, 2001, 258 (1-2) :491-522

[7]

EMERSON EA, 1957, ANN MATH STUDIES, V3

[8] ALGORITHMS FOR 2 BOTTLENECK OPTIMIZATION PROBLEMS [J].

GABOW, HN ;

TARJAN, RE .

JOURNAL OF ALGORITHMS, 1988, 9 (03) :411-417

[9]

Kearns M., 2001, P 17 C UNC ART INT, P253

[10]

Knuth D.E., 1997, Sorting and Searching, V3

← 1 2 →