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

Lecture Schedule and Notes

Date	Topics	Reading
Games, Equilibria, and Computation
Wed, 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.
Fri, 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.
Wed, Sept 4	Lemke-Howson algorithm, Sperner	Notes on Lemke-Howson algorithm. Slides on Sperner.
Fri, Sept 6	Class PPAD and other TFNP classes, iterated dominance, and correlated equilibrium	For complexity classes see Slides. For iterated dominance and CE see Slides.
Wed, Sept 11	Other equilibrium ((coarse) correlated, stackelberg) and game (extensive form, Bayesian) notions.	See Slides.
Fri, 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
Wed, Sept 18	Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching.	Notes by Prof. Tim Roughgarden. Notes by Widmayer and Dutting
Fri, Sept 20	Single item auctions -- First and second price	Notes by Tim.
Wed, Sept 25	Single parameter auction. Myerson's Lemma	Notes by Tim.
Fri, Sept 27	VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle	On VCG, and notes on the rest by Tim.
Wed, Oct 2	Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem	Notes1 and Notes2 by Tim.
Fri, Oct 4	Prophet Inequality, Combinatorial Auctions	Prophet Inequality notes due to Tim, and Slides due to Brendan. Comb. Auction by Tim
Wed, Oct 9	Implementability of Comb. Auction	KC Auction by Tim
Fri, Oct 11	Walrasian Equilibrium	VCG+Walrasian Equilibrium by Tim
Wed, Oct 16	Case Study on Spectrum Auction	Spectrum Auc by Tim
Fri, Oct 18	Fair Division	For definitions see Section 1,2,3 except 3.2 from Notes by Endriss. Indivisible goods: for EF1 Section 3 of paper 1. For the remaining, Sections 3 and 4 (Lemma 1 for EFx) of paper 4.
Selfish Routing, Congestion Games, Potential Games
Wed, Oct 23	Selfish-Routing and Price of Anarchy	Notes by Tim
Fri, Oct 25	Network Over-Provisioning and Non-Atomic Routing	Notes by Tim.
Wed, Oct 30	Cancelled
Fri, Nov 1	Smooth Games	Notes by Tim on (i); this also includes smoothness proof for Location Games where players want to maximize payoff
Wed, Nov 6	Congestion games, Potential Games, Equilibrium Existence and Complexity of Computation. Cost Sharing Games	First part of Tim's Notes on Potential games. Notes by Prof. Kesselheim on complexity of computing NE in congestion games. Notes by Tim on Cost-sharing games
Fri, Nov 8	Best Response Dynamics.	Notes on best-response dynamics by Tim.
Wed, Nov 13	No-Regret Dynamics.	Notes by Tim.
Fri, Nov 15	Review Lecture/Swap regret
Wed, Nov 20	Presentation: Stable Matching: Algorithms, Results and Open Problems Presentation: Housing Allocation with Budget Constraints
Fri, Nov 22	Presentation: Analyzing GAN training with game theory Presentation: On finding fair allocation for chores Presentation: The stock market as a game
Wed, Dec 4	Presentation: Strategic Behavior in Dynamic Matching Presentation: A Bisection Protocol for Political Redistricting on Planar Graphs Presentation: Research on Factoring's Relationship with TFNP Subclasses
Fri, Dec 6	Presentation: A Trend in Games and Logic Presentation: Playing Poker with Game Theory Presentation: Market Dynamics Convergence

Relevant Material

Lecture 1 (Wed, 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 (Fri, 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. Here is a proof of Brouwer's theorem.

Lecture 3 (Wed, Sept 4)

Lemke-Howson algorithm. And a note on Sperner's Lemma.

Lecture 4 (Fri, 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 6 (Fri, 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 (Wed, 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).

Lecture 10 (Fri, Sept 27)

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

Lecture 11 (Wed, Oct 2)

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

Lecture 12 (Fri, 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).

Lecture 15 (Wed, Oct 16)

FCC Spectrum Auction website is here. The public reporting from the last auction.

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.

Lectures 17 (Wed, Oct 23):

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 21 (Wed, Nov 6):

We discussed how congestion games reduces to potential games. There is a reduction in the reverse direction as well. See Slides by Prof. Apt on Congestion to Potential game reduction.

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

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

Showing constant bound on price-of-stability in cost-sharing games with undirected graph is still open.

A latest paper on hierarchical Network Formation (cost-sharing) Games.

Remaining tentative topics we may cover (not in order)

Date	Topics	Reading
Games and Equilibiria
	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
Mechanism Design
	Voting	Notes by Widmayer and Dutting. Notes by Tim
Selfish Routing, Congestion Games, Potential Games
Fair Division
Markets
	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.

Presentation Abstracts

Wed, November 20th:

Stable Matching: Algorithms, Results and Open Problems
Forming stable matchings lies at the core of many human relations, from forming families to picking long-term roommates and colleagues. Ever since Gale and Shapley’s seminal paper in 1962, academia has been trying to generalize their findings to different settings, such as allowing multiple parties to be matched, partial preference lists and preference lists with ties, for instance. This talk aims to give a broad survey of such extensions and compactly present the most impactful results on the field, as well as contextualize their importance by presenting some potential and actual applications for the generalized versions of the problem.

Housing Allocation with Budget Constraints
In this project, we study the problem of housing allocation with budget constraints along with variants such as spousal allocation, and the combinatorial setting where agents can buy multiple houses. The input to the problem is a set of houses, a set of agents, who have preferences defined on the houses, and a budget. The goal is to price the houses and find an equilibrium allocation of houses to agents. We show how the basic version of the problem can be solved with a deferred acceptance algorithm, and expand the algorithm to solve the variations of the problem.

Fri, November 22th:

Analyzing GAN training with game theory
GAN is a family of machine learning algorithms that learns to generate realistic samples by playing a two-player minimax game. Since its proposal in 2014, people have been trying to analyze it from a game theory perspective; however, several challenges are still unsolved regarding the theoretical understanding of GAN training. In my project I will analyze some of the newest progresses in GT-related GAN researches and GAN-relevant GT researches and explore possibilities to combine them together.

On finding fair allocation for chores
In class we learnt about fair division of divisible goods, as well as the concept of Walrasian equilibrium that guarantees a Pareto optimal and envy free allocation. What if instead of goods, we have chores that we wish to allocate among a set of agents? In this talk, I will describe some challenges in this model, as well as give an efficient algorithm that finds a Pareto optimal and envy free allocation.

The stock market as a game
The stock market is one of the more complex problems in the world where there's numerous players that make the market in order to maximize their own profits. Our project aims to model the stock market as a game with multiple agents and attempt to maximize our own agent's profits within the environment. We use the S&P 500 index as a benchmark and try to use various techniques in order to game the market.

Wed, December 4th:

Strategic Behavior in Dynamic Matching
Dynamic matching, or matching with partial information and temporal constraints, is an important generalization of the stable matching with a variety of applications. This talk discusses manipulation strategies in the context of ride-sharing and introduces a different formulation of stability better-suited for dynamic matching. Finally, a strategy-proof and stable algorithm for this problem is proposed, along with some possible generalizations.

A Bisection Protocol for Political Redistricting on Planar Graphs
Every ten years, states must update their electoral district boundaries for state and federal elections using the latest U.S. Census results; this process is called redistricting. For over 200 years, political parties have at times engaged in gerrymandering, the manipulation of district lines for political advantage. As a potential remedy for gerrymandering, this presentation proposes the bisection protocol, a two-player zero-sum extensive-form redistricting game inspired by fair cake-cutting in which the two major parties alternately divide pieces of the state in half (up to rounding) to obtain a district plan. Computing the subgame perfect Nash equilibrium of the bisection protocol on planar graphs is proved NP-hard, even for M x 3 grid graphs. A mixed-integer programming (MIP) formulation is applied to small instances of the problem as a step toward understanding how the bisection protocol might play out in practice.

Research on Factoring's Relationship with TFNP Subclasses
We will explore the problem Factoring and its relationship with certain complexity classes inside TFNP, namely PPA, PPAD, and PLS. Buresh-Oppenheim proved that factoring a special subset of integers is in PPA. Jeřábek extended this result to general integers with randomized reductions. In this work we will summarize the results of Buresh-Oppenheim and Jeřábek, and then discuss some ideas that could be used to show that Factoring is in PPAD and PLS.

A Trend in Games and Logic
The question of how to synthesize finite-state systems to meet interactive specifications goes back to work by Pnueli and Rosner on the synthesis of reactive modules for linear temporal logic. This line of research has led to a string of new logics for checking properties of multiagent systems. A recent goal in this area is to find the right logic to express strategies and solution concepts from game theory for reasoning about such systems. The primary question to ask with such a logic is whether a given system satisfies a specification formula written in the logic. This is the model checking problem; it’s of obvious interest to the formal verification community. Whatever the logic, we want to minimize the complexity of the model checking problem, while keeping the logic expressive (these are in tension). In what follows, I’ll give an overview of recent work on a logic for a class of multi-agent system models called concurrent game structures.

Playing Poker with Game Theory
Recently, several breakthroughs have been made in creating AI to play Texas Hold'em, the most popular form of poker. In 2017, Libratus beat 4 top pros in a 1v1 format. And just this July, Pluribus beat pros with 6 players at a time. Both AI used the game theoretic concept of counterfactual regret. My talk will discuss the algorithms and techniques that enabled their success.

Market Dynamics Convergence
We survey the current formulations of Fisher and Arrow-Debreu markets, and the approaches to solve them. We propose 2 gradient-descent based heuristic approaches to solve linear Arrow-Debreu markets, and present experimental results related to their convergence.