Solutions for the stable roommates problem with payments

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

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