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.

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

**Lecture 1**(August 26, 2013): Course overview. Nash Equilibria. Slides pptx.**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 notes.**Lecture 5**(September 11, 2013): Fictitious play. Lecture notes.**Lecture 6**(September 13, 2013): Fictitious play continued. Lecture notes.**Lecture 7**(September 16, 2013): Multiplicative Weights Updates. Lecture notes.**Lecture 8**(September 18, 2013): Multiplicative Weights Updates and learning in games. Lecture notes.**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 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 10**(September 27, 2013): Potential games continued. Lecture notes.**Lecture 11**(October 2, 2013): Application of potential games to network design. Lecture notes.**Lecture 12**(October 2, 2013): Network Congestion Games. Wardrop Equilibrium; Nash flow; Social Optimum; Price of Anarchy. Lecture notes; Slides (pdf); Slides (pptx).**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*. Preliminary version.

- E. Nikolova and N. Stier-Moses. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times", forthcoming in
**Lecture 14**(October 16, 2013): Computing approximate Nash equilibria in two-player games. Lecture notes. Suggested reading (see Theorem 1):- 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**(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 notes.**Lecture 24**(November 27, 2013): VCG Mechanisms. Lecture notes.**Lecture 25,26**(December 2, 2013): Final project presentations. Schedule.

Background material: 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;