CSCE 489/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.
- No lecture on Monday, September 9, 2013. Replacement lecture on Friday, September 13, 2013 at 01:40 pm-02:55 pm @ HRBB 126.
- Homework 1 is out, due Friday, September 13, 2013 at the beginning of class.
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: Mondays 3-5 pm or send me an email.
- Lecture: MW 01:40 pm-02:55 pm @ HRBB 126.
- 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.
- 20% from homework problems;
- 30% 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 (August 26, 2013): Course overview. Nash Equilibria.
- Lecture 2 (August 28, 2013): Strategic Form Games. Nash Equilibria.
Section 1 of these lecture notes.
- Lecture 3 (September 2, 2013): Existence of Nash equilibria in two-player zero-sum games via LP Duality.
Section 2 of these lecture notes.
- Lecture 4 (September 4, 2013): Strategic form games. Nash equilibria in separable multiplayer zero-sum games.
- Lecture 5 (September 11, 2013): Fictitious play.
- Lecture 6 (September 13, 2013): Fictitious play continued.
- Lecture 7 (September 16, 2013): Multiplicative Weights Updates.
- Lecture 8 (September 18, 2013): Multiplicative Weights Updates and learning in games.
- Lecture 9 (September 25, 2013): Proof of Nash's theorem. Potential games.
For Nash's theorem, see Section 3 of these lecture notes.
For potential games,
my notes and
- Dov Monderer and Lloyd S. Shapley. "Potential Games". Games and Economic Behavior 14, pp. 124--143 (1996).
- Lecture 10 (September 27, 2013): Potential games continued.
- Lecture 11 (October 2, 2013): Application of potential games to network design.
- Lecture 12 (October 2, 2013): Network Congestion Games. Wardrop Equilibrium; Nash flow; Social Optimum; Price of Anarchy.
- Lecture 13 (October 14, 2013): Network Congestion Games with stochastic delays and risk-averse users. Suggested reading:
- E. Nikolova and N. Stier-Moses. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times", forthcoming in Operations Research.
- Lecture 14 (October 16, 2013): Computing approximate Nash equilibria in two-player games. Lecture notes. Suggested reading (see Theorem 1):
- Lecture 15 (October 21, 2013): Games of Incomplete Information. Bayesian Nash equilibria. Lecture notes.
- Lecture 16 (October 23, 2013): Review for midterm.
- Lecture 17 (October 28, 2013): Midterm.
- Lecture 18 (November 4, 2013): Introduction to Mechanism Design. Second Price Auctions. Lecture notes (pages 1-5).
- Lecture 19 (November 6, 2013): First Price Auctions. Revenue Equivalence. Lecture notes (pages 6-10).
- Lecture 20 (November 13, 2013): The Generalized Second Price Auction with application to Sponsored Search. Lecture notes.
- Lecture 21 (November 18, 2013): Direct mechanisms; Incentive-compatible mechanisms. Lecture notes (pages 1-5).
- Lecture 22 (November 20, 2013): General revenue-equivalence principle; Individual rationality. Lecture notes (pages 6-9).
- Lecture 23 (November 25, 2013): Optimal Mechanisms.
- Lecture 24 (November 27, 2013): VCG Mechanisms.
- Lecture 25,26 (December 2, 2013): Final project presentations.
Some classes with overlapping topics at other universities: