Amin Saberi
Georgia Tech
Abstract:
We study a fundamental problem in micro economics called
optimal auction design: A seller wishes to sell an item to
a group of self-interested agents. Each agent i has a
privately known valuation vi for the object. Given a
distribution on these valuations, the goal is to construct an
optimal auction, i.e. a truth revealing protocol that maximizes the
seller's expected revenue.
We study this problem from a computational perspective and show several lower bounds. In particular we prove that no deterministic polynomial time ascending auction can achieve an approximation ratio better than 3/4. The probability distribution constructed in our example has sensitive dependencies among the agents. On the flip side, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1.
Joint work with Amir Ronen.