14.16 STRATEGY AND INFORMATION MEDIAN STABLE MATCHINGS Department of Economics, MIT Consider a one-to-one matching market, where M is the set of men and W is the set of women, and strict preferences for the men and women are given. Let µ and µ0 be any two stable matchings. Let µ ∨M µ0 be the function from M ∪ W to M ∪ W that assigns to each man m the more preferred of µ(m) and µ0 (m), and assigns to each woman w the less preferred of µ(w) and µ0 (w). Similarly, let µ ∧M µ0 be the function that assigns to each man m the less preferred of µ(m) and µ0 (m), and assigns to each woman w the more preferred of µ(w) and µ0 (w). We saw in the matching theory slides (Theorem 5) that µ ∨M µ0 and µ ∧M µ0 are again matchings, and moreover are stable. Now suppose we have any collection S = {µ1 , . . . , µk } of stable matchings. Define supM (S) to be the function from M ∪ W to M ∪ W that assigns to each man m the most preferred of µ1 (m), . . . , µk (m), and assigns to each woman w the least preferred of µ1 (w), . . . , µk (w). We can see that supM (S) = (· · · ((µ1 ∨M µ2 ) ∨M µ3 ) ∨M · · · ) ∨M µk and therefore, by the preceding result, supM (S) is again a stable matching. Similarly, we can define inf M (S) to be the function from M ∪ W to M ∪ W that assigns to each man m the least preferred of µ1 (m), . . . , µk (m), and assigns to each woman w the most preferred of µ1 (w), . . . , µk (w). Then inf M (S) is again a stable matching. This leads to the following result. The theorem is due to Teo and Sethuraman (1998), but our exposition follows the approach of Klaus and Klijn (2006). 1 Theorem 1. Let µ1 , . . . , µl be stable matchings, not necessarily distinct, and let k be any integer with 1 ≤ k ≤ l. Consider the function ν : M ∪ W → M ∪ W given as follows. For each man m, order the matches µ1 (m), . . . , µl (m) from most to least preferred (there may be some repetitions in this list); let ν(m) be the kth entry in this list. For each woman w, order the matches µ1 (w), . . . , µl (w) from most to least preferred, and let ν(w) be the (l − k + 1)th entry in this list. Then ν is also a stable matching. For a proof, note that µ1 := supM ({µ1 , . . . , µl }) has the desired property for k = 1, µ2 := supM ({µ1 , . . . , µl } \ {µ1 }) has the desired property for k = 2, and so on. If {µ1 , . . . , µl } is the set of stable matchings and l is odd, then applying the theorem for k = (l + 1)/2 we obtain the median matching, in which every agent is assigned to the median partner over all stable matchings. This formally expresses the idea that we can choose a stable matching that balances the interests of men and women. If l is even, then there are two “almost-median” stable matchings, given by k = l/2 and k = l/2 + 1. 2

Median Stable Matchings Notes

Related Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock