Computer Science – Computer Science and Game Theory
Scientific paper
2012-04-07
Computer Science
Computer Science and Game Theory
Scientific paper
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. There has been little focus in matching theory on 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. One of our key computational results for the stable marriage setting also carries over to different classes of hedonic games for which individual-based stability has already been of much interest.
No associations
LandOfFree
Stable marriage and roommate problems with individual-based stability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Stable marriage and roommate problems with individual-based stability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stable marriage and roommate problems with individual-based stability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-37213