Name
Abstract | ||
|---|---|---|
We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players an d on the mode of interaction between them. On the basis of information the classification is as fol- lows: (a) partial-observation (both players have partial v iew of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the ba- sis of mode of interaction we have the following classificati on: (a) concurrent (players interact simultaneously); and (b) turn-based (pl ayers interact in turn). The two sources of randomness in these games are randomness in transition func- tion and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. We present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function (proba- bilistic transition can be simulated by deterministic tran sition); and (b) strategies (pure strategies are as powerful as randomized strategies) . As consequence of our characterization we obtain new undecidability results for these games. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-15155-2_23 | Computing Research Repository |
Keywords | DocType | Volume |
deterministic strategy,players interact,transition function,following classification,complete view,probabilistic transition,complete observation,complete characterization,deterministic transition,randomized strategy | Conference | abs/1006.0 |
Issue | ISSN | ISBN |
C | 0302-9743 | 3-642-15154-X |
Citations | PageRank | References |
9 | 0.57 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Krishnendu Chatterjee | 1 | 2179 | 162.09 |
| Laurent Doyen | 2 | 979 | 55.96 |
| Hugo Gimbert | 3 | 249 | 21.31 |
| Thomas A. Henzinger | 4 | 14827 | 1317.51 |