Computational game theory, Q2, 2009

Lecturer

Time and Place

Monday, 14.15-16 in Shannon-159. Friday, 10.15-12 in IT-huset, lokale 129.

About the course

This is what the course catalogue says about the course. To pass the course, each student must write one or two lecture notes, each covering a two-hour lecture. The combined set of (revised) lecture notes will define the curriculum of the course (while the literature below may be considered background information). Also, each student must take an oral exam in this curriculum. A grade on the 7-scale will be given based on this exam.

Scribe notes will be produced be a student after each lecture. For a uniform appearence, please typeset the notes using the following LaTeX file.

LaTeX include file.

Example file.

To make all benefit the most from these scribe notes, it is important that they are produced quickly after each lecture. For the Monday lecture, have the draft ready the following Wednesday. For the Friday lecture, have the draft ready the following Tuesday. Email the notes to me so that I can place them on the course web site. Please send the LaTeX source as well as a compiled pdf file. You are encouraged to comment on each others scribe notes.

The exam

The exam will take place on January 7th and January 20th, in Turing-030, starting 9am. On January 6th and January 19th at 1pm, we will have a QA session, also in Turing-030. If you did not do so already, please send me an email about which of the two days you prefer. The exam schedule will be posted here before Christmas. The exam is an oral exam without preparation. A dice throw will determine one of the followng three topics.

Solving two-player zero-sum games in strategic and extensive form.
Solving two-player zero-sum games of unbounded or infinite duration.
Solving general-sum games.

We will have a conversation lasting strictly less than 30 minutes about the course, starting from topic determined by the dice.

Exam Schedule

Lectures

October 30. Special session with Uri Zwick and Kousha Etessami. See here. We start at 10.01, not 10.15
November 2. The minimax solution concept. Matrix games. Ferguson (see below), Sections 1-4. Scribe notes: pdf
November 6. Nash equilibrium concept. Games in extensive form. Ferguson, Section 5. Scribe notes: pdf.
November 9. The sequence form. Koller, Megiddo, von Stengel. Scribe notes: pdf
November 13. Games of perfect information. Backwards induction. Solving games of perfect information in randomized sublinear time. Saks and Wigderson. Ferguson, section 6. Scribe Notes: pdf.
November 16. Alpha-beta evaluation. Deterministic graphical games. Retrograde analysis. Andersson et al Scribe Notes: pdf.
November 20. More on retrograde analysis. Simple stochastic games. Stochastic games. Scribe Notes: pdf.
November 23. More on stochastic games. Value iteration and strategy iteration. Ferguson section 6. Scribe notes:pdf
November 27. Guest lecturer. Hardness of minimax computation in 3-player games. Hansen, Hansen, Miltersen, Sorensen. Scribe notes: pdf.
November 30. Almost last words on stochastic games. de Alfaro et al., Hansen, Koucky, Miltersen. Andersson and Miltersen. Condon. Friedman. Scribe notes: part 1,, part 2.
December 4. Very last words on stochastic games. Nash equilibrium theorem. Scribe notes: part1, part2
December 7. Nash equilibrium computation in 2-player games. Lemke-Howson algorithm and Lemke's algorithm. Linear complementarity programming. Approximate Nash equilibrium computation. Sperner's lemma. von Stengel. Scribe notes: pdf.
December 11. Scarf's algorithm, PPAD, Lipton-Mehta-Markakis. Scribe Notes: pdf.
December 14. Equilibrium refinements. Scribe notes: pdf, Miltersen and Sorensen. Slides.

Literature (partial and preliminary list, in no particular order)

Thomas S. Ferguson, Game Theory.
Michal Saks and Avi Wigderson, Probabilistic boolean decision trees and the complexity of evaluating game trees
Bernhard von Stengel, Equilibrium computation for two-player games.
Christos Papadimitriou, Computing correlated equilibria in multiplayer games .
Daphne Koller, Nimrod Megiddo, Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees:
Hansen et al. Approximability and fixed parameter tractability of minmax values.
Anne Condon, On algorithms for simple stochastic games.
Xi Chen, Xiaotie Deng, Settling the complexity of 2-player Nash equilibrium.
Kousha Etessami and Mihalis Yannakakis, On the complexity of Nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis, Recursive Markov Decision Processes and Recursive Stochastic Games.
de Alfaro, Henzinger, Kupferman, Concurrent reachability games
Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen, Winning concurrent reachability games requires doubly-exponential patience
Peter Bro Miltersen, Trembling hand perfection is NP-hard.
Daniel Andersson and Peter Bro Miltersen, On the computational complexity of solving stochastic mean-payoff games.
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen, Approximability and parameterized complexity of minmax values.
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen, Deterministic graphical games revisited.
Peter Bro Miltersen, Troels Bjerre Sørensen, Fast algorithms for finding proper strategies in game trees
Peter Bro Miltersen and Troels Bjerre Sørensen, Computing a quasi-perfect equilibrium of a two-player game
Vincent Conitzer and Tuomas Sandholm. New Complexity Results about Nash Equilibria.
Vincent Conitzer and Tuomas Sandholm. Complexity of (Iterated) Dominance.
Richard Lipton, Evangelois Markakis, Aranyak Mehta, Playing large games using simple strategies.
Michael Kearns, Graphical games.
Martin Zinkevich, Michael Johanson, Michael Bowling, Carmelo Piccione. Regret minimization in games with incomplete information.
Uri Zwick and Mike Paterson, The complexity of mean payoff games on graphs.
Oliver Friedman, A super-polynomial lower bound on the parity game strategy improvement algorithm as we know it.