The seminal work of Myerson (Mathematics of OR 81) characterizes incentive-compatible single-item auctions among bidders with independent valuations. In this setting, relatively simple deterministic auction mechanisms achieve revenue optimality. When bidders have correlated valuations, designing the revenue-optimal deterministic auction is a computationally demanding problem; indeed, Papadimitriou and Pier-rakos (STOC 11) proved that it is APX-hard, obtaining an explicit in-approximability factor of 99.95%. In the current paper, we strengthen this inapproximability factor to 57/58 ≈ 98.3%. Our proof is based on a gap-preserving reduction from the problem of maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo 2 and uses the classical inapproximability result of Hastad (J. ACM 01). We furthermore show that the gap between the revenue of deterministic and randomized auctions can be as low as 13/14 ≈ 92.9%, improving an explicit gap of 947/948 ≈ 99.9% by Dobzinski, Fu, and Kleinberg (STOC 11).
展开▼
