Computational game theory, Q2, 2010

Lecturer

Time and Place

Monday, 14.15-16 in Lecture room 112, Incuba Science Park. Wednesday, 14.15-16 in Lecture room 112, Incuba science Park.

About the course

This is what the course catalogue says about the "plain" version of the course and this is what is said about the honors version. It is all true!

Literature

Thomas S. Ferguson, Game Theory.
Howard Shapiro, Note on a computation method in the theory of games.
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sorensen, Deterministic Graphical Games revisited.

Exam question

Matrix games and Imperfect Information Extensive Form Games.
- Curriculum: Miltersen, Chapter 1 and 2. Ferguson Section 1-5.
Perfect Information Extensive Form Games and Deterministic Graphical Games.
- Curriculum: Miltersen, Chapter 3 and 4. Andersson et al.
Shapley's Stochastic Games, Existence of Value and Value Iteration.
- Curriculum: Shapley.
Shapley's Stochastic Games, Howard's algorithm.
- Curriculum: Hansen, Miltersen, Zwick.
Shapley's Stochastic Games, The random facet algorithm.
- Curriculum: Ludwig.
Concurrent Reachability Games.
- Curriculum: Hansen, Koucky, Miltersen and Hansen, Ibsen-Jensen, Miltersen.

The exam will be January 21st.

Notes

We will attempt to produced a full series of notes for the course, mainly based on scribe notes from last years course, but corrected and with new material added along the way. Please be prepared for and do not get frustrated from the fact that they will be a moving target throughout the course. Each section will be annotated here with its latest update date.

Peter Bro Miltersen, Computational aspects of two-player zero-sum games:

Section 1 and 2 (last update Nov 1).
Section 3 (last update Nov 10, subsection added).
Section 4 (last update Jan 16, corrections made)
Section 5 (last update Nov 17)

First compulsory assignment (due Nov 17)

Do one of the following:

From Shapiro's proof of the convergence of fictitious play, it is possible to derive a function f(ε,n), so that for all games with n pure strategies for each player and payoffs between 0 and 1, after at least f(ε, n) iterations of fictitious play, the empirical distribution of the choices of the row player guarantees at least the value of the game minus ε. Derive an explicit expression for f, without any big-Os.
Implement fictitious play and do experiments designed to shed light on the convergence rate.

Alert: Asger Felthaus has pointed out a very annoying misprint in Shapiro: In Theorem 3.1, the denominator is wrong: The reciprocal should be inside the exponent!

Second compulsory assignment (due Dec 1)

Show how to solve one-player extensive form game with perfect recall in linear time.

Third compulsory assignment (due Dec 15)

The SQRT-SUM problem is the following: Given a list of positive integers, determine if the sum of their square roots is at least a given integer. This problem is not known to be in P, as discusssed in the course dKS. We say that a decision problem is SQRT-SUM-hard if the SQRT-SUM problem polynomial time reduces to it. Show that comparing the value of a Shapley stochastic game to a given rational number is SQRT-SUM-hard. Hint: As a gadget, consider the following variant of matching pennies: The column player hides a penny and the row player must guess if it is heads up or tails up. If he guesses incorrectly, his reward is 0 and the play stops. If he guesses correctly "heads", his reward is a and the play stops. If he guesses correctly "tails", his reward is b and with probability $p < 1$, the game starts over. What is the value of this game, as a function of a,b,p?

Lectures

November 1st. The minimax solution concept. Matrix games. Ferguson, Sections 1-4. Miltersen, Section 1,2
November 3rd. Fictitious play. Notes by Daskalakis. Miltersen, rest of section 2.. The extensive form.
November 8th. The extensive form. Ferguson, Section 5. Miltersen, Section 3.
November 10th. Finite perfect information games. Miltersen, rest of Section 3, Section 4.
November 15th. Sublinear time evaluation of game trees. Deterministic graphical games. Miltersen, rest of Section 4, Section 5, and Deterministic Graphical Games Revisited.
November 17th. Sublinear time evaluation of game trees. Deterministic graphical games. Miltersen, rest of Section 5. Stochastic games. 0-player stochastic games, using these notes
November 22th. Guest lecture by Nicole Immorlica on Dueling Algorithms.
November 24th. Stochastic games. We wrote a big hierarchy on the whiteboard. The "big match" and "purgatory" were presented as examples.
Noveember 29th. No good notes just yet (apart form 0-player notes above). We will go by these classical papers: Shapley and Everett. Read also Ferguson, Section 6. We discuss Shapley's games which is the cleanest model, Explain why they are a special case of Everett games, do the 0- and 1-player case computationally, and discuss the value and strategy iteration algorithms for the two-player case.
December 1st. Continued...
December 6th. Strategy iteration. Complexity bounds for strategy iteration from Hansen, Miltersen, Zwick. Also, the RANDOM FACET algorithm from Ludwig.
December 8th. Value and Strategy iteration for Concurrent Reachability Games, following this and that.
December 13th. Mu-calculus and Parity games. Notes by Bradfield and Stirling and notes by Wilke.