
Game theory studies mathematical models of the interaction of multiple agents, where each agent is rational. In a highly connected world where large populations commonly interact, game theory finds applications both in the analysis and design of systems.
This is an introductory course, and our goal in this course is to understand the fundamentals of game theory, particularly focusing on algorithmic aspects. We will introduce a number of widelystudied games, and analyse equilibria and related problems in their context. Topics that I plan to cover include: games and their representation; equilibria and notions of stability; zerosum games; bimatrix games; potential games; learning dynamics and convergence to equilibria; games on networks; price of stability and price of anarchy; auctions and mechanism design; computational social choice and fairness. 

While most of the course will be selfcontained, some lectures will require a basic course in algorithms, linear programming, and complexity theory. You should know how to write concise and correct mathematical proofs. 

Classes will be held Mon/Wed 23:30 pm in A201.
Classes begin on August 17th. 

Although most of what we cover is available in the reference materials below, we won't be following any particular book or set of notes too closely. I will be uploading lecture notes following the lecture.



Rationality, Prisoner's Dilemma and dominant / dominated strategies. Game notation. IRDS game and Iterated Removal of Dominated Strategies. The Canteen game and pure strategy Nash equilibria.
References: Slides by Tayfun Sonmez until slide 20, for a good description of dominance and the classical games we talked about.  
Mixed Strategies, Nash's Theorem, and Zerosum Games.  
Computing equilibria in zerosum games via LP duality.  
Symmetric games and the LemkeHowson algorithm. An example.
Reference: Chapter 2 from the AGT book (which also has the example above).  
A proof of Nash's Theorem.
 
A proof of Brouwer's FixedPoint Theorem and Sperner's Lemma.
 
The complexity of finding a Nash equilibrium.
 
Fictitious play and coarse correlated equilibria.
 
Algorithms for no external regret, and correlated equilibria.
 
An algorithm for no internal regret. Best response dynamics, network congestion games, and potential games.
 
PLS, PLScompleteness, and complexity of pure Nash equilibrium computation.
 
Price of Anarchy and Price of Stability in congestion games and global connection games.
 
PoA and PoS in facility location and valid utility games.
References: Sections 19.3 and 19.4 from the AGT book.
 
Smooth games, and PoA and PoS in load balancing games.
References: For smooth games, Tim's notes lecture 14, particularly Sections 3 and 4. For selfish loadbalancing games, Chapter 20 from the AGT book, and in particular Theorem 20.7. I would recommend reading the proof of existence of PNE (Proposition 20.3) as well.
 
Mechanism design. Condorcet's paradox and Arrow's impossibility theorem.
References: AGT book, Chapter 9 until section 9.2.4.
 
Social choice functions, and the GibbardSatterthwaite theorem. Cardinal mechanisms with money, and Vickrey's second price auction.
References: AGT book, Chapter 9 until Section 9.3.1.
 
Cardinal mechanisms with money more formally, DSIC mechanisms, the Revelation Principle. Single parameter domains and Myerson's Lemma.
References: Tim Roughgarden's notes for lecture 3.
 
Proof of Myerson's Lemma. Sponsored search auctions, multiunit auctions, and knapsack auctions.
References: Tim Roughgarden's notes for lecture 4.
 
Revenue maximization in Bayesian auctions.
References: Tim Roughgarden's notes for lecture 5
 
Simple nearoptimal auctions.
References: Tim Roughgarden's notes for lecture 6
 
Multiparameter mechanism design.
References: Tim Roughgarden's notes for lecture 7
 
Maximalinrange mechanisms.
References: The paper "Mechanisms for multiunit auctions" by Dobzinski and Nisan, available here , particularly Section 3.2.
 
Truthful mechanisms without money: housing allocation and kidney exchange.
References: Tim Roughgarden's notes for lecture 9 and lecture 10
 
Stable matching.
References: Tim Roughgarden's notes for lecture 10
 
Fair division of indivisible goods. 


