Shahar Dobzinski
Approximations and Truthfulness: The Case of Multi-Unit Auctions
Abstract:
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