Solutions for the stable roommates problem with payments

Biró, Péter and Bomhoff, M. and Golovach, PA. and Kern, W. and Paulusma, D. (2014) Solutions for the stable roommates problem with payments. THEORETICAL COMPUTER SCIENCE, 540-54. pp. 53-61. ISSN 0304-3975

Preview

Text BBGKP2014tcs_last.pdf Download (721kB) | Preview

Abstract

The stable roommates problem with payments has as input a graph G = (V, E) with an edge weighting w : E -> R->= 0 and the problem is to find a stable solution. A solution is a matching M with a vector p is an element of R->= 0(V) that satisfies p(u) + p(v) = w(uv) for all uv is an element of M and p(u) = 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 p(u) + p(v) < w(uv), or equivalently, if the total blocking value Sigma(uv is an element of E), max{0, w(uv) - (P-u + P-v)} = 0. By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a 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 generalizes a result of Chen, Fujishige and Yang (2011) [4] 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. (C) 2013 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item