Strategyproof auction mechanisms for network procurement

Martin Bichler (), Zhen Hao (), Richard Littmann () and Stefan Waldherr ()
Additional contact information
Martin Bichler: Technical University of Munich
Zhen Hao: Technical University of Munich
Richard Littmann: Technical University of Munich
Stefan Waldherr: Technical University of Munich

OR Spectrum: Quantitative Approaches in Management, 2020, vol. 42, issue 4, No 5, 965-994

Abstract: Abstract Deferred-acceptance auctions can be seen as heuristic algorithms to solve $${{\mathcal {N}}}{{\mathcal {P}}}$$ N P -hard allocation problems. Such auctions have been used in the context of the Incentive Auction by the US Federal Communications Commission in 2017, and they have remarkable incentive properties. Besides being strategyproof, they also prevent collusion among participants. Unfortunately, the worst-case approximation ratio of these algorithms is very low in general, but it was observed that they lead to near-optimal solutions in experiments on the specific allocation problem of the Incentive Auction. In this work, which is inspired by the telecommunications industry, we focus on a strategic version of the minimum Steiner tree problem, where the edges are owned by bidders with private costs. We design several deferred-acceptance auctions (DAAs) and compare their performance to the Vickrey–Clarke–Groves (VCG) mechanism as well as several other approximation mechanisms. We observe that, even for medium-sized inputs, the VCG mechanisms experiences impractical runtimes and that the DAAs match the approximation ratios of even the best strategy-proof mechanisms in the average case. We thus provide another example of an important practical mechanism design problem, where empirics suggest that carefully designed deferred-acceptance auctions with their superior incentive properties need not come at a cost in terms of allocative efficiency. Our experiments provide insights into the trade-off between solution quality and runtime and into the additional premium to be paid in DAAs to gain weak group-strategyproofness rather than just strategyproofness.

Keywords: Steiner tree problem; Network procurement; Approximation mechanism; Deferred-acceptance auction (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-020-00597-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:42:y:2020:i:4:d:10.1007_s00291-020-00597-7

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-020-00597-7

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().