Fall 2019 — Algorithmic Game Theory

Location: Cory 367

Time: 18:30 - 20:00

Logistics: Please fill out our interest form here if you would like to join this reading group

From an article by Professor Tim Roughgarden:

The widespread adoption of the Internet and the emergence of the Web changed society’s relationship with computers. The primary role of a computer evolved from a stand-alone, well-understood machine for executing software to a conduit for global communication, content-dissemination, and commerce. The algorithms and complexity theory community has responded to these changes by formulating novel problems, goals, and design and analysis techniques relevant for modern appli- cations. Game theory, which has studied deeply the interaction between competing or cooperating individuals, plays a central role in these new developments. Research on the interface of theoretical computer science and game theory, an area now known as algorithmic game theory (AGT), has exploded phenomenally over the past ten years.

The primary research themes in AGT differ from those in classical microeconomics and game theory in important, albeit predictable, respects. Firstly in application areas: Internet-like networks and non-traditional auctions motivate much of the work in AGT. Secondly in its quantitative engi- neering approach: AGT research typically models applications via concrete optimization problems and seeks optimal solutions, impossibility results, upper and lower bounds on feasible approxi- mation guarantees, and so on. Finally, AGT usually adopts reasonable (e.g., polynomial-time) computational complexity as a binding constraint on the feasible behavior of system designers and participants. These themes, which have played only a peripheral role in traditional game theory, give AGT its distinct character and relevance.

Date	Topic	Resources
Week 1 (9/17)	Introduction to (Algorithmic) Game Theory. Why does Algorithmic Game Theory Matter? Week 1 of Roughgarden’s AGT.	notes
Week 2 (9/24)	Introduction to Auctions. What properties make a good auction? Vickrey, Sponsored Search, and Myerson’s Lemma. Week 2 of Roughgarden’s AGT. Week 3 of Roughgarden’s AGT.	notes
Week 3 (10/1)	The challenge of Revenue Maximization. Briefly discuss the difference between revenue maximization and welfare maximization, then talk about the revelation principle. Finally, find a formula relating revenue to welfare. Week 4 of Roughgarden’s AGT (briefly). Week 5 of Roughgarden’s AGT.	notes
Week 4 (10/8)	Prophet Inequality. How close can we get in sequential auctions to oracle optimality? Discuss interesting single-item auctions with Prophet Inequality, and introduce Bulow-Klemperer. Find interesting problems from psets online to discuss. Week 6 of Roughgarden’s AGT.	notes
Week 5 (10/15)	Multi-parameter Mechanism Design, and VCG Mechanism. Can we find desirable auctions when demand is multi-parametered? Using VCG, we look at Combinatorial Auctions. Week 7 of Roughgarden’s AGT. Week 8 of Roughgarden’s AGT.
Week 6 (10/22)	Mechanism Design in non-monetary settings: school choice, kidney exchange, stable matching, etc. Briefly, we discuss the Clinching Auction. Week 9 of Roughgarden’s AGT. Week 10 of Roughgarden’s AGT.
Week 7 (10/29)	Price of Anarchy. How much can games/outcomes suffer if everyone decides to act selfishly instead of working together? We revisit Braess’ Paradox, and find tighter bounds on the Price of Anarchy. We introduce the Atomic Selfish Routing game. Week 11 of Roughgarden’s AGT. Week 12 of Roughgarden’s AGT.
Week 8 (11/5)	Equilibrium Hierarchy. What types of equilibria exist in games, and how can we think about them? Find interesting problems from psets online to discuss. Week 13 of Roughgarden’s AGT.
Week 9 (11/12)	Price of Anarchy 2: Electric Boogaloo. Analysis of the price of different forms of equilibria. Week 14 of Roughgarden’s AGT. Week 15 of Roughgarden’s AGT.
Week 10 (11/19)	Convergence to Equilibrium: Should we expect players to converge towards an equilibrium? How quickly? Under what circumstances? Lecture 17 is on the Experts algorithm, but we won’t discuss it much because it’s covered in CS 170. Week 16 of Roughgarden’s AGT. Week 17 of Roughgarden’s AGT.
Week 11 (11/26)	Convergence to more specific types of equilibrium, including Correlated Equilibrium and Mixed Nash Equilibrium. We’ll look at Minimax, Max Cut, and Congestion problems. Week 18 of Roughgarden’s AGT. Week 19 of Roughgarden’s AGT.
Week 12 (12/3)	Intractability of Equilibrium: which games are inherently intractable in terms of finding equilibria? Wrapup, with look at take-home final. Week 20 of Roughgarden’s AGT. Final of Roughgarden’s AGT.