Research Repository

Limitations of Deterministic Auction Design for Correlated Bidders

Caragiannis, Ioannis and Kaklamanis, Christos and Kyropoulou, Maria (2016) 'Limitations of Deterministic Auction Design for Correlated Bidders.' ACM Transactions on Computation Theory, 8 (4). pp. 1-18. ISSN 1942-3454

arxiv-final-TOCT-3OAD.pdf - Accepted Version

Download (217kB) | Preview


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 1999/2000 = 99.95%. In the current paper, we strengthen this inapproximability factor to 63/64 ≈ 98.5%. Our proof is based on a gap-preserving reduction from the Max-NM 3SAT problem; a variant of the maximum satisfiability problem where each clause has exactly 3 literals and no clause contains both negated and unnegated literals. 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).

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 18 Dec 2018 13:29
Last Modified: 23 Sep 2022 19:03

Actions (login required)

View Item View Item