Incentive-Compatible Auction Mechanisms for Network Procurement

Bibtex

Cite as text

						@Select Types{,
							 
							 
							 
							 
							 
							Journal   = "Band-1",
							 Title= "Incentive-Compatible Auction Mechanisms for Network Procurement", 
							Author= "Martin Bichler, Richard Littmann, and Stefan Waldherr", 
							Doi= "https://doi.org/10.30844/wi_2020_c4-bichler", 
							 Abstract= "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.

", 
							 Keywords= "Steiner tree problem, approximation mechanism, deferredacceptance auction", 
							}
					
Martin Bichler, Richard Littmann, and Stefan Waldherr: Incentive-Compatible Auction Mechanisms for Network Procurement. Online: https://doi.org/10.30844/wi_2020_c4-bichler (Abgerufen 20.08.22)

Abstract

Abstract

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.

Keywords

Schlüsselwörter

Steiner tree problem, approximation mechanism, deferredacceptance auction

References

Referenzen

Leider ist der Eintrag nur auf Amerikanisches Englisch verfügbar.

Most viewed articles

Meist angesehene Beiträge

GITO events | library.gito