Stable marriage problem

In mathematics , economics and computer science , the stable marriage problem (English for: problem of stable pairing, also "stable matching problem" or SMP) describes the problem of finding a stable pairing between two equal sets of elements, using a given order of preference for each element. A pairing (or a matching) is an assignment of the elements of one set to the elements of the other set. She is n't stable, though

a.) An element A from the first set favors a given element B from the second set over the element with which A is already matched, and

b.) B also prefers A over the element with which B is already matched.

In other words, a pairing is stable if no match ( A , B ) exists in which both A as well as B would be better off individually with the element with which they are just matched.

The stable marriage problem accepts heterosexual couples and was phrased as follows:

“Given n men and n women, each person having arranged all members of the opposite sex in the order of their preference, the men and women marry each other in such a way that there are no two people of the opposite sex who would both rather have married than their present Partner. If there are no such couples, the number of marriages is considered stable. "

Note that this problem differs from the Stable Roommates problem in that there are two different classes that must be paired with each other (men and women in this example).

Applications

Algorithms for solving the stable marriage problem can be used in many practical situations. Of these, the referral of medical graduates to hospital medical training is perhaps the best known. In 2012 Lloyd Shapley and Alvin E. Roth received the Nobel Prize in Economics “for the theory of stable allocations and the application of market design”.

An important application of stable marriage on a large scale is the assignment of users to servers in a large distributed Internet service. Billions of users access websites, videos and other services on the Internet. Each user must be matched to one of (potentially) hundreds of thousands of servers around the world that offer this service. A user prefers servers that are sufficiently close to enable a faster response time for the desired service. This leads to a (partial) order of preferences for the server for each user. Each server, in turn, prefers users who are inexpensive to operate, so that there is a (partial) order of preference of the users for each server. Content delivery networks , which distribute a large part of the worldwide content and services, solve this large and complex stable marriage problem between users and servers every tenths of a second. They enable billions of users to be matched with the respective servers that provide their desired websites, videos or other services.

Gale-Shapley algorithm

In 1962, David Gale and Lloyd Shapley proved that it is always possible for an equal number of men and women to solve the stable marriage problem so that all marriages are stable. They presented an algorithm for this .

The Gale-Shapley algorithm contains a certain number of "rounds" or " iterations ":

In the first round do first

a) every non-engaged man proposes marriage to the woman he likes best, and then

b) every woman answers the admirer she likes best with “maybe” and everyone else with “no”. She is thus provisionally engaged to the suitor she likes best up to then, and this suitor is accordingly provisionally engaged to her.

In each subsequent round, go first

a) every non-engaged man proposes to the woman he likes best and to whom he has not yet made a proposal (regardless of whether this woman is already engaged).

b) Then each woman replies “maybe” if she is not engaged at the moment or if she prefers this man over her current temporary partner (in which case she rejects her current temporary partner and breaks the engagement). Because engagements are provisional, an already engaged woman retains the right to leave her previous partner and replace him with a better one.

This process is repeated until everyone is engaged.

The run time complexity of this algorithm is where the number of men or women is. ${\ displaystyle O (n ^ {2})}$ ${\ displaystyle n}$

This algorithm guarantees that

Everyone is getting married: In the end, there cannot be a man and a woman who are both not engaged. This is because he must have proposed to her at some point (after all, a man will propose to any woman if necessary). And as soon as she receives a proposal, she would necessarily be engaged (to someone).
The marriages are stable: Alice and Bob are both engaged, but not to each other. After the algorithm finishes, it is not possible for both Alice and Bob to prefer each other over their respective current partners. If Bob prefers Alice to his current partner, he must have proposed Alice before her. If Alice accepted his proposal but ended up not being married to him, she must have left him for someone she likes more. Hence, she can't like Bob any more than her current partner. If Alice turned down his proposal, she was already engaged to someone she liked more than Bob.

algorithm

function stableMatching {
    Initialisiere alle m ∈ M und w ∈ W als alleinstehend
    while ∃ Mann m, der noch einer Frau w einen Antrag machen kann alleinstehend {
       w = erste Frau auf m’s Liste, der m noch keinen Antrag gemacht hat
       if w ist alleinstehend
         (m, w) sind verlobt
       else gibt es schon ein Paar (m', w)
         if w m gegenüber m' bevorzugt
            m' wird alleinstehend
           (m, w) sind verlobt
         else
           (m', w) bleiben verlobt
    }
}

Optimality of the solution

While the solution is stable, it is not necessarily optimal from the point of view of all individuals. The traditional form of the algorithm is optimal for the group making the requests. However, this stable and optimal solution for the applicant does not have to be optimal for the applicant. This is shown in the following example:

There are three applicants (A, B, C) and three applicants (X, Y, Z) who have the following preferences:

A: YXZ B: ZYX C: XZY X: BAC Y: CBA Z: ACB

There are three stable solutions to this matching arrangement:

Applicants get their first choice and claim recipients their third (AY, BZ, CX)

All participants get their second choice (AX, BY, CZ)

Applicants get their first choice and applicants their third (AZ, BX, CY)

All three solutions are stable because instability requires both participants to be happier with a different partner. If a group receives their first choice, it guarantees that the matches are stable because group members would be more unhappy with any other proposed match. If everyone gets their second choice, any other match is guaranteed to be displeased by either party. The algorithm converges to the applicant-optimal solution in a single round, because each applicant receives exactly one application and therefore selects this application as the best choice. This guarantees that every applicant's application is accepted, which ends the match. This asymmetry of optimality is due to the fact that the applicants can choose from the entire set, but the applicants can choose from a limited subset of applicants at any point in time.

Stable marriage with indifference

In the classic version of the problem, each person has to arrange the members of the opposite sex in a strict order of preference. In practice, however, one person can favor two or more people equally. Such an undecided preference is called indifference. In the following example is tie between , and is tie between . ${\ displaystyle m_ {2}}$ ${\ displaystyle w_ {3} \ & w_ {1}}$ ${\ displaystyle w_ {2}}$ ${\ displaystyle m_ {1} \ & m_ {2}}$

${\ displaystyle m_ {1} [\ w_ {2} \ w_ {1} \ w_ {3} \] \ \ \ \ \ \ w_ {1} [\ m_ {3} \ m_ {2} \ m_ {1 } \]}$

${\ displaystyle m_ {2} [\ left (w_ {3} \ w_ {1} \ right) w_ {2}] \ \ \ \ \ \ \ w_ {2} [\ left (m_ {1} \ m_ {2 } \ right) m_ {3}]}$

${\ displaystyle m_ {3} [\ w_ {1} \ w_ {2} \ w_ {3} \] \ \ \ \ \ \ w_ {3} [\ m_ {2} \ m_ {3} \ m_ {1 } \]}$

If undecided preference lists are allowed, the stable marriage problem has three stability concepts, which are discussed in the following sections.

A matching is said to be weakly stable if there is no pair, so that each of the two strictly favors the other over his / her matching partner. Robert W. Irving has extended the Gale-Shapley algorithm as follows to provide a weakly stable matching at the point in time , where n denotes the size of the stable marriage problem. If the men and women are indifferent in their preferences, decisions are made arbitrarily. As the algorithm advances, the preference lists become shorter and shorter. ${\ displaystyle O (n ^ {2})}$

 1 Ordne jede Person als alleinstehend ein;
 2 	while (irgendein Mann m alleinstehend ist) do
 3 	begin
 4 		w := erste Frau auf m's Liste;
 5 		m macht einen Antrag und verlobt sich mit w;
 6 		if (irgendein Mann m' mit w verlobt ist) then
 7 		    ordne m' als alleinstehend ein;
 8 		for each (Nachfolger m'' von m auf w's Liste) do
 9 			delete das Paar (m'', w)
10 	end;
11 	gib die verlobten Paare aus, die ein stabiles Matching bilden

A matching is super-stable when there is no pair, so that each of the two strictly favors the other over his / her partner or is indifferent between them. Robert W. Irving modified the algorithm described above to check whether there is such a super-stable matching and, if it exists, outputs the matching at the time . The following is the pseudo-code: ${\ displaystyle O (n ^ {2})}$

 1 Ordne jede Person als alleinstehend ein;
 2 repeat
 3 	while (irgendein Mann m alleinstehend ist) do
 4 	  for each (Frau w am Anfang von m's Liste) do
 5 	  begin
 6 	  m macht einen Antrag und verlobt sich mit w;
 7 		for each (strikten Nachfolger m' von m auf w's Liste) do
 8 		begin
 9 			if (m' ist verlobt) mit w then
10 			   break die Verlobung;
11 			delete the pair (m'. w)
12 		end
13 	  end
14 	for each (woman w who is multiply engaged) do
15 	begin
16 		break all engagements involving W;
17 		for each (man m at the tail of w’s list) do
18 		  delete the pair (m. w)
19     end;
20 until (some man’s list is empty) or (jeder verlobt ist);
21 if jeder verlobt ist, then
22 	ist die Verlobungsrelation ein super-stabiles Matching
23 else
24 	existiert kein super-stabiles Matching

A matching is strongly stable if there is no pair x, y such that xy is strictly preferred over his / her partner and y is either strictly preferred over his / her partner or indifferent between the two. Robert W. Irving has developed an algorithm that checks whether such a highly stable matching exists and, if it exists, outputs the matching. The algorithm calculates the perfect match between sets of men and women so that it finds the critical amount of men who are engaged to multiple women. Since such engagements are never stable, all such couples are deleted and the application process is repeated until either 1) any man's preference list becomes empty (in which case there is no highly stable matching) or 2) a highly stable matching is achieved . Here is the pseudo-code to find a strongly stable matching. It has a running time of what is explained in Lemma 4.6. ${\ displaystyle O (n ^ {4})}$

 1 Ordne jede Person als alleinstehend ein;
 2 repeat
 3 	while (irgendein Mann alleinstehend ist) do
 4 	  for each (Frau w am Anfang von m's Liste) do
 5 	  begin
 6 	  m macht einen Antrag und verlobt sich mit w;
 7 		for each (strikten Nachfolger m' von m auf w's Liste) do
 8 		begin
 9 			if (m' verlobt ist) mit w then
10 			   break die Verlobung;
11 			delete das Paar (m'. w)
12 		end
13 	  end
14     if (die Verlobungsrelation kein perfektes Matching enthält) then
15     begin
16 	    finde die kritische Menge Z an Männern;
17 	    for each (Frau w die mit einem Mann aus Z verlobt ist) do
18 	    begin
19 	        break alle Verlobungen von w;
20   	        for each Mann m am Ende von w's Liste do
21 	            delete das Paar (m, w)
22 	    end;
23     end;
24 until (die Liste eines Mannes leer ist) or (jeder verlobt ist);
25 if jeder verlobt ist then
26 	ist die Verlobungsrelation ein super-stabiles Matching
27 else
28 	existiert kein stark-stabiles Matching

Implementation in software packages

R : The Gale – Shapley algorithm (also known as the deferred acceptance algorithm) for the stable marriage problem and the hospitals / interns problem is matchingMarketsimplemented in the package .

Python : The Gale-Shapley algorithm is QuantEcon/MatchingMarkets.pyincluded in the package along with several other algorithms for generalized matching problems .

API : The MatchingTools API makes the Gale-Shapley algorithm available via a free programming interface.

Individual evidence

^ The Prize in Economic Sciences 2012 . Nobelprize.org. Retrieved January 2, 2018.

↑ ^a ^b Bruce Maggs and Ramesh Sitaraman: Algorithmic nuggets in content delivery . In: ACM SIGCOMM Computer Communication Review . 45, No. 3, 2015.

^ ^A ^b D. Gale, LS Shapley: College Admissions and the Stability of Marriage . In: American Mathematical Monthly . 69, 1962, pp. 9-14. doi : 10.2307 / 2312726 .

↑ Harry Mairson: The Stable Marriage Problem . In: The Brandeis Review , 12, 1992 ( cs.columbia.edu ).

↑ Kazuo Iwama, Shuichi Miyazaki: A Survey of the Stable Marriage Problem and Its Variants . In: International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) . 2008, pp. 131-136. doi : 10.1109 / ICKS.2008.7 .

↑ ^a ^b ^c ^d Robert W. Irving: Stable marriage and indifference . In: Discrete Applied Mathematics . 48, No. 3, February 15, 1994, pp. 261-272. doi : 10.1016 / 0166-218X (92) 00179-P .

^ Sara Robinson: Are Medical Students Meeting Their (Best Possible) Match? Archived from the original on November 18, 2016. Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. In: SIAM News . No. 3, April 2003, p. 36. Retrieved January 2, 2018. @1@ 2

↑ D. Gusfield, RW Irving: The Stable Marriage Problem: Structure and Algorithms . MIT Press, 1989, ISBN 0-262-07118-5 , p. 54.

^ John William Hatfield, Paul Milgrom: Matching with Contracts . In: American Economic Review . 95, No. 4, 2005, pp. 913-935. doi : 10.1257 / 0002828054825466 .

^ Vincent Crawford, Elsie Marie Knoer: Job Matching with Heterogeneous Firms and Workers . In: Econometrica . 49, No. 2, 1981, pp. 437-450. doi : 10.2307 / 1913320 .

^ Thilo Klein: Analysis of Stable Matchings in R: Package matchingMarkets . In: Vignette to R Package matchingMarkets . 2015.

^ MatchingMarkets: Analysis of Stable Matchings . In: R Project .

^ MatchingMarkets.py . In: Python package .

↑ MatchingTools API .

Textbooks and other important works that are not cited in the text

Dubins L., Freedman D.: Machiavelli and the Gale-Shapley algorithm . In: American Mathematical Monthly . 88, No. 7, 1981, pp. 485-494. doi : 10.2307 / 2321753 .
J. Kleinberg, E. Tardos (2005). Algorithm Design , Chapter 1, pp 1–12. See companion website for text aw-bc.com .
DE Knuth (1976). Mariages stables . Montreal: Les Presses de l'Universite de Montreal.
DE Knuth (1996). Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms , english translation, (CRM Proceedings and Lecture Notes), American Mathematical Society.
B. Pittel (1992). On likely solutions of a stable marriage problem , The Annals of Applied Probability 2; 358-401.
AE Roth (1984). The evolution of the labor market for medical interns and residents: A case study in game theory , Journal of Political Economy 92: 991-1016.
AE Roth, MAO Sotomayor (1990). Two-sided matching: A study in game-theoretic modeling and analysis Cambridge University Press .
Yoav Shoham, Kevin Leyton-Brown: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations . Cambridge University Press , New York 2009, ISBN 978-0-521-89943-7 . See section 10.6.4; downloadable free online .
J. Schummer, RV Vohra: Mechanism design without money . In: Algorithmic Game Theory 2007, ISBN 978-0-521-87282-9 , pp. 255-262.

Web links

[1] The Prize in Economic Sciences 2012 . Nobelprize.org. Retrieved January 2, 2018.

[nuggets-2] Bruce Maggs and Ramesh Sitaraman: Algorithmic nuggets in content delivery . In: ACM SIGCOMM Computer Communication Review . 45, No. 3, 2015.

[gale-3] A ^b D. Gale, LS Shapley: College Admissions and the Stability of Marriage . In: American Mathematical Monthly . 69, 1962, pp. 9-14. doi : 10.2307 / 2312726 .

[4] Harry Mairson: The Stable Marriage Problem . In: The Brandeis Review , 12, 1992 ( cs.columbia.edu ).

[IwamaMiyazaki2008-5] Kazuo Iwama, Shuichi Miyazaki: A Survey of the Stable Marriage Problem and Its Variants . In: International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) . 2008, pp. 131-136. doi : 10.1109 / ICKS.2008.7 .

[sciencedirect-6] Robert W. Irving: Stable marriage and indifference . In: Discrete Applied Mathematics . 48, No. 3, February 15, 1994, pp. 261-272. doi : 10.1016 / 0166-218X (92) 00179-P .