Incentive-compatible auction mechanisms for network procurement

The allocation of scarce resources is an important task in information systems. We focus on network procurement where a telecommunications provider aims to connect specific nodes in a network. To establish connection between nodes, the provider needs to buy the respective edge. In this strategic version of the Steiner Minimum Tree problem the edges are owned by bidders with private costs. Thus, in order to find an efficient solution, a mechanism that incentivizes participants to state their costs truthfully and runs in polynomial time is required. Recently, deferred-acceptance auctions have been proposed to solve NP-hard allocation problems. We implement several approximation mechanisms and provide an extensive experimental analysis comparing the average-case solution quality of deferred-acceptance algorithms with that of traditional approximation algorithms. We find that deferred-acceptance algorithms are comparable or even outperform the best approximation algorithms on instances from the SteinLib test data collection.