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

Lecture Schedule and Notes

Date	Topics	Reading
Wed, Jan 18	Course overview. Two-player games. Zero-sum, min-max = LP duality.	Overview slides. My hand written notes. Notes by Prof. Costis Daskalakis on Two-player games, Zero-sum games, min-max = LP duality.
Fri, Jan 20	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.
Wed, Jan 25	Lemke-Howson (path-following) algorithm to find a Nash equilibrium	My hand-written notes. Slides from a previous course. AGT book by Nisan, Roughgarden, Tardos, and Vazirani, sections 2.1-2.4, 3.1-3.6
Fri, Jan 27	(i) Class PPAD, and other TFNP classes. (ii) Dominant Strategy NE, Correlated Equilibria.	For part (i), see Slides. For part (ii) see Slides up to slide 23.
Wed, Feb 1	Stackelberg Equilibria (SE) and connections with security game. Nash bargaining	For Stackelberg Eq. see Slides 30-39. 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.
Fri, Feb 3	Selfish-Routing and Price of Anarchy	Notes by Prof. Tim Roughgarden
Wed, Feb 8	Network Over-Provisioning and Non-Atomic Routing	Notes by Tim.
Fri, Feb 10	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.
Wed, Feb 15	(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).
Fri, Feb 17	No Lecture.	-
Wed, Feb 22	(i) Best Response Dynamics. (ii) No Regret Dynamics (discussed briefly).	Notes1 on (i), and Notes2 on (ii) by Tim.
Fri, Feb 24	More on No-Regret Dynamics.	Notes by Tim. Notes on Swap-Regret by Tim.
Wed, Mar 1	Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching.	Notes by Tim. Notes by Widmayer and Dutting
Fri, Mar 3	Voting	Notes by Widmayer and Dutting. Slides by Joe Corliss
Wed, Mar 8	Single item auctions -- First and second price	Notes by Tim.
Fri, Mar 10	Single parameter auction. Myerson's Lemma	Notes by Tim.
Wed, Mar 15	Auction design to Algorithm design, Indirect Mechanism, Revelation Principle	Notes by Tim.
Fri, Mar 17	Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem	Notes1 and Notes2 by Tim.
Wed, Mar 29	Some Prior Independent Auctions, VCG	Notes by Tim.
Fri, Mar 31	No Lecture
Wed, April 5	VCG properties, Spectrum Auction	Notes1, Notes2 by Tim
Fri, April 7	Market: Fisher, Equilibrium	Notes by Prof. Mansor. AGT book Chapter 5, Sections 1 and 3
Wed, April 12	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.
Fri, April 14	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.
Fri, April 21	Market: Discrete-goods, Strategization	Slides. Sections 2, 3.2 and 4.1 of this paper.
Wed, May 3	Review Session	Slides

Relevant Material

Lecture 1 (Wed, Jan 18):

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 (Fri, Jan 20):

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 3 (Wed, Jan 25):

Pre-requisite: Simplex method, and Geometry of polytopes. Essentially understanding of what is a polytope, how vertices and edges form, how to move from a vertex to its adjacent vertex, etc. Jeff's notes on Simplex method. My slides from CS473. Notes on geometry of 3-D polyhedron.

Webpage of a bimatrix game solver.

Lecture 4 (Fri, Jan 27):

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 (Fri, Jan 27):

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.

For various applications of Stackelberg Equilibria to device strategies for security settings, see Prof Milind Tambe's page. AFAIK, he started with devising schedule for security personals at LAX airport (see his publications from 2009).

Lectures 6,7,8 (Feb 2, Feb 8, Feb 10):

Tim's Thesis on Selfish Routing.

Classical paper by Roughgarden and Tardos that started this line of work in TCS.

Lecture 9 (Wed, Feb 15):

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 11, 12 (Wed Feb 22, Fri Feb 24)

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.

Lectures 13 (Wed, Mar 1)

The proof of the fact that TTC gives a solution in CORE, and that CORE is unique for this problem may be found in Notes by Widmayer and Dutting.

Stable Matching: The algorithm we discussed is by Gale and Shapley (1962), and is known as Differed Acceptance (DA) or Proposal Algorithm. The proof that DA gives proposer optimal matching may be found in Tim's Notes. Further, it show that the DA as a mechanism is truthful for the proposers, but not for the other party.

A lot of literature on all three topics of TTC, Kidney exchange, and Stable Matching. Here is a 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 exaple 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 14 (Fri, Mar 3)

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.

Lectures 18 (Fri, Mar 17)

Myerson's paper on optimal auctions. It also handles the case with non-regular distributions.

Bulow-Klemperer paper (the general case)

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 21 (Wed, April 5)

Article on Spectrum Auction 2014.

Article on recent (2016-17) Spectrum Auction. There are many other. Here is the FCC Website for the auction.

Paper (relatively old) on enhancing competition in Spectrum Auctions. There are many more.

On the team who helped designed the auction.

Lectures 23 (Wed, April 12)

Kelly's 1997 paper, Kelly, Maullo and Tan 1998 paper.

Market equilibrium as a tool to solve resource allocation and scheduling problems: paper1 (bottom of page 7), Paper 2, and many more.

Lectures 24 (Fri, April 14)

The paper by Arrow and Debreu (1954) that showed existence of equilibrium for general exchange economies with firms.

Paper on PPAD hardness for exchange market with Leontief utilities.

Paper on PPAD hardness for Fisher market with separable peicewise-linear concave (SPLC) utilities.

Paper on a pivoting algorithm for exchange markets with SPLC utilities.

Paper on strongly polynomial time algorithm for Fisher market with Linear utilities. Strongly polynomial time algorithm for exchange markets with linear utilities is still open!

Tentative Plan

Date	Topics	Reading
Wed, Apr 7 Fri, Apr 18	(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.