Network winner determination problem

• Autorzy: Kaleta M.

Identyfikatory

DOI

10.24425/119077

• Języki publikacji: EN

Abstrakty

EN

Many real-world marketplaces involve some additional constraints to be addressed during the market clearing process. This is the case of various infrastructure sectors of the economy, where market commodities are associated with some elements of the infrastructure, e.g., elements of telecommunication, power transmission or transportation network. Transactions are allowed only if the infrastructure, modeled as a flow network, is able to serve them. Determination of the best offers is possible by solving the optimization problem, so called the Winner Determination Problem (WDP). We consider a new subclass of the WDP, i.e., the Network Winner Determination Problem (NWDP). We characterize different poblems in the NWDP class and analyze their computational complexity. The sharp edge of tractability for NWDP-derived problems is generally designated by integer offers. However, we show that some specific settings of the problem can still be solved in polytime. We also presents ome exemplary applications of NWDP in telecommunication bandwidth market and electrical energy balancing market.

Słowa kluczowe

EN

network auctions; network winner determination problem (NWDP); complexity of the NWDP; MILP models; multi-commodity flow optimization; graph models

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2018
• Tom: Vol. 28, No. 1
• Strony: 51--88
• Opis fizyczny: Bibliogr. 33 poz., rys., tab., wzory

Twórcy

autor

Kaleta M.

• Institute of Control and Computational Engineering, Warsaw University of Technology, Nowowiejska str. 15/19, 00-665 Warsaw, Poland

Bibliografia

• [1] N. Nisan: Bidding and allocation in combinatorial auctions. Proceedings of ACM Conference on Electronic Commerce, (2000), 1-12.
• [2] T. Sandholm, S. Suri, A. Gilpin and D. Levine: Winner determination in combinatorial auction generalizations. Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, AAMAS ’02, (New York, NY, USA), (2002), 69–76, ACM.
• [3] T. Sandholm and S. Suri: Side constraints and non-price attributes in markets. Games and Economic Behavior, 55(2) (2006), 321–330. Mini Special Issue: Electronic Market Design.
• [4] M. Kaleta and T. Traczyk, eds.: ModelingMulti-commodity Trade: Information ExchangeMethods. Advances in Intelligent and Soft Computing, Springer, 2012.
• [5] T. Sandholm: Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1-2) (2002), 1-54.
• [6] M. Kaleta: Security constrained network winner determination problem, Automatyzacja procesów dyskretnych. Teoria i zastosowania, A. Świerniak and J. Krystek, eds., pp. 111-118, Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, 2012.
• [7] M. H. Rothkopf, A. Pekec and R. M. Harstad: Computationally manageable combinational auctions. Manage. Sci., 44 (1998), 1131-1147, Aug.
• [8] D. Lehman, R. Müller and T. Sandholm: The winner determination problem. Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, eds., ch. 12, The MIT Press, 2006.
• [9] N. Nisan: Bidding languages. Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, eds., ch. 9, The MIT Press, 2006.
• [10] M. Kaleta: Bidding languages for continuous auctions. New Trends in Databases and Information Systems, (2013), 211-220, Springer Berlin Heidelberg.
• [11] R. Müller: Tractable cases of the winner determination problem. Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, eds., ch. 13, The MIT Press, 2006.
• [12] S. De Vries and R. V. Rakesh: Combinational auctions: A survey. Informs Journal on Computing, 15(3) (2003), 284-309.
• [13] V. Conitzer, J. Derryberry and J. Sandholm: Combinatorial auctions with structured item graphs. Proceedings of the National Conference on Artificial Intelligence (AAAI), (2004), 212-217, The AAAI Press.
• [14] G. Gotllob and G. Greco: On the complexity of combinatorial auctions: Structured item graphs and hypertree decomposition. Proceedings of the 8th ACM Conference on Electronic Commerce, EC ’07, (New York, NY, USA), (2007), 152-161, ACM.
• [15] T. SANDHOLM and S. SURI: Side constraints and non-price attributes in markets. Games and Economic Behavior, 55(2) (2006), 321-330, Mini Special Issue: Electronic Market Design.
• [16] M. Bichler, J. R. Kalagnanam and H. S. Lee: Reco: Representation and evaluation of configurable offers. In Computational Modeling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research, H.K. Bhargava and N. Ye, eds., (2003), 235-258, Boston, MA: Springer US.
• [17] A. Davenport and J. Kalagnanam: Price negotiations for procurement of direct inputs. Tech. Rep. RC 22078, IBM, May 2001.
• [18] M. Tennenholtz: Tractable combinatorial auctions and b-matching. Artificial Intelligence, 140(1) (2002), 231-243.
• [19] A. Kothari, T. Sandholm and S. Suri: Solving combinatorial exchanges: optimality via a few partial bids. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (2004), 1418-1419, July.
• [20] D. Loker and K. Larson: Parameterizing the winner determination problem for combinatorial auctions. 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, Volume 1-3, (2010), 1483-1484.
• [21] T. Sandholm, S. Suri, A. Gilpin and D. Levine: Winner determination in combinatorial auction generalizations. AAMAS ’02: Proceedings of the first international joint conference on Autonomous agents and multiagent systems, (2002), 69-76, ACM.
• [22] S. Bikhchandani, S. De Vries, J. Schummer and R. V. Vohra: Linear programming and Vickrey auctions. Mathematics of the Internet: E-Auction and Markets, vol. 127 of IMA Volumes in Mathematics and its Applications, pp. 75-116, Springer, 2002.
• [23] J. Hershberger and S. Suri: Vickrey pricing in network routing: Fast payment computation, In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, (2001), 252-259.
• [24] P. Cramton, Y. Shoham and R. Steinberg: Combinatorial Auctions. The MIT Press, 2006.
• [25] L. G. Khachiyan: A polynomial algorithm in linear programming (in Russian). Doklady Akademii Nauk SSSR, 244 (1979), 1093-1096. English translation: Soviet Mathematics Doklady, 20(1), (1979), 191-194.
• [26] S. Even, A. Itai and A. Shamir: On the complexity of time table and multi-commodity flow problems. 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), (1975), 184-193, Oct.
• [27] A. Scharijver: Combinatorial Optimization – Polyhedra and Efficiency. Springer, 2003.
• [28] W. Stańczuk, J. Lubacz and E. Toczyłowski: Trading transport resources of communication networks on bandwidth exchanges. Proceedings 46th FITCE Congress - The Broadband Way to the Future, (2007), 222-444.
• [29] W. Stańczuk, J. Lubacz and E. Toczyłowski: Trading links and paths on a communication bandwidth market. Journal of Universal Computer Science, 14 (2008), 642-653, Mar.
• [30] P. Pałka, K. Kołtys, E. Toczyłowski and I. Żółtowska: Model for balancing aggregated communication bandwidth resources. Journal of Telecommunication and Information Technology, 3 (2009).
• [31] K. Kołtys, P. Pałka, E. Toczyłowski and I. Żółtowska: Multicommodity auctionmodel for indivisible network resource allocation. Journal of Telecommunication and Information Technology, 4 (2008), 60-66.
• [32] P. Kacprzak, M. Kaleta, K. Kołtyś, P. Pałka, K. Pieńkosz, E. Toczyłowski and I. Żółtowska: Multicommodity exchange model for trading bandwidth in undirected networks. Proceedings of 14th International Telecommunications Network Strategy and Planning Symposium NETWORKS (2010), 180-184.
• [33] K. Kołtyś, K. Pieńkosz and E. Toczyłowski: A flexible auction model for virtual private networks. Lecture Notes in Computer Science, 6641 (2011), 97–108.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).