Incentive-Compatible Auction Mechanisms for Network Procurement

Martin Bichler; Richard Littmann; and Stefan Waldherr

						@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", 
							}

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.

Referenzen

1. Adomavicius, G., Gupta, A.: Toward comprehensive real-time bidder support in iterative combinatorial auctions. Information Systems Research 16, 169-185 (2005)
2. Adomavicius, G., Gupta, A., Sanyal, P.: Effect of information feedback on the outcomes and dynamics of multisourcing multiattribute procurement auctions. Journal of Management Information Systems 28, 199-230 (2012)
3. Bichler, M., Gupta, A., Ketter, W.: Research commentary—designing smart markets. Information Systems Research 21, 688-699 (2010)
4. Goetzendorff, A., Bichler, M., Shabalin, P., Day, R.W.: Compact bid languages and core pricing in large multi-item auctions. Management Science 61, 1684-1703 (2015)
5. Bichler, M., Shabalin, P., Pikovsky, A.: A computational analysis of linear price iterative combinatorial auction formats. Information Systems Research 20, 33-59 (2009)
6. Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic behavior 35, 166-196 (2001)
7. Vazirani, V.V.: Approximation algorithms. Springer Science & Business Media (2013)
8. Karp, R.M.: Reducibility among combinatorial problems. Complexity of computer computations, pp. 85-103. Springer (1972)
9. Öncan, T., Cordeau, J.-F., Laporte, G.: A tabu search heuristic for the generalized minimum spanning tree problem. European Journal of Operational Research 191, 306-319 (2008)
10. Xu, J., Chiu, S.Y., Glover, F.: Tabu search heuristics for designing a Steiner tree based digital line network. University of Colorado (1995)
11. Contreras, I., Fernández, E.: General network design: A unified view of combined location and network design problems. European Journal of Operational Research 219, 680-697 (2012)
12. Milgrom, P., Segal, I.: Clock Auctions and Radio Spectrum Reallocation. (2018)
13. Leyton-Brown, K., Milgrom, P., Segal, I.: Economics and computer science of a radio spectrum reallocation. Proceedings of the National Academy of Sciences 114, 7202-7209 (2017)
14. Li, S.: Obviously strategy-proof mechanisms. American Economic Review 107, 3257-3287 (2017)
15. Dütting, P., Gkatzelis, V., Roughgarden, T.: The performance of deferred-acceptance auctions. Mathematics of Operations Research 42, 897-914 (2017)
16. Newman, N., Leyton-Brown, K., Milgrom, P., Segal, I.: Assessing economic outcomes in simulated reverse clock auctions for radio spectrum. arXiv preprint arXiv:1706.04324 (2017)
17. Takahashi, H.M., A: An approximate solution for the Steiner problem in graphs. Math. Japonica. 6, 573-577 (1990)
18. Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta informatica 15, 141-145 (1981)
19. Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters 27, 125-128 (1988)
20. Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems 144-191 (1997)
21. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics 19, 122-134 (2005)
22. Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: An improved LP-based approximation for Steiner tree. In: Proceedings of the forty-second ACM symposium on Theory of computing, pp. 583-592. ACM, (Year)
23. Myerson, R.B.: Optimal auction design. Mathematics of operations research 6, 58-73 (1981)
24. Gualà, L., Proietti, G.: A truthful (2–2/k)-approximation mechanism for the Steiner tree problem with k terminals. In: International Computing and Combinatorics Conference, pp. 390-400. Springer, (Year)
25. Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for least common ancestors, mst verification, and dominators. arXiv preprint cs/0207061 (2008)
26. Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 267-276. Society for Industrial and Applied Mathematics, (Year)
27. Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters 14, 30-33 (1982)
28. Brandes, U.: A faster algorithm for betweenness centrality. Journal of mathematical sociology 25, 163-177 (2001)
29. Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16, 8-37 (1961)
30. Clarke, E.H.: Multipart pricing of public goods. Public choice 11, 17-33 (1971)
31. Groves, T.: Incentives in teams. Econometrica 41, 617-631 (1973)
32. Erickson, R.E., Monma, C.L., Veinott Jr, A.F.: Send-and-split method for minimumconcave- cost network flows. Mathematics of Operations Research 12, 634-664 (1987)
33. Iwata, Y.S., Takuto: Send-and-split method for minimum-concave-cost network flows. (2018)
34. Koch, T.M., Alexander, Voß, S.: SteinLib: An Updated Library on Steiner Tree Problems in Graphs. (2000)

Search

Outline

Gliederung

Abstract

Abstract

Keywords

Schlüsselwörter

References

Referenzen

Most viewed articles

Meist angesehene Beiträge

Search