Speaker: Aaron Roth

Title: Truthful Mechanisms for Online Supply 

Abstract:
Motivated by the sale of banner ads, we study the mechanism design
problem of selling items to a set of n known bidders when the supply
is unknown and arrives online. We begin with the simplest case, when
all items are identical, and bidders each demand only a single item.
In this case, the algorithmic problem is trivial; the greedy algorithm
that simply assigns items as they come in to the highest bidders
achieves optimal social welfare. However, such an algorithm depends on
knowing the true values that the bidders place on the items, and using
such a mechanism, there is no way to incentivize selfish bidders to
reveal this information truthfully. In fact, we show that in the face
of adversarial supply, no deterministic ex-post truthful mechanism can
achieve better than a trivial n-approximation to social welfare. We
then consider randomized mechanisms, and give a simple mechanism that
achieves a 2*log(n) approximation to social welfare; Unfortunately, we
also show that no envy-free mechanism can achieve better than a
logn/loglogn approximation to social welfare, and no randomized
mechanism can achieve better than a loglog(n) approximation.

We then study the case in which the supply is stochastic rather than
adversarial: the number of available items is drawn from a
distribution that is known to the mechanism. We give a mechanism which
achieves a 16-approximation to social welfare (given mild assumptions
on the distribution). This provides a strong separation between the
welfare guarantees achievable in the adversarial and in the stochastic
models.

Time permitting, we will discuss extensions to the case of multiple
item types, and to more general bidder valuations.

This is joint work with Moshe Babaioff and Liad Blumrosen.