Fast core pricing algorithms for path auction

摘要

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.