CS 580: Topics in Algorithmic Game Theory

All lectures will be recorded. Recordings will be available on Mediaspace under channel name "CS 580 Fall 2025"

Lecture Schedule and Notes

Will be updated as the class progresses.

td>Stable Matching, House Allocation, Kidney Exchange

Date	Topics	Reading
Fair-division, Social Choice (some of the covered topics are relatively new)
Aug 26	Introduction. Course overview.	Slides
Aug 28	Fair-division of Divisibles	Slides See also sections 10.1 and 10.2 of Yishay Mansour's notes. Note here that B_i is the budget that we assumed to be 1, and ρ is also 1 when valuations are linear.
Sept 2	Competitive Equilibrium Algorithm	Lecture slides. The paper on the first combinatorial flow-based algorithm by Devanur, Papadimitriou, Saberi, and Vazirani (2008).
Sept 4	Fair Division of Indivisibles: EF and Prop	Lecture slides.
Sept 9	Fair Division of Indivisibles: MaxMinShare (MMS)	Lecture slides. 2/3-MMS paper by Garg, McGlaughlin, and Taki
Sep 11	Mechanism Design w/o Money: Stable Matching and Top-Trading-Cycle	Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting
Games and Equilibria
Sept 16	Nash Equilibrium, Nash's Existence Theorem, Zero-sum games	Lecture Slides. Nash's paper.
Sept 18	Min-Max Theorem for Zero-sum Games, Lemke-Howson for General Two-Player Games	Lecture Slides. For Lemke-Howson algorithm, see Chapter 2 of the AGT book.
Sept 23	Lemke-Howson Algo (quick recap), Class PPAD, Other Equilibrium Notions	Lecture Slides on Lemke-Howson Algorithm and class PPAD. For those interested, < a href="Slides/NE-Fixedpoint-Sperner-PPAD.pdf">slides on the connection between Nash, Brouwer's fixed-point theorem, Sperner's lemma, and PPAD. Lecture Slides on other equilibrium notions of DSE, CE and CCE
Sept 25	CE, CCE, Extensive form games -- SPE, Stackelberg Eq	Lecture Slides
Sept 28	Security Games, Stackelberg Equilibrium	Lecture scribbles on security games. Also see thisSection 3 of this paper by H. Xu.
Routing+Costsharing Games and Price-of-Anarchy
Oct 2	Routing Games: Non-atomic Routing	Notes by Tim. Lecture scribbles
Oct 7	N/W Over Provisioning, Atomic Selfish Routing	Notes by Tim. Lecture scribbles
Oct 9	Potential Games and Smoothed Games	See section 1 of notes for Potential games, and notes on smooth games by Tim; this also includes smoothness proof for Location Games where players want to maximize payoff. Lecture scribbles
Oct 14	Cost Sharing Games	Notes by Tim on Cost-sharing games. Lecture scribbles
Oct 16	No regret dynamics	Lecture scribbles. Tim's notes on best-response dynamics notes on no-regret dynamics, and notes on on-swap-regret leading to approximate CE, that we did not cover.
Mechanism Design
Oct 21	Single Item Auction -- First and Second Price	Scribbles on single item auction. Notes by Tim.
Oct 23	Myerson's Single Parameter Auction	Notes by Tim. Lecture scribbles
Oct 28	Canceled
Oct 30	VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle	Notes by Tim. Lecture scribbles
Nov 4	Myerson's optimal (revenue maximizing) auction	Notes by Tim. Lecture scribbles
Nov 6	Simple vs Optimal Auctions: Bulow-Klemperer's Theorem and Prophet Inequality	Lecture notes and scribbles. Notes by Tim. Slides by Brendan.
Project Presentations
Nov 11	Project Presentations
Nov 13	Project Presentations
Nov 18	Project Presentations
Nov 20	Project Presentations
Dec 2	Project Presentations
Dec 4	Project Presentations
Dec 9	Tentatively Final Exam

Extra Reading Material

Lecture 2:

NP-Completeness - Notes by Prof. Jeff Erickson from CS473. What is NP, NP-Hardness, NP-Completeness and reductions to show NP-Hardness are the relevant part for us.

Lecture 3:

Linear programming and duality - Notes by Prof. Jeff Erickson from CS473. What are linear programs, dual linear program, complementary slackness conditions, and strong-duality theorem are the relevant part for us.
KKT Conditions: Lecture notes by Arya Mazumdar

Fair Division

Envy-freeness w/ indivisible items: A recent, comprehensive survey
first significant work, recent work
See last slides of fair-division lectures for tons of relevant papers.

Stable Matching

The differed acceptance (DA) algorithm for stable matching has other interesting properties: (a) every man gets her best match among all stable matchings, (b) the outcome is DSIC for the men
There is a lot of literature on all three topics of TTC, Kidney exchange, and Stable Matching.
Note on this by Tim in his book Twenty Lectures on AGT: Roth et al. (2004) also extend the TTC algorithm and its incentive guarantee to accommodate both deceased donors (houses without owners) and patients without a living donor (agents without houses). The application of graph matching to pairwise kidney exchange is from Roth et al. (2005), Roth et al. (2007) consider three way kidney exchanges, with simultaneous surgeries on three donors and three patients. Three-way exchanges can significantly increase the number of matched patients, and for this reason are becoming common. Allowing four-way and larger exchanges does not seem to lead to significant further improvements.
An example exhibiting a tie-breaking rule between maximum-cardinality matchings such that the corresponding pairwise kidney exchange mechanism is not DSIC was obtained by Gale and Sotomayor (1985).

Nash equilibrium computation

Nash's paper from 1951. We discussed proof for only two player games, while he proves for general n-player games. And also existence of symmetric NE in symmetric n-player game. Here is a proof of Brouwer's theorem.
LMM'03 Paper on quasi-polynomial time algorithm for finding O(1)-approximate NE.
Simplex-like path following Lemke-Howson (1964) algorithm to find Nash equilibrium in any two-player game.

Sperner and PPAD-hardness of two-player games

note on Sperner's Lemma.
Here are Slides on showing PPAD-hardness of Nash equilibrium computation in two-player games.

Security Games (Tue, Sept 29):

For various security games and application of Stackelberg Equilibria in these games, see Prof Milind Tambe's page. AFAIK, he started with devising schedule for security personals at LAX airport (see his publications from 2008, 2009).
For solving a linear program with exponentially many constraints using Ellipsoid method (through Separation Oracle), see Section 2 of notes, Section 2.3 in particular.
For CORE of a game (a play that is coalition-proof), see notes (there is plethora of other lecture notes on the internet).

Routing games, PoA:

Prof. Tim Roughgarden did initial important work on Price-of-Anarchy in routing games. See Tim's Thesis on Selfish Routing.
Classical paper by Roughgarden and Tardos that started this line of work in TCS.