CS364B: Frontiers in Mechanism Design (Winter 2014)

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

Teaching Assistant:

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.

Lecture videos and notes

Schedule and references:

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

PART II: DSIC APPROXIMATION MECHANISMS FOR NP-HARD CASES

PART III: BETTER GUARANTEES FOR WEAKER SOLUTION CONCEPTS

PART IV: THE PRICE OF ANARCHY IN SIMPLE AUCTIONS

PART V: MULTI-PARAMETER REVENUE MAXIMIZATION