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
Oct 6 Best-response Dynamics and No-regret Learning Lecture scribbles. See Tim Roughgarden's notes on best-response dynamics and no-regret dynamics.
Mechanism Design
Oct 8 Single Item Auction: First and Second Price Lecture notes. Tim Roughgarden's notes on single-item auctions.
Oct 13 Myerson's Single Parameter Auction Lecture notes. Tim Roughgarden's mechanism-design notes.
Oct 15 CANCELED
Oct 20 Myerson's Optimal (Revenue Maximizing) Auction Notes by Tim. Lecture scribbles
Oct 22 VCG, Indirect Mechanisms, Revelation Principle Lecture notes. Tim Roughgarden's mechanism-design notes.
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 Lecture slides. Pointers: 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 Mechanism Design for AI Agents: Autonomous Bidding, Bid subsidies Lecture Slides. Pointer: See last two slides
Nov 10 Algorithmic Collusion by Large Language Models Paper. Talk
Nov 12 Mechaism Design for Alignment and Control Paper.
Project Presentations
Nov 17 Project Presentations I

Groups Presenting:
Group I: Anthony, Tatiana, Eeshan
Group II: Franklin, Ethan
Group III: Vishesh Prasad 

Nov 19 Project Presentations II

Groups Presenting:
Strong EFX Allocation for Agent with Three Relevant Goods: Evan Lin, Peter Lin, Gerald Osterhaus
Decentralized Equilibrium Discovery After Shocks: Sejun Park, Chirag Rastogi
Fair Randomization in Mechanism Design: Zirui Wang

Dec 1 Project Presentations III Groups Presenting:
Group I: Wangjia Zhan, Meitong Liu, Haoqi Chen
Group II: Ben Fauman, Roshan Hegde, Shreyes Bharat
Pricing Dive / Experiment: Carver Ossoff
Dec 3 Final Exam Review Class  
Dec 8 Project Presentations IV Groups Presenting:
Group I: Yuxuan Wan
Reputation with Replaceable Identities: Jocelyn Ho, Aahan Thapliyal
Group II: Tang Cheng, Shixuan Liu
Auction Collusion Algorithms: Kaixuan Wang, Yifan Jiao

Extra Reading Material

Lecture 2:

Fair Division

CE Computation: Chores Market

Stable Matching

Voting

Nash equilibrium computation

Approximation Algorithms:

Sperner and PPAD-hardness of two-player games

Security Games

Routing games, PoA:

Best-response Dynamics and Convergence Rates:

Power of Competition vs. Price Optimization

Spectrum Auction (FCC):

Mechanism Design and Prophets:

LLMs and AI Agents