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.
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...
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!
Transcribed Image Text: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
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY