We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Solutions for the stable roommates problem with payments.

Biró, P. and Bomhoff, M. and Golovach, P.A. and Kern, W. and Paulusma, Daniel (2014) 'Solutions for the stable roommates problem with payments.', Theoretical computer science., 540-541 . pp. 53-61.


The stable roommates problem with payments has as input a graph G=(V,E)G=(V,E) with an edge weighting w:E→R≥0w:E→R≥0 and the problem is to find a stable solution. A solution is a matching MM with a vector p∈R≥0V that satisfies pu+pv=w(uv)pu+pv=w(uv) for all uv∈Muv∈M and pu=0pu=0 for all uu unmatched in MM. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices uu and vv with pu+pv<w(uv)pu+pv<w(uv), or equivalently, if the total blocking value ∑uv∈Emax{0,w(uv)−(pu+pv)}=0∑uv∈Emax{0,w(uv)−(pu+pv)}=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] 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.

Item Type:Article
Keywords:Game theory, Stable roommates, Blocking pairs.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical computer science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical computer science, 540-541, 2014, 10.1016/j.tcs.2013.03.027
Date accepted:No date available
Date deposited:19 April 2013
Date of first online publication:June 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar