In Chapter 10, we discussed the notion of social-welfare maximization for matching markets:…
In Chapter 10, we discussed the notion of social-welfare maximization for matching markets: finding a matching M that maximizes the sum of buyers’ valuations for what they get, over all possible perfect matchings. We say such a matching is socialwelfare maximizing. However, the sum of buyers’ valuations is not the only quantity one may want to maximize; another natural goal might be to make sure that no individual buyer gets a valuation that is too small.
With this in mind, let’s define the baseline of a perfect matching M to be the minimum valuation that any buyer has for the item she gets in M. We could then seek a perfect matching M whose baseline is as large as possible, over all possible perfect matchings. We say such a matching is baseline-maximizing.
For example, in the following set of valuations,
the matching M consisting of the pairs a-x, b-y, and c-z has a baseline of 8 (this is the valuation of z for what she gets, which is lower than the valuations of x and y for what they get), while the matching M consisting of the pairs b-x, c-y, and a-z has a baseline of 7. In fact the first of these example matchings, M, is baseline-maximizing for this sample set of valuations.
Now, finding a perfect matching that is baseline-maximizing is grounded in a kind of “egalitarian” motivation – no one should be left too badly off. This may sometimes be at odds with the goal of social-welfare maximization. We now explore this tension further.
(a) Give an example of equal-sized sets of sellers and buyers, with valuations on the buyers, so that there is no perfect matching that is both socialwelfare maximizing and baseline-maximizing. (In other words, in your example, social-welfare maximization and baseline maximization should only occur with different matchings.)
(b) It is also natural to ask whether a baseline-maximizing matching can always be supported by market-clearing prices. Here is a precise way to ask the question.
For any equal-sized sets of sellers and buyers, with valuations on the buyers, is there always a set of market-clearing prices so that the resulting preferred-seller graph contains a baseline-maximizing perfect matching M?
Give a yes/no answer to this question, together with a justification of your answer. (If you answer “yes,” you should explain why there must always exist such a set of market-clearing prices; if you answer “no,” you should explain why there can be examples in which a baseline-maximizing matching cannot be found in the preferred-seller graph resulting from market-clearing prices.)