CS 580: Topics in Algorithmic Game Theory

All lectures will be recorded. Recordings will be available on Mediaspace under channel name "Topics in Algrothmic Game Theory (CS 580 AGT) Fall 2023"

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 22	Introduction. Course overview.	Slides
Aug 24	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.
Aug 29	Competitive Equilibrium Algorithm	Lecture slides. The paper on the first combinatorial flow-based algorithm by Devanur, Papadimitriou, Saberi, and Vazirani (2008).
Aug 31	Fair Division of Indivisibles: EF and Prop	Lecture slides.
Sep 5	Fair Division of Indivisibles: MaxMinShare (MMS)	Lecture slides. 2/3-MMS paper by Garg, McGlaughlin, and Taki
Sep 7	Mechanism Design w/o Money: Stable Matching and Top-Trading-Cycle	Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting
Sept 12	Voting: Arrow's Impossibility Theorem	Lecture Scribbles. Slides by Kevin-Leyton Brown.
Games and Equilibria
Sept 14	Nash Equilibrium, Nash's Existence Theorem, Zero-sum games	Lecture Slides. Nash's paper.
Sept 19	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 21	Lemke-Howson Algo (quick recap), Class PPAD, Other Equilibrium Notions	Lecture Slides on Lemke-Howson Algorithm and class PPAD. Lecture Slides on other equilibrium notions of DSE, CE and CCE
Sept 26	CE, CCE, Extensive form games -- SPE, Stackelberg Eq	Lecture Slides
Sept 28	Security Games, Stackelberg Equilibrium	Slides. Lecture scribbles on security games. Also see thisSection 3 of this paper by H. Xu.
Oct 3	Shapley Value and Applications to ML (by Jack Bai)	Tentative slides
Routing+Costsharing Games and Price-of-Anarchy
Oct 5	Routing Games: Non-atomic Routing	Notes by Tim. Lecture scribbles
Oct 10	N/W Over Provisioning, Atomic Selfish Routing	Notes by Tim. Lecture scribbles
Oct 12	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 17	Cost Sharing Games	Notes by Tim on Cost-sharing games. Lecture scribbles
Oct 19	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 24	Single Item Auction -- First and Second Price	Scribbles on single item auction. Notes by Tim.
Oct 26	Canceled
Oct 31	Myerson's Single Parameter Auction	Notes by Tim. Lecture scribbles
Nov 2	VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle	Notes by Tim. Lecture scribbles
Nov 7	Myerson's optimal (revenue maximizing) auction	Notes by Tim. Lecture scribbles
Nov 9	Simple vs Optimal Auctions: Bulow-Klemperer's Theorem and Prophet Inequality	Lecture notes and scribbles. Notes by Tim. Slides by Brendan.
Project Presentations
Nov 14	Project Presentations	By Rhuzang on Strategic cake eating. By Flora on Chess Strategies By Zhenyu on Evolutionary stable strategies. By Jack (Hao) on SHAP -- Shapley value for ML. By WonJun on TFNP Complexity classes.
Nov 16	Project Presentations	By David Roosevelt Wallach, Eric Liu on FX for 4 agents The-Anh Vu and Nabarun Deka on Combinatorial games Prathamesh Sonawane and Arav chheda on Poker strategies.
Nov 28	Project Presentations	By Huiqian Jing on auctions with interdependent values. By Haoxiang Sun on Behavioural Game Theory By Haotian Lu on Block Withholding Attack in cypto currencies. By Chi Han on LLMs
Nov 30	Project Presentations	Ryan Ziegler and Alex Desjardins on EFX Allocations Praneet Rathi and Malcolm Forsyth on Feature Selection as a Two-Player Game Shitao Liu and Huyen on Survey on Game theory and Multi-agent learning
Dec 5	Project Presentations	Eklavya Sharma Tue Do William Zhang Ruizhong Qiu Anh Phung

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

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

Best-response Dynamics and Convergence Rates:

Notes by Tim.

Mechanism Design and Prophets:

Spectrum Auction Case Study: Notes by Tim.
Non-iid Bulow-Kremperer: Paper by Sivan and Syrgkanis.
Prophet Inequalities: There is too much material on this topic. This survey by Lucier is a good place to start.

Tentative list of topics for the course project

Will be updated as the course progresses.