A group-strategyproof mechanism for steiner forests

In this paper we design an approximately budget-balanced and group-strategyproof cost-sharing mechanism for the Steiner forest game. An instance of this game consists of an undirected graph G = (V, E), non-negative costs ce for all edges e ∈ E, and a set R ⊆ V × V of k terminal pairs. Each terminal pair (s, t) ∈ R is associated with an agent that wishes to establish a connection between nodes s and t in the underlying network. A feasible solution is a forest F that contains an s, t-path for each connection request (s, t) ∈ R. Previously, Jain and Vazirani gave a 2-approximate budget-balanced and group-strategyproof cost-sharing mechanism for the Steiner tree game - a special case of the game considered here. Such a result for Steiner forest games has proved to be elusive so far, in stark contrast to the well known primal-dual (2 - 1/k)-approximate algorithms for the problem. The cost-sharing method presented in this paper is 2-approximate budget-balanced and this is tight with respect to the budget-balance factor. Our algorithm is an original extension of known primal-dual methods for Steiner forests. An interesting byproduct of the work in this paper is that our Steiner forest algorithm is (2-1/k)-approximate despite the fact that the forest computed by our method is usually costlier than those computed by known primal-dual algorithms. In fact the dual solution computed by our algorithm is infeasible but we can still prove that its total value is at most the cost of a minimum-cost Steiner forest for the given instance.