On the hardness of optimal auctions

Abstract

We study a fundamental problem in microeconomics 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 v/sub i/ 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. In contrast, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1.