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.

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 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
Markets
Market: Fisher, competitive equilibrium
Computation of competitive equilibrium
Hylland-Zeckhauser, Spending restricted models
Connections to fair division