Skip to main content

Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

Author(s): Braverman, Mark; Mao, J; Weinberg, SM

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr15m3h
Abstract: We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpolation mechanism has two phases. In the first phase, the bidders participate in some non-truthful protocol whose output is itself a truthful protocol. In the second phase, the bidders participate in the truthful protocol selected during phase one. Note that virtually all existing auctions have either a non-existent first phase (and are therefore truthful mechanisms), or a non-existent second phase (and are therefore just traditional protocols, analyzed via the Price of Anarchy/Stability). The goal of this paper is to understand the benefits of interpolation mechanisms versus truthful mechanisms or traditional protocols, and develop the necessary tools to formally study them. Interestingly, we exhibit settings where interpolation mechanisms greatly outperform the optimal traditional and truthful protocols. Yet, we also exhibit settings where interpolation mechanisms are provably no better than truthful ones. Finally, we apply our new machinery to prove that the recent single-bid mechanism of Deva-nur et. al. [DMSW15] (the only pre-existing interpolation mechanism in the literature) achieves the optimal price of anarchy among a wide class of protocols, a claim that simply can't be addressed by appealing just to machinery from communication complexity or the study of truthful mechanisms.
Publication Date: 2016
Electronic Publication Date: 2016
Citation: Braverman, M, Mao, J, Weinberg, SM. (2016). Interpolating between truthful and non-truthful mechanisms for combinatorial auctions. 3 (1444 - 1457
Pages: 1444 - 1457
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.