Date

Topic

Readings

Exercises

Notes

Jan 20
Introduction; Class overview
Examples of games and pure equilibria
A global network connection game; congestion
games; and the potential function method
Price of stability
AGT Book: Foreword, Chapter 1, 19.1 and 19.3
Algorithmic Game Theory, By Roughgarden
The Price of Stability for Network Design with Fair Cost Allocation
By Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler and Roughgarden
Set 1
Note 1.pdf
By Sebastian Zimmeck
Jan 27
Convergence, approximation and complexity
of pure equilibria in congestion games; and
the complexity class PLS
Price of anarchy in selfish routing
AGT Book: Chapter 17 and 18
Convergence to Approximate Nash Equilibria in Congestion Games
By Chien and Sinclair
The Complexity of Pure Nash Equilibria
By Fabrikant, Papadimitriou and Talwar
How Easy is Local Search?
By Johnson, Papadimitriou and Yannakakis
How Bad Is Selfish Routing?
By Roughgarden and Tardos
Set 2
Note 2.pdf
By Delia Wang
Feb 3
Mixed (Nash) equilibria
Two-player zero-sum games
Minmax theorem and linear duality
AGT Book: Section 1.4
Lecture Notes on Linear Duality
By Trevisan
Game Theory, On-line Prediction and Boosting
By Freund and Schapire
When the Players Are Not Expectation Maximizers
By Fiat and Papadimitriou
Randomized Algorithms: Section 2.2, The Minimax Principle
By Motwani and Raghavan
Set 3
Note 3.pdf
By Yifu Zheng and Rui Liu
Feb 10
Existence of Mixed (Nash) equilibria
Brouwer's fixed point theorem
via Sperner's lemma
Equilibrium Points in N-Person Games
By Nash
The Nash Equilibrium: A Perspective
By Holt and Roth
The Mathematics of Strategy
By Klarreich
Sperner's Lemma and Brouwer's Fixed Point Theorem
By Wright
Atropos: The Sperner Game
By Burke and Teng
IMDB: A Beautiful Mind (2001)
Set 4
Notes 4.pdf
By Barbara Kiskovski
and Melanie Kambadur
Feb 17
Brouwer's fixed point theorem (cont.)
Approximation of Nash equilibria with
small supports
Playing Large Games Using Simple Strategies
By Lipton, Markakis and Mehta
Approximating Nash Equilibria Using Small-Support Strategies
By Feder, Nazerzadeh and Saberi
Probability Inequalities for Sums of Bounded Random Variables
By Hoeffding
Hoeffding's Inequality on Wikipedia
Set 5
Note 5.pdf
By Yundi Zhang
Feb 24
PPAD; Complexity of Nash equilibria
The Complexity of Computing a Nash Equilibrium
By Daskalakis, Goldberg and Papadimitriou
Recent Development in Computational Complexity
Characterization of Nash Equilibrium, By Chen and Deng
The Complexity of Computing a Nash Equilibrium
By Daskalakis, Goldberg and Papadimitriou
Settling the Complexity of Computing Two-player Nash Equilibria
By Chen, Deng and Teng
No exercise
Notes of a similar
lecture I gave at USC
can be found here
(The construction
there is slightly
more detailed.)
Mar 3
Finishing the reduction
Exchange markets
and existence of market equilibria
Existence of an Equilibrium for a Competitive Economy
By Arrow and Debreu
General Equilibrium and the Theory of Directed Graph
By Maxfield
Nash and Walras Equilibrium via Brouwer
By Geanakoplos
A Complexity View of Markets with Social Influence
By Chen and Teng
Set 6/7

Mar 10
The Eisenberg-Gale convex program
for Fisher's model with linear utilities
AGT Book: Chapter 5 and 6
How to Compute Equilibrium Prices in 1891
By Brainard and Scarf
Consensus of Subjective Probabilities: The Pari-Mutuel Method
By Eisenberg and Gale
Market Equilibrium via a Primal-Dual Algorithm for a Convex Program
By Devanur, Papadimitriou, Saberi and Vazirani
The Computation of Market Equilibria
By Codenotti, Pemmaraju and Varadarajan
Set 8
Note 8.pdf
By Yi Zhang and Minglei Wang
Mar 17
Spring Recess, No Class



Mar 24
Social choice theory
Arrow's impossibility theorem
The Gibbard–Satterthwaite theorem
AGT Book: Chapter 9
No exercise

Mar 31
Proof of the Gibbard-Satterthwaite theorem
Incentive compatibility
VCG mechanisms
AGT Book: Chapter 9
Set 9

Apr 7
Bayesian mechanism design
Myerson's optimal mechanism
AGT Book: Chapter 13
Optimal Auction Design
By Myerson
Lectures on Optimal Mechanism Design
By Hartline
No exercise

Apr 14
Cost Sharing
Cross-monotone cost-sharing schemes
and group incentive compatible mechanisms
AGT Book: Chapter 15
On Balanced Sets and Cores
By Shapley
Incremental Cost Sharing: Characterization by
Coalition Strategy-Proofness
By Moulin
Strategyproof Sharing of Submodular Costs: Budget Balance
versus Efficiency By Moulin and Shenker
Sharing the Cost of Multicast Transmissions
By Feigenbaum, Papadimitriou and Shenker
Set 10

Apr 21
Student presentations
Nash Equilibria for Bimatrix Games
By Dimitris Paparas and Vasilis Gkatzelis
Graphical Games
By Matthew D'Zmura


Apr 28
Student presentations
Sink Equilibrium and Best-Reply Mechanism
By Yundi Zhang
Bargaining Solutions for Licensing Negotiations
By Sebastian Zimmeck
Graphical Games
By Barbara Kiskovski and Melanie Kambadur


April 29
Student presentations
A Survey of Two-Player Games in Intrusion Detection
By Yi Zhang and Minglei Wang
Application of Stackelberg Games in Security
By Rui Liu and Yifu Zheng
On the Severity of Braess' Paradox
By Wei Han
A Survey of Incentives for Peer-to-peer Networks
By Delia Wang