Strategyproof auction mechanisms for network procurement

• Published in: OR Spectrum 2020-12, Vol.42 (4), p.965-994
• Main Authors: Bichler, Martin, Hao, Zhen, Littmann, Richard, Waldherr, Stefan
• Format: Article
• Language: English
• Subjects: Approximation mechanism; Business and Management; Calculus of Variations and Optimal Control; Optimization; Deferred-acceptance auction; Network procurement; Operations Research/Decision Theory; Regular Article; Steiner tree problem
• ISSN: 1436-6304; 0171-6468; 1436-6304
• DOI: 10.1007/s00291-020-00597-7

Deferred-acceptance auctions can be seen as heuristic algorithms to solve 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.