A group-strategyproof cost sharing mechanism for the Steiner forest game

J. Könemann, S. Leonardi, G. Schäfer, S.H.M. Zwam, van

Research output: Contribution to journalArticleAcademicpeer-review

27 Citations (Scopus)
97 Downloads (Pure)

Abstract

We consider a game-theoretical variant of the Steiner forest problem in which each player $j$, out of a set of $k$ players, strives to connect his terminal pair $(s_j, t_j)$ of vertices in an undirected, edge-weighted graph $G$. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 (1995), pp. 445–456] yields a $2$-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than $2$ for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem.
Original languageEnglish
Pages (from-to)1319-1341
JournalSIAM Journal on Computing
Volume37
Issue number5
DOIs
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'A group-strategyproof cost sharing mechanism for the Steiner forest game'. Together they form a unique fingerprint.

  • Cite this

    Könemann, J., Leonardi, S., Schäfer, G., & Zwam, van, S. H. M. (2008). A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM Journal on Computing, 37(5), 1319-1341. https://doi.org/10.1137/050646408