Stable matching problem: Difference between revisions

Revision as of 20:14, 15 January 2024

Revision as of 22:41, 15 January 2024

Line 1:

{{Short description|Pairing where no unchosen pair prefers each other over their choice}}

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 (graph theory)|matching]] is a [[bijection]] from the elements of one set to the elements of the other set. A matching is ''not'' stable if:

{{Ordered list|list-style-type=numeric

Line 18:

An important and large-scale application of stable marriage is in assigning users to servers in a large distributed Internet service.<ref name=nuggets>{{cite journal | author= Bruce Maggs and [[Ramesh Sitaraman]] | title = Algorithmic nuggets in content delivery | journal= ACM SIGCOMM Computer Communication Review |year=2015|volume=45|issue=3|url = http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf}}</ref> 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. A user prefers servers that are proximal enough to provide a faster response time for the requested service, resulting in a (partial) preferential ordering of the servers for each user. Each server prefers to serve users that it can with a lower cost, resulting in a (partial) preferential ordering of users for each server. [[Content delivery network]]s 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.<ref name=nuggets />

The [[Gale-Shapley algorithm]] for stable matching is used to assign rabbis who graduate from [[Hebrew Union College – Jewish Institute of Religion|Hebrew Union College]] to Jewish congregations.<ref>{{Cite journal |last=Bodin |first=Lawrence |last2=Panken |first2=Aaron |date=June 2003-06 |title=High Tech for a Higher Authority: The Placement of Graduating Rabbis from Hebrew Union College—Jewish Institute of Religion |url=https://pubsonline.informs.org/doi/10.1287/inte.33.3.1.16013 |journal=Interfaces |language=en |volume=33 |issue=3 |pages=1–11 |doi=10.1287/inte.33.3.1.16013 |issn=0092-2102}}</ref>

==Different stable matchings==

Line 85:

{{main|Gale–Shapley algorithm}}

[[File:Gale-Shapley.gif|thumb|right|Animation showing an example of the Gale–Shapley algorithm]]

In 1962, [[David Gale]] and [[Lloyd Shapley]] proved that, for any equal number of men and women, it is always possible to solve the SMPstable marriage problem and make all marriages stable. They presented an [[algorithm]] to do so.<ref name=gs62>{{cite journal |first1=D. |last1=Gale |first2=L. S. |last2=Shapley |title=College Admissions and the Stability of Marriage |journal=[[American Mathematical Monthly]] |volume=69 |issue= 1|pages=9–14 |year=1962 |jstor=2312726 |doi=10.2307/2312726|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |archive-url=https://web.archive.org/web/20170925172517/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |url-status=dead |archive-date=September 25, 2017 }}</ref><ref>[[Harry Mairson]]: "The Stable Marriage Problem", ''The Brandeis Review'' 12, 1992 ([http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online]).</ref>

The [[Gale–Shapley algorithm]] (also known as the deferred acceptance algorithm) involves a number of "rounds" (or "[[iteration]]s"):

Line 168:

==External links==

*[http://mathsite.math.berkeley.edu/smp/smp.html Interactive Flashflash Demonstrationdemonstration of SMPthe stable marriage problem]

*https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP

*http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html

*[http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture5.pdf SMPStable Lecturemarriage Notesproblem lecture notes]

{{game theory}}