** **

Shahar Dobzinski

**Approximations and Truthfulness: The Case of Multi-Unit Auctions **

**
**

**M****onday
September 21, 2009**

**4:00 PM,
**
5130 Upson Hall

__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