Computer Science – Artificial Intelligence
Scientific paper
2010-07-29
Computer Science
Artificial Intelligence
To appear in Proceedings of Third International Workshop on Computational Social Choice, Dusseldorf, Germany, September 13-16,
Scientific paper
The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or more generally to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here we consider stable marriage problems with quantitative preferences: each man (resp., woman) provides a score for each woman (resp., man). Such problems are more expressive than the classical stable marriage problems. Moreover, in some real-life situations it is more natural to express scores (to model, for example, profits or costs) rather than a qualitative preference ordering. In this context, we de?fine new notions of stability and optimality, and we provide algorithms to find marriages which are stable and/or optimal according to these notions. While expressivity greatly increases by adopting quantitative preferences, we show that in most cases the desired solutions can be found by adapting existing algorithms for the classical stable marriage problem.
Pini Maria Silvia
Rossi Francesca
Venable Brent
Walsh Toby
No associations
LandOfFree
Stable marriage problems with quantitative preferences 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 problems with quantitative preferences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stable marriage problems with quantitative preferences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-450641