Prove it is impossible for every male to be paired with their last choice in the stable marriage algorithm...












0














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.










share|cite|improve this question






















  • if there is only one couple, $textit{technically}$ the man is with his last choice =P
    – Zachary Hunter
    Jan 4 at 4:43










  • 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.
    – Hans
    Jan 4 at 6:48
















0














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.










share|cite|improve this question






















  • if there is only one couple, $textit{technically}$ the man is with his last choice =P
    – Zachary Hunter
    Jan 4 at 4:43










  • 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.
    – Hans
    Jan 4 at 6:48














0












0








0







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.










share|cite|improve this question













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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 4 at 3:32









Matteo CiccozziMatteo Ciccozzi

36




36












  • if there is only one couple, $textit{technically}$ the man is with his last choice =P
    – Zachary Hunter
    Jan 4 at 4:43










  • 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.
    – Hans
    Jan 4 at 6:48


















  • if there is only one couple, $textit{technically}$ the man is with his last choice =P
    – Zachary Hunter
    Jan 4 at 4:43










  • 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.
    – Hans
    Jan 4 at 6:48
















if there is only one couple, $textit{technically}$ the man is with his last choice =P
– Zachary Hunter
Jan 4 at 4:43




if there is only one couple, $textit{technically}$ the man is with his last choice =P
– Zachary Hunter
Jan 4 at 4:43












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.
– Hans
Jan 4 at 6:48




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.
– Hans
Jan 4 at 6:48










1 Answer
1






active

oldest

votes


















0














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.






share|cite|improve this answer























    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    0














    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.






    share|cite|improve this answer




























      0














      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.






      share|cite|improve this answer


























        0












        0








        0






        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.






        share|cite|improve this answer














        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.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 4 at 7:02

























        answered Jan 4 at 6:27









        HansHans

        4,96821032




        4,96821032






























            draft saved

            draft discarded




















































            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            1300-talet

            1300-talet

            Display a custom attribute below product name in the front-end Magento 1.9.3.8