Theory Seminar: Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

Friday, April 29, 2016 -
2:00pm to 3:00pm
CS 4310

Speaker Name: 

Benjamin Miller

Speaker Institution: 

UW Madison




We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers’ values are additive subject to a feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers.

Our work expands upon and unifies long lines of work on unit-demand settings and additive settings. We employ the ex ante relaxation approach developed by Alaei [2011] for reducing a multiple-buyer mechanism design problem with an ex post supply constraint into single-buyer ones with ex ante supply constraints. Solving the single-agent problems requires us to significantly extend techniques developed in the context of additive values by Li and Yao [2013] and their extension to subadditive values by Rubinstein and Weinberg [2015].