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.

**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 here.*An introduction to game theory*by Martin J. Osborne (Oxford University Press, August 2003). More info here.*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.

**Assessment:**- 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.
- Matchings;
- Social Networks.

**Lecture 1**(January 17, 2012): Course overview. Nash Equilibria. Slides pptx, pdf.**Lecture 2**(January 19, 2012): Existence of Nash equilibria in two-player zero-sum games via LP Duality. My notes. 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. My notes. 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. Scribe notes. Suggested reading:- Dov Monderer and Lloyd S. Shapley. "Potential Games",
*Games and Economic Behavior*14, pp. 124--143 (1996).

- Dov Monderer and Lloyd S. Shapley. "Potential Games",
**Lecture 9**(February 14, 2012): Potential games continued; Congestion games. Scribe notes.**Lecture 10**(February 16, 2012): Network Congestion Games. Wardrop Equilibrium; Nash flow; Social Optimum; Price of Anarchy. My notes. Scribe notes.**Lecture 11**(February 21, 2012): Midterm review.**Lecture 12**(February 23, 2012): No lecture; make-up lecture held on Feb. 13, 2012 on "Prediction Markets."**Lecture 13**(February 28, 2012): Midterm.**Lecture 14**(March 1, 2012): Network design; Algorithms for computing equilibria in congestion games. Lipton-Markakis-Mehta algorithm for computing approximate equilibria. Scribe notes. Suggested reading:- Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar, "The Complexity of Pure Nash Equilibria". In Proc. of STOC 2004, pages 604-612.
- R. J. Lipton, E. Markakis, A. Mehta. "Playing Large Games using Simple Strategies." ACM Conference on Electronic Commerce (EC), pp. 36-41, 2003.

**Lecture 15**(March 6, 2012): No-regret learning in congestion games. Guest lecture by Dr. Georgios Piliouras, Georgia Tech. Scribe notes.**Lecture 16**(March 8, 2012): Lemke-Howson algorithm for equilibria computation. Scribe notes.**Lecture 17**(March 20, 2012): Introduction to Mechanism Design. First and second-price auctions. Scribe notes.**Lecture 18**(March 22, 2012): First-price auctions. Revenue equivalence for standard auctions. Scribe notes.**Lecture 19**(March 27, 2012): Direct mechanisms; Incentive-compatible mechanisms. Scribe notes.**Lecture 20**(March 29, 2012): Revelation principle, revenue equivalence, Incentive compatibility, Individual rationality. Scribe notes.**Lecture 21**(April 5, 2012): Optimal mechanism design. Scribe notes.**Lecture 22**(April 10, 2012): VCG Mechanisms. Scribe notes.**Lecture 23**(April 12, 2012): Application of the VCG Mechanism to Interdomain routing. My notes.**Lecture 24**(April 17, 2012): The Generalized Second Price Auction with application to Sponsored Search. My notes. My notes.**Lecture 25**(April 19, 2012): Matchings. Guest lecture by Prof. Nicole Immorlica, Northwestern University. Slides.**Lecture 26,27**(April 26, 2012): Final Project Presentations.

Some classes with overlapping topics at other universities:

- Topics in Algorithmic Game Theory by Costis Daskalakis;
- Algorithmic Game Theory by Eva Tardos;
- Algorithmic Mechanism Design by Jason Hartline;
- Market Design by Nicole Immorlica;
- Social Networks 101 by Jason Hartline and Nicole Immorlica;