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

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.