Mechanism design in the presence of Bayesian priors has received much attention in the Economics literature, focusing among other problems on generalizing Myerson's celebrated auction to multi-item settings. Nevertheless, only special cases have been solved, with a general solution remaining elusive. More recently, there has been an explosion of algorithmic work on the problem, focusing on computation of optimal auctions, and understanding their structure. The goal of this tutorial is to overview this work, with a focus on our own work. The tutorial will be self-contained and aims to develop a usable framework for mechanism design in multi-dimensional settings.
Tutorial Venue
Sheraton Palo Alto
625 El Camino Real
Palo Alto, CA 94301
USA
Tutorial Schedule
Session 1 (8:30am-10:30am)
Coffee Break (provided) (10:30am-11am)
Session 2 (11:00am-12:30pm)
Abstracts
Part 1: Optimal Multi-Item Auctions
Speaker: Constantinos Daskalakis (MIT)
This part of the tutorial will develop computationally efficient revenue-optimal auctions for selling multiple items to multiple additive bidders, i.e. bidders who value bundles of items additively in their contents. We will chacracterize the structure of optimal auctions in multi-item settings, explaining how to properly generalize Myerson's single-item auction. We will also delve into the efficient computation of optimal auctions. This part of the tutorial will focus on structural results, and will require minimal training in algorithms to follow.
Part 2: Revenue-Optimal Mechanisms
Speaker: Yang Cai (UC Berkeley and McGill University)
We introduce complexity to the revenue maximization problem considered in Part 1 in two respects: we allow constraints on the feasible outcomes and also allow for more general bidder valuations. We will show how to extend our structural results from Part 1, explain the algorithmic challenges that arise for the computation of optimal mechanisms in this more general setting, and provide detailed solutions to address them. Our focus will be both structural and algorithmic. En route to obtaining our results, we establish a theorem that generalizes the classical equivalence of linear optimization and separation for use in Bayesian mechanism design, which is of independent interest.
Part 3: Beyond Revenue: Optimal Mechanisms for Non-linear Objectives
Speaker: Matt Weinberg (MIT)
In this part of the tutorial, we further extend the framework developed in Parts 1 and 2 to develop a generic reduction from mechanism to algorithm design, accommodating arbitrary objectives beyond revenue and welfare. We will explain the challenges that arise in applying this extension to objectives such as makespan and fairness, and expand further our algorithmic techniques for addressing them. The key algorithmic tool developed in this section is a generalization of the equivalence of linear optimization and separation accommodating traditional approximation algorithms and specific types of bi-criterion approximation algorithms. Finally, we will discuss open problems and future directions.