چه ثبات قیمتی؟ رفاه اجتماعی در تطبیق بازار

In two-sided matching markets, stability can be costly. We define social welfare functions for matching markets and use them to formulate a definition of the price of stability. We then show that it is common to find a price tag attached to stability, and that the price of stability can be substantial. Therefore, when choosing a matching mechanism, a social planner would be well advised to weigh the price of stability against the value of stability, which varies from market to market.

We treat formally two issues that have been dealt with in an ad hoc manner in the marriage matching literature: the price of stability and welfare comparisons of matchings. In the theory and practice of marriage matching, stability has traditionally been considered a vital requirement. By definition, every unstable matching contains at least one blocking pair, a man and a woman who prefer each other to their assigned mates. The presence of such pairs can be problematic since individuals then have the incentive to leave their assigned partners to be with each other. But in some scenarios stability is not vital; for example, a strong central authority can prevent renegotiation, that is, can prevent blocking pairs from abandoning their assigned mates to form new marriages, and can thereby prevent unstable matchings from falling apart after partners are assigned. A school district, for example, with a strong central administration, could potentially forbid schools from altering their enrollments once matchings have been made by the mechanism of choice. In fact, it is important to recognize that two-sided matching markets were originally centralized not to prevent matchings from falling apart after assignments have been made, but rather to prevent backward unraveling, that is, to prevent individuals from trying to form partnerships earlier and earlier, before adequate time is allowed to ascertain partners’ post-match potential. The requirement of stability, however, is neither necessary nor sufficient to prevent backward unraveling. Unstable matchings can survive over time and successfully limit backward unraveling ( Unver, 2001 and Unver, 2005), while stable mechanisms on their own do not guarantee that backward unraveling will not occur ( Halaburda, 2010). If participants are made aware that they would expect to do better under a mechanism that does not guarantee stability than under any stable matching, they might be willing and able to commit as a group to not seek alternative partners before or after the unstable matching is assigned. Alternatively, even when participants are not aware that they could expect to do better under a mechanism that does not guarantee stability, they may be extremely unhappy about the results of a stable matching mechanism.1 And even when forced or committed non-renegotiation cannot be attained, it may be so difficult for blocking pairs to find each other that match breaking is unlikely to start and once started is likely to stall. In cases such as these, where stability is not vital, it is useful to weigh the price of stability against the value of stability. Finally, even when stability is considered necessary, curiosity alone motivates an investigation of the price of stability. This paper is not the first to question the priority of stability over other welfare criteria in matching markets. Axtell and Kimbrough (2008), for example, compare the man-optimal stable matching mechanism introduced by Gale and Shapley (1962) with a decentralized algorithm that terminates in unstable matchings and show that the unstable mechanism outperforms significantly in terms of agents’ average rank of partner. Anshelevich et al., 2009 and Anshelevich et al., 2013 similarly point out that stability can come at a substantial cost in utilitarian terms, and investigate the potential size of such costs both theoretically and with simulation experiments for various distributions of agents’ utility functions. And in a companion paper (Boudreau and Knoblauch, 2013) we also study tradeoffs in utilitarian terms,2 also both theoretically and with simulation experiments, though in that paper we focus on how the price of stability changes with ordinal categorizations of agents’ preferences. Clearly, however, traditional utilitarianism is just one notion of welfare. This brings us to our second issue. In order to present a formal, more general definition of the price of stability, we need a general method for assigning values to matchings. Many studies assign values to matchings, but this has always been done in an ad hoc manner. We provide a formal foundation for assigning values to matchings by adapting the concept of a social welfare function for use in the marriage matching arena. As a brief and informal preview of our two key definitions, a social welfare function (SWF) assigns a non-negative real number to every ordered pair consisting of a matching and a preference profile. For a market of size nn with preference profile PnPn, the price of stability associated with an SWF ff is the ratio of the maximum value of ff over all matchings to the maximum value of ff over all stable matchings. Then we will say there is a price tag attached to stability for a market of size nn if that ratio is greater than one for some PnPn. When defined as above, an SWF can vary not only with the outcome of some process–in our case the outcome is a matching–but also with a feature of the market, the preference profile. This makes it possible for the values we place on matchings to depend, in a variety of ways, on the levels of satisfaction of the participants. In the next section, Section 2, we define SWFs over marriage matchings, provide several families of SWFs motivated by previous literature, and argue that SWFs in general are legitimate tools for the study of marriage matching. In Section 3 we define the price of stability for marriage matching and show that for most of our examples of SWFs there is a price tag attached to stability. We show that for at least two of our examples, when markets are large, a randomly chosen preference profile will almost certainly show that the SWF in question comes with a price tag attached to stability. We also demonstrate that the price of stability for four of our examples is substantial. Section 4 concludes with a discussion of how simulation can provide information about the price of stability for many scenarios that are intractable via theory.

Our first theorem demonstrates that requiring matchings to be stable can lead to potential welfare sacrifices for a wide array of SWFs, while Theorem 3 demonstrates that those sacrifices can be substantial. Theorem 2 shows that, for two of our examples of SWFs, there is a price tag attached to stability for nearly all preference profiles, and for many SWFs the expected price of stability is greater than one. In real-life markets, a social planner or mechanism designer might want a combination of Theorems 2 and 3-type information; that is, she might want to know the price of stability defined as an average over a category of preference profiles rather than a maximum over all preference profiles. For example, the social planner might know the approximate level of correlation (the extent to which the preferences are similar) on each side of the market, and/or the approximate level of intercorrelation (the extent to which men prefer women who prefer them) and wish to know the expected-magnitude price of stability. In a companion study (Boudreau and Knoblauch, 2013) we use another tool to address such questions—simulation. The simulation approach involves three steps: the generation of preference profiles, the construction of matchings by the mechanisms to be tested and the evaluation of the social welfare function for each matching. The process is repeated many times to yield an approximation of the expected level of social welfare provided by each mechanism. The social planner then has all the information needed (including the price of stability) to choose a matching mechanism. The advantage of the theoretical approach used in this study is that theory is more rigorous and more transparent. On the other hand the advantage of the simulation approach is that it works for any category of preference profiles and any matching mechanism. A further consideration for social planners or market designers when considering the price of stability, in addition to the restriction of certain types of preference profiles, might be the restriction of some types of matchings. In matching markets where agents are not required to list all potential partners as acceptable, for example, stability also requires individual rationality. Further restrictions on which matchings are permissible would likely alter the existence and prevalence of welfare tradeoffs for many cases of SWFs, and we leave a more in-depth consideration that of topic for future work.