An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

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 = {(s_i, t_i)}_1≤i≤k, and penalties π₁, ⋯, π k. A feasible solution (F,Q) consists of a forest F and a subset Q of terminal pairs such that for all (s_i, t_i) ∈ R either s_i, t_i are connected by F or (s_i, t_i) ∈ 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 s_i and t_i, and the player derives a privately held utility u_i ≥ 0 from being connected. A service provider can connect the terminals s_i and t_i of player i in two ways: (1) by buying the edges of an s_i, t_i-path in G, or (2) by buying an alternate connection between s_i and t_i (maybe from some other provider) at a cost of π_i. In this paper, we present a simple 3-budget-balanced 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² 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).