CS 598 RM: Schedule, Relevant Material, and Tentative Topics

 

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

Lecture Schedule and Notes

Date Topics Reading
Markets and Fair-division
Tue, Aug 24, 2020 No lecture due to ADFOCS 2020
Thu, Aug 28, 2020 Course overview. Competitive equilibrium (CE) Course overview slides and CE slides. For notes on CE, see Chapter 5 of the Algorithmic Game Theory book.
Tue, Sept 1, 2020 Competitive equilibrium and Properties CE slides. For notes on CE, see Chapter 5 of the Algorithmic Game Theory book.
Thu, Sept 3, 2020 Computation of Competitive equilibrium Slides. See Sections 2, 3, 4, 5 of the DPSV08 paper for CE algorithm.
Tue, Sept 8, 2020 Hylland-Zeckhauser. Fair division w/ indivisible items: EF1, EFX Slides. See Section 4 of VY20 for the HZ equilibrium algorithm.
Thu, Sept 10, 2020 Fair division w/ indivisible items: MMS, Prop1 Slides
Tue, Sept 15, 2020 Fair division w/ indivisible items: MMS, MNW Slides
Thu, Sept 17, 2020 Fair division w/ indivisible items: Maximizing Nash welfare Slides
Games and Equilibria
Tue, Sept 22, 2020 Two-player games and Nash equilibrium Slides
Thu, Sept 24, 2020 Nash equilibrium computation Scribbles
Tue, Sept 29, 2020 Nash, Brouwer, Sperner, and TFNP classes Slides
Thu, Oct 1, 2020 Game models and other equilibrium notions Slides
Tue, Oct 6, 2020 Bayesian games and Security games For Bayesian games see Slides (slides 33-38). For security games see Scribbles, and Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2).
Thu, Oct 8, 2020 Security game (contd.). Selfish-Routing and Price of Anarchy Notes by Prof. Tim Roughgarden. Lecture scribbles
Selfish Routing, Congestion Games, Potential Games
Tue, Oct 13, 2020 Non-Atomic Selfish-Routing, N/w Over Provisioning Notes1 and notes2 by Tim. Lecture scribbles
Thu, Oct 15, 2020 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, Oct 20, 2020 Cost Sharing Games Notes by Tim on Cost-sharing games. Lecture scribbles
Thu, Oct 22, 2020 Best Response Dynamics and the Rate of Convergence Notes by Tim on Cost-sharing games. Lecture scribbles
Mechanism Design
Tue, Oct 27, 2020 Single item auctions -- First and second price Notes by Tim. Lecture scribbles
Thu, Oct 29, 2020 Single parameter auction. Myerson's Lemma Notes by Tim. Lecture scribbles
Thu, Nov 5, 2020 Cancelled
Tue, Nov 10, 2020 VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle On VCG, and notes on the rest by Tim. Lecture scribbles
Thu, Nov 12, 2020 Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem Notes1 and Notes2 by Tim. Lecture scribbles
Tue, Nov 17, 2020 Case Study on Spectrum Auction Spectrum Auc by Tim. Lecture scribbles

Relevant Material

Competitive Equilibrium:
  • KKT: Wikipedia article, Lecture slides by Gordon and Tibshirani.
  • Convex programming formulations: Notes by N. Devanur, Paper by CDGJMVY.
  • Simplex-like path following algorithm: Paper by GM.SV

    Lecture 8-9 (Tue-Thu, Sept 22,24):
  • 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.

    Lecture 10 (Tue, Sept 29)
  • note on Sperner's Lemma.
  • Here are Slides on showing PPAD-hardness of Nash equilibrium computation in two-player games.

    Lectures 12, 13 (Tue-Thu, Oct 6, 8):
  • 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).

    Lectures 15 (Thu, Oct 15):
  • 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.

    Lectures 17 (Thu, Oct 22):
  • Notes1 and notes2 on no regret dynamics Tim.

    Lecture 20-21 (Tue-Thu, Nov 10-12)
  • 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).

    Lecture 22 (Tue, Nov 17)
  • 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.

    Tentative topics we may cover (not in order)

    Date Topics Reading
    Mechanism Design
      Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching. Notes by Prof. Tim Roughgarden. Notes by Widmayer and Dutting
      Prophet Inequality, Combinatorial Auctions Prophet Inequality notes due to Tim, and Slides due to Brendan. Comb. Auction by Tim
      Implementability of Comb. Auction KC Auction by Tim
      Walrasian Equilibrium VCG+Walrasian Equilibrium by Tim
    Selfish Routing, Congestion Games, Potential Games
      No-Regret Dynamics. Notes by Tim.
    Fair-division
    Markets
      Market: Fisher, Equilibrium Notes by Prof. Mansor. AGT book Chapter 5, Sections 1 and 3
      Eisenberg-Gale Convex Formulation, Kelly's resource allocation problem -- fair solution AGT book Chapter 5, Sections 5.1-5.3, Section 13. Chapter 6, section 6.2. More notes will be posted.
      Exchange Model: Existence, Convex formulation and auction based approximation algorithm for the Linear utilities case. AGT book Chapter 5, Sections 5.11, 5.12, Chapter 6, Section 6.1.1. Chapter 3 (Section 3.3) of Notes by Prof. Bisin.
      Market: Discrete-goods, Strategization Slides. Sections 2, 3.2 and 4.1 of this paper.
      (market equilibrium) Fisher markets, Eisenberg-Gale convex formulation, an overview of Devanur-Papadimitriou-Saberi-Vazirani (DPSV) algorithm. Arrow-Debreu market, PPAD-hardness, Lemke’s algorithm. Â