Prove it is impossible for every male to be paired with their last choice in the stable marriage algorithm...
$begingroup$
I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm.
I have a general idea of how to approach it, which is:
Suppose there exists a stable pairing T in which every man is paired with his least favorite woman, also suppose it took K days for the algorithm to halt. This means that on every day before the Kth day every man had been rejected by every woman. However, it is impossible for every woman to reject every n-1 men. If the algorithm halts on the Kth day then there has to be at least one woman who has not yet received a proposal on the K-1th day. Therefore, on the last day there is a woman who receives only one proposal and cannot reject it. Consequently, such stable pairing T does not exist.
Is this logically correct? I know I probably need to refine it a bit.
discrete-mathematics algorithms algorithmic-game-theory
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
$endgroup$
add a comment |
$begingroup$
I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm.
I have a general idea of how to approach it, which is:
Suppose there exists a stable pairing T in which every man is paired with his least favorite woman, also suppose it took K days for the algorithm to halt. This means that on every day before the Kth day every man had been rejected by every woman. However, it is impossible for every woman to reject every n-1 men. If the algorithm halts on the Kth day then there has to be at least one woman who has not yet received a proposal on the K-1th day. Therefore, on the last day there is a woman who receives only one proposal and cannot reject it. Consequently, such stable pairing T does not exist.
Is this logically correct? I know I probably need to refine it a bit.
discrete-mathematics algorithms algorithmic-game-theory
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
$endgroup$
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48
add a comment |
$begingroup$
I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm.
I have a general idea of how to approach it, which is:
Suppose there exists a stable pairing T in which every man is paired with his least favorite woman, also suppose it took K days for the algorithm to halt. This means that on every day before the Kth day every man had been rejected by every woman. However, it is impossible for every woman to reject every n-1 men. If the algorithm halts on the Kth day then there has to be at least one woman who has not yet received a proposal on the K-1th day. Therefore, on the last day there is a woman who receives only one proposal and cannot reject it. Consequently, such stable pairing T does not exist.
Is this logically correct? I know I probably need to refine it a bit.
discrete-mathematics algorithms algorithmic-game-theory
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
$endgroup$
I'm trying to prove that it is impossible for every man to be paired with their last choice in the stable marriage algorithm.
I have a general idea of how to approach it, which is:
Suppose there exists a stable pairing T in which every man is paired with his least favorite woman, also suppose it took K days for the algorithm to halt. This means that on every day before the Kth day every man had been rejected by every woman. However, it is impossible for every woman to reject every n-1 men. If the algorithm halts on the Kth day then there has to be at least one woman who has not yet received a proposal on the K-1th day. Therefore, on the last day there is a woman who receives only one proposal and cannot reject it. Consequently, such stable pairing T does not exist.
Is this logically correct? I know I probably need to refine it a bit.
discrete-mathematics algorithms algorithmic-game-theory
discrete-mathematics algorithms algorithmic-game-theory
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
asked Jan 4 at 3:32
Matteo CiccozziMatteo Ciccozzi
5019
5019
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48
add a comment |
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.
answered Jan 4 at 6:27
HansHans
5,03421232
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061292%2fprove-it-is-impossible-for-every-male-to-be-paired-with-their-last-choice-in-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.
answered Jan 4 at 6:27
HansHans
5,03421232
$endgroup$
add a comment |
$begingroup$
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.
answered Jan 4 at 6:27
HansHans
5,03421232
$endgroup$
add a comment |
$begingroup$
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.
answered Jan 4 at 6:27
HansHans
5,03421232
$endgroup$
Suppose there is such a pairing for $n$ pairs of men and women. Let $d$ be the earliest round when there is a man to pair with his woman of his last choice. One of such men is thus rejected by his more favored $n-1$ women who having ever been proposed to are all engaged by the $d-1$'th round. All the other men are by this reason engaged. The woman of his last choice has not ever been proposed to by any man by the $d-1$'th round. Otherwise she would have been engaged by then and all women would have been engaged and the algorithm ends on round $d-1$ which is impossible. On round $d$ only that man is left to propose. He proposes to that woman. Since that woman is not engaged, it does not affect all the pairings having already formed by round $d-1$. Round $d$ is thus the ultimate round. All the other $n-1$ men favor the women they are paired to more than this woman last proposed to. We have a contradiction.
answered Jan 4 at 6:27
HansHans
5,03421232
edited Jan 4 at 7:02
answered Jan 4 at 6:27
HansHans
5,03421232
answered Jan 4 at 6:27
HansHans
5,03421232
answered Jan 4 at 6:27
HansHans
5,03421232
5,03421232
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061292%2fprove-it-is-impossible-for-every-male-to-be-paired-with-their-last-choice-in-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
if there is only one couple, $textit{technically}$ the man is with his last choice =P
$endgroup$
– Zachary Hunter
Jan 4 at 4:43
$begingroup$
Your derivation is not clear. "On every day before the Kth day every man had been rejected by every woman" is wrong. Every day there is at least one engagement and thus not every man is rejected by every woman. "every woman to reject every n-1 men" does not make sense.
$endgroup$
– Hans
Jan 4 at 6:48