Optimal deterministic auctions with correlated priors

• 成果类型: Article
• 署名作者: Papadimitriou, Christos; Pierrakos, George
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.08.009
• 发表日期: 2015
• 页码: 430-454
• 关键词: Revenue-maximizing auction design; Correlated priors; Approximation algorithms; computational complexity

摘要

We revisit the problem of designing the profit-maximizing single-item auction, solved by Myerson in his seminal paper for the case in which bidder valuations are independently distributed. We focus on general joint distributions, either discrete or Lipschitz-continuous, seeking the optimal deterministic incentive compatible auction. We give a geometric characterization of the optimal auction, resulting in a duality theorem and an efficient algorithm for finding the optimal deterministic auction in the two-bidder case and an NP-completeness result for three or more bidders. (C) 2013 Elsevier Inc. All rights reserved.