Question

1.2 Find a stable marriage matching for the instance defined by the following ranking matrix. Break a tie using the alphabetic order. Draw a matrix after each iteration, and describe what happens in the iteration, using the format of Figure 10.12. When the process is over, write the matching a B y S A 1,3 1,4 2,2 4,1 B 2,3 4,1 1,4 2,2 C 3,2 3,4 3,3 3,1 D 4,3 2,2 4,1 1,4 AN

Answer 1

since given problem stable marriage problem

here 4 men and 4 women are exist

suppose men are $\alpha \beta \gamma \delta$ and women are ABCD

for simplicity lets assume men PQRS and women are ABCD

first make new 2 matrics for men and women according their prefrence

from given matrics we drive men preference matrics

P	1	2	3	4
Q	1	4	3	2
R	2	1	3	4
S	4	2	3	1

from given matrics we drive women prefenece matrics

A	3	4	2	1
B	3	1	4	2
C	2	4	3	1
D	3	2	1	4

here 1,2,3,4 number are used for opposite sex like men R preferenec order is 2,1,3,4 which is B,A,C,D

means men R most like women B then A,then C and least like women D

similarly

women D prefernece order is 3,2,1,4 which is R,Q,P,S means women D most like men R,then Q,then P and least like men S

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

at initial all men and women are free, none of them engaged

now pick up a men P which is initial free and see his prefenece list which is A now pair P with A

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now pick men Q and his first prefence is A so Q propose A but A is already engaged so A check her prefernce list since A like more Q than P so A break up with P now P again find new match

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now again P check his prefence his next prefence is B now B is free so P propose B

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now pick up new free man which is R and check his preference list he like most B and propose her now B is already engaged so she check her preference list since he likes R more than P so breaks up with P

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now p check again free womwn in his preference list which is C and woman C is free so P propose C

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now pick free new free men which is S and he like D and propose her who is free

P	A	B	C	D
Q	A	D	C	B
R	B	A	C	D
S	D	B	C	A

A	R	S	Q	P
B	R	P	S	Q
C	Q	S	R	P
D	R	Q	P	S

now pair is <men,women> = <P,C>,<Q,A>,<R,B>,<S,D>= $<\alpha ,C>,<\beta ,A>,<\gamma,B>,< \delta,D>$