A groupstrategyproof mechanism for steiner forests

In this paper we design an approximately budget-balanced and group-strategyproofcost-sharing mech-anism 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 2 E, and a set R V V of k terminal pairs. Each terminal pair (s; t) 2 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) 2 R. Previously, Jain and Vazirani [6] 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 (21=k)-approximate algorithms [1, 4] for the problem. The cost-sharing method presented in this paper is 2-approximate budget-balanced. In a recent work, van Zwam [10] proved that no cross-monotonic cost-sharing method for Steiner trees is α-approximate budget-balanced with α < 2. This implies that our result is tight. Our algorithm is an original extension of known primal-dual methods for Steiner forests [1]. 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 for the classical undirected cut relaxation for Steiner forests but we can still prove that its total value is at most the cost of a minimum-cost Steiner forest for the given instance. Our algorithm gives rise to a new undirected cut dual for Steiner forests which we coin the lifted-cut dual. We show that this new dual is strictly stronger than the standard undirected cut dual for Steiner forests. Moreover, our Steiner forest algorithm produces a feasible solution for it.