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.

A group-strategyproof mechanism for steiner forests / Jochen, Koenemann; Leonardi, Stefano; Guido, Schaefer. - (2005), pp. 612-619. (Intervento presentato al convegno Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms tenutosi a Vancouver; United States nel 23 January 2005 through 25 January 2005) [10.1145/1070432.1070517].

A group-strategyproof mechanism for steiner forests

LEONARDI, Stefano;
2005

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), 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.
2005
Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Budget-balance factors; Cost-sharing methods; Steiner forest games
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
A group-strategyproof mechanism for steiner forests / Jochen, Koenemann; Leonardi, Stefano; Guido, Schaefer. - (2005), pp. 612-619. (Intervento presentato al convegno Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms tenutosi a Vancouver; United States nel 23 January 2005 through 25 January 2005) [10.1145/1070432.1070517].
File allegati a questo prodotto
File Dimensione Formato  
VE_2005_11573-60762.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 732.79 kB
Formato Adobe PDF
732.79 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/60762
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 42
  • ???jsp.display-item.citation.isi??? 28
social impact