On the Complexity of Optimal Correlated Auctions and Reverse Auctions

We investigate the problem of finding a revenue-optimal auction with correlated bidders. We give an algorithm for the exact solution for two bidders, and for a 5 3-approximation for many bidders, improving from O(n 6) runtime to O(n 3) for both problems by exploiting structural properties of this problem directly. We show that for correlated bidders, reverse auctions behave differently from auctions. For two bidders we discuss a constant-factor reduction in complexity. For k ≥ 3 bidders, we show that the optimal reverse auction must sometimes buy k copies of the item.