Two-Sided Markets: More Practice
Prepared by:
Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
The tables below give strict preferences (without ties) for five men and five women.
1st | 2nd | 3rd | 4th | 5th | |
m1 | w2 | w3 | w1 | w5 | w4 |
m2 | w2 | w1 | w3 | w5 | w4 |
m3 | w2 | w1 | w3 | w5 | w4 |
m4 | w5 | w3 | w4 | w2 | w1 |
m5 | w3 | w4 | w5 | w1 | w2 |
1st |
2nd | 3rd | 4th | 5th | |
w1 | m2 | m1 | m3 | m5 | m4 |
w2 | m2 | m5 | m1 | m5 | m4 |
w3 | m5 | m1 | m3 | m2 | m4 |
w4 | m4 | m1 | m5 | m2 | m3 |
w5 | m2 | m4 | m5 | m1 | m3 |
1. Is the following pairing a stable marriage? m1 and w1; m2 and w2; m3 and w4; m4 and w5; m5 and w3? If not list a blocking pair for this marriage assignment.
2. Is the following pairing a stable marriage? m1 and w2; m2 and w1; m3 and w5; m4 and w4; m5 and w3? If not list a blocking pair for this marriage assignment.
3. Find the male optimal stable marriage using the Gale-Shapley Deferred Acceptance Algorithm.
4. Find the female optimal stable marriage using the Gale-Shapley Deferred Acceptance Algorithm.
5. If the male optimal and female optimal stable matchings are not the same, can you find another stable marriage different from these two?
6. Apply the breakmarriage procedure using m2 starting with the male-optimal stable marriage. Does a new stable marriage occur?
7. Apply the breakmarriage procedure using m4 starting with the male-optimal stable marriage. Does a new stable marriage occur?
8. Apply the breakmarriage procedure using w1 starting with the female-optimal stable marriage. Does a new stable marriage occur?
Definition:
A matching is a way of pairing the men with the women, one man with one women. When there are n men and n women, n pairs result in the matching. A matching M has a blocking pair for M if m and w are not paired in M, and m prefers w to the women he is paired with in M and w prefers m to the man she is paired with in M. If a matching has no blocking pair it is called stable. A matching for which there is at least one blocking pair is called unstable. If there is a blocking pair, the intuition is that the couple involved will find a way to break the ties to their assigned mates to form a pair perhaps resulting in a cascading pattern of changes. The Gale/Shapley deferred acceptance algorithm guarantees at least one stable marriage.
Breakmarriage involves starting with a stable marriage (which we know exists) picking a man (or a woman) and having this man propose to the next lower woman (man) on his (her) list by preference, and otherwise following the Gale/Shapley Algorithm.