Fast core pricing algorithms for path auction

作     者：Cheng, Hao Zhang, Wentao Zhang, Yi Zhang, Lei Wu, Jun Wang, Chongjun 

作者机构：Nanjing Univ Dept Comp Sci & Technol Natl Key Lab Novel Software Technol Nanjing Peoples R China 

出 版 物：《AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS》 (独立代理和多头代理系统)

年 卷 期：2020年第34卷第1期

页      面：1-37页

核心收录：

学科分类：08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Research and Development Program of China [2018YFB1403400] National Natural Science Foundation of China Collaborative Innovation Center of Novel Software Technology and Industrialization at Nanjing University 

主　　题：Path auction Core Pricing algorithm Constraint set 

摘      要：Path auction is held in a graph, where each edge stands for a commodity and the weight of this edge represents the prime cost. Bidders own some edges and make bids for their edges. The auctioneer needs to purchase a sequence of edges to form a path between two specific vertices. Path auction can be considered as a kind of combinatorial reverse auctions. Core-selecting mechanism is a prevalent mechanism for combinatorial auction. However, pricing in core-selecting combinatorial auction is computationally expensive, one important reason is the exponential core constraints. The same is true of path auction. To solve this computation problem, we simplify the constraint set and get the optimal set with only polynomial constraints in this paper. Based on our constraint set, we put forward two fast core pricing algorithms for the computation of bidder-Pareto-optimal core outcome. Among all the algorithms, our new algorithms have remarkable runtime performance. Finally, we validate our algorithms on real-world datasets and obtain excellent results.