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

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.     

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.     

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.     

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.     

Substitutes and stability for matching with contracts

We consider the matching with contracts framework of Hatfield and Milgrom [20], and we introduce new concepts of bilateral and unilateral substitutes. We show that the bilateral substitutes condition is a sufficient condition for the existence of a stable allocation in this framework. However, the set of stable allocations does not form a lattice under this condition, and there does not necessarily exist a doctor-optimal stable allocation. Under a slightly stronger condition, unilateral substitutes, the set of stable allocations still does not necessarily form a lattice with respect to doctors' preferences, but there does exist a doctor-optimal stable allocation, and other key results such as incentive compatibility and the rural hospitals theorem are recovered.     

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.     

Price Volatility and Risk Exposure: On the Interaction of Quota and Product Markets

We consider an industry with firms that produce a final good emitting pollution to different degree as a side effect. Pollution is regulated by a tradable quota system where some quotas may have been allocated at the outset, i.e. before the quota market is opened. We study how volatility in quota price affects firm behaviour, taking into account the impact of quota price on final-good price. The impact on the individual firm differs depending on how polluting it is??whether it is ??clean?? or ??dirty????and whether it has been allocated quotas at the outset. In the absence of long-term or forward contracting, a grandfathering regime??where clean firms are allocated no quotas and dirty firms are allocated quotas for a part of their emissions??minimizes the impact on firm behavior relative to a risk-neutral benchmark.With forward contracts and in the absence of wealth effects initial quota allocation has no effect on firm behaviour. Allowing for abatement does not change the qualitative nature of our results.     

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.     

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.     

Endogenous Choice of Trade Instrument Under Uncertainty *

This Paper endogenizes the choice between import tariffs and quotas of two policy active countries in a duopsonistic world market. Without uncertainty, import quotas are welfare superior to import tariffs in equilibrium. If two importers can precommit to a type of instrument before deciding the level of the instrument to use in a future period, an import quota equilibrium emerges. We introduce asymmetric risk in the import demand schedule of the two importers. There exists a range of parameters in which a mixed equilibrium emerges, i.e. one country uses a tariff while the other restricts trade with an import quota. The likelihood that both importers choose a different trade instrument in equilibrium is increasing with the correlation coefficient of the two random shocks. [F13]     

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

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.     

Timing and Commitment of Environmental Policy,Adoption of New Technology,and Repercussions on R&;D

We investigate the interplay between environmental policy, incentives to adoptnew technology, and repercussions on R&D. We study a model where a monopolistic upstream firm engages in R&D and sells advanced abatement technology to polluting downstream firms. We consider four different timing and commitment regimes of environmental tax and permit policies: ex post taxation (or issuing permits), interim commitment to a tax rate (a quota of permits) after observing R&D success but before adoption, and finally two types of ex antecommitment before R&D activity, one with a unique tax rate (quota of permits), the other one with a menu of tax rates (permit quotas). We study the second best tax and permit policies and rank these with respect to welfare. In particular, we find that commitment to a menu of tax rate dominates all other policy regimes.     

Climate Policy under Technology Spillovers

We study climate policy when there are technology spillovers between countries, as there is no instrument that (directly) corrects for these externalities. Without an international climate agreement, the (non-cooperative) equilibrium depends on whether countries use tradable quotas or carbon taxes as their environmental policy instruments. All countries are better-off in the tax case than in the quota case. Two types of international climate agreements are then studied: One is a Kyoto type of agreement where each country is assigned a specific number of internationally tradable quotas. In the second type of agreement, a common carbon tax is used domestically in all countries. None of the cases satisfy the conditions for the social optimum. Even if the quota price is equal to the Pigovian level, R&D investments will be lower than what is socially optimal in the quota case. It is also argued that the quota agreement gives higher R&D expenditures and more abatement than the tax agreement.     

The Nonequivalence of Import and Export Quotas in Strategic Equilibrium

The authors use a standard general‐equilibrium trade model to show that export and import policies are not symmetric in the equilibrium of a strategic game with quotas. It is assumed that N (identical) large countries, without cooperation, set their import (or export) quotas to maximize domestic welfare. It is shown that the equilibrium in which all countries use import quotas differs from, and is superior to, the equilibrium in which countries use export quotas. The difference arises because the elasticity of the residual foreign export supply schedule differs between the two equilibria. The authors also study the properties of the sequential equilibrium of the game. In a simultaneous‐move game, each country is indifferent as to whether it uses an import or export quota, given the policy of the other country. However, in a sequential‐move game, the first mover will prefer to use an import quota rather than an export quota.     

Market structure and matching with contracts

Ostrovsky (2008) [9] develops a theory of stability for a model of matching in exogenously given networks. For this model a generalization of pairwise stability, chain stability, can always be satisfied as long as agents' preferences satisfy same side substitutability and cross side complementarity. Given this preference domain I analyze the interplay between properties of the network structure and (cooperative) solution concepts. The main structural condition is an acyclicity notion that rules out the implementation of trading cycles. It is shown that this condition and the restriction that no pair of agents can sign more than one contract with each other are jointly necessary and sufficient for (i) the equivalence of group and chain stability, (ii) the core stability of chain stable networks, (iii) the efficiency of chain stable networks, (iv) the existence of a group stable network, and (v) the existence of an efficient and individually stable network. These equivalences also provide a rationale for chain stability in the unrestricted model. The (more restrictive) conditions under which chain stability coincides with the core are also characterized.     

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.     

Tariffs Versus Quotas in a Differentiated Products Market: A Conjectural Variations in Prices Approach

This paper examines the (non)equivalence of a tariff and a quota set at the level of imports generated by the tariff using a conjectural variations in prices model. It extends previous studies by considering a variety of firm behavior patterns in the tariff equilibrium and when the imports and the domestic products are complements. The results obtained encompass most of the previous results. In addition, for complements, replacing a tariff with a quota has opposite effects on the prices of two products. Also, the prices under tariffs and quotas are not necessarily equivalent for complements. [F13]     

When is fish quota enforcement worth while? A study of the Northeast Arctic cod

Many fish stocks are controlled by fish quotas divided among individual firms. Such quota regimes need an enforcement mechanism in order to be effective. Whether or not quota management regimes are worth while depends on whether the rents generated by such regimes cover their costs. Cost-efficient quota regimes would attain an optimal deterrence through minimal control and high fines, but in practice there are likely to be socially determined limits on how high fines could be set. We analyze these questions for the Northeast Arctic cod stock, using data on enforcement of Norwegian fish quotas.