Monday, April 12 , 2010
4:00pm

5130 Upson Hall

Abstract: It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true for single-parameter domains: creating a randomized truthful mechanism is essentially as easy as a *single* call to a monotone allocation function. Our main result is a general procedure to take a monotone allocation rule and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. Moreover, the mechanism implements the same outcome as the original allocation rule with probability
arbitrarily close to $1$, and requires evaluating that allocation rule only once.

Because our reduction is simple, versatile, and general,  it has many applications to mechanism design problems in which re-evaluating the allocation function is either burdensome or informationally impossible. Applying our result to the multi-armed bandit problem, we obtain truthful randomized mechanisms whose regret matches the information-theoretic lower bound up to logarithmic factors. On the other hand, we show that this is impossible for truthful deterministic mechanisms.

Joint work with Moshe Babaioff, Bobby Kleinberg and Yogi Sharma, ACM EC'09 and ACM EC'10.