Stable marriage problem (nonfiction): Difference between revisions
(Created page with "In mathematics, economics, and computer science, the '''stable marriage problem''' (also stable matching problem...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 11: | Line 11: | ||
</blockquote> | </blockquote> | ||
Note that the existence of two classes that need to be paired with each other (men and women in this example), distinguishes this problem from the stable roommates problem. | Note that the existence of two classes that need to be paired with each other (men and women in this example), distinguishes this problem from the [[Stable roommates problem (nonfiction)|stable roommates problem]]. | ||
* [[Computer science (nonfiction)]] | * [[Computer science (nonfiction)]] | ||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
* [[Stable marriage with indifference (nonfiction)]] - | * [[Stable marriage with indifference (nonfiction)]] - a variant of the stable marriage problem in which a person may prefer two or more persons as equally favorable partner. Such tied preference is termed as indifference. | ||
* [[Stable roommates problem (nonfiction)]] - the problem of finding a stable matching for an even-sized set. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women". | |||
* [https://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem] @ Wikipedia | * [https://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem] @ Wikipedia | ||
Latest revision as of 02:35, 14 October 2019
In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is not stable if:
- There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
- B also prefers A over the element to which B is already matched.
In other words, a matching is stable when there does not exist any match (A, B) which both prefer each other to their current partner under the matching.
Here is another definition:
Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.
Note that the existence of two classes that need to be paired with each other (men and women in this example), distinguishes this problem from the stable roommates problem.
- Computer science (nonfiction)
- Mathematics (nonfiction)
- Stable marriage with indifference (nonfiction) - a variant of the stable marriage problem in which a person may prefer two or more persons as equally favorable partner. Such tied preference is termed as indifference.
- Stable roommates problem (nonfiction) - the problem of finding a stable matching for an even-sized set. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women".
- Stable marriage problem @ Wikipedia