Stable Marriage Problem | GeeksforGeeks
Stable Marriage Problem | GeeksforGeeks
Find Complete Code at GeeksforGeeks Article: http://www.geeksforgeeks.org/stable-m…
This video is contributed by Sagar Khurana
Please Like, Comment, Share the Video among your friends.
Also, Subscribe if you haven’t already! :)
Content
0.95 -> Hello and welcome to this video tutorial of
Stable Marriage Problem by GeeksforGeeks.
6.319 -> Let’s begin, with The Problem Statement
of stable marriage problem, which states the
12.4 -> input as two sets with n men and n women respectively,
where each man has a preference list of women
21.49 -> for marriage and similarly each woman also
have preference list of all men in it. We
29.03 -> can represent these preferences in 2-D matrices
as shown below for each men and women. This
35.33 -> matrix represent the preference list of all
men and other represents the preferences of
38.08 -> women for men. For eg:- When we see in left
matrix, that is preferences for Men, we see
42.88 -> that Man A has preference list such that A
likes woman O the most and woman P the least.
52.23 -> More preferable = more like, preference decreases
as we move towards right.
58.64 -> Now, when we have preferences of both sets.
The stable marriage problems wants to create
66.67 -> pairs of men and women with each other, such
that there are no two people of opposite sex
74.399 -> who would both rather have each other than
their current partners. As shown in the given
81.35 -> figure, with n men and n women, we need n
pairs of men and women, such that it is a
88.219 -> stable pair or marriage, for given figure,
consider
92.92 -> A1 B2 are matched,
A2 B3 are matched
96.959 -> and A3 B1 are connected
100.729 -> Such that these pairs are stable pairs, and
stable pairs are defined as, that there are
106.289 -> no two people of opposite sex from different
matching, who would prefer each other more
112.28 -> than their current partners.
114.09 -> For eg:-Let’s say A3 likes B2 more than
it’s current partner B1, but that doesn’t
124.529 -> make an unstable marriages, but when B2 also
likes A3 more than it’s current partner
133.04 -> A1, then we call these two pairs as unstable
pairs.
144.42 -> Let us examine the current matching, whether
these pairs are stable or not, with taking
149.61 -> an example of preference list.
Let’s start with first matching A1,B2
155.079 -> A1 is matched with B2, but there is B1 before
B2 in A1’s preference list, now we see in
165.47 -> B2’s preference list, and examine if, there
is some A, before A1 in it.
173.11 -> A3 and A2 are both before A1, hence we check
whether A2 has B2 before it’s present partner
183.26 -> in A2’s Preference List.
185.26 -> A2 has it’s current partner as 1st on Preference
i.e. B3 and B3 also have A2 as first member
194.78 -> of its preference list.
196.939 -> Hence, we examine last pair A3 B1, we start
from A3’s preference list and see there
207.959 -> is B2 before B1 in A3’s list, and similarly
B2 has A3 before A1.
217.04 -> Hence
this matching is unstable. Please note, when
228.689 -> we are given a pair, we can’t tell whether
it’s stable or unstable. Stability is defined
234.4 -> for the complete matching(on complete set
of pairs), but not single pair.
238.049 -> Let’s move on to the solution of stable
marriage problem, the solution of the given
242.709 -> stable marriage problem was given by Gale
and shapely and is known as gale-shapley algorithm.
249.44 -> We will read the whole algorithm and produce
it’s pseudo code side by side. First of
255.15 -> all, we initialize all men and women to be
free i.e i.e there is no pair in starting.
261.42 -> Then we iterate on free man available in list
of men, which has a woman to be proposed,
269.29 -> whom he haven’t already proposed from his
preference list.. This man proposes to the
274.97 -> first woman, whom he hasn't proposed yet,
and if the proposed girl is free, get’s
281.03 -> engaged with him. You can see the pseudo code,
which says while we can find a man who is
284.41 -> free and haven’t proposed to at least one
woman from his preference list, we move, then
292.401 -> we find whether first woman is free or engaged
and move forward.
297.77 -> else, when women is already engaged with someone,
if that woman finds the proposing man before
309.25 -> the present partner on her present preference
list that she likes proposing man more, she
315.35 -> dumps her present partner and get’s engaged
or pair up with proposing man. Otherwise,
321.24 -> nothing happens and we move to next iteration
of algorithm. The pseudo code also works like
326.92 -> this, if there is a pair (m’,w), and m is
before m’ in her preference list, w dumps
335.42 -> or unpair with m’ and pairs up with m.
338.72 -> Algorithm is terminated and we get a stable
matching, when all men are paired.
346.21 -> Now we start working on an example using pseudo
code. Take two 2-D matrices as shown bleow.
352.57 -> These are Preference lists for both men and
women as shown below, where A,B,C,D,E are
358.69 -> 5 men and L,M,N,O,P are 5 women. We have 2
5x5 matrices to depict preference lists. Now
368.46 -> we work on this input and create a stable
matching. We start with A, which is first
373.28 -> free man available in list, first woman in
his list is O, and hence A proposes O and
381.22 -> we see that O is also free and hence
384.271 -> O and A pairs up or get engaged.
389.75 -> Next free man is B, and first woman on his
preference list is P, and hence B proposes
396.9 -> P and P is free as you can see.
400.74 -> Therefore we have both B and P paired up or
engaged.Similarly C has M on first and M is
409.53 -> free, they both pair up
411.66 -> Now, we move to next free man i.e. D, D has
P as first unproposed woman on preference
420.91 -> list. We see that P is already paired and
hence, we are in this part of code we see
428.28 -> the pair B P is already there.
431.7 -> we see that D is after B on preference list
of P, hence P will not break-up and move on
439.61 -> with B and D is still free and he has already
proposed P.
445.61 -> Now D goes to second unproposed woman on his
preference list i.e M, and proposes M, we
453.19 -> see here that M has a pair C M and D is before
C in M’s preference list, hence, M breaks
463.34 -> up with C and pairs up with D.
467.55 -> So, we found a new pair D M. and C is free
now.Now C already proposed M, and now goes
475.99 -> to P and proposes her, P is paired up with
most liked man by P, hence P will not break
484.01 -> up and
485.01 -> C is rejected and still unpaired.C goes to
next i.e L and we can see L is free and
493.72 -> pairs up with C.
497.14 -> Next here we have E as free man and E proposes
to O and O dislikes E more than her present
504.96 -> partner and hence doesn’t unpair and continues.
508.52 -> E next goes to L. L has E before C in preference
list, hence L breaks up with C
520.63 -> and L pair up with E. So, C is again unpaired.
525.74 -> Next here, we see that C is free and goes
to O, for pairing but O rejects as O has C
535.36 -> after A(the present partner) in Preference
list.
539.63 -> hence, C is still free, C goes to next i.e.
N. N is free this time and of course N pairs
547.76 -> up with C.
549.29 -> Now we can see, that all men are paired, hence
algo terminates here.
553.5 -> Let’s have a look at the C code of Stable
Marriage Problem. We start with input for
560.36 -> the same. I n this code, we take input as
a 2-D Matrix of size 2N x N, where rows 0
570.52 -> - N-1 represents men and their preference
list and row N to 2N - 1 represents Women
578.96 -> with their preference list.
It is exactly the same kind of matrix, we
583.86 -> took in example previously.
586.25 -> Let’s discuss, the function, which tells
us, whether woman w prefers m1 over m or not,
595.08 -> in this we pass, w, m and m1, if women prefers
m1 over m, it comes before m in prefer matrix,
604.75 -> and hence first if statement occurs, and function
returns true, i.e. w prefers m1 over m. Otherwise,
614.58 -> if she prefers m more, Second if statement
is true before first and function ends and
622.86 -> returns false, i.e women is prefers proposing
partner m over current partner m1.
631.26 -> Next we have the function to generate stable
pairs, which only takes prefer matrix as input.
638.47 -> Let’s define our variables. wPartner stores
-1 at w-Nth index, if she is free, otherwise
647.46 -> it have index of paired man.
mFree stores false , if ith man is free, and
655.83 -> true, if ith man is paired.
659.16 -> Now that, we initialize wPartner with -1,
i.e. all are free and mFree as False, i.e
667.22 -> all men are also free. Since all men are free,
we have freecount as N.
673.98 -> We discuss the actual implementation of pseudo
code. We go, while iterating through free
682.03 -> man,then we find a free man, from mFree array,
and extract first false, i.e. first free man
689.91 -> in this list.
691.31 -> Then, we iterate through m’s preference
list to find his prefered women, m proposes
696.91 -> to this women. Then if w is free, we pair
w with m, and m is paired now, hence we decrease
706.32 -> freecount by 1. Otherwise, if w is already
paired, we find her current partner m1, and
714.05 -> then find if w likes m over m1, i.e if this
func. Returns false, we pair w with m and
725 -> m1 is free, while m got paired with w. Note,
we doesn’t have any change in number of
733.19 -> free men in this case,as one got paired and
other got unpaired. Otherwise, if w likes
739.97 -> current partner more, we do nothing, and move
forward. We do this until we get all men paired,
747.93 -> hence algo terminates when freecount is zero.
751.47 -> Time complexity comes out to be O(n^2), as
in worst case, all men are paired with their
758.16 -> last prefered women, and hence we first iterate
through N men, and iterate through preference
765.63 -> list of each man. We will have complexity
O(n^2).
771.87 -> Now we see some applications of the given
Algorithm, we see that this stable matching
778.1 -> analogy can be extended to stable matching
of two sets and even when a problem can represented
786.44 -> in graph theory as bipartite graph and we
need a matching, such that there is some preference
794.02 -> in both partite sets, we apply gale shapely
algo to find stable matching. For eg. There
801.44 -> are N students/candidates sitting for placement
session and N companies come to campus with
807.91 -> 1 vacant position in each. Now each company
has preference for candidates after interview
816.81 -> and candidates also have some preference for
each company. We can now apply gale shapely
822.4 -> algo to find perfect or preferable/stable
match b/w candidates and companies.
828.74 -> Thanks for watching, please like and share
this video, and leave us your comments for
833.649 -> feedback. Stay tuned for more updates.
Source: https://www.youtube.com/watch?v=o1olHmxDzTw