|Picasso's Bull, December 1945 -- January 1946.|
Mechanism Design and Approximation
Textbook: Mechanism Design and Approximation (pdf available)
Instructor: Jason D. Hartline.
Online Discussion: on Piazza. (Enroll with access code picasso)
Office Hours: TBA; Ford 3-329.
Synopsis. This course is a self-study course from the manuscript "Mechanism Design and Approximation" which is based on a graduate course that has been developed at Northwestern over the past five years. Over the fall quarter we will work through roughly one chapter per week. The week will start with students reading and discussing the material of the chapter and it will conclude with students working together to solve and write up solutions to the chapter exercises.
Excerpt from Chapter 1: Our world is an interconnected collection of economic and computational systems. Within such a system, individuals optimize their actions to achieve their own, perhaps selfish, goals; and the system combines these actions with its basic laws to produce an outcome. Some of these systems perform well, e.g., the national residency matching program which assigns medical students to residency programs in hospitals, e.g., auctions for online advertising on Internet search engines; and some of these systems perform poorly, e.g., financial markets during the 2008 meltdown, e.g., gridlocked transportation networks. The success and failure of these systems depends on the basic laws governing the system. Financial regulation can prevent disastrous market meltdowns, congestion protocols can prevent gridlock in transportation networks, and market and auction design can lead to mechanisms for allocating and exchanging goods or services that yield higher profits or increased value to society.
This text focuses on a combined computational and economic theory for the study and design of mechanisms. A central theme will be the tradeoff between optimality and other desirable properties such as simplicity, robustness, computational tractability, and practicality. This tradeoff will be quantified by a theory of approximation which measures the loss of performance of a simple, robust, and practical approximation mechanism in comparison to the complicated and delicate optimal mechanism. The theory provided does not necessarily suggest mechanisms that should be deployed in practice, instead, it pinpoints salient features of good mechanisms that should be a starting point for the practitioner.
Textbook. Mechanism Design and Approximation
- Chapter 1: Mechanism Design and Approximation
- Topics: mechanism design, approximation, first-price auction, second-price auction, lottery, posted pricings
- Dates: Sept 23-29
- Chapter 2: Equilibrium
- Topics: Bayes-Nash equilibirum, dominant strategy equilibrium, single-dimensional agents, revenue equivalence, revelation principle, incentive compatibility.
- Dates: Sept 30-Oct 6
- Chapter 3: Optimal Mechanisms
- Topics: single-dimensional mechanism design, surplus-optimal mechanism (VCG), revenue-optimal mechanism, revenue curves, virtual values, ironing, marginal revenue, revenue linearity, Lagrangian virtual values
- Dates: Oct 7-Oct 15 (1.5 weeks)
- Chapter 4: Bayesian Approximation
- Topics: reserve pricing, posted pricing, prophet inequality, correlation gap, matroid set systems, greedy algorithms, monotone hazard rate distributions.
- Dates: Oct 16-27 (1.5 weeks)
- Chapter 5: Prior-independent Approximation
- Topics: Bulow-Klemperer, single sample mechanism, digital goods.
- Dates: Oct 28-Nov 3
- Chapter 6: Prior-free Approximation
- Topics: envy-free pricing (benchmark), random sampling auction, profit extraction, lower bounds.
- Dates: Nov 4-10
- Chapter 7: Multi-dimensional and Non-linear Preferences
- Topics: revenue linearity, interim feasibility, unit-demand agents, agents with budgets, optimal mechanisms as convex optimization, matching markets.
- Dates: Nov 11-17
- Chapter 8: Multi-dimensional and Non-linear Approximation
- Topics: posted pricing, approximate revenue linearity, single-dimensional representative environments
- Dates: Nov 18-Dec 1 (two weeks, happy thanksgiving)
- Chapter 9: Computational Tractability
- Topics: approximation algorithms, greedy-by-value, BIC blackbox reductions, payment computation.
- Dates: Dec 2-8.