CS 580: Topics in Algorithmic Game Theory

 

All lectures will be recorded. Recordings will be available on Mediaspace.

Lecture Schedule and Notes

Date Topics Reading
Fair-division, Social Choice (some of the covered topics are relatively new)
Tue, Aug 23, 2022 Introduction. Course overview. Slides
Thu, Aug 25, 2022 Fair-division of Divisible Goods 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.
Tue, Aug 30, 2022 Fair-division of Indivisible Goods - EF1 and Prop1 Slides
Thu, Sep 1 2022 Fair-division of Indivisible Goods - MMS Slides
Tue, Sep 6 2022 Stable Matching, House Allocation, Kidney Exchange Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting
Thu, Sep 8 2022 Arrow's Impossibility Theorem Notes.Slides by Kevin-Leyton Brown.
Mechanism Design
Tue, Sept 13, 2022 Single Item Auction-- First and Second Price Slides on equilibrium notions. Scribbles on single item auction. Notes by Tim.
Sept 15, 2022 Single parameter auction. Myerson's Lemma Notes by Tim. Lecture scribbles
Sept 20, 2022 VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle Lecture scribbles
Sept 22, 2022 Myerson's optimal (revenue maximizing) auction Lecture scribbles
Sept 27, 2022 Simple vs Optimal Auctions: Bulow-Klemperer's Theorem and Prophet Inequality Lecture notes and scribbles. Notes by Tim. Slides by Brendan.
Sept 29, 2022 Prophet Inequality: Variants and Extensions Lecture notes and scribbles. Sahil's, Michal's and Thomas's slides.
Oct 4, 2022 Case Study on Spectrum Auction Spectrum Auc by Tim. Lecture scribbles.
Games and Equilibria
Oct 6, 2022 Two-player games and Nash equilibrium, zero-sum, minmax = LP duality Slides
Oct 13, 2022 Nash, Brouwer, Lemke-Howson algorithm, Sperner, and TFNP classes Slides
Oct 18, 2022 Game models and other equilibrium notions Slides
Oct 20, 2022 Stackelberg equilibrium and Nash Bargaining Lecture scribbles. Also see slides by Asu Ozdaglar on Nash bargaining
Routing+Costsharing Games and Price-of-Anarchy
Oct 25, 2022 Non-Atomic Selfish RoutingNotes by Tim. Lecture scribbles
Oct 27, 2022 N/W Over Provisioning, Atomic Selfish Routing Notes by Tim. Lecture scribbles
Nov 1, 2022 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
Nov 3, 2022 Cost Sharing Games Notes by Tim on Cost-sharing games. Lecture scribbles
Nov 8, 2022 No class - Election Day Please Go Vote!
Nov 10, 2022 No-regret Dynamics Tim's notes on best-response dynamics notes on no-regret dynamics, and notes on on-swap-regret. Lecture scribbles
Project Presentations
Nov 15, 2022 Project Presentations
  • Hardness of End-Of-Line and Similar Problems by Cruz Barnum
  • A Truthful-Incentivizing Mechanism for Crowdsourcing with Nonidentical Workers by Ameya Anjarlekar and Seo Taek Kong
  • Mechanisms for Matching Markets on Ride-sharing by Ruofan Yu and Jiawei Zhang
    		•
    Nov 17, 2022 Project Presentations
  • Theory and Algorithm of Stochastic Games by Ivor Chen
  • When can the 4/5 Maximum Share be Guaranteed by Yanlong Yao
  • Survey of Evolutionary Stable Strategies by William Wang
  • Desirable Fair Cake-Cutting Algorithm in Practice by Junjie Yang
    		•
    Nov 29, 2022 Project Presentations
  • Large-Scale Multi-Item Auctions by Ishas Kekre and Tom Herschberg
  • Multi-Item Auctions by Krzysztof Dutka
  • Prospect Theory by Kyle McNamara and Avi Porath
    		•
    Dec 1, 2022 Project Presentations
  • α-MMS Bounds by Albert Cao and Estelle Lee
  • EF1+PO for chores by Jane Du
  • No-Regret Learning dynamics by Alec Diraimondo
  • 3D Stable Matching by Lang Ying
  • EFX Allocations with Perturbed Additive Valuations by Sizhuo Li
    		•
    Dec 6, 2022 Project Presentations
  • Pros and Cons of Auctions Used in Practice by Shih-Chiang Lee and Minyang Ye
  • Existence of EFX Allocations for 4 Players by Tom Reichel
  • Dynamic Matching Markets by Zhen Lin and Tiancheng Jiang
  • Optimization of Bilinear Games by Audrey Huang
    		•

    Extra Reading Material

    Lecture 2 (Thu, Aug 25):
  • 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.
  • 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.

    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.

    Auctions (theory)
  • Myerson's paper on optimal auctions. It also handles the case with non-regular distributions.
  • OPT vs Competition: Bulow-Klemperer paper (the general case). Extension to multi-parameter setting can be found in this paper.
  • Work on posted-price mechanisms: Auction vs Posted-Prices, envy-free, on digital goods, etc..
  • Work on Prior Independent Mechanisms: Multi-Parameter case,Revenue Maximizing with Single Sample, For Scheduling, Learning Distribution, etc..

    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 (Tue, Sept 21)
  • 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.