CS 580: Topics in Algorithmic Game Theory

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

Lecture Schedule and Notes

Will be updated as the class progresses.

Date	Topics	Reading
Fair-division, Social Choice (some of the covered topics are relatively new)
Aug 25	Introduction. Course overview.	Slides
Aug 27	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.
Sep 1	Competitive Equilibrium Algorithm	Lecture slides. See Devanur, Papadimitriou, Saberi, and Vazirani (2008) on combinatorial algorithms for market equilibrium.
Sep 3	Fair Division of Indivisibles: EF, Proportionality, EF1/EFX	Lecture slides. See the survey on fair division of indivisible goods.
Sep 8	Fair Division of Indivisibles: Maximin Share (MMS), Nash Social Welfare	Lecture slides. See Garg, McGlaughlin, and Taki on 2/3-MMS.
Games and Equilibria
Sep 10	Nash Equilibrium, Nash's Existence Theorem, Zero-sum Games	Lecture slides. Nash's paper.
Sep 15	Min-Max Theorem for Zero-sum Games; Equilibrium Computation in Two-player Games	Lecture slides. See Chapter 2 of the AGT book. For those interested, slides on the connection between Nash, Brouwer's fixed-point theorem, Sperner's lemma, and PPAD.
Sep 17	Other Eq. Notions: Correlated and Coarse Correlated Equilibrium, Extensive-form Games	Lecture slides.
Sep 22	Stackelberg Equilibrium and Security Games, Nash bargaining, Bayesian games	Lecture slides. For security games, see lecture scribbles,, and Section 3 of Xu (2016).
Routing Games, Price-of-Anarchy, and Learning
Sep 24	Routing Games: Non-atomic Routing and Price of Anarchy	Lecture notes. See Tim Roughgarden's notes on selfish routing.
Sep 29	Non-atomic routing -- PoA; Atomic Routing Games	For non-atomic routing, PoA proof see notes from the previous lecture. Lecure notes Atomic Routing. See Tim Roughgarden's notes on potential games.
Oct 1	Smoothness games and Potential 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
The Rest is Tentative
Oct 6	Best-response Dynamics and No-regret Learning	See Tim Roughgarden's notes on best-response dynamics and no-regret dynamics.
Oct 8	No-regret; CCE; Swap Regret; CE; Repeated Interaction	Lecture notes. See also Roughgarden's notes on no-regret and swap-regret dynamics.
Mechanism Design
Oct 13	Single Item Auction: First and Second Price	Lecture notes. Tim Roughgarden's notes on single-item auctions.
Oct 15	Myerson's Single Parameter Auction	Lecture notes. Tim Roughgarden's mechanism-design notes.
Oct 20	VCG, Indirect Mechanisms, Revelation Principle	Lecture notes. Tim Roughgarden's mechanism-design notes.
Oct 22	Myerson's Optimal (Revenue Maximizing) Auction	Lecture notes. Myerson / Roughgarden.
Oct 27	Combinatorial Auction: Spectrum Auction Case Study	Lecture notes. See FCC auction formats.
Games and Markets with AI Agents
Oct 29	LLMs as Strategic Agents: Beliefs, Best Responses, Equilibrium Play, Bounded Rationality	Primary: Junqu de Fortuny and Cappelli, LLMs as Strategic Agents: Beliefs, Best Response Behavior, and Emergent Heuristics (2025). Also: Jia et al., Large Language Model Strategic Reasoning Evaluation through Behavioral Game Theory (2025).
Nov 3	Delegation to AI Agents: Negotiation, Commitment, Preference Specification	Primary: Bianchi et al., How Well Can LLMs Negotiate? NegotiationArena Platform and Analysis, ICML 2024. Also: Mirrokni et al., LLMs at the Bargaining Table (2024).
Nov 5	Mechanism Design for AI Agents: Autonomous Bidding, Strategic Adaptation, Robustness	Pointer: Performative Prediction on Games and Mechanism Design, AISTATS 2025. The lecture will use classical mechanism-design tools to formulate open questions for sophisticated autonomous participants.
Nov 10	Agent Markets: AI Intermediaries, Matching, Pricing, Reputation, Heterogeneous Capabilities	Primary: Bichler, Agentic Markets (2026). Also: Kapoor, Kolt, and Lazar, Build Agent Advocates, Not Platform Agents, ICML 2025.
Nov 12	AI-Agent Collusion and Emergent Coordination	Primary: Fish, Gonczarowski, and Shorrer, Algorithmic Collusion by Large Language Models (2024). Background: repeated games, learning dynamics, and algorithmic-pricing collusion.
Project Presentations
Nov 17	Project Presentations I
Nov 19	Project Presentations II
Dec 1	Project Presentations III
Dec 3	Project Presentations IV
Dec 8	(tetative) Final Exam	Reserved for in-person final exam.

Extra Reading Material

Lecture 2:

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.

CE Computation: Chores Market

Approximate CE computation (FPTAS): Exterior-point, Combinatorial, Frank-Wolf
Labor markets:
Tatonnement Dynamics.

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).

Voting

Academic study on Voting theory started around the time of French Revolution (1770). Borda (Borda count mechanism) and Condorcet (Condorcet method and paradox) are credited as founders of Voting Theory, however recent research showed that the philosopher Ramon Llull discovered both their methods in 13th century!
All hopes are not lost despite Arrow's impossibility theorem. Voting theory is still an active area of research, and quite a few references available on the Wikipedia page on "Electoral Systems". See Table for summary of different voting mechanisms and their properties.

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.

Approximation Algorithms:

Excellent book on Approximation Algorithms by Vijay V. Vazirani.
Approximation Algorithms course taught by Chandra Chekuri.

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

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).