(6) Consider the following set of valuations that a set of buyers have for the items being offered by a set of sellers. Buyer Value a's item for Value b's item for Value c's item for X 10 2 1 y Z 12 11 10 11 1 10 (a) Describe what happens if we run the bipartite graph auction procedure from Chap- ter 10 to find market-clearing prices on the matching market defined by this given set of valuations, by saying what the prices are at the end of each round of the auction, including what the final market-clearing prices are when the auction comes to an end. You can either draw the preferred-seller graph from each round, or it is also fine to simply list the prices for each seller at the end of each round of the auction. (Note: If in any round you notice that there are multiple choices for the constricted set of buyers, then under the rules of the auction, you may choose any such constricted set.) (b) In Chapter 10, we evaluated matchings of buyers to sellers according to social welfare: the sum of buyers' valuations for what they get under the given matching. Note that this notion of social welfare applies independently of the prices that the sellers charge; it is determined by adding up the valuation of what the buyers get. (Recall that a price that a seller charges a buyer raises the seller's payoff by exactly the amount that it reduces a buyer's payoff; so prices don't have an effect on the total welfare of the whole system, since the gain to the seller cancels the loss to the buyers.) The perfect matching that maximizes the social welfare, over all possible perfect match- ings, is called welfare-maximizing. In Chapter 10 we saw that any perfect matching de- termined by a set of market-clearing prices must be welfare-maximizing. If you ran the procedure to construct market-clearing prices in part (a) correctly, you'll have discovered that the perfect matching M it finds which we know is welfare-maximizing consists of the pairs a-x, b-y, and c-z. It has social welfare 10+ 10+ 10 = 30, and no other perfect matching has higher social welfare. Note, however, that the sum of buyers' valuations is not the only quantity one might 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 they get in M. We could then seek a perfect matching M whose baseline is as large as possible, over all possible perfect matchings. We will call such a matching baseline-maximizing.