Computer Science Theory Seminar

Renato Paes LemeGoogle Research New York
Non-clairvoyant mechanism design

Monday, October 16, 2017 - 4:00pm
Gates 122

Today we run auctions in the internet by adapting classical formats that were originally designed for one-off auctions (art, stamps, spectrum, ...). In this talk, I'll discuss how we can use the repeated nature of internet auctions to design the next generation of auctions for the web. In the first part of the talk, I'll give an introduction to the theory of dynamic mechanism design.

In the second part, I'll discuss which problems need to be addressed in current dynamic mechanisms to make them practical for the web. I'll focus on the issue of clairvoyance, which is the fact that traditional mechanisms usually depend on information that the seller doesn't have in practice. We introduces the concept of non-clairvoyance, which is a measure-theoretic restriction on the information that the seller is allowed to use. A dynamic mechanism is non-clairvoyant if the allocation and pricing rule at each period does not depend on the type distributions in future periods. The main result is that the revenue of non-clairvoyant mechanisms is comparable to clairvoyant ones.

Time permitting, I'll also discuss other issues, such as stationarity, analyze the performance of such mechanisms on data and present a general technique for designing dynamic mechanisms (bank accounts mechanisms).

The talk is based on joint work with Vahab Mirrokni, Pingzhong Tang and Song Zuo (