Solutions for the stable rommates problem with payments

Biró, P.; Bomhoff, M.; Golovach, P.A.; Kern, W.; Paulusma, D.; Golumbic, Martin Charles; Stern, Michal; Levy, Avivit; Morgenstern, Gila

Abstract

The stable roommates problem with payments has as input a graph G = (V,E) with an edge weighting w: E → ℝ +  and the problem is to find a stable solution. A solution is a matching M with a vector p∈R V + that satisfies pu + pv = w(uv) for all uv ∈ M and pu = 0 for all u unmatched in M. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices u and v with pu + pv < w(uv). By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a simple constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This result generalizes a result of Chen, Fujishige and Yang for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable.

Citation

Biró, P., Bomhoff, M., Golovach, P., Kern, W., Paulusma, D., Golumbic, M. C., …Morgenstern, G. (2012). Solutions for the stable rommates problem with payments. In Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers (69-80). https://doi.org/10.1007/978-3-642-34611-8_10

• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Volume: 7551
• Pages: 69-80
• Series Title: Lecture notes in computer science
• Series Number: 9551
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers.
• ISBN: 9783642346101
• DOI: https://doi.org/10.1007/978-3-642-34611-8_10
• Additional Information: Series: Lecture Notes in Computer Science, Volume 7551