In class we talked about the bipartite graph auction procedure (BGAP) and how it can be used to find a set of market clearing prices – that is, a set of prices whereby a perfect matching of sellers to buyers exists. As discussed, the resulting preferred-seller graph given by the BGAP is socially optimal - it has the maximum total valuation of any assignment of sellers to buyers. However, we have also seen that the optimality of market-clearing prices does not guarantee that each buyer gets matched with his ‘favorite’ seller, i.e. the seller selling the good that the buyer values most highly. In fact, this is usually not the case. This begs the following question: is it possible that, given a preferred seller graph generated by the BGAP, there exists a buyer and seller who prefer to be matched with each other rather than the seller/buyer that they are currently matched with? A reasonable expectation in such a situation is for the given seller and buyer to abandon their current partners and trade with each other instead. It is interesting to explore the implications of such situations on the dynamics of the market, and how we can avoid these negative implications by searching for more ‘stable’ alternatives to the BGAP.

A stable matching, as defined on Wikipedia, is ‘a matching in which no element of the first matched set prefers an element of the second matched set that also prefers the first element.’ The problem of finding a stable matching in a bipartite matching problem is known as the Stable Marriage Problem (SMP). As discussed in this student’s blogpost, the existence and optimality of stable matchings in SMPs was proven back in 1962 by David Gale and Lloyd Shapley, a pair of American mathematicians and economists. They presented an algorithm to solve the SMP, which can be found at the above links.

It is perhaps relevant to relate Gale and Shapley’s findings to matching markets since they model the SMP in that both buyers and sellers have a preference list – in the case of buyers, in the order given by their valuations of each seller’s good, and for sellers, the order given by how much each buyer is willing to pay (their valuations) for their good.

As expected, Gale and Shapley’s findings have several implications on the stability of interactions in trading markets. The most direct implication is that stable matchings do exist in matching markets, and can be derived by applying the Gale-Shapley Algorithm or some variation thereof. This leads us to raise some further questions: How does a stable market differ from a market with non-stable matching in terms of market properties such as prices of goods, cash flow, and social welfare? Would a stable market be seller optimal or buyer optimal? Do all market clearing prices contain a perfect matching that is stable? If not, how can we modify the BGAP to derive a matching that is not only perfect but also stable? Also, how relevant is it to consider the stability of simplified market models (like the matching markets we discussed in class) and how can it be applied to real world markets? I plan to explore some of these questions and come up with some formalized models and examples in my final paper, so stay tuned for more!