Question
This is a stable matching problem: The Hotel Partner Problem is as follows. There are 2n people and n hotel rooms. Each person maintains a
This is a stable matching problem:
The Hotel Partner Problem is as follows. There are 2n people and n hotel rooms. Each person maintains a preference list of the remaining 2n 1 people. The objective is to assign two people to each room such that the assignment is stable. An assignment is stable if there are no two people assigned to different rooms who prefer each other over their current partners. Give an instance of the Hotel Partner Problem for which there is no stable solution.
My answer is:
proof: Suppose there are P1 and P2 assigned to room A and room B, and they prefer to each other than their current partner P1' and P2'. In some execution Gale-Shapley algorithm results in a matching S, P1 will become a partner to P1', P2 will become to partner P2'. Thus, the other stable matching, consisting of the pairs(P1, P2) and (P1', P2') attainable from an execution of the G-S algorithm in which people's purpose. Also, the question doesn't mention that P1' prefer P2' to P1. Thereby, there is no stable solution.
Please correct my answer, thank you!
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started