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 v_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 \frac{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.