Paths to stability for matching markets with couples

We study two-sided matching markets with couples and show that for a natural preference domain for couples, the domain of weakly responsive preferences, stable outcomes can always be reached by means of decentralized decision making. Starting from an arbitrary matching, we construct a path of matchings obtained from ‘satisfying’ blocking coalitions that yields a stable matching. Hence, we establish a generalization of Roth and Vande Vate's [Roth, A.E., Vande Vate, J.H., 1990. Random paths to stability in two-sided matching. Econometrica 58, 1475–1480] result on path convergence to stability for decentralized singles markets.Furthermore, we show that when stable matchings exist, but preferences are not weakly responsive, for some initial matchings there may not exist any path obtained from ‘satisfying’ blocking coalitions that yields a stable matching.     

Corrigendum to “Stable matchings and preferences of couples” [J. Econ. Theory 121 (1) (2005) 75–106]

We correct an omission in the definition of the domain of weakly responsive preferences introduced in [B. Klaus, F. Klijn, Stable matchings and preferences of couples, J. Econ. Theory 121 (2005) 75–106] or KK05 for short. The proof of the existence of stable matchings [KK05, Theorem 3.3] and a maximal domain result [KK05, Theorem 3.5] are adjusted accordingly.     

Credible group stability in many-to-many matching problems

It is known that in two-sided many-to-many matching problems, pairwise-stable matchings may not be immune to group deviations, unlike in many-to-one matching problems (Blair, 1988). In this paper, we show that pairwise stability is equivalent to credible group stability when one side has responsive preferences and the other side has categorywise-responsive preferences. A credibly group-stable matching is immune to any “executable” group deviations with an appropriate definition of executability. Under the same preference restriction, we also show the equivalence between the set of pairwise-stable matchings and the set of matchings generated by coalition-proof Nash equilibria of an appropriately defined strategic-form game.     

Equilibria under deferred acceptance: Dropping strategies,filled positions,and welfare

We study many-to-one matching markets where hospitals have responsive preferences over students. We study the game induced by the student-optimal stable matching mechanism. We assume that students play their weakly dominant strategy of truth-telling.Roth and Sotomayor (1990) showed that equilibrium outcomes can be unstable. We prove that any stable matching is obtained in some equilibrium. We also show that the exhaustive class of dropping strategies does not necessarily generate the full set of equilibrium outcomes. Finally, we find that the ‘rural hospital theorem’ cannot be extended to the set of equilibrium outcomes and that welfare levels are in general unrelated to the set of stable matchings. Two important consequences are that, contrary to one-to-one matching markets, (a) filled positions depend on the equilibrium that is reached and (b) welfare levels are not bounded by the optimal stable matchings (with respect to the true preferences).     

Stochastic stability for roommate markets

We show that for any roommate market the set of stochastically stable matchings coincides with the set of absorbing matchings. This implies that whenever the core is non-empty (e.g., for marriage markets), a matching is in the core if and only if it is stochastically stable, i.e., stochastic stability is a characteristic of the core. Several solution concepts have been proposed to extend the core to all roommate markets (including those with an empty core). An important implication of our results is that the set of absorbing matchings is the only solution concept that is core consistent and shares the stochastic stability characteristic with the core.     

Absorbing sets in roommate problems

We analyze absorbing sets as a solution for roommate problems with strict preferences. This solution provides the set of stable matchings when it is non-empty and some matchings with interesting properties otherwise. In particular, all matchings in an absorbing set have the greatest number of agents with no incentive to change partners. These “satisfied” agents are paired in the same stable manner. In the case of multiple absorbing sets we find that any two such sets differ only in how satisfied agents are matched with each other.     

A class of multipartner matching markets with a strong lattice structure

Summary. For a two-sided multipartner matching model where agents are given by path-independent choice functions and no quota restrictions, Blair [7] had shown that stable matchings always exist and form a lattice. However, the lattice operations were not simple and not distributive. Recently Alkan [3] showed that if one introduces quotas together with a monotonicity condition then the set of stable matchings is a distributive lattice under a natural definition of supremum and infimum for matchings. In this study we show that the quota restriction can be removed and replaced by a more general condition named cardinal monotonicity and all the structural properties derived in [3] still hold. In particular, although there are no exogenous quotas in the model there is endogenously a sort of quota; more precisely, each agent has the same number of partners in every stable matching. Stable matchings also have the polarity property (supremum with respect to one side is identical to infimum with respect to the other side) and a property we call {\it complementarity}. Received: May 5, 2000; revised version: January 25, 2001     

Non-revelation mechanisms in many-to-one markets

In this study we present a simple mechanism in a many-to-one matching market where multiple costless applications are allowed. The mechanism is based on the principles of eligibility and priority and it implements the set of stable matchings in Subgame Perfect Nash Equilibrium. We extend the analysis to a symmetric mechanism where colleges and students interchange their roles. This mechanism also implements the set of stable matchings.     

“Timing Is Everything” and Marital Bliss

We first show that in a marriage market, when the stability of a matching is disturbed when a new agent joins the game, natural greedy behavior defines an equilibration procedure that converges to a stable matching for the extended problem. We then consider the iterative procedure under which agents join the game sequentially, and the natural greedy procedure is applied after the entrance of each agent. It is shown that this procedure converges to a stable matching for the original (global) problem and that for each agent, if the order of all other agents is given, he/she weakly improves his/her final outcome by deferring his/her arrival time. The agent that arrives last gets his/her optimal outcome under stable matchings. Journal of Economic Literature Classification Numbers: C78, C62.     

Weak stability and a bargaining set for the marriage model

In this note we introduce weak stability, a relaxation of the concept of stability for the marriage model by assuming that the agents are no longer myopic in choosing a blocking pair. The new concept is based on threats within blocking pairs: an individually rational matching is weakly stable if for every blocking pair one of the members can find a more attractive partner with whom he forms another blocking pair for the original matching. Our main result is that under the assumption of strict preferences, the set of weakly stable and weakly efficient matchings coincides with the bargaining set of Zhou (1994, Games Econ. Behav. 6, 512–526) for this context.     

Stable schedule matching under revealed preference

Baiou and Balinski (Math. Oper. Res., 27 (2002) 485) studied schedule matching where one determines the partnerships that form and how much time they spend together, under the assumption that each agent has a ranking on all potential partners. Here we study schedule matching under more general preferences that extend the substitutable preferences in Roth (Econometrica 52 (1984) 47) by an extension of the revealed preference approach in Alkan (Econom. Theory 19 (2002) 737). We give a generalization of the Gale-Shapley algorithm and show that some familiar properties of ordinary stable matchings continue to hold. Our main result is that, when preferences satisfy an additional property called size monotonicity, stable matchings are a lattice under the joint preferences of all agents on each side and have other interesting structural properties.     

Von Neumann-Morgenstern stable sets in matching problems

The following properties of the core of a one-to-one matching problem are well-known: (i) the core is non-empty; (ii) the core is a distributive lattice; and (iii) the set of unmatched agents is the same for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (Von Neumann-Morgenstern) stable sets in one-to-one matching problems. We show that a set V of matchings is a stable set of a one-to-one matching problem only if V is a maximal set satisfying the following properties: (a) the core is a subset of V; (b) V is a distributive lattice; and (c) the set of unmatched agents is the same for all matchings belonging to V. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b), and (c).     

For the Student: Matching and Economic Design

This article presents a brief survey of two‐sided matching. We introduce the reader to the problem of two‐sided matching in the context of the college admission model and explain two central requirements for a matching mechanism: stability and non‐manipulability. We show how the frequently used ‘Boston Mechanism’ fails these key requirements and describe how an alternative, the Deferred Acceptance Algorithm, leads to stable matchings but fails to be non‐manipulable in general. A third mechanism, the Top Trading Cycle, is efficient and non‐manipulable when only one side of the match acts strategically. We also discuss some applications of matching theory.     

Incentives in two-sided matching with random stable mechanisms

Summary This paper considers the incentives confronting agents who face the prospect of being matched by some sort of random stable mechanism, such as that discussed in Roth and Vande Vate (1990). A one period game is studied in which all stable matchings can be achieved as equilibria in a natural class of undominated strategies, and in which certain unstable matchings can also arise in this way. A multi-period extension of this game is then considered in which all subgame perfect equilibria must result in stable matchings. These results suggest avenues to explore markets in which matching is organized in a decentralized way.     

Matching with preferences over colleagues solves classical matching

In this note, we demonstrate that the problem of “many-to-one matching with (strict) preferences over colleagues” is actually more difficult than the classical many-to-one matching problem, “matching without preferences over colleagues.” We give an explicit reduction of any problem of the latter type to a problem of the former type. This construction leads to the first algorithm which finds all stable matchings in the setting of “matching without preferences over colleagues,” for any set of preferences. Our construction directly extends to generalized matching settings.     

“Fair marriages”: An impossibility

For marriage markets [Gale, D. and Shapley, L.S., 1962, College admissions and the stability of marriage, American Mathematical Monthly 69, 9–15.] so-called fair matchings do not always exist. We show that restoring fairness by using monetary transfers is not always possible: there are marriage markets where no amount of money can guarantee the existence of a fair allocation.     

Core many-to-one matchings by fixed-point methods

We characterize the core many-to-one matchings as fixed points of a map. Our characterization gives an algorithm for finding core allocations; the algorithm is efficient and simple to implement. Our characterization does not require substitutable preferences, so it is separate from the structure needed for the non-emptiness of the core. When preferences are substitutable, our characterization gives a simple proof of the lattice structure of core matchings, and it gives a method for computing the join and meet of two core matchings.     

On randomized matching mechanisms

Summary This note showed by means of Knuth's example that some stable matchings may not be obtained by the random order mechanism.I wish to thank an anonymous referee for helpful comments that have greatly improved the presentation of the paper.     

The communication requirements of social choice rules and supporting budget sets

The paper examines the communication requirements of social choice rules when the (sincere) agents privately know their preferences. It shows that for a large class of choice rules, any minimally informative way to verify that a given alternative is in the choice rule is by verifying a “budget equilibrium”, i.e., that the alternative is optimal to each agent within a “budget set” given to him. Therefore, any communication mechanism realizing the choice rule must find a supporting budget equilibrium. We characterize the class of choice rules that have this property. Furthermore, for any rule from the class, we characterize the minimally informative messages (budget equilibria) verifying it. This characterization is used to identify the amount of communication needed to realize a choice rule, measured with the number of transmitted bits or real variables. Applications include efficiency in convex economies, exact or approximate surplus maximization in combinatorial auctions, the core in indivisible-good economies, and stable many-to-one matchings.     

Measuring the instability in two-sided matching procedures

Summary Two-sided matching procedures are considered using the stable marriage model. There exist some matching procedures that, in spite of producing unstable matches, have nonetheless survived in practice; other such procedures have failed and been abandoned. The success or failure of these procedures may be linked to the amount of instability in the matchings they produce. We describe a way to measure the amount of instability likely to result from such algorithms, and use it to analyze the performance of a particular matching procedure much like those used by the United States Naval Academy and the National Football League. We also consider how favorable the matchings are likely to be from the standpoint of the agents, and examine how our results change when agents agree on some portion of their preference lists.The presentation of this material was improved considerably by comments from three anonymous reviewers. The author is especially grateful to one of the referees, who provided a wealth of valuable advice on motivating this work and relating it to other literature in the field. Another reviewer pointed out the related results proved by Pittel, and suggested improvements to the proof of Theorem 1. Peter Tinsley and Jeff Fuhrer read and offered helpful suggestions on various drafts of this paper.