An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
Anupam Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer · 2007
In an instance of the prize-collecting Steiner forest problem (PCSF) we are given an undirected graph G = (V,E), non-negative edge-costs c(e) for all e ∈ E, terminal pairs R = {(si,ti)}1≤i≤k, and penalties π1,...,πk. A feasible solution (F,Q) consists of a forest F and a subset Q of terminal pairs such that for all (si,ti) ∈ R either si,ti are connected by F or (si,ti) ∈ Q. The objective is to compute a feasible solution of minimum cost c(F) + π(Q). A game-theoretic version of the above problem has k players, one for each terminal-pair in R. Player i’s ultimate goal is to connect si and ti, and the player derives a privately held utility ui ≥ 0 from being connected. A service provider can connect the terminals si and ti of player i in two ways: (1) by buying the edges of an si,ti-path in G, or (2) by buying an alternate connection between si and ti (maybe from some other provider) at a cost of πi. In this paper, we present a simple 3-budgetbalanced and group-strategyproof mechanism for the above problem. We also show that our mechanism computes client sets whose social cost is at most O(log 2 k) times the minimum social cost of any player set. This matches a lower-bound that was recently given by Roughgarden and Sundararajan (STOC ’06).