Limitations of Deterministic Auction Design for Correlated Bidders

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 Pierrakos (STOC 11) proved that it is APX-hard, obtaining an explicit inapproximability factor of 99.95%. In the current paper, we strengthen this inapproximability factor to 57/58 approximate to 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 approximate to 92.9%, improving an explicit gap of 947/948 approximate to 99.9% by Dobzinski, Fu, and Kleinberg (STOC 11).