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 20Voting Notes by Widmayer and Dutting. Notes by Tim
Tue, Sept 25Single item auctions -- First and second priceNotes by Tim.
Thu, Sept 27Single parameter auction. Myerson's LemmaNotes by Tim.
Tue, Oct 2Auction design to Algorithm design, Indirect Mechanism, Revelation PrincipleNotes by Tim.
Thu, Oct 4Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer TheoremNotes1 and Notes2 by Tim.
Tue, Oct 9Prophet Inequality, VCG, Combinatorial AuctionsProphet Inequality, VCG+Comb. Auction by Tim
Thu, Oct 11Implementability of Comb. AuctionKC Auction, VCG+Walrasian Equilibrium by Tim
Tue, Oct 16VCG properties, Spectrum AuctionNotes1, Notes2 by Tim
Selfish Routing, Congestion Games, Potential Games
Thu, Oct 18Selfish-Routing and Price of Anarchy Notes by Tim
Tue, Oct 23Network Over-Provisioning and Non-Atomic RoutingNotes by Tim.
Thu, Oct 25Congestion 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 GamesNotes 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 1No 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, EquilibriumNotes by Prof. Mansor. AGT book Chapter 5, Sections 1 and 3
    Eisenberg-Gale Convex Formulation, Kelly's resource allocation problem -- fair solutionAGT 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, StrategizationSlides. 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.