UIUC
Computer Science Department

CS 573: Topics in Algorithms - Algorithmic Game Theory

Chandra Chekuri

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 e-commerce and sponsored search auctions at search engines. This course will be a broad graduate-level 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 e-commerce. 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 11-12:15 in Siebel Center 1304.

Instructor:  Chandra Chekuri- 3228 Siebel Center, 265-0705, chekuri at cs dot uiuc dot edu

Office Hours: by appointment.

Grading: 2-3 Homeworks, scribe 1-2 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 non-theory students who might be interested in applications. Consult the instructor if you have questions.

Study material

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 Gibbard-Satterthwaite
  • 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 strategy-proof 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 2-player 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 2-player games.

  • Wed, 1/23/08: 2-player zero-sum 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(2-3):585--603, 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 Aigner-Ziegler. Springer-Verlag.

  • 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. Non-atomic 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 non-existence 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 non-negative valuations.

  • Wed, 2/27/08: Single-minded bidders and a truthful non-VCG 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 single-minded 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. Gibbard-Satterthwaite 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.
    • Chapter 9 of text book.

  • Fri, 3/14/08: Mechanisms without money. Single-peak 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 top-trading 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 single-item auctions. Examples of pay-all and third-price 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 1-3).

  • Wed, 4/2/08: Recap of mechanism design. Proof of characterization of truthful in expectation mechanisms for single-parameter 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 1-3).

  • Fri, 4/4/08: Myerson's optimal mechanism in the Bayesian setting. Basics of prior-free 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 1-5).

  • Wed, 4/9/08: Prior-free 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 cost-sharing.
    • Notes
    • Chapter 15 (and bit of Chapter 14) from text book.

  • Fri, 4/18/08: Cross-monotonic cost-sharing schemes and group strategy proof mechanism design.
    • Notes
    • Chapter 15 from text book.

  • Wed, 4/23/08: Shapley value for cost-sharing 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