Official LSV Web Site
Game-Theoretic Techniques in Computing
MPRI, Winter 2009/10
Final exam: Tuesday, February 9 at 13h00 in Rentiers
Main course page: MPRI 20-2-1
Instructors: Dietmar
Berwanger and Wieslaw Zielonka
See also cours material by Wieslaw Zielonka.
Graph games with perfect information
[Notes]
- Reachability and safety games: attractors
- Undetermined Gale-Stewart games
- Parity games: Memoryless determinacy, solution procedure
- Games with ω-regular conditions
- Mean-payoff games:
U. Zwick, M. Paterson, The complexity of mean-payoff games. In Theoretical Computer Science 158(1996) [download draft from Uri Zwick's homepage]
Games with imperfect information
[Notes]
- One player against the environment, Reiff's knowledge-set construction
- Distributed games: infinite memory, undecidability
Pursuit-Evasion games
Literature:
-
N. Nisse, Graph Searching and Graph Decompositions, Course notes, MDFI Marseille/Luminy 2008/09
-
Y. C. Stamatiou and D. M. Thilikos, Monotonicity and inert fugitive search games. In Electronic Notes in Discrete Mathematics, 3(1999), p. 184.
Elsevier [online version, mail to D. Berwanger for a copy]
- Graph searching, taxonomy
- Invisible robber, pathwidth, monotonicity
- Visible agile robber: treewidth, brambles; invisible inert robber