Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/108267 
Erscheinungsjahr: 
2012
Schriftenreihe/Nr.: 
IEHAS Discussion Papers No. MT-DP - 2012/11
Verlag: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
Zusammenfassung: 
The stable roommates problem with payments has as input a graph G(E,V) with an edge weighting w:E_ùR+ and the problem is to find a stable solution. A solution is a matching M with a vector p.RV 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-complete. Finally, we prove that the first problem is NP-complete also when a matching is prescribed, whereas this variant of the second problem becomes polynomial-time solvable.
Schlagwörter: 
roommates problem
matching game
cooperative game theory
JEL: 
C61
C63
C71
C78
ISBN: 
978-615-5243-04-2
Dokumentart: 
Working Paper

Datei(en):
Datei
Größe
239.16 kB





Publikationen in EconStor sind urheberrechtlich geschützt.