CS 580: Topics in Algorithmic Game Theory


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

Lecture Schedule and Notes

Date Topics Reading
Fair-division (covered topics are relatively new)
Tue, Aug 24, 2021 Course overview. Fair-division. Course overview slides and fair-division (first few slides)
Thurs, Aug 26, 2021 Fair-division: Envy-free Slides
Tue, Aug 31, 2021 Fair division w/ indivisible items: Prop1, MMS Slides
Thurs Sep 2, 2021 Fair division w/ indivisible items: MMS (Cont...), NSW Slides
Tue Sep 7, 2021 Fair division w/ indivisible items: Max Nash Social Welfare (Cont.) Slides
Thu Sep 9, 2021 Stable Matching, House Allocation, Kidney Exchange Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting
Games and Equilibria
Tue, Sept 14, 2021 Two-player games and Nash equilibrium Slides
Thu, Sept 16, 2021 Nash equilibrium: Existence and Computation Slides
Tue, Sept 21, 2021 Nash, Brouwer, Sperner, and TFNP classes Slides
Thu, Sept 23, 2021 Game models and other equilibrium notions Slides
Tue, Sept 28, 2021 Stackelberg equilibrium and Security games For Stackelberg equilibrium see Slides. For security games see Scribbles, and Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2).
Thu, Sept 30, 2021 Bayesian Games, Nash Bargaining For Bayesian games see Slides. For Nash Bargaining see lecture Scribbles, and Asu Ozdaglar Slides.
Mechanism Design
Tue, Oct 5, 2021 Cancelled
Thu, Oct 7, 2021 Single item auctions -- First and second price Notes by Tim. Lecture scribbles
Tue, Oct 12, 2021 Single parameter auction. Myerson's Lemma Notes by Tim. Lecture scribbles
Thu, Oct 14, 2021 VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle On VCG, and notes on the rest by Tim. Lecture scribbles
Tue, Oct 19, 2021 Myerson's optimal (revenue maximizing) auction, Bulow-Klemperer theorem  Notes1 and Notes2 by Tim. Lecture scribbles
Thu, Oct 21, 2021 Prophet Inequality and Simple Auctions Prophet Inequality notes due to Tim, and Slides due to Brendan.
Tue, Oct 26, 2021 Case Study on Spectrum Auction Spectrum Auc by Tim. Lecture scribbles
Thu, Oct 28, 2021 Spectrum Reverse Auction and Routing games Spectrum Auc by Tim. Notes on routing games by Tim. Lecture scribbles
Routing+Costsharing Games and Price-of-Anarchy
Tue, Nov 2, 2020 Non-Atomic Selfish-Routing, N/w Over Provisioning Notes1 and notes2 by Tim. Lecture scribbles
Thu, Nov 4, 2021 Atomic Selfish Routing, Potential Games, Smooth Games Notes on atomic selfish routing, 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
Tue, Nov 9, 2020 Cost Sharing Games Notes by Tim on Cost-sharing games. Lecture scribbles
Thu, Nov 11, 2020 No-regret Dynamics Notes1 and notes2 by Tim. Lecture scribbles

Relevant Material

Fair Division
  • Envy-freeness w/ indivisible items: first significant work, recent work
  • See last slides of fair-division lectures for tons of relevant papers.

    Stable Matching (Thu, Sept 9)
  • 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).

    Nash equilibrium computation (Tue-Thu, Sept 14,16):
  • 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-polinomial 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 coaliation proof), see notes (there is plethora of other lecture notes on the internet).

    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-Pirces, envy-free, on digital goods, etc..
  • Work on Prior Independnet Mechanisms: Multi-Parameter case,Revenue Maximizing with Single Sample, For Scheduling, Learning Distribution, etc..

    Other interesting relevant works on auctions
  • See an informative presentation by Brendan Lucier on applications of Prophet Inequality in auction design.
  • There is a lot of literature on Combinatorial Auctions. For example, see book by Cramton, Shoham, and Steinberg (editors).

    Spectrum Auctions (in practice)
  • FCC Spectrum Auction explained here. Also see FCC's public reporting.
  • Video on how it works.
  • Snap shots of package bidding and item bidding from the last auction are here.
  • FCC Fact Sheet from Sept 5, 2019, regarding the bidding procedure for the auction.

  • 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 imposibility theorem. Voting theory is still an active area of reserach, and quite a few references available on the Wikipedia page on "Electoral Systems". See Table for summary of different voting mechanisms and their properties.

    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:
  • Notes1 by Tim.

  • Tentative Topics we may cover (not in order)

    Topics Reading (coming up soon)
    Stable Matching  
    Mechanism Design
    Voting - Arrow's theorem  
    Single item auction: first and second price  
    Single parameter auction, Myerson's lemma  
    VCG, Auction design to algorithm design, Indirect mechanism, Revelation principle  
    Myerson's optimal (revenue maximizing) auction, Bulow-Klemperer theorem   
    Prophet inequality, Combinatorial auctions  
    Case study on Spectrum auctions  
    Games and Equlibria
    Two player games, zero-sum, minmax = LP duality  
    Nash equlibria in bimatrix games: characterization, enumeration, existence, reduction to symmetric games  
    Lemke-Howson algorithm, Sperner  
    Class PPAD and other TFNP classes, iterated dominance and correlated equilibrium  
    Other equilibrium (coarse correlated, Stackelberg) and game (extensive form and Bayesian) notions  
    Security games and Stackelberg equilibria, Nash bargaining  
    Public good games  
    Price of Anarchy: Selfish Routing, Congestion Games, Potential games
    Selfish routing and Price-of-Anarchy  
    Network over-provisioning and Non-atomic routing  
    Smooth games  
    Congestion games, potential games, equilibrium existence and complexity of computation, cost sharing games  
    Best response dynamics  
    No-regret dynamics  
    Market: Fisher, competitive equilibrium  
    Computation of competitive equilibrium  
    Hylland-Zeckhauser, Spending restricted models  
    Connections to fair division