Results 1 to 2 of 2

Math Help - Stable Matching

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Stable Matching

    Prove that if man x is paired with woman a in some stable matching, then a
    does not reject x in the proposal algorithm with men proposing. (Hint: Consider the first
    occurrence of such a rejection.)

    Conclude that among all stable matchings, every man is happiest in the matching
    produced by this algorithm.

    Thanks for any advice!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    I am using w for the woman and m for the man.

    Suppose such a rejection occurs. Consider the first such rejection. This means w rejects m because some m' higher on her priority list proposes to her later. Say, in the stable matching S where w was paired with m, m' was paired with w'. Since w prefers m' to m, the matching must have been stable because m' prefers w' to w. So in the algorithm, m' must have proposed to w' first and got rejected. Therefore we get a contradiction to our initial assumption.

    The second part is obvious.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Stable by but not Asymptotically Stable
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: September 9th 2010, 05:26 AM
  2. stable/unstable DEs
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: April 25th 2010, 04:43 PM
  3. alpha stable
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: July 16th 2009, 12:12 PM
  4. Stable, but not asymptotically stable
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: February 25th 2009, 11:06 AM
  5. Stable Equilibrium
    Posted in the Calculus Forum
    Replies: 0
    Last Post: August 28th 2008, 05:41 AM

Search Tags


/mathhelpforum @mathhelpforum