CSCE 689: Special Topics in Algorithmic Game Theory
As our world becomes increasingly connected, the mutual effect we have on each other's decisions and actions is ever more pronounced. Game Theory models the strategic interaction of multiple people (players, agents or users of a system). Algorithmic Game Theory merges computation with economic reasoning in order to better understand and improve the strategic interaction that occurs in the complex systems that surround us: the Internet, telecommunication and transportation networks, social networks, online markets, etc.
This class will provide an introduction to Algorithmic Game Theory, as well as survey state-of-art research in the field. Sample topics include: Strategic Form Games (Matrix and continuous games. Nash Equilibrium, Mixed and correlated equilibrium. Supermodular games. Potential/congestion games.); Learning, Evolution, and Computation; Extensive Games with Perfect Information (Subgame Perfect Equilibrium, Bargaining games); Repeated Games; Games with Incomplete Information; Mechanism Design and Auction Theory; Network Effects and Games over Networks; Price of Anarchy; Matchings; Social Networks.
There is a significant dynamic component to the course, as topics drop
in and out, or get longer or shorter treatment, depending on audience
interest/reaction/resistence. Given this, here is a rough outline of the course material:
- Professor: Evdokia Nikolova. Office: HRBB 515A.
Office Hours: Tuesdays 12:25-1:25 pm or send me an email.
- Lecture: Tuesday-Thursday 11:10-12:25 pm @ HRBB 302. Classroom change on April 17, 2012 to HRBB 425A
- Textbook: There is no required textbook; however, the following texts may be helpful:
- A course in game theory by Martin J. Osborne and Ariel Rubinstein (MIT Press, 1994). Free electronic copy available
- An introduction to game theory by Martin J. Osborne (Oxford University Press, August 2003). More info
- Algorithmic Game Theory, edited by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (Cambridge University Press, 2007).
Non-printable electronic copy available here.
Additional relevant research papers and surveys will be posted as the class develops the list.
- Prerequisites: A course in algorithms (CSCE 411 or equivalent), mathematical maturity.
- 25% from homework problems;
- 25% from a midterm exam;
- 20% from class participation;
- 30% from a final project: this could either be a survey, or original research; students will be encouraged to collaborate and to relate the project to their own research interests.
- Strategic Form Games (Matrix and continuous games; Nash Equilibrium; Mixed and correlated equilibrium; Computation);
- Supermodular games;
- Potential games, congestion games, Price of Anarchy;
- Learning, Evolution, and Computation; No-regret algorithms;
- Extensive Games with Perfect Information (Subgame Perfect Equilibrium; Bargaining games);
- Repeated Games;
- Games with Incomplete Information;
- Mechanism Design and Auction Theory (First and Second Price Auctions; Optimal Mechanisms; Revenue Equivalence);
- Algorithmic Mechanism Design (VCG Mechanism, cost sharing, combinatorial auctions);
- Sponsored Search Auctions;
- Network Effects and Games over Networks;
- Strategic Network Formation.
- Social Networks.
LaTeX: Feel free to use the following template for writing your assignments in LaTeX. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here which results in the following pdf.
- Lecture 1 (January 17, 2012): Course overview. Nash Equilibria.
- Lecture 2 (January 19, 2012): Existence of Nash equilibria in two-player zero-sum games via LP Duality.
Daskalakis's lecture notes.
- Lecture 3 (January 24, 2012): Continued: Existence of Nash equilibria in two-player zero-sum games via LP Duality. Second half of notes above.
- Lecture 4 (January 26, 2012): Strategic form games. Nash equilibria in separable multiplayer zero-sum games.
Daskalakis's lecture notes.
- Lecture 5 (January 31, 2012): Fictitious play.
First three pages of the following lecture notes.
- Lecture 6 (February 2, 2012): Learning from expert advice.
Second half of the following lecture notes.
- Lecture 7 (February 7, 2012): Multiplicative weights updates with application to two-player zero-sum games.
See these notes.
- Lecture 8 (February 9, 2012): Nash's Theorem (see the previous lecture notes). Potential games.
- Dov Monderer and Lloyd S. Shapley. "Potential Games", Games and Economic Behavior 14, pp. 124--143 (1996).
- Lecture 9 (February 14, 2012): Potential games continued; Congestion games.
- Lecture 10 (February 16, 2012):
Network Congestion Games. Wardrop Equilibrium; Nash flow; Social Optimum; Price of Anarchy.
- Lecture 11 (February 21, 2012):
- Lecture 12 (February 23, 2012): No lecture; make-up lecture held on Feb. 13, 2012 on "Prediction Markets."
- Lecture 13 (February 28, 2012):
- Lecture 14 (March 1, 2012): Network design; Algorithms for computing equilibria in congestion games. Lipton-Markakis-Mehta algorithm for computing approximate equilibria.
- Lecture 15 (March 6, 2012): No-regret learning in congestion games. Guest lecture by Dr. Georgios Piliouras, Georgia Tech.
- Lecture 16 (March 8, 2012): Lemke-Howson algorithm for equilibria computation.
- Lecture 17 (March 20, 2012): Introduction to Mechanism Design. First and second-price auctions.
- Lecture 18 (March 22, 2012): First-price auctions. Revenue equivalence for standard auctions.
- Lecture 19 (March 27, 2012): Direct mechanisms; Incentive-compatible mechanisms.
- Lecture 20 (March 29, 2012): Revelation principle, revenue equivalence, Incentive compatibility, Individual rationality.
- Lecture 21 (April 5, 2012): Optimal mechanism design.
- Lecture 22 (April 10, 2012): VCG Mechanisms.
- Lecture 23 (April 12, 2012): Application of the VCG Mechanism to Interdomain routing.
- Lecture 24 (April 17, 2012): The Generalized Second Price Auction with application to Sponsored Search. My notes.
- Lecture 25 (April 19, 2012): Matchings. Guest lecture by Prof. Nicole Immorlica, Northwestern University.
- Lecture 26,27 (April 26, 2012): Final Project Presentations.
Some classes with overlapping topics at other universities: