All lectures will be recorded. Recordings will be available on Mediaspace under channel name "CS 580 Fall 2026"
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. |
| The Rest is Tentative | ||
| Sep 17 | Class PPAD; Correlated and Coarse Correlated Equilibrium | Lecture slides. Supplementary notes on PPAD, CE, and CCE. |
| Sep 22 | Extensive-form Games; SPE; Stackelberg Equilibrium and Security Games | Lecture slides. For security games, see Section 3 of Xu (2016). |
| Routing Games, Price-of-Anarchy, and Learning | ||
| Sep 24 | Routing Games: Non-atomic Routing and Price of Anarchy | See Tim Roughgarden's notes on selfish routing. |
| Sep 29 | Atomic Congestion Games and Potential Games | See Tim Roughgarden's notes on potential games. |
| Oct 1 | Smoothness Framework and Price of Anarchy | See Tim Roughgarden's notes on smooth games. |
| 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. |
Lecture 2:
Fair Division
CE Computation: Chores Market
Stable Matching
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.
Voting