Problem Set 4: Two-Sided Markets

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 m1 m3 m5 m4 w3 m5 m1 m3 m2 m4 w4 m4 m1 m5 m2 m3 w5 m4 m2 m5 m1 m3

1. Is the following pairing a stable marriage? m1 and w1; m2 and w2; m3 and w4; m4 and w4; m5 and w5? 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. How many different ways are there for the 5 men to fill out the first table above?

7. How many different ways are there for the 5 women to fill out the second table above?

8. How many different ways are for the 5 men and women to fill out the two tables above?

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.