Organizers: Rojin Rezvan (UT Austin) and Ariel Schvartzman (Google Research)

Date: week of June 20-23 (exact times TBA) 

Where: virtual - please register for access to live links. 

Abstract: Optimal multi-item auctions are known to be complex and hard to characterize. In fact, we know that no finite-sized mechanism can approximate the optimal mechanism when selling two items to a single, additive buyer. This pathological result constructs a valuation and distribution that can be exploited by a highly-tailored mechanism. One reason the revenue of this mechanism is unbounded is that it abuses the fact that the buyer can only interact with the mechanism once. Indeed, a series of recent works show how to get around this pathological construction via so-called buy-many or buy-k mechanisms, where the buyer is allowed to interact with the mechanism any number of times or k times, respectively. These new classes of mechanisms show that, perhaps, the benchmark set by the standard buy-one model is too strong to compare against and thus should be relaxed. 

Keywords: revenue maximization, multi-item mechanism design, buy-many mechanisms, correlated distributions.

Please note that the details below are subject to change due to time constraints and other restrictions. 

Structure

• Lecture 1 (Ariel Schvartzman, Google Research): Brief introduction to revenue maximization beyond single-item settings. Overview of the Hart-Nisan framework, proof of their main result and its converse. Overview of the remaining lectures. 

• Lecture 2 (Rojin Rezvan, UT Austin): Introduction to buy-many mechanisms (Briest et al. 2010) and the key pricing Lemma from (Chawla et al. 2019). Overview of the O(log n) approximation for arbitrary valuation classes. Discussion of other desirable properties that buy-many mechanisms satisfy.

• Lecture 3 (Rojin Rezvan, UT Austin): When is item-pricing good? Buy-many mechanisms in the case of totally ordered or partially ordered items. Discussion about buy-many mechanisms for the case of multiple buyers. 

• Lecture 4 (Ariel Schvartzman, Google Research): Fine-grained buy-many mechanisms.  Generalization of the Hart-Nisan framework to the case of buy-k mechanisms. Discussion of future directions.

Target Audience and Goals

The target audience will be an average EC attendee with previous exposure/familiarity to multi-item auction design. The lectures will encompass all known work in the CS literature on the topic, thus enabling any interested researcher to contribute in state-of-the-art work This will include all key technical tools and lemmas, as well as a rich discussion about future directions. In particular, one exciting direction is that of using the buy-many benchmark for the case of independent items. The goal of this tutorial is to encourage other researchers to join this line of work. 

Organizers

• Rojin Rezvan is a fourth year graduate student of Computer Science at the University of Texas at Austin, working under the supervision of Shuchi Chawla. Her primary research field is algorithmic mechanism design. 

• Ariel Schvartzman Cohenca is a research scientist at Google Research. He earned his PhD in Computer Science from Princeton University under the supervision of S. Matthew Weinberg. His primary research field is algorithmic mechanism design.  

Relevant Literature and Full Proposal 

Please see the full proposal with the appropriate citations and references here.