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

Lecture Schedule and Notes

Date	Topics	Reading
Games, Equilibria, and Computation
Tue, Aug 28	Course overview. Two-player games. Zero-sum, min-max = LP duality.	Overview slides and notes. Notes by Prof. Costis Daskalakis on Two-player games, Zero-sum games, min-max = LP duality.
Thu, Aug 30	Nash Eq. in bimatrix games, Characterization, enumeration, existence, reduction to symmetric game.	My hand-written notes. Notes by Prof. Costis Daskalakis on Two-player games.
Tue, Sept 4	Cancelled
Thu, Sept 6	Nash, Brouwer, Sperner; Class PPAD, and other TFNP classes.	Slides.
Tue, Sept 11	Other equilibrium (dominant strategy, (coarse) correlated, stackelberg) and game (extensive form, Bayesian) notions.	For Eq. notions see Slides.
Thu, Sept 13	Security games and stackelberg equilibria. Nash bargaining	For material covered on security games, see Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2). For Nash bargaining see Slides 6-15 by Prof. Asu Ozdaglar, and also Section 8.2 (Chapter 8) of book Game Theory by Roger Myerson.
Mechanism Design
Tue, Sept 18	Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching.	Notes by Prof. Tim Roughgarden. Notes by Widmayer and Dutting
Thu, Sept 20	Voting	Notes by Widmayer and Dutting. Notes by Tim
Tue, Sept 25	Single item auctions -- First and second price	Notes by Tim.
Thu, Sept 27	Single parameter auction. Myerson's Lemma	Notes by Tim.
Tue, Oct 2	Auction design to Algorithm design, Indirect Mechanism, Revelation Principle	Notes by Tim.
Thu, Oct 4	Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem	Notes1 and Notes2 by Tim.
Tue, Oct 9	Prophet Inequality, VCG, Combinatorial Auctions	Prophet Inequality, VCG+Comb. Auction by Tim
Thu, Oct 11	Implementability of Comb. Auction	KC Auction, VCG+Walrasian Equilibrium by Tim
Tue, Oct 16	VCG properties, Spectrum Auction	Notes1, Notes2 by Tim
Selfish Routing, Congestion Games, Potential Games
Thu, Oct 18	Selfish-Routing and Price of Anarchy	Notes by Tim
Tue, Oct 23	Network Over-Provisioning and Non-Atomic Routing	Notes by Tim.
Thu, Oct 25	Congestion games, Potential Games, Equilibrium Existence and Complexity of Computation.	First part of Tim's Notes on Potential games. Slides by Prof. Apt on Congestion to Potential game reduction. Notes by Prof. Kesselheim on complexity of computing NE in congestion games.
Tue, Oct 30	(i) Smooth Games. (ii)Cost Sharing Games	Notes by Tim on (i); this also includes smoothness proof for Location Games where players want to maximize payoff. Notes by Tim on (ii).
Thu, Nov 1	No Lecture
Tue, Nov 6	(i) Best Response Dynamics. (ii) No Regret Dynamics (discussed briefly).	Notes1 on (i), and Notes2 on (ii) by Tim.
Thu, Nov 8	More on No-Regret Dynamics.	Notes by Tim. Notes on Swap-Regret by Tim.
Fair Division
Tue, Nov 13	Fair division: Divisible goods	Section 1,2,3 except 3.2 from Notes by Endriss.
Thu, Nov 15	Fair division: Indivisible goods. EF1, MMS, egalitarian, utilitarian, NSW	For EF1, Section 2 of paper 1 and Section 3 of paper 2. For MMS, Section 3 of paper 3. For the remaining, Sections 3 and 4 of paper 4, and Section 4.2 of paper 5

Relevant Material

Lecture 1 (Tue, Aug 28):

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.

Lecture 2 (Thu, Aug 30):

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 (now you may ask what do we mean by "symmetric n-player game". Think!)

Lecture 4 (Thu, Sept 6):

Here are Slides on showing PPAD-hardness of Nash equilibrium computation in two-player games.

If you are interested in knowing more about polynomial-time algorithms for sub-classes of two-player games, here are the relevant slides.

Lecture 5 (Tue, Sept 11):

These Slides provide overview of various other types equilibrium notations (Correlated Eq, Coarse Correlated Eq, Stackelberg Eq), game settings (Bayesian, extensive-form), and some related open problems.

Lecture 6 (Thu, Sept 13):

For CORE of a game (a play that is coaliation proof), see notes (there is plethora of other lecture notes on the internet).

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

Lectures 7 (Tue, Sept 18)

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

Lectures 8 (Thu, Sept 20)

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.

Lecture 11 (Tue, Oct 2)

Paper on the limits of black-box reduction from best approximation algorithm to best approximate DSIC mechanism.

Lectures 12 (Thu, Oct 4)

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

Lectures 13 (Thu, Oct 4)

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

Lectures 16 (Thu, Oct 18):

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.

Lecture 19 (Tue, Oct 30):

Latest (AFAIK) significant results on Price of Stability in cost sharing games: Paper 1, Paper 2. Also see papers citing these.

A latest paper on hierarchical Network Formation Games.

Paper on complexity of computing Nash equilibrium in cost sharing games.

Lectures 21, 22 (Tue Nov 6, Thu Nov 8)

Black box reduction from No-Swap-Regret algorithm to No-Regret algorithm in Notes of Tim.

No-Regret as online learning, online convex optimization via gradient descent: Notes, Paper 1, Paper 2, etc. Search for the terms, and you will find many.

Course webpage on No-Regret in Game Theory and Machine Learning at UPenn.

Remaining tentative topics we may cover (not in order)

Date	Topics	Reading
	Lemke-Howson (path-following) algorithm to find a Nash equilibrium	Slides from a previous course. AGT book by Nisan, Roughgarden, Tardos, and Vazirani, sections 2.1-2.4, 3.1-3.6
	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.