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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorMao, J-
dc.contributor.authorWeinberg, SM-
dc.date.accessioned2018-07-20T15:10:28Z-
dc.date.available2018-07-20T15:10:28Z-
dc.date.issued2016en_US
dc.identifier.citationBraverman, M, Mao, J, Weinberg, SM. (2016). Interpolating between truthful and non-truthful mechanisms for combinatorial auctions. 3 (1444 - 1457en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr15m3h-
dc.description.abstractWe 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.en_US
dc.format.extent1444 - 1457en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleInterpolating between truthful and non-truthful mechanisms for combinatorial auctionsen_US
dc.typeConference Articleen_US
dc.date.eissued2016en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Interpolating between truthful and non-truthful mechanisms for combinatorial auctions.pdf264.41 kBAdobe PDFView/Download


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