The Problem The stable marriage problem does not handle divorces. This is because we assume everyone is interested in everyone else of the opposite sex and we assume that the preferences do not change. In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley algorithm (for this problem you can assume the version of the Gale-Shapley algorithm that we did in class where the women do all the proposing). Given an instance of the stable marriage problem (i.e. set of men M and the set of women W along with their preference lists: Lm and Lw for every m E M and w E W respectively), call a man m E M a home- wrecker if the following property holds. There exists an Lm such that if m changes his preference list to Lm (from Lm) then the Gale-Shapley algorithm matches everyone to someone else. In other words, let Sorig be the stable marriage output by the Gale-Shapley algorithm for the original input and Snew be the stable marriage output by the Gale-Shapley algorithm for the new instance of the problem where m's preference list is replaced by Lm (but everyone else has the same preference list as before). Then Sorig n Snew = Ø. %3D Here are the two parts: • Part (a): You will first solve a simpler version of the problem. For every integer n > 2 argue the following: There exists an instance of the stable marriage problem with n men and n women such that there is a man m such that is he changes his preference list from Lm to Lm then we have Sorig + Snew- • Part (b) : For every integer n > 2 argue the following: There exists an instance of the stable marriage problem with n men and n women such that there is a man who is a home-wrecker.

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

100%

I am a bit confused with how this would. prove part b sir/ma'am.

Could I have an example of a home-wrecker, where changing the preference list of one man changes all the other stable pairs? Thanks!

The Problem
The stable marriage problem does not handle divorces. This is because we assume everyone is interested
in everyone else of the opposite sex and we assume that the preferences do not change.
In this problem, we will see the effect of changes in preferences in the outcome of the Gale-Shapley
algorithm (for this problem you can assume the version of the Gale-Shapley algorithm that we did in class
where the women do all the proposing).
Given an instance of the stable marriage problem (i.e. set of men M and the set of women W along with
their preference lists: Lm and Lw for every m E M and w E W respectively), call a man m E M a home-
wrecker if the following property holds. There exists an Lm such that if m changes his preference list to
Lm (from Lm) then the Gale-Shapley algorithm matches everyone to someone else. In other words, let Sorig
be the stable marriage output by the Gale-Shapley algorithm for the original input and Snew be the stable
marriage output by the Gale-Shapley algorithm for the new instance of the problem where m's preference
list is replaced by Lm (but everyone else has the same preference list as before). Then
Sorig n Snew
Ø.
Here are the two parts:
• Part (a) :
You will first solve a simpler version of the problem. For every integer n > 2 argue the following:
There exists an instance of the stable marriage problem with n men and n women such that there is
a man m such that is he changes his preference list from Lm to Lm then we have
Sorig + Snew-
Part (b) : For every integer n > 2 argue the following: There exists an instance of the stable
marriage problem with n men and n women such that there is a man who is a home-wrecker.

Expert Solution

Step 1

Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}