2008 | OriginalPaper | Buchkapitel
Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
verfasst von : Yvonne Bleischwitz, Florian Schoppmann
Erschienen in: Algorithmic Game Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the context of
general demand
cost sharing, we present the first group-strategyproof mechanisms for the
metric fault tolerant uncapacitated facility location problem
. They are
$(3 \ensuremath{L})$
-budget-balanced and
$(3 \ensuremath{L} \cdot (1 + \mathcal H_n))$
-efficient, where
$\ensuremath{L}$
is the maximum service level and
n
is the number of agents. These mechanisms generalize the seminal
Moulin mechanisms
for
binary demand
. We also apply this approach to the
generalized Steiner problem in networks
.