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 3Selfish-Routing and Price of Anarchy Notes by Prof. Tim Roughgarden
Wed, Feb 8Network Over-Provisioning and Non-Atomic RoutingNotes by Tim.
Fri, Feb 10Congestion 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 GamesNotes 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 3Voting Notes by Widmayer and Dutting. Slides by Joe Corliss
Wed, Mar 8Single item auctions -- First and second priceNotes by Tim.
Fri, Mar 10Single parameter auction. Myerson's LemmaNotes by Tim.
Wed, Mar 15Auction design to Algorithm design, Indirect Mechanism, Revelation PrincipleNotes by Tim.
Fri, Mar 17Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer TheoremNotes1 and Notes2 by Tim.
Wed, Mar 29Some Prior Independent Auctions, VCG Notes by Tim.
Fri, Mar 31No Lecture
Wed, April 5VCG properties, Spectrum AuctionNotes1, Notes2 by Tim
Fri, April 7Market: Fisher, EquilibriumNotes by Prof. Mansor. AGT book Chapter 5, Sections 1 and 3
Wed, April 12Eisenberg-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.
Fri, April 14Exchange 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 21Market: Discrete-goods, StrategizationSlides. Sections 2, 3.2 and 4.1 of this paper.
Wed, May 3Review SessionSlides

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.