Prove If the boyoptimal matching and the girloptimal matchin

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.

Solution

A number of boys and girls have preferences for each other and would like to be matched. There is a “stable” way to match each boy with a girl so that no unmatched pair can later find out that they can both do better by matching each other.

If we can match a boy with a girl who finds him unacceptable, then there may be a matching where all boy receive better mates than under the boy-optimal stable matching. If, however, we are seeking an individually rational matching while some boy can receive better mates without hurting any other boy, it is not possible to match all boy with strictly more-preferred mates.same condition applicable for the girls

Stability Checking: It may not be immediately obvious from the problem statement that a stable matching always exists or how we can find a stable matching, but it should be obvious. It suffices to consider each member of ne se, say the boy, as a potential member of blocking a pair. For each boy, only the girl that he prefers need to be checked. If some boy b and some girl g are partners in all stable matchings, then (b, g) is called a fixed pair.

                     for b := 1 to n do

                        for each w such that m prefers w to pM(b)do

                          if g prefers b to pM(g) then

                            begin

                                    report matching unstable:

                                    halt

                           end;

                 report matching stable