Two-Sided Markets: Practice (2018)

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. Men ranking women first, and women ranking men second.

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

w1 m2 m1 m3 m5 m4
w2 m2 m5 m1 m3 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.

References:

Gusfield, D., and R. Irving, The Stable Marriage Problem, MIT Press, Cambridge, 1989.

Roth, A., and M. Sotomayor, Two-Sided Matching, Cambridge U. Press, New York, 1990.