Stable marriage problem
The stable marriage problem has been stated as follows: 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.
Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments.
[1] In 2012, the Nobel Memorial Prize in Economic Sciences was awarded to Lloyd S. Shapley and Alvin E. Roth "for the theory of stable allocations and the practice of market design.
"[2] An important and large-scale application of stable marriage is in assigning users to servers in a large distributed Internet service.
[3] Billions of users access web pages, videos, and other services on the Internet, requiring each user to be matched to one of (potentially) hundreds of thousands of servers around the world that offer that service.
Content delivery networks that distribute much of the world's content and services solve this large and complex stable marriage problem between users and servers every tens of seconds to enable billions of users to be matched up with their respective servers that can provide the requested web pages, videos, or other services.
[3] The Gale-Shapley algorithm for stable matching is used to assign rabbis who graduate from Hebrew Union College to Jewish congregations.
In general, the family of solutions to any instance of the stable marriage problem can be given the structure of a finite distributive lattice, and this structure leads to efficient algorithms for several problems on stable marriages.
[12] It is a truthful mechanism from the point of view of men (the proposing side), i.e., no man can get a better matching for himself by misrepresenting his preferences.
[14] The GS algorithm is non-truthful for the women (the reviewing side): each woman may be able to misrepresent her preferences and get a better match.
The rural hospitals theorem concerns a more general variant of the stable matching problem, like that applying in the problem of matching doctors to positions at hospitals, differing in the following ways from the basic n-to-n form of the stable marriage problem: In this case, the condition of stability is that no unmatched pair prefer each other to their situation in the matching (whether that situation is another partner or being unmatched).
