Lectures in game theory for computer scientists

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Contributors......Page 10
Preface......Page 11
1.1 Introduction......Page 15
1.2 Basic concepts......Page 16
1.3.1 Elimination of strictly dominated strategies......Page 19
1.3.2 Elimination of weakly dominated strategies......Page 23
1.3.3 Elimination of never best responses......Page 25
1.4 Mixed extension......Page 27
1.5.1 Elimination of strictly dominated strategies......Page 30
1.5.2 Elimination of weakly dominated strategies......Page 31
1.5.3 Rationalizability......Page 32
1.5.4 A comparison between the introduced notions......Page 34
1.6 Variations on the definition of strategic games......Page 36
1.7 Mechanism design......Page 37
1.8 Pre-Bayesian games......Page 44
1.9.1 Bibliographic remarks......Page 47
1.9.2 Suggestions for further reading......Page 48
References......Page 49
2.1 Introduction......Page 52
2.2 Basic notations and definitions......Page 54
2.3 Transformation of winning conditions......Page 58
2.3.1 ω-automata......Page 60
2.3.2 Game reductions......Page 63
Linear temporal logic......Page 65
Monadic second-order logic......Page 69
2.4 Tree automata......Page 71
2.4.1 Complementation......Page 73
2.4.2 Emptiness......Page 79
2.5 Beyond finite automata......Page 82
References......Page 84
3.1 Games on graphs......Page 88
3.2 Solving repeated reachability and eventual safety games......Page 91
3.3 Solving parity games......Page 95
3.3.1 Divide and conquer......Page 96
3.3.2 Divide and conquer with dominion preprocessing......Page 99
3.3.3 Value iteration: progress measure lifting......Page 102
3.3.4 Divide and conquer with dominion preprocessing by progress measure lifting......Page 106
3.4 Related work......Page 109
References......Page 111
4.1 Introduction......Page 113
4.2 Reachability games and parity games......Page 116
4.3.1 Games and Horn formulae......Page 119
4.3.2 Model-checking games for first-order logic......Page 120
4.3.3 Complexity of first-order model-checking......Page 121
4.3.4 Definability of winning regions......Page 122
4.4 Logics with least and greatest fixed-points......Page 123
4.4.1 Least fixed-point logic and reachability games......Page 125
4.4.2 Capturing polynomial time......Page 127
4.4.3 Model-checking games for least fixed-point logic......Page 128
4.4.4 The modal μ-calculus......Page 132
4.5 Definability of winning regions in parity games......Page 134
4.5.1 Parity games with a bounded number of priorities......Page 135
4.5.2 Alternation hierarchies......Page 137
4.5.3 Parity games with an unbounded number of priorities......Page 138
4.6 Inflationary fixed-point logic and backtracking games......Page 141
4.6.1 Inflationary fixed-point logic......Page 142
4.6.2 Parity games with backtracking......Page 144
4.6.3 Games for IFP......Page 146
4.6.4 Definability of winning regions in backtracking games......Page 149
4.7 Logic and games in a quantitative setting......Page 152
4.7.1 Quantitative transition systems and quantitative μ-calculus......Page 153
4.7.2 Quantitative parity games......Page 154
4.7.3 Model-checking games for Qμ......Page 155
4.7.4 Defining game values in Qµ......Page 156
References......Page 158
5.1 Introduction......Page 160
Words, paths, and runs......Page 161
Probability spaces......Page 162
Markov chains......Page 163
Turn-based stochastic games and Markov decision processes......Page 164
5.2 Winning objectives in stochastic games......Page 165
5.2.1 Games with Borel measurable payoffs......Page 166
Qualitative payoffs......Page 167
Quantitative payoffs......Page 168
The problems of interest......Page 170
The existing results......Page 171
5.2.2 Win–lose games......Page 175
Linear-time logics......Page 176
Branching-time logics......Page 178
The problems of interest......Page 180
The existing results......Page 181
5.3.1 The existence of a value revisited......Page 184
5.3.2 Optimal strategies and determinacy......Page 186
5.4 Some directions of future research......Page 194
References......Page 195
6.1 Introduction......Page 199
6.2 Games with perfect information......Page 202
6.3.1 Game structure with imperfect information......Page 208
6.3.2 Reduction to games with perfect information......Page 211
6.3.3 Symbolic algorithms and antichains......Page 213
6.3.4 Strategy construction......Page 216
6.4.1 Playing with randomised strategies......Page 218
6.4.2 An algorithm for reachability objectives......Page 220
References......Page 225
7.1 Introduction......Page 227
Node searching......Page 228
Optimal strategies......Page 229
Applications......Page 230
7.2 Classifying graph searching games......Page 231
7.2.1 Abstract graph searching games......Page 232
7.2.2 Invisible abstract graph searching games......Page 233
7.2.3 Visible abstract graph searching games......Page 236
Example: The Visible Cops and Robber Game......Page 238
7.2.4 Complexity of strategies......Page 239
7.2.5 Monotonicity......Page 240
7.2.6 Connection to reachability games......Page 241
7.3.1 A different Cops and Robber game......Page 243
7.3.2 Node and edge searching with an invisible fugitive......Page 244
7.3.3 Visible Robber games......Page 245
7.3.5 Games played on directed graphs......Page 246
7.3.7 Further variants......Page 249
7.4.1 Monotonicity by sub-modularity......Page 250
Sub-modularity......Page 255
Monotonicity of the visible Cops and Robber Game......Page 257
Further applications of sub-modularity......Page 259
7.4.2 Approximate monotonicity......Page 260
7.4.3 Games which are strongly non-monotone......Page 262
7.5 Obstructions......Page 263
7.6 An application to graph-decompositions......Page 266
7.7 Complexity of graph searching......Page 269
7.7.1 Classical complexity bounds for graph searching games......Page 270
Games with a visible fugitive......Page 271
Games with an invisible fugitive......Page 272
7.7.2 Parametrised complexity of graph searching......Page 273
7.8 Conclusion......Page 274
References......Page 275
Appendix Notation......Page 277
8.1 Introduction......Page 278
8.2 Robust and resilient equilibrium......Page 280
8.3 Taking computation into account......Page 284
8.4 Taking (lack of) awareness into account......Page 288
8.5 Iterated regret minimisation......Page 294
8.6 Conclusions......Page 299
References......Page 301
Index......Page 305