Stable matching problem: Difference between revisions

Revision as of 18:46, 9 March 2025

Latest revision as of 14:58, 24 June 2025

(2 intermediate revisions by one other user not shown)

Line 1:

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

In [[mathematics]], [[economics]], and [[computer science]], the '''stable marriagematching problem''' (also<ref>{{cite '''stableweb matching|author=Tesler, problem''')G.|url=https://mathweb.ucsd.edu/~gptesler/154/slides/154_galeshapley_20-handout.pdf|website=mathweb.ucsd.edu|title=Ch. 5.9: Gale-Shapley Algorithm|date= 2020|publisher=[[University of California San Diego]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web|last1=Kleinberg|first1=Jon |last2=Tardos|first2=Éva |url=https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf|website=www.cs.princeton.edu|title=Algorithmn Design: 1. Stable Matching|date= 2005|publisher=[[Pearson PLC|Pearson]]-[[Addison Wesley]]: [[Princeton University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web |last1=Goel|first1=Ashish |editor1-last=Ramseyer|editor1-first=Geo |url=https://web.stanford.edu/~ashishg/cs261/win21/notes/l5_note.pdf|website=web.stanford.edu|title=CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith|date= 21 January 2019|publisher=[[Stanford University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref> 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 [[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 |last1=Bodin |first1=Lawrence |last2=Panken |first2=Aaron |date=June 2003 |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|url-access=subscription }}</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 in different groups, in the context of mencollege admissions and women,individuals wanting marriage it is always possible to solve theas stablematched marriagecouples problem andto make all marriagesresultant pairings / matched factors 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"):