On the Economic Efficiency of the Combinatorial Clock Auction

DOI10.1137/1.9781611974331.CH97zbMATH Open1417.91227arXiv1507.06495OpenAlexW2952493971MaRDI QIDQ4575680FDOQ4575680

Authors: Yang Cai, Christoph Hunkenschröder, Adrian Vetta, Nicolas Bousquet 

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: Since the 1990s spectrum auctions have been implemented world-wide. This has provided for a practical examination of an assortment of auction mechanisms and, amongst these, two simultaneous ascending price auctions have proved to be extremely successful. These are the simultaneous multiround ascending auction (SMRA) and the combinatorial clock auction (CCA). It has long been known that, for certain classes of valuation functions, the SMRA provides good theoretical guarantees on social welfare. However, no such guarantees were known for the CCA. In this paper, we show that CCA does provide strong guarantees on social welfare provided the price increment and stopping rule are well-chosen. This is very surprising in that the choice of price increment has been used primarily to adjust auction duration and the stopping rule has attracted little attention. The main result is a polylogarithmic approximation guarantee for social welfare when the maximum number of items demanded $mathcalC$ by a bidder is fixed. Specifically, we show that either the revenue of the CCA is at least an $OmegaBig(frac1mathcal{C}^{2}lognlo{g}^{2}mBig)$-fraction of the optimal welfare or the welfare of the CCA is at least an $OmegaBig(frac1lognBig)$-fraction of the optimal welfare, where $n$ is the number of bidders and $m$ is the number of items. As a corollary, the welfare ratio -- the worst case ratio between the social welfare of the optimum allocation and the social welfare of the CCA allocation -- is at most $O(mathcal{C}^{2}cdotlogncdotlo{g}^{2}m)$. We emphasize that this latter result requires no assumption on bidders valuation functions. Finally, we prove that such a dependence on $mathcalC$ is necessary. In particular, we show that the welfare ratio of the CCA is at least $OmegaBig(mathcalCcdotfraclogmloglogmBig)$.

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

Recommendations

• Combinatorial clock auctions: price direction and performance
• On the clock of the combinatorial clock auction
• Asymptotically optimal prior-free clock auctions
• Efficient constrained combinatorial auctions
• Combinatorial auctions: a survey
• On the complexity of computing an equilibrium in combinatorial auctions
• Equilibria of greedy combinatorial auctions
• scientific article; zbMATH DE number 1816801
• On simultaneous two-player combinatorial auctions
• An Efficient Winner Approximation for a Series of Combinatorial Auctions

zbMATH Keywords

stopping ruleoptimal welfarecombinatorial clock auction

Mathematics Subject Classification ID

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

Cited In (5)

• Handbook of spectrum auction design
• Welfare and rationality guarantees for the simultaneous multiple-round ascending auction
• Best-response dynamics in combinatorial auctions with item bidding
• Spiteful bidding and gaming in combinatorial clock auctions
• On the clock of the combinatorial clock auction

This page was built for publication: On the Economic Efficiency of the Combinatorial Clock Auction

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