Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
The Price of Matching with Metric Preferences
verfasst von : Yuval Emek, Tobias Langner, Roger Wattenhofer
Erschienen in: Algorithms - ESA 2015
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
We consider a version of the Gale-Shapley stable matching setting, where each pair of nodes is associated with a (symmetric) matching cost and the preferences are determined with respect to these costs. This stable matching version is analyzed through the Price of Anarchy (PoA) and Price of Stability (PoS) lens under the objective of minimizing the total cost of matched nodes (for both the marriage and roommates variants). A simple example demonstrates that in the general case, the PoA and PoS are unbounded, hence we restrict our attention to metric costs. We use the notion of
α
-stability, where a pair of unmatched nodes defect only if both improve their costs by a factor greater than
α
≥ 1. Our main result is an asymptotically tight trade-off, showing that with respect to
α
-stable matchings, the Price of Stability is
$\Theta \big( n^{\log ( 1 + \frac{1}{2 \alpha} )} \big)$
. The proof is constructive: we present a simple algorithm that outputs an
α
-stable matching satisfying this bound.