Lectures in Game Theory for Computer Scientists

by Edited by Krzysztof R. Apt , Erich Grädel

• ISBN13: 9780521198660
• ISBN10: 0521198666
• Format: Hardcover
• Copyright: 2011-02-14
• Publisher: Cambridge University Press

Summary

Games provide mathematical models for interaction. Numerous tasks in computer science can be formulated in game-theoretic terms. This fresh and intuitive way of thinking through complex issues reveals underlying algorithmic questions and clarifies the relationships between different domains. This collection of lectures, by specialists in the field, provides an excellent introduction to various aspects of game theory relevant for applications in computer science that concern program design, synthesis, verification, testing and design of multi-agent or distributed systems. Originally devised for a Spring School organised by the GAMES Networking Programme in 2009, these lectures have since been revised and expanded, and range from tutorials concerning fundamental notions and methods to more advanced presentations of current research topics. This volume is a valuable guide to current research on game-based methods in computer science for undergraduate and graduate students. It will also interest researchers working in mathematical logic, computer science and game theory.

Author Biography

Krzysztof R. Apt is Professor at the University of Amsterdam and a Fellow at Centrum Wiskunde en Informatica (CWI), Amsterdam. Erich Grdel is Professor for Mathematical Foundations of Computer Science at RWTH Aachen University, Germany.

Table of Contents

List of contributors	p. viii
Preface	p. ix
A Primer on Strategic Games	p. 1
Introduction	p. 1
Basic concepts	p. 2
Iterated elimination of strategies I	p. 5
Mixed extension	p. 13
Iterated elimination of strategies II	p. 16
Variations on the definition of strategic games	p. 22
Mechanism design	p. 23
Pre-Bayesian games	p. 30
Conclusions	p. 33
Infinite Games and Automata Theory	p. 38
Introduction	p. 38
Basic notations and definitions	p. 40
Transformation of winning conditions	p. 44
Tree automata	p. 57
Beyond finite automata	p. 68
Conclusion	p. 70
Algorithms for Solving Parity Games	p. 74
Games on graphs	p. 74
Solving repeated reachability and eventual safety games	p. 77
Solving parity games	p. 81
Related work	p. 95
Back and Forth Between Logic and Games	p. 99
Introduction	p. 99
Reachability games and parity games	p. 102
Reachability games and logic	p. 105
Logics with least and greatest fixed-points	p. 109
Definability of winning regions in parity games	p. 120
Inflationary fixed-point logic and backtracking games	p. 127
Logic and games in a quantitative setting	p. 138
Turn-Based Stochastic Games	p. 146
Introduction	p. 146
Winning objectives in stochastic games	p. 151
Reachability objectives in games with finitely and infinitely many vertices	p. 170
Some directions of future research	p. 180
Games with Imperfect Information: Theory and Algorithms	p. 185
Introduction	p. 185
Games with perfect information	p. 188
Games with imperfect information: surely-winning	p. 194
Games with imperfect information: almost-surely-winning	p. 204
Graph Searching Games	p. 213
Introduction	p. 213
Classifying graph searching games	p. 217
Variants of graph searching games	p. 229
Monotonicity of graph searching	p. 236
Obstructions	p. 249
An application to graph-decompositions	p. 252
Complexity of graph searching	p. 255
Conclusion	p. 260
Beyond Nash Equilibrium: Solution Concepts for the 21st Century	p. 264
Introduction	p. 264
Robust and resilient equilibrium	p. 266
Taking computation into account	p. 270
Taking (lack of) awareness into account	p. 274
Iterated regret minimisation	p. 280
Conclusions	p. 285
Index	p. 291
Table of Contents provided by Ingram. All Rights Reserved.