Theory Seminar: The FedEx Problem

Friday, November 4, 2016 - 2:00pm
CS 3310

Speaker Name: 

Kira Goldner

Speaker Institution: 

University of Washington




(Joint work with Amos Fiat, Anna Karlin, and Elias Koutsoupias.)

Consider the following setting: a customer has a package and is willing to pay up to some value v to ship it, but needs it to be shipped by some deadline d. Given the joint prior distribution from which (v, d) pairs are drawn, we characterize the auction that yields optimal revenue, contributing to the very limited understanding of optimal auctions beyond the single-parameter setting. Our work further demonstrates the importance of 'ironing' in revenue maximization, helping to illustrate why randomization is necessary to achieve optimal revenue. Finally, we strengthen the emerging understanding that duality is useful for both the design and analysis of optimal auctions in multi-parameter settings.