
CS 573: Topics in Algorithms 
Algorithmic Game Theory

Spring 2008

Course Summary
Algorithmic Game Theory is study of topics at the interface of
theoretical computer science, game theory and economics. There has
been a recent surge of interest in this area, partly due to the
emergence of large scale ecommerce and sponsored search auctions at
search engines. This course will be a broad graduatelevel
introduction to this area. Topics of interest are: auctions,
existence and computation of equilibria in games and markets,
algorithmic mechanism design, price of anarchy and price of stability,
games relevant to networks and ecommerce. The emphasis will be on
conceptual ideas and algorithmic aspects. No familiarity with
game theory or economics will be assumed.
Administrative Information
Lectures: Wed, Fri 1112:15 in Siebel Center
1304.
Instructor: Chandra Chekuri 3228 Siebel Center,
2650705, chekuri at cs dot uiuc dot edu
Office Hours: by appointment.
Grading: 23 Homeworks, scribe 12 lectures, present
a research paper with a report. A sample tex file
for scribing.
Prerequisites: This is a
graduate level class and a reasonable background in algorithms and
discrete mathematics would be needed. Knowledge of some probability and linear
programming would be useful. No knowledge of game theory will be assumed.
Attempt will be made to make the material
accessible
to nontheory students who might be interested in applications. Consult the
instructor if you have questions.
Study material
 Recommended text book: Algorithmic Game Theory, Edited by NisanRoughgardenTardosVazirani, Cambridge University Press, 2007. Online nonprintable copy available here. Errata in the first printing.

Other useful books: Combinatorial Auctions, CramptonShohamSteinberg, MIT Press, 2006. Auctions: Theory and Practice, Paul Klemperer. Auction Theory, Vijay Krishna, Academic Press, 2002.
 Books on algorithms and related topics: Algorithm Design (KleinbergTardos), Approximation Algorithms (Vazirani), Combinatorial Optimization (Schrijver), Randomized Algorithms
(MotwaniRaghavan)
 Lecture notes from various
places: Tim Roughgarden (Stanford), Noam Nisan (Hebrew U), Ron Lavi (Technion), EasleyKleinberg (Cornell), Eva Tardos (Cornell),
Michael Kearns (U. Penn),
Adrian Vetta (McGill), Christos Papadimitriou(Berkeley)
.
 Collection of Lecture Notes: Game Theory.net
Tentative Topic List
Not all of the topics below will (can) be covered.
 Strategic Games, Nash Equilibria (proof of existence), Correlated Equilibria, Bayesian Nash equlibria, Potential and Congestion Games
 Price of Anarchy and Price of Stability: Analysis for games in
Scheduling, Routing, Network Design and Facility Location

 Basics of Social Choice Theory: Impossibility theorems of
Arrow and GibbardSatterthwaite

 Algorithmic Mechanism Design: Vickery auction, VCG mechanism,
examples, revelation principle, mechanisms with approximation algorithms, example of
mechanism without money
 Intro to auction theory: revenue equivalence theorem, optimal auctions, competitive auctions, sponsered search auctions
 Cooperative game theory and group strategyproof cost sharing
 Basics of market equilibria and algorithms for special cases
 Other topics: complexity of computing equilibria (PPAD), convergence
to equilibria in congestion games (PLS completeness),
Homework
Lectures
 Wed, 1/16/08: Introduction. Vickery auction, Selfish Routing, Cost sharing
for Multicast, simple 2player games towards definition of Strategic Games.

Fri, 1/18/08: Definitions of a Strategic game, pure and mixed Nash equilibria,
existence of pure and mixed Nash equilibria. Proof of
rational mixed equilibria in 2player games.

Wed, 1/23/08: 2player zerosum games and Minmax theorem. Application to
lower bounds for randomized algorithms (Yao's lemma). Proof of Nash's theorem
assuming Brouwer fixed point theorem.
 Notes
 Minmax theorem: Chapter 1 of textbook and Chapter 15 of V. Chvatal: Linear Programming, W. H. Freeman & Co.
 Yao's lemma and application to lower bounds for randomized algorithms.
See R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge Univ Press.
 Proof of Nash's theorem. Eva Tardos lecture notes and below.
 J. Geanakoplos, Nash and Walras Equilibrium Via Brouwer, Economic Theory 21(23):585603, 2003.

Fri, 1/25/08: Intro to inefficiency of equilibria. Price of Anarchy and
Price of Stability. Load Balancing game on identical machines.
 Notes
 Chapters 17 and 20 from textbook and references therein.

Wed, 1/30/08: Price of Anarchy for load balancing on related machines.
Lower bound for PofA for mixed equilibria on identical machines.
Mention coordination mechanisms and state some known results including
improvement in PofA for LongestFirst.
 Notes
 Chapter 20 from textbook.
 G. Christodoulou, E. Koutsoupias, and A. Nanavati.
Coordination mechanisms. ICALP 2004.
 N. Immorlica, L. Li, V. Mirrokni, A. Schulz:
Coordination Mechanisms for Selfish Scheduling. WINE 2005.
 Y. Azar, K. Jain, V. Mirrokni. Optimal Coordination Mechanisms for Selfish Scheduling. SODA 2008.

Fri, 2/1/08: Brouwer's fixed point theorem via Sperner's lemma.
 Notes
 Chapter 22, Section 6 of
Proofs from THE BOOK, 3rd Edn by AignerZiegler. SpringerVerlag.

Wed, 2/6/08: PoA and PoS of a Network design game with Shapley cost
sharing. Congestion games and Rosenthal's potential function. Weighted
Shapley games and mention known results on approximate Nash equilibria.
 Notes
 Chapter 19 of textbook.
 H. Chen and T. Roughgarden. Network Design with Weighted Players, SPAA 2006.
 H. Chen, T. Roughgarden, G. Valiant. Designing Networks with Good Equilibria, SODA 2008.

Fri, 2/8/08: Selfish Routing. Nonatomic case. Wardrop equilibria, existence
and PoA using potential function.

Wed, 2/13/08: Selfish Routing continued. Optimality of the Pigou bound.
Two proofs. Describe Braess paradox.
 See refs for previous class.

Fri, 2/15/08: Selfish Routing continued. Reducing PoA: send half the
optimal flow (or increase capacity), Stackleberg strategies, tolls/taxation.
Atomic games: existence and nonexistence of pure equlibria, bound on PoA
for affine cost functions.

Wed, 2/20/08: Intro to auctions and algorithmic mechanism design. Single
item auctions, Vickrey auction and its properties. Statement of Arrow's theorem.

Fri, 2/22/08: Combinatorial auctions and VCG mechanism. Examples.
 Notes
 Tim Roughgarden's excellent notes on combinatorial auctions.
 Chapter 9 of text book, especially examples in Section 9.3.5. Note: Example 9.3.5.5 Public Project claims that payments never exceed C but this
is true only with nonnegative valuations.

Wed, 2/27/08: Singleminded bidders and a truthful nonVCG mechanism for approximating social welfare.
 Notes
 Tim Roughgarden's excellent notes on combinatorial auctions.
 Section 11.2 of text book.

Fri, 2/29/08: Truthful mechanism for approximating social welfare with
singleminded bidders. LP Relaxation for social welfare and Walrasian
equilibrium.
 Notes
 Chapter 11 of text book.

Wed, 3/5/08: LP Relaxation for social welfare and Walrasian equlibrium.
Matching markets. Describe randomized truthful mechanism for submodular/subadditive bidders.

Fri, 3/7/08: Formal aspects of mechanism design. GibbardSatterthwaite
impossibility theorem. Truthful direct revelation
mechanisms and possibility/impossibility results.

Wed, 3/12/08: Formal aspects of mechanism design continued. Implementation
issues and the revelation principle.

Fri, 3/14/08: Mechanisms without money. Singlepeak preferences, house
allocation, stable matchings.
 Notes
 Chapter 10 of text book. Note: The TTC algorithm in the text book is described incorrectly, correction can be found in errata.
 Application of house allocation and toptrading cyle ideas for
kidney exchange. See Alvin Roth's page on game theory, experimental economics and market design.

Wed, 3/19/08 and Fri, 3/21/08: Spring break.

Wed, 3/26/08: First and Second price auctions in the Bayesian setting.
 Notes
 Chapter 2 of Vijay Krishna's book on Auction Theory.
 Ron Lavi's lecture notes (see lectures 1 and 2).

Fri, 3/28/08: Revenue equivalence theorem for symmetric singleitem auctions.
Examples of payall and thirdprice auctions and their equilibria. Start of
Bayesian optimal mechanism design.
 Notes
 Chapter 3 of Vijay Krishna's book on Auction Theory.
 Chapter 9 of text book. See revenue equivalence theorem in Bayesian setting.
 Ron Lavi's lecture notes (see lectures 13).

Wed, 4/2/08: Recap of mechanism design. Proof of characterization
of truthful in expectation mechanisms for singleparameter case.
Start of derivation of Myerson's optimal mechanism.
 Notes
 Chapters 9 and 13 of text book.
 Jason Hartline's lecture notes on optimal mechanism design.
 Ron Lavi's lecture notes (see lectures 13).

Fri, 4/4/08: Myerson's optimal mechanism in the Bayesian setting.
Basics of priorfree and competitive auctions.
 Notes
 Chapter 13 of text book.
 Jason Hartline's lecture notes on optimal mechanism design.
 Ron Lavi's lecture notes (see lectures 15).

Wed, 4/9/08: Priorfree and competitive auctions for digital goods. Start of
sponsored search auctions.
 Notes
 Chapters 13, 28 of text book.
 Jason Hartline's lecture notes on optimal mechanism design.
 Two papers on sponsered search auctions (see links below on topics)

Fri, 4/11/08: Sponsored search auctions.
 Notes
 Chapter 28 of text book.
 Two papers on sponsered search auctions (see links below on topics)

Wed, 4/16/08: Cooperative games and costsharing.
 Notes
 Chapter 15 (and bit of Chapter 14) from text book.

Fri, 4/18/08: Crossmonotonic costsharing schemes and group strategy proof mechanism design.
 Notes
 Chapter 15 from text book.

Wed, 4/23/08: Shapley value for costsharing and overview of market equilibria.
 Notes
 Chapter 15 from text book for Shapley value.
 Chapters 5,6 from text book for market equilibria.

Fri, 4/25/08: no class.

Wed, 4/30/08: Proportional allocation mechansim for resource sharing. Course review.
 Chapter 21 from the text book.
Topics for Reports
 Severity of Braess's paradox in selfish routing
 Taxation and tolls for selfish routing
 Convergence to equilibria in routing and congestion games
 PPAD and hardness of computing Nash equilibria
 See Chapter 2 in text book and references.
 Correlated equilibria and complexity of computing them
 Algorithms for market equilibria
 See Chapters 5 and 6 in text book and references.
 Sink equilibria and their properties
 Mechanism Design for Social Welfare
 Frugality in Mechanism Design
 Mechanism Design for Revenue
 Sponsered Search Auctions
 Cost Sharing.