Conference rusure::math

    It's a homework assignment I haven't been able to solve.  I'm looking
    for hints on how to procede.  Since the assignment is due 2/19/93,
    if you have qualms about providing such hints, you need only wait until
    the 20 to post.
    
                                    August G. Reinig

>>	A Marriage is a perfect matching between the boys and the
>>	girls.  

Could you further describe what the above means?  I can see 2 different
interpretations of it.

Thanks.

JPB

    My understanding is that you pair each boy with one girl and vice
    versa, so that you have n pairs.  Can you do so in such a way that each
    pair is stable?
    
                                    August

        A plausible approach is to come up with an algorithm which
        given an assignment with at least one unstable pair, will
        always munge it into an assignment with at least one fewer
        unstable pair.
        
        If you can do that, then the smallest k such that there is an
        assignment with exactly k unstable pairs, has to be k=0.
        
        Dan

    Found the answer in Algorithms, 2nd Edition by Robert Sedgewick.
    
    Choose the first man a the suitor.  He proposes to the woman he prefers
    most and they become engaged.  The second man then proposes to the
    woman he prefers most.  If she is free, they become engaged.  If not,
    if she prefers her fianc� to him, she refuses.  If she prefers her
    hime to her fianc�, she breaks the current engagement and
    becomes engaged to her new suitor.  The man man who's engagement was
    broken is now the suitor and proposes to the next woman he prefers the
    most.  This continues until all men have been suitors and are engaged.
    
    Women break engagements only if they prefer the new beau more than the
    old.  Women always move up in preference.  Once a man loses a fianc�,
    he can never regain her.  So, for each man, the process of breaking
    engagements must terminate.
    
    Since a man proposes in order of preference, any woman he prefers to
    his fianc� either rebuffed his proposals or broke the engagement for a
    man she prefered to him.  Also, any man a woman prefers to her fianc� 
    is paired with someone he prefers to her.
    
    Every man must find at least one unengaged woman, so he always finds a 
    fianc�.  Every woman is engaged since men may be engaged to only one
    woman and there are as many men as women.  
    
    Thus, a stable marriage exists.  
    
                                August G. Reinig
    

>    In a group of n boys and n girls, each girl ranks the n boys according
>    to her preference and each boy ranks the n girls according to his
>    preference.  A Marriage is a perfect matching between the boys and the
>    girls.  A marriage is unstable if there is a pair who are not married
>    to each other but like each other more than they like their respective
>    spouses; otherwise, it is stable.  Prove that a stable marriage always
>    exists.

	Generalize the problem:  consider 2*n monogamous bisexuals.   Each
individual ranks all the 2*n-1 others.   Retain exactly the same definition of 
stability as worded above.   Does a stable Marriage still exist?

	Not necessarily.

	Suppose that there are 4 individuals: labeled imaginatively A,B,C & D.
Let the preferences be as follows:

A: prefers B over C over D
B: prefers C over A over D
C: prefers A over B over D
D: irrelevant

	Suppose that a Marriage exists.   By symmetry we may suppose that it's
A+B & C+D.   But B & C are yearningly attracted to one another more than they
are to their respective spouses.

Andrew.

    
    The algorithm for bipartite matching is usually called 'linear
    assignment'.  If the boys rank each girl in order of preference, the
    solution to the linear assignment problem is a 'stable marriage'.
    
    regret to say that this is only boy-optimal, though.
    
    ;)