Game Theory and Algorithms ‒ Disopt ‐ EPFL

Instructor	David Pritchard
Language	English

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).

Format

The meetings take place twice a week. Most meetings will be lectures but approximately twice per month there will be an exercise session, where we review solutions to exercises given in lecture. At the end of the term, each student will give a ~40 minute presentation on a topic of their choice related to the material covered in the course.

Time and location (starting Feb 22):

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.

You do not need a textbook for the course: we will cover the material in lecture and post notes as each lecture takes place.

The course code is MATH-764. This is a 4-credit doctoral course.

Course Contents

Strategic Games

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

Extensive Games

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

Auctions

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

5/10 (17) Network Games and Quality of Equilibria
5/12 (18) Routing Games and Potentials

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

Student Presentations

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.)

Prerequisites

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.

Contact Information

David Pritchard, [email protected], Office hours available upon appointment

Presentation Suggestions

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.