Skip to main content

Research Repository

Advanced Search

Solutions for the stable roommates problem with payments

Biró, P.; Bomhoff, M.; Golovach, P.A.; Kern, W.; Paulusma, D.

Solutions for the stable roommates problem with payments Thumbnail


Authors

P. Biró

M. Bomhoff

P.A. Golovach

W. Kern



Abstract

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

Citation

Biró, P., Bomhoff, M., Golovach, P., Kern, W., & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science, 540-541, 53-61. https://doi.org/10.1016/j.tcs.2013.03.027

Journal Article Type Article
Publication Date Jun 26, 2014
Deposit Date Apr 15, 2013
Publicly Available Date Apr 19, 2013
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 540-541
Pages 53-61
DOI https://doi.org/10.1016/j.tcs.2013.03.027
Keywords Game theory, Stable roommates, Blocking pairs.
Public URL https://durham-repository.worktribe.com/output/1456278

Files

Accepted Journal Article (400 Kb)
PDF

Copyright 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





You might also like



Downloadable Citations