Richard Littmann (TUM, AdONE): "Strategyproof Auction Mechanisms for Network Procurement" – 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 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 Steiner minimum tree problem, where the edges are owned by bidders with private costs. We design several deferred acceptance auctions (DAA) 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 running times, and that the DAAs we devise match the approximation ratios of even the best strategyproof mechanisms in the average case. This serves as another example of practical relevance where cautiously designed DAAs offer superior incentive properties without losses regarding allocative efficiency. Finally, our experiments provide insights into the trade-off between solution quality and running time, and into the additional premium to be paid in DAAs to gain weak group-strategyproofness rather than just strategyproofness.
This is joint work with Martin Bichler and Stefan Waldherr
Date: Monday 15th of June 2020, starting at 2 p.m.
