Strategyproof auction mechanisms for network procurement
- PDF / 1,672,172 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 110 Downloads / 182 Views
Strategyproof auction mechanisms for network procurement Martin Bichler1 · Zhen Hao1 · Richard Littmann1,2 · Stefan Waldherr1 Received: 13 March 2018 / Accepted: 10 July 2020 © The Author(s) 2020
Abstract Deferred-acceptance auctions can be seen as heuristic algorithms to solve NP -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 nearoptimal 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
* Martin Bichler [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
M. Bichler et al.
1 Introduction There is a significant literature in the design of approximation algorithms for computationally hard problems (Vazirani 2013). Algorithmic mechanism design extends this literature in an important way (Nisan and Ronen 1999). The goal of approximation mechanisms is the design of computationally efficient algorithms which take into account the incentives of participants as well. These mechanisms should run in polynomial time and satisfy strong game-theoretical equilibrium solution concepts such that bidders have incentives to reveal their valuations truthfully and the auctioneer can determine the optimal allocation or one that approximates the optimal solution. This has led to a rich literature studying approximation mechanisms for different types of NP -hard resource allocation problems. Typically, designers of approximation mechanisms aim for dominant-strategy incentive-compatibility or strategyproofness. Such mechanisms are pr
Data Loading...
