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.
展开▼
