CS364B: Frontiers in Mechanism Design (Winter 2014)

Instructor: Tim Roughgarden (Office hours: After class and by appointment.)

Teaching Assistant:

• Okke Schrijvers (Office hours: Tuesdays 3-5 PM, in Gates 463A. Email: okkes "at" stanford.edu)

Time/location: 2:15-5 PM on Wednesdays in Hewlett 103.

Piazza site: here

Course description: Advanced topics in mechanism design. Possible topics include ascending auctions and other indirect mechanisms; Bayes-Nash equilibrium analysis; the price of anarchy in simple auctions; correlated and interdependent valuations; black-box reductions in algorithmic mechanism design; revenue maximization in multi-parameter settings.

Prerequisites: CS364A

Course requirements: All students are required to complete weekly exercise sets, which fill in details from lecture. Students taking the course for a letter grade are also required to complete a course project, which involves synthesizing recent research papers and/or working on open research problems (details TBA). No late assignments accepted.

• A LaTeX template that you can use to type up solutions. Here and here are good introductions to LaTeX.

• Exercise Set #1 (Due by class Wed 1/15.)
• Exercise Set #2 (Due by class Wed 1/22.)
• Exercise Set #3 (Due by class Wed 1/29.)
• Exercise Set #4 (Due by class Wed 2/5.)
• Exercise Set #5 (Optional.)

Lecture videos and notes

• Lecture 1 (Ascending Auctions):   Video    Notes (alpha version)
• Lecture 2 (Unit-Demand Valuations):   Video    Notes (alpha version)
• Lecture 3 (Crawford-Knoer Auction):   Video    Notes (alpha version)
• Lecture 4 (Clinching Auction):   Video    Notes (alpha version)
• Lecture 5 (Gross Substitutes I):   Video    Notes (alpha version)
• Lecture 6 (Gross Substitutes II):   Video    Notes (alpha version)
• Bonus Lecture (Gross Substitutes III): (no video)    Notes (alpha version)
• Lecture 7 (Submodular Valuations):   Video    Notes (alpha version)
• Lecture 8 (MIR and MIDR Mechanisms):   Video    Notes (alpha version)
• Lecture 9 (Scaling Algorithms):   Video    Notes (alpha version)
• Lecture 10 (Convex Rounding):   Video    Notes (alpha version)
• Lecture 11 (Shrinking Auction):   Video    Notes (alpha version)
• Lecture 12 (BIC Mechanisms):   Video    Notes (incomplete draft)
• Lecture 13 (Black-Box Reductions):   Video
• Lecture 14 (POA of Simple Auctions):   Video    Notes (alpha version)
• Lecture 15 (Bayes-Nash POA):   Video    Notes (alpha version)
• Lecture 16 (First-Price Auctions):   Video    Notes (alpha version)
• Lecture 17 (Uniform-Price Auctions):   Video    Notes (alpha version)
• Lecture 17.5 (Beyond Smoothness):   Video    Notes (alpha version)
• Lecture 18 (Revenue Maximization):   Video    Notes (alpha version)
• Lecture 19 (Border's Theorem):   Video    Notes (alpha version)
• Lecture 20 (Optimal Mechanisms):   Video    Notes (alpha version)

Schedule and references:

PART I: WELFARE MAXIMIZATION: TRACTABLE SPECIAL CASES AND ASCENDING IMPLEMENTATIONS

• Lecture 1 (Wed 1/8): Ascending auctions. EPIC vs. DSIC implementations. Further reading:
  • AGT book, Section 9.4.

• Lecture 2 (Wed 1/8): Unit-demand bidders. Walrasian equilibria. Characterization of VCG payments. Further reading:
  • AGT book, Section 11.3.2.
  • Shapley/Shubik, The Assignment Game I: The Core, International Journal of Game Theory, 1972.
  • Leonard, Elicitation of Honest Preferences for the Assignment of Individuals to Positions, Journal of Politcal Economy, 1983.
  • Goemans, lecture notes on bipartite matching.

• Lecture 3 (Wed 1/15): Crawford-Knoer auction for unit-demand bidders. Convergence to smallest Walrasian equilibrium. EPIC guarantee. Further reading:
  • Crawford/Knoer, Job Matching with Heterogenous Firms and Workers, Econometrica, 1981.
  • Demange/Gale/Sotomayor, Multi-Item Auctions, Journal of Politcal Economy, 1986.

• Lecture 4 (Wed 1/15): Multi-unit auctions with downward-sloping valuations. Ausubel's clinching auction. Further reading:
  • Ausubel, An Efficient Ascending-Bid Auction for Multiple Objects, American Economic Review, 2004.
  • Nisan, Algorithmic Mechanism Design: Through the lens of Multi-unit auctions, 2014, Sections 2.2 and 4.2.

• Lecture 5 (Wed 1/22): Kelso-Crawford auction. Gross substitutes: definition, examples, and existence of Walrasian equilibria. Further reading:
  • AGT book, Section 11.7.1.
  • Kelso/Crawford, Job Matching, Coalition Formation, and Gross Substitutes, Econometrica, 1982.
  • Gul/Stacchetti, Walrasian Equilibrium with Gross Substitutes, Journal of Economic Theory, 1999.

• Lecture 6 (Wed 1/22): Walrasian equilibria exist if and only if the configuration LP relaxation is exact. Representations of valuation functions. Polynomial-time welfare maximization with gross substitutes valuations. Further reading:
  • AGT book, Sections 11.3 and 11.5.
  • Bikhchandani/Mamer, Competitive Equilibrium in an Exchange Economy with Indivisibilities, Journal of Economic Theory, 1997.
  • Nisan/Segal, The communication requirements of efficient allocations and supporting prices, Journal of Economic Theory, 2006.
  • Goemans, lecture notes on the ellipsoid algorithm.

• Bonus Lecture (Fri 2/7): Gross substitutes valuations and greedy algorithms. Further reading:
  • Paes Leme, Gross Substitutability: An Algorithmic Survey, working paper, 2013.

PART II: DSIC APPROXIMATION MECHANISMS FOR NP-HARD CASES

• Lecture 7 (Wed 1/29): Final comments on gross substitutes valuations (see last section of the Lecture 5 notes). Introduction to and goals for Part II of the course. Welfare maximization with submodular valuations. Further reading:
  • AGT book, Section 11.7.2.
  • Gul/Stacchetti, Walrasian Equilibrium with Gross Substitutes, Journal of Economic Theory, 1999.
  • Lehmann/Lehmann/Nisan, Combinatorial Auctions with Decreasing Marginal Utilities, EC 2001.
  • Fu/Kleinberg/Lavi, Conditional Equilibrium Outcomes via Ascending Price Processes with Applications to Combinatorial Auctions with Item Bidding, EC 2012.

• Lecture 8 (Wed 1/29): Maximal-in-range (MIR) and maximal-in-distributional-range (MIDR) mechanisms. Multi-unit auctions with general monotone valuations. Welfare maximization with multiple copies of each item. Further reading:
  • AGT book, Section 12.3.
  • Dughmi, Randomization and Computation in Strategic Settings, PhD Thesis, 2011, Sections 3.3.1, 3.3.2, 3.4.1, 3.4.2.
  • Nisan, Algorithmic Mechanism Design: Through the lens of Multi-unit auctions, 2014, Section 5.3.
  • Raghavan/Thompson, Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs, Combinatorica, 1987. (See Section 4.)

• Lecture 9 (Wed 2/5): MIDR mechanisms via scaling algorithms. DSIC (1-epsilon)-approximation for general valuations with logarithmic supply. Further reading:
  • AGT book, Section 12.3.
  • Lavi/Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, FOCS 2005.

• Lecture 10 (Wed 2/5): MIDR mechanisms via convex rounding. DSIC .63-approximation for converage valuations. Further reading:
  Dughmi/Roughgarden/Yan, From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions, STOC 2011.

PART III: BETTER GUARANTEES FOR WEAKER SOLUTION CONCEPTS

• Lecture 11 (Wed 2/12): Brief comments on impossibility results for DSIC implementations (see Lecture 10 notes). The shrinking auction for single-value unknown multi-minded bidders. Further reading:
  • AGT book, Section 12.5.
  • Babaioff/Lavi/Pavlov, Single-Value Combinatorial Auctions and Algorithmic Implementation in Undominated Strategies, JACM 2009.

• Lecture 12 (Wed 2/12): Finish analysis of the shrinking auction (see Lecture 11 notes). Bayes-Nash equilibria and Bayesian incentive compatible mechanisms. Introduction to black-box reductions (see Lecture 13 notes). Further reading:
  • Hartline, Mechanism Design and Approximation, Sections 2.2-2.5 and 2.10.

• Lecture 13 (Wed 2/19): Black-box reduction from BIC mechanism design to approximation algorithm design. Further reading:
  • Bei/Huang, Bayesian Incentive Compatibility via Fractional Assignments, SODA 2011.
  • Hartline/Kleinberg/Malekian, Bayesian Incentive Compatibility via Matchings, SODA 2011.

PART IV: THE PRICE OF ANARCHY IN SIMPLE AUCTIONS

• Lecture 14 (Wed 2/19): Simultaneous second-price auctions with submodular and XOS valuations. Further reading:
  • Christodoulou/Kovacs/Schapira, Bayesian Combinatorial Auctions, ICALP 2008.

• Lecture 15 (Wed 2/26): The Bayes-Nash POA of simultaneous second-price auctions. Further reading:
  • Bhawalkar/Roughgarden, Welfare Guarantees for Combinatorial Auctions with Item Bidding, SODA 2011.
  • Roughgarden, The Price of Anarchy in Games of Incomplete Information, EC 2012.
  • Syrgkanis, Bayesian Games and the Smoothness Framework, 2012.

• Lecture 16 (Wed 2/26): The Bayes-Nash POA of first-price auctions. Further reading:
  • Hassidim/Kaplan/Mansour/Nisan, Non-Price Equilibria in Markets of Discrete Goods, EC 2011.
  • Syrgkanis/Tardos, Composable and Efficient Mechanisms, STOC 2013.

• Lecture 17 (Wed 3/5): The Bayes-Nash POA of uniform-price auctions with downward-sloping valuations. Subadditive valuations and bypassing smoothness arguments. Further reading:
  • de Keijzer/Markakis/Schaefer/Telelis, On the Inefficiency of Standard Multi-unit Auctions, ESA 2013.
  • Babaioff/Lucier/Nisan/Paes Leme, On the Efficiency of the Walrasian Mechanism, 2013.
  • Feldman/Fu/Gravin/Lucier, Simultaneous Auctions are (almost) Efficient, STOC 2013.

PART V: MULTI-PARAMETER REVENUE MAXIMIZATION

• Lecture 18 (Wed 3/5): Recap of single-parameter revenue-maximization. Multi-parameter challenges. A linear programming formulation of the optimal mechanism. Further reading:
  • Manelli/Vincent, Bundling As An Optimal Selling Mechanism For A Multiple-Good Monopolist, JET 2006.
  • Hart/Nisan, Approximate Revenue Maximization with Multiple Items, EC 2012.

• Lecture 19 (Wed 3/12): Interim allocation rules and Border's theorem. Further reading:
  • Lecture notes by Vohra.

• Lecture 20 (Wed 3/12): Structure of optimal multi-parameter mechanisms. Further reading:
  • Cai/Daskalakis/Weinberg, Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization, FOCS 2012.
  • Alaei/Fu/Haghpanah/Hartline/Malekian, Bayesian Optimal Auctions via Multi- to Single-agent Reduction, EC 2012.