A group-strategyproof mechanism for Steiner forests

Abstract

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), nonnegative 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 [4] gave a 2approximate 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 [1, 2] 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 [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 but we can still prove that its total value is at most the cost of a minimum-cost Steiner forest for the given instance.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 61 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.