Question

Prove: If the boy-optimal matching and the girl-optimal matching turn out to be same for a set of preferences, there exists only one possible solution for stable matching.

Answer 1

Stable matching problem in mathematics and information technology is the problem of finding the stable matching between two equal sized sets of elements given an ordering of preferences individually element. A matching is a mapping from the elements of one contend the elements of the other set. A matching is not stable if:

1. There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
2. B also prefers A over the element to which B is already matched.

In other words, a matching is stable when there does not exist any match (A, B) how both A and B potential individually happier than they attend the element anywhere they are currently matched.

While the solution is stable, it is not necessarily optimal from all individuals' points of view. The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals. An example is as follows:

consider there are three boys (A,B,C) and three girls (X,Y,Z) which have preferences of:

    A: YXZ   B: ZYX   C: XZY   X: BAC   Y: CBA   Z: ACB

There are 3 stable solutions to this matching arrangement:

    boys get their first choice and girls their third (AY, BZ, CX) OR
    all participants get their second choice (AX, BY, CZ) OR
    girls get their first choice and boys their third (AZ, BX, CY)

As alredy said all 3 are stable solutions based on the selection but out of three only one can be preferred as the condition is both boy and a girl optimal matching is same.

The algorithm of the stable matching is given by:

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = first woman on m’s list to whom m has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
            m' becomes free
           (m, w) become engaged
         else
           (m', w) remain engaged
    }
}