Name
Abstract | ||
|---|---|---|
We consider finding maximin strategies and equilibria of explicitly given extensive form games with imperfect information but with no moves of chance. We show that a maximin pure strategy for a twoplayer game with perfect recall and no moves of chance can be found in time linear in the size of the game tree and that all pure Nash equilibrium outcomes of a two-player general-sum game with perfect recall and no moves of chance can be enumerated in time linear in the size of the game tree. We also show that finding an optimal behavior strategy for a one-player game of no chance without perfect recall and determining whether an equilibrium in behavior strategies exists in a two-player zero-sum game of no chance without perfect recall are both NP-hard. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73545-8_28 | COCOON |
Keywords | Field | DocType |
maximin strategy,maximin pure strategy,one-player game,perfect recall,twoplayer game,two-player zero-sum game,extensive form game,game tree,behavior strategy,two-player general-sum game,nash equilibrium,linear time,imperfect information | Combinatorial game theory,Mathematical economics,Mathematical optimization,Expectiminimax tree,Computer science,Repeated game,Normal-form game,Centipede game,Sequential game,Game tree,Extensive-form game | Conference |
Volume | ISSN | ISBN |
4598 | 0302-9743 | 3-540-73544-5 |
Citations | PageRank | References |
3 | 0.48 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kristoffer Arnsfelt Hansen | 1 | 176 | 21.40 |
| Peter Bro Miltersen | 2 | 1146 | 94.49 |
| Troels Bjerre Sørensen | 3 | 181 | 18.08 |