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

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.     

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.     

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.     

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.     

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.     

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.     

Group size paradox and public goods

In an economy with voluntarily provided public goods and private product varieties, and a general class of CES preferences, it is shown that aggregate public good contribution follows an inverted-U pattern with respect to group size when private and public goods are substitutable in preferences. With complementarity, however, aggregate provision grows monotonically with group size.     

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.     

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.     

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.     

On the existence of a strictly strong Nash equilibrium under the student-optimal deferred acceptance algorithm

This study analyzes a preference revelation game in the student-optimal deferred acceptance algorithm in a college admission problem. We assume that each college's true preferences are known publicly, and analyze the strategic behavior of students. We demonstrate the existence of a strictly strong Nash equilibrium in the preference revelation game through a simple algorithm that finds it. Specifically, (i) the equilibrium outcome from our algorithm is the same matching as in the efficiency-adjusted deferred acceptance algorithm and (ii) in a one-to-one matching market, it coincides with the student-optimal von Neumann–Morgenstern (vNM) stable matching. We also show that (i) when a strict core allocation in a housing market derived from a college admission market exists, it can be supported by a strictly strong Nash equilibrium, and (ii) there exists a strictly strong Nash equilibrium under the college-optimal deferred acceptance algorithm if and only if the student-optimal stable matching is Pareto-efficient for students.     

Underestimation of probabilities modifications: characterization and economic implications

The aim of this paper is to propose a behavioral characterization of individuals who underestimate probabilities modifications and to characterize this behavior in the standard preferences representation models under risk (expected utility, dual theory, rank dependent utility theory and MaxMin expected utility). Our main results are the following. Underreaction to probabilities modifications is in general independent from standard risk aversion and prudence. In models involving probabilities transformation functions, it is characterized by the slope of the probability transformation function. In the MaxMin expected utility model under risk, it is related to the weights of the maximal and minimal consequences in the preferences representation function. Considering a simple prevention decision, consisting in the reduction in the probability of a monetary loss, we show that individuals who underreact to probabilities modifications, invest less in prevention than individuals who objectively evaluate these modifications. Underreaction to probabilities modification is thus a possible explanation for low investment in prevention.     

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.     

Social Preferences, Skill Segregation, and Wage Dynamics

We study the earning structure and the equilibrium assignment of workers to firms in a model in which workers have social preferences, and skills are perfectly substitutable in production. Firms offer long-term contracts, and we allow for frictions in the labour market in the form of mobility costs. The model delivers specific predictions about the nature of worker flows, about the characteristics of workplace skill segregation, and about wage dispersion both within and across firms. We show that long-term contracts in the presence of social preferences associate within-firm wage dispersion with novel "internal labour market" features such as gradual promotions, productivity-unrelated wage increases, and downward wage flexibility. These three dynamic features lead to productivity-unrelated wage volatility within firms.     

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 governments and the semistrict core

We consider the class of proper monotonic simple games and study coalition formation when an exogenous weight vector and a solution concept are combined to guide the distribution of power within winning coalitions. These distributions induce players' preferences over coalitions in a hedonic game. We formalize the notion of semistrict core stability, which is stronger than the standard core concept but weaker than the strict core notion and derive two characterization results for the semistrict core, depending on conditions we impose on the solution concept. A bounded power condition, which connects exogenous weights and the solution, turns out to be crucial. It generalizes a condition termed “absence of the paradox of smaller coalitions” that was previously used to derive core existence results.     

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

The structure of strategy-proof social choice — Part I: General characterization and possibility results on median spaces

We define a general notion of single-peaked preferences based on abstract betweenness relations. Special cases are the classical example of single-peaked preferences on a line, the separable preferences on the hypercube, the “multi-dimensionally single-peaked” preferences on the product of lines, but also the unrestricted preference domain. Generalizing and unifying the existing literature, we show that a social choice function is strategy-proof on a sufficiently rich domain of generalized single-peaked preferences if and only if it takes the form of voting by issues (“voting by committees”) satisfying a simple condition called the “Intersection Property.”Based on the Intersection Property, we show that the class of preference domains associated with “median spaces” gives rise to the strongest possibility results; in particular, we show that the existence of strategy-proof social choice rules that are non-dictatorial and neutral requires an underlying median space. A space is a median space if, for every triple of elements, there is a fourth element that is between each pair of the triple; numerous examples are given (some well-known, some novel), and the structure of median spaces and the associated preference domains is analysed.     

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