Algorithmic game theory, Fall 2008

Lecturer

Peter Bro Miltersen.

Time and Place

Mondays, 13.15-15, Shannon-159.
Thursdays, 9.15-11, Shannon-159.

About the course

This is what the course catalogue says about the course.

Problems for Monday, September 1

Verify that the linear programs for a minimax and a maximin strategy are duals.
Show an example of a matrix game and a maximin strategy of the game that puts strictly positive probability mass on some weakly dominated strategy.
We define a pure strategy j of Player II to be exploitable if there is a maximin strategy p, so that when p is played against j, the expected payoff is strictly more than the value of the game.
- Exhibit a game with an exploitable strategy that is not weakly dominated.
- Exhibit a game with a weakly dominated strategy that is not exploitable.
- Show how to determine with a linear program if a particular strategy is exploitable.
- Show how to determine with a single linear program the set of exploitable strategies of Player II.
- Show that a strategy is exploitable if and only if all minimax strategies put probability mass zero on it. Show that "all" can not be replaced with "some" in that statement.
- Show that there is a maximin strategy that exploits all exploitable strategies, i.e., achieves an expected payoff strictly greater than the value of the game when played against each of them.

Problems for Thursday, September 11

Solve Ferguson's exercises 5.9.1, 5.9.2, 5.9.3, 5.9.5, 5.9.10. Also, write down the linear programs expressing the maximin/minimax strategies in sequence form for the games.
Find the mixed Nash equilibrium of "Chicken", described on September 8.
Show how to find an undominated maximin behavior strategy of a two-player extensive-form zero-sum game with perfect recall using linear programming. Hint: Solve two linear programs, the one finding the maximin strategy in sequence form described at the lecture, and one linear program derived from the solution.

Problems for Thursday, October 2

Questions of Roughgarden and:

Specialize the VCG combinatorial auction to the following settings and aruge that the implementation can be made computationally efficient:
- A setting with homogeneous goods: That is, the valuation of a bundle may only depends on its size, not on the items in the bundle.
- An "AdWords-like" auction. That is, k advertising slots are for sale. Each bidder wants exactly one. Bidder i has a private valuation v_i for a clickthrough and his payoff when getting slot j will be r_j(v_i - p_i) where p_i is the price charged to bidder i per clickthrough and r_j is a publically known clickthrough rate for slot j.

Lectures

August 25. Introduction. Games and solution concepts. Solving 0-sum games. Reading material: Ferguson: Game theory
August 28. More on matrix games. Generalized matrix games. Dominated Strategies. Exploitable strategies. We have covered all that I want to cover from Ferguson, Chapters 1-4 by now.
September 1. Problems.
September 4. Extensive form games. Ferguson, Chapter 5.
September 8. Sequence form. Reading material: Fast algorithms for finding randomized strategies in game trees. Afterwards, we began discussion on non-zero sum games. After looking at "Coordination" and "Chicken", we introduced the important notion of incomplete information games. A source for all the formal definitions were requested. Lecture notes containing the formal definitions of all the game classes we look at can be found at: virtualperfection.com. The definitions today are in Chapter 1, 3.1 and 6.1. These notes are in general very good and are recommended reading, but making notes of the definitions at the lectures may also be sufficient to proceed (that is, we are not going to cover these notes).
September 11. The above problems.
September 15. Guest lecture by Troels Bjerre Sørensen, world champion of computer poker (see here) ....on computer poker. Troels will be covering some of the same material as he did on the Tuesday session here. There is a lot of it, so please consider it background reading for you to browse.
September 18. Troels will continue talking about poker bots
September 22. We found the mixed equilibrium of "Chicken" and talked about how to interpret mixed equilibria as "equilibra of beliefs" rather than as active randomization. We found a Nash equilibrium of a single item, first price, sealed bid auction with two bidders. We shwoed that the Brouwer fixed point theorem implies the Nash equilibrium theorem following these course notes of Eva Tardos: Note 1 and Note 2. We proved the Sperner lemma and was just about to prove that it implies the Brouwer fixed point theorem.
September 25. Nash Eq. theorem, continued. Also, we talk about Nash eq. from a computational complexity perspective, introducing the class PPAD, following this talk by Paul Goldberg.
September 29. Combinatorial auctions, following these notes by Tim Roughgarden.
October 2. The above problems and more from Roughgarden's notes. Also, we will look at algorithmic mechanism design in a broader perspective taking examples from Nisan, Algorithms for selfish agents. We covered the two examples in section 5.2 and 5.3 - the entire exposition is recommended reading (for more details see Nisan and Ronen, Algorithmic mechanism design.)
October 6. After finishing the discussion of the LOS auction, we discuss revenue maximization using these notes by Jason Hartline (we covered Section 1)
October 9. Optimal Bayesian auctions (Myerson's mechanism) and non-Bayesian revenue maximization in digital goods auctions, using Hartline's notes (Section 2 and 3).
October 30. Recap. Recursive and stochastic games (Ferguson, Section 6). Also, we shall look at perfect information recursive and stochastic games from an algorithmic point of view following:Condon, Gurvich and Miltersen and Andersson et al.
November 3. continued...
November 6. We start looking at imperfect information stochastic games and consider the asoociated algorithmic problems. In addition to Ferguson's chapter, we will in particular look at the algorithm of Alfaro et al for determining which positions in a concurrent reachability game have value one.
November 10. Project discussions. Also, the "Big match" is discussed (handout).
November 13. Project discussions
November 17. Guest lecturer: Orestis Telelis. Cost sharing mechanisms. Material for Orestis' lectures is here.
November 20. Guest lecturer: Orestis Telelis. Cost sharing mechanisms.
November 24. Guest lecturer: Orestis Telelis. Cost sharing mechanisms.
November 25. The Center for Algoritmic Game Theory is co-organizing the DORS day on applications of OR. Students are encouraged to sign up.
November 27. Hardness and easyness of approximating minimax strategies in 3-player games, following Borgs et al Borgs et al og Hansen et al..
December 1. After finishing minmax strategies in 3-player games, we consider Position auctions, following Varian.
December 4. Before concluding the discussion of Varian, we talk about the projects.
December 8. Combinatorial game theory, following These other notes of Ferguson,
December 11. Combinatorial game thoery and wrapup.
Decemember 15. No class. Have fun with the projects.