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).     

Stable matchings and preferences of couples

Couples looking for jobs in the same labor market may cause instabilities. We determine a natural preference domain, the domain of weakly responsive preferences, that guarantees stability. Under a restricted unemployment aversion condition we show that this domain is maximal for the existence of stable matchings. We illustrate how small deviations from (weak) responsiveness, that model the wish of couples to be closer together, cause instability, even when we use a weaker stability notion that excludes myopic blocking. Our remaining results deal with various properties of the set of stable matchings for “responsive couples markets”, viz., optimality, filled positions, and manipulation.     

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.     

Two-sided matching with interdependent values

We introduce and study two-sided matching with incomplete information and interdependent valuations on one side of the market. An example of such a setting is a matching market between colleges and students in which colleges receive partially informative signals about students. Stability in such markets depends on the amount of information about matchings available to colleges. When colleges observe the entire matching, a stable matching mechanism does not generally exist. When colleges observe only their own matches, a stable mechanism exists if students have identical preferences over colleges, but may not exist if students have different preferences.     

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.     

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.     

On the Existence of Stable Roommate Matchings

This paper identifies a condition called “no odd rings” that is sufficient for the existence of stable roommate matchings in the weak preferences case. It shows that the process of allowing randomly chosen blocking pairs to match converges to a stable roommate matching with probability one as long as there are no odd rings. This random-paths-to-stability result generalizes that of Roth and Vande Vate (1990, Econometrica58, 1475–1480) and may not hold if there are odd rings. The “no odd rings” condition can also be used to prove a number of other sufficient conditions that are more economically interpretable. Journal of Economic Literature Classification Numbers: C78, D71.     

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).     

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     

TAXATION IN MATCHING MARKETS

We analyze the effects of taxation in two-sided matching markets where agents have heterogeneous preferences over potential partners. Our model provides a continuous link between models of matching with and without transfers. Taxes generate inefficiency on the allocative margin, by changing who matches with whom. This allocative inefficiency can be nonmonotonic, but is weakly increasing in the tax rate under linear taxation if each worker has negative nonpecuniary utility of working. We adapt existing econometric methods for markets without taxes to our setting, and estimate preferences in the college-coach football market. We show through simulations that standard methods inaccurately measure deadweight loss.     

Misrepresentation and stability in the marriage problem

It has been shown previously that, for two-sided discrete markets of the kind exemplified by the “marriage problem,” no strategy-proof procedure for aggregating preferences into stable outcomes exists. Here it is shown that (Nash) equilibrium misrepresentation of preferences nevertheless results in a stable outcome in terms of the true preferences when the aggregation procedure yields the optimal stable outcome in terms of the stated preferences for one side of the market.     

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.     

Group robust stability in matching markets

We introduce the notion of group robust stability which requires robustness against a combined manipulation, first misreporting preferences and then rematching, by any group of students in the school choice type of matching markets. Our first result shows that there is no group robustly stable mechanism even under acyclic priority structures. Next, we define a weak version of group robust stability, called weak group robust stability. Our main theorem, then, proves that there is a weakly group robustly stable mechanism if and only if the priority structure of schools is acyclic, and in that case, it coincides with the student-optimal stable mechanism.     

Corrigendum to “On randomized matching mechanisms” [Economic Theory 8(1996)377–381]

Ma (in Econ. Theory 8, 377–381, 1996) studied the random order mechanism, a matching mechanism suggested by Roth and Vande Vate (Econometrica 58, 1475–1480, 1990) for marriage markets. By means of an example he showed that the random order mechanism does not always reach all stable matchings. Although Ma's (1996) result is true, we show that the probability distribution he presented – and therefore the proof of his Claim 2 – is not correct. The mistake in the calculations by Ma (1996) is due to the fact that even though the example looks very symmetric, some of the calculations are not as “symmetric.” We thank two anonymous referees for their helpful comments. B. Klaus’s and F. Klijn’s research was supported by Ramón y Cajal contracts of the Spanish Ministerio de Ciencia y Tecnología. The work of the authors was also partially supported through the Spanish Plan Nacional I+D+I (BEC2002-02130 and SEJ2005-01690) and the Generalitat de Catalunya (SGR2005-00626 and the Barcelona Economics Program of CREA).     

Harmful signaling in matching markets

Several labor markets, including the job market for new Ph.D. economists, have recently developed formal signaling mechanisms. We show that such mechanisms are harmful for some environments. While signals transmit previously unavailable information, they also facilitate information asymmetry that leads to coordination failures. In particular, we consider a two-sided matching game of incomplete information between firms and workers. Each worker has either the same “typical” known preferences with probability close to one or “atypical” idiosyncratic preferences with the complementary probability close to zero. Firms have known preferences over workers. We show that under some technical condition if at least three firms are responsive to some workerʼs signal, the introduction of signaling strictly decreases the expected number of matches.     

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.     

Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness

Hedonic pricing with quasi-linear preferences is shown to be equivalent to stable matching with transferable utilities and a participation constraint, and to an optimal transportation (Monge–Kantorovich) linear programming problem. Optimal assignments in the latter correspond to stable matchings, and to hedonic equilibria. These assignments are shown to exist in great generality; their marginal indirect payoffs with respect to agent type are shown to be unique whenever direct payoffs vary smoothly with type. Under a generalized Spence-Mirrlees condition (also known as a twist condition) the assignments are shown to be unique and to be pure, meaning the matching is one-to-one outside a negligible set. For smooth problems set on compact, connected type spaces such as the circle, there is a topological obstruction to purity, but we give a weaker condition still guaranteeing uniqueness of the stable match.     

Incentives in decentralized random matching markets

Decentralized markets are modeled by means of a sequential game where, starting from any matching situation, firms are randomly given the opportunity to make job offers. In this random context, we prove the existence of ordinal subgame perfect equilibria where firms act according to a list of preferences. Moreover, every such equilibrium preserves stability for a particular profile of preferences. In particular, when firms best reply by acting truthfully, every equilibrium outcome is stable for the true preferences. Conversely, when the initial matching is the empty matching, every stable matching can be reached as the outcome of an ordinal equilibrium play of the game.