Shahar Dobzinski

Approximations and Truthfulness: The Case of Multi-Unit Auctions


Monday  September 21, 2009
4:00 PM, 5130 Upson Hall



In this talk we study the clash between computational efficiency and truthfulness: how good are polynomial-time truthful mechanisms comparing to polynomial-time (non-truthful) algorithms?

To simplify the discussion, we restrict our attention to the problem of multi-unit auctions. We present a truthful algorithm that provides an approximation ratio of 2 for this problem, and argue that this is probably the best ratio achievable by a truthful deterministic polynomial-time algorithm. We then show that if randomization isallowed then there exists a polynomial-time randomized truthful (1+epsilon)-approximation algorithm.

Based on a joint work with Noam Nisan and a joint work with Shaddin Dughmi