Game Theory and Algorithms
This doctoral course offers a broad introduction to game theory (models of competition, cooperation and multi-party decision-making) from an algorithmic perspective. We begin from scratch and cover interesting results in several game-theoretic models. Some results give insight into real-life situations (e.g., finite vs infinitely repeated games), some are useful in practice (e.g., auctions) and others show what kind of properties in a model are reasonable/unreasonable or possible/incompatible (e.g., voting models).
- 10:15-12:00 Tuesdays in MA A1 10 (except CM 010 for Mar 22)
- 10:15-12:00 Thursdays in MA A3 30
News: Lecture will be cancelled on the last day of class (May 31). In place of this, the last exercise session will be made optional and moved to the morning of Monday May 23, 10:15-12:00 in MA A3 31.
- 2/22 (1) Prisoner's dilemma, dominated actions, iterated elimination
- 2/24 (2) Best responses, Nash equilibria, examples, oligopoly
- 3/1 (3) Weakly dominant strategies, auctions, elections
- 3/3 Exercises 1
- 3/8 (4) Mixed strategies, mixed equilibria, and Nash's theorem
- 3/10 (5, scan only) Efficient algorithm for Nash Equilibria in 2-player zero-sum games (LP Duality)
- 3/15 (6, and scan) Algorithm for Nash Equilibria in 2-player games (Lemke-Howson)
- 3/17 (7) Topological proof of Nash's theorem, and PPAD-hardness (neat: Sperner's applet)
- 3/22 Exercises 2
- 3/24 (8, and scan) Introduction, subgame-perfect equilibria (thanks to Dejan Novakovic for scribing!)
- 3/29 (9) Repeated games and infinitely repeated games
- 3/31 (10) Incomplete information, modelling mixed strategies, critiques of backwards induction
- 4/5 Exercises 3
- 4/7 (11, and scan) Cake-cutting; and the VCG mechanism (thanks to Andres Ruiz-Vargas for scribing!)
- 4/12 (12) More about VCG; fractional VCG via approximation algorithms
- 4/14 (13) Revenue maximization (for known bidder distributions)
- 4/19 (14) Revenue maximization (for unknown bidder distributions)
- See also the video "How to Think About Mechanism Design," Tim Roughgarden
- 4/21 Exercises 4
Social Choice / Elections
- In the news: May 5, the UK has a referendum on voting systems
- 5/3 (15) Elections and Arrow's Theorem
- 5/5 (16) Elections on a Line and in Practice
Social Cost of Equilibria
Impartial Combinatorial Games
- 5/17 (19) Algorithm for perfect play via the Sprague-Grundy theorem
- 5/23 (Monday) Exercises 5. Optional! 10:15-12:00 AM in MA A3 31
- 5/26 Chomp tournament and strategy-stealing proof
- 5/19 Jean-Benoît (regret minimization as a solution concept) reference
- 5/19 Dejan (complexity in elections) references: 1 2 3
- 5/24 Andres (selfish load balancing) from Nisan et al, Chapter 7 (Michael Kearns)
- 5/24 Leo (graphical games) from Nisan et al, Chapter 20 (Berthold Vöcking)
- 5/26 Christian (dueling algorithms) reference (Note from DP: data in graphs about algorithm performance is work of the presenter, not part of the original paper, do not reuse without permission.)
We will deal frequently with probability (e.g. expected values), algorithms, and proofs, so students should be comfortable with these concepts. In a few places we will use linear programming and students who have seen the simplex algorithm will be at an advantage when we discuss the Lemke-Howson algorithm. There is a little bit of calculus in the sections on auctions and network games. You can contact me if you want a better idea of whether the course suits your situation.
One well-written explanation of the simplex algorithm is Sections 2-5 of these lecture notes by Vempala.
- A comprehensive source of ideas is Algorithmic Game Theory by Nisan et al, 2007
- Strategic and Extensive Games
- On the Equivalence of Linear Programming Problems and Zero-Sum Games. We saw a reduction from solving zero-sum two-player games to linear programming in class. This paper shows the reverse is possible, fixing a very old faulty folklore result.
- On Equilibria in Finite Games, A classical exact algorithmic reduction from n-player Nash Equilibria to 3 players.
- The Myth of the Folk Theorem. The "folk theorem" characterizes SPEs in repeated games (in short, there are a lot of them). This paper shows that several related problems are computationally difficult.
- Dueling Algorithms. A model where algorithms do not want to maximize their objective value, but just want to "win" as often as possible.
- Mechanisms and Auctions
- Cutting Cake Really is Not a Piece of Cake and Balanced Allocations of Cake. These papers give upper and lower bounds on the number of queries needed for a mechanism to cut a cake fairly.
- On Optimal Single-Item Auctions. This shows how to design (near-)optimal auctions when two bidders use arbitrary correlated distributions. It gives an approximation algorithm for more than 2 players, or APX-hardness, depending on the desired solution concept.
- Optimal Auctions with Correlated Bidders are Easy. Related to the previous paper, and gives a new analysis extending a classic result of Ronen showing how to design approximately-optimal auctions for many bidders.
- Bayesian Algorithmic Mechanism Design. If you can approximately solve an optimization problem when the inputs come from some known independent distriibutions, you can turn it into a truthful auction while still approximating social welfare just as well.
- Arrow's Theorem and Social Choice
- Recognizing interval matrices or acyclic hypergraphs. These are classical algorithms in combinatorics which are related to Black's condition.
- Voting Systems What voting systems are used in practice?
- Using Complexity to Protect Elections. A survey about manipulability of voting systems, which could be the subject of a talk, and which has lots of references.
- Social Cost of Equilibria
- There are some good topics in Algorithmic Game Theory such as cost-sharing games.
- Impartial Combinatorial Games
- Additive Periodicity for Wythoff’s Game. Shows that a particular impartial combinatorial game has a nice structure, using finite automata in the proof.
- Master/Diploma/Bachelor/Semester Theses
- Spring 2011 Courses
- Fall 2010 Courses
- Spring 2010 Courses
- Fall 2009 Courses
- Spring 2009 Courses
- Fall 2008 Courses
Final presentations will take place May 19, 24, 26. Each presentation will be 45 minutes long (1/2 a lecture period).
Proposals are due April 19 and should include:
-- proposed title and brief (~5 sentences) description of what you will cover
-- pointer to one paper/book chapter which is the subject
You will get feedback on the content, clarity, timing/organization, and impact of your presentations.
For topics, there is a list of some suggestions below, or you can propose something else.