Stable Marriage and Roommate Problems with Individual-Based Stability

[AAMAS '13]
Stable Marriage and Roommate Problems with Individual-Based Stability

Haris Aziz NICTA and University of New South Wales, Sydney, Australia

Research regarding the stable marriage and roommate problem has a long and distinguished history in mathematics, computer science and economics. Stability in this context is predominantly core stability or one of its variants in which each deviation is by a group of players. We consider stability concepts such as Nash stability and individual stability in which the deviation is by a single player. Such stability concepts are suitable especially when trust for the other party is limited, complex coordination is not feasible, or when only unmatched agents can be approached. Furthermore, weaker stability notions such as individual stability may in principle circumvent the negative existence and computational complexity results in matching theory. We characterize the computational complexity of checking the existence and computing individual-based stable matchings for the marriage and roommate settings. Some of our key computational results also carry over to different classes of hedonic games and network formation games for which individual-based stability has already been of much interest.


full paper:
http://dl.acm.org/citation.cfm?id=2484968