Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

DOI10.1137/1.9781611974331.CH99zbMATH Open1417.91228arXiv1511.02831OpenAlexW2950920780MaRDI QIDQ4575682FDOQ4575682

Authors: Mark Braverman, Jieming Mao, S. Matthew Weinberg 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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 Devanur et. al.~cite{DevanurMSW15} (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.

Full work available at URL: https://arxiv.org/abs/1511.02831

Recommendations

• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• Truthful approximation mechanisms for restricted combinatorial auctions
• Two Randomized Mechanisms for Combinatorial Auctions

zbMATH Keywords

communication complexitycombinatorial auctionsinterpolation mechanism

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (2)

• Best-response dynamics in combinatorial auctions with item bidding
• Learning in auctions: regret is hard, envy is easy

This page was built for publication: Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575682)