Limitations of randomized mechanisms for combinatorial auctions

• 成果类型: Article
• 署名作者: Dughmi, Shaddin; Vondrak, Jan
• 署名单位: University of Southern California; International Business Machines (IBM); IBM USA
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.01.007
• 发表日期: 2015
• 页码: 370-400
• 关键词: Algorithmic mechanism design; combinatorial auctions; incentive compatibility; submodular valuations

摘要

We address the following fundamental question in the area of incentive-compatible mechanism design: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation? In particular, can polynomial-time truthful-in-expectation mechanisms achieve a near-optimal approximation ratio for combinatorial auctions with submodular valuations? We prove that this is not the case: There is a constant gamma > 0 such that there is no randomized mechanism that is truthful-in-expectation or even approximately truthfulin-expectation - and guarantees an m(-gamma)-approximation to the optimal social welfare for combinatorial auctions with submodular valuations in the value oracle model. In contrast, a non-truthful (1-1/e)-approximation algorithm is known (Vondrak, 2008), and a truthfulin-expectation (1-1/e)-approximation mechanism was recently developed for the special case of coverage valuations (Dughmi et al., 2011b). We also prove an analogous result for the combinatorial public projects (CPP) problem. Both our results present a significant separation between coverage functions and submodular functions, which does not occur for these problems without strategic considerations. (C) 2014 Elsevier Inc. All rights reserved.