Agreement toward stability in matching markets

For firms with responsive preferences, we prove that the set of stable matchings unanimously preferred by workers to any firm quasi-stable matching has a lattice structure. This follows from a generalization of the Decomposition Lemma. The result does not hold when firms have q-substitutable preferences. Nevertheless, we show that the set of stable matchings unanimously preferred by workers to a firm quasi-stable matching contains an element which is unanimously least preferred by workers, and most preferred by firms. When a firm quasi-stable matching is fed into our extension of the Deferred Acceptance algorithm (where firms propose), the existence of this matching guarantees the success of the algorithm.     

Partnership-enhancement and stability in matching problems

In two-sided matching problems, we consider “natural” changes in preferences of agents in which only the rankings of current partners are enhanced. We introduce two desirable properties of matching rules under such rank-enhancements of partners. One property requires that an agent who becomes higher ranked by the original partner should not be punished. We show that this property cannot always be met if the matchings are required to be stable. However, if only one agent changes his preferences, the above requirement is compatible with stability, and moreover, envy-minimization in stable matchings can also be attained. The other property is a solidarity property, requiring that all of the “irrelevant” agents, whose preferences as well as whose original partners’ preferences are unchanged, should be affected in the same way; either all weakly better off or all worse off. We show that when matchings are required to be stable, this property does not always hold.     

A bargaining set for roommate problems

Since stable matchings may not exist, we propose a weaker notion of stability based on the credibility of blocking pairs. We adopt the weak stability notion of Klijn and Massó (2003) for the marriage problem and we extend it to the roommate problem. We first show that although stable matchings may not exist, a weakly stable matching always exists in a roommate problem. Then, we adopt a solution concept based on the credibility of the deviations for the roommate problem: the bargaining set. We show that weak stability is not sufficient for a matching to be in the bargaining set. We generalize the coincidence result for marriage problems of Klijn and Massó (2003) between the bargaining set and the set of weakly stable and weakly efficient matchings to roommate problems. Finally, we prove that the bargaining set for roommate problems is always non-empty by making use of the coincidence result.     

Stable many-to-many matchings with contracts

We consider several notions of setwise stability for many-to-many matching markets with contracts and provide an analysis of the relations between the resulting sets of stable allocations for general, substitutable, and strongly substitutable preferences. Apart from obtaining “set inclusion results” on all three domains, we introduce weak setwise stability as a new stability concept and prove that for substitutable preferences the set of pairwise stable matchings is nonempty and coincides with the set of weakly setwise stable matchings. For strongly substitutable preferences the set of pairwise stable matchings coincides with the set of setwise stable matchings.     

The Blocking Lemma for a many-to-one matching model

The Blocking Lemma identifies a particular blocking pair for each non-stable and individually rational matching that is preferred by some agents of one side of the market to their optimal stable matching. Its interest lies in the fact that it has been an instrumental result to prove key results on matching. For instance, the fact that in the college admissions problem the workers-optimal stable mechanism is group strategy-proof for the workers and the strong stability theorem in the marriage model follow directly from the Blocking Lemma. However, it is known that the Blocking Lemma and its consequences do not hold in the general many-to-one matching model in which firms have substitutable preference relations. We show that the Blocking Lemma holds for the many-to-one matching model in which firms’ preference relations are, in addition to substitutable, quota q-separable. We also show that the Blocking Lemma holds on a subset of substitutable preference profiles if and only if the workers-optimal stable mechanism is group strategy-proof for the workers on this subset of profiles.     

Stable sets in matching problems with coalitional sovereignty and path dominance

We study von Neumann Morgenstern stable sets for one-to-one matching problems under the assumption of coalitional sovereignty (C), meaning that a deviating coalition of players does not have the power to arrange the matches of agents outside the coalition. We study both the case of pairwise and coalitional deviations. We argue further that dominance has to be replaced by path dominance (P) along the lines of van Deemen (1991) and Page and Wooders (2009). This results in the pairwise CP vNM set in the case of pairwise deviations and the CP vNM set in the case of coalitional deviations. We obtain a unique prediction for both types of stable sets: the set of matchings that belong to the core.     

School choice: Nash implementation of stable matchings through rank-priority mechanisms

We consider school choice problems (Abdulkadiroğlu and Sönmez, 2003) where students are assigned to public schools through a centralized assignment mechanism. We study the family of so-called rank-priority mechanisms, each of which is induced by an order of rank-priority pairs. Following the corresponding order of pairs, at each step a rank-priority mechanism considers a rank-priority pair and matches an available student to an unfilled school if the student and the school rank and prioritize each other in accordance with the rank-priority pair. The Boston or immediate acceptance mechanism is a particular rank-priority mechanism. Our first main result is a characterization of the subfamily of rank-priority mechanisms that Nash implement the set of stable matchings (Theorem 1). Our second main result is a strong impossibility result: under incomplete information, no rank-priority mechanism implements the set of stable matchings (Theorem 2).     

Stable matchings and the small core in Nash equilibrium in the college admissions problem

Both rematching proof and strong equilibrium outcomes are stable with respect to the true preferences in the marriage problem. We show that not all rematching proof or strong equilibrium outcomes are stable in the college admissions problem. But we show that both rematching proof and strong equilibrium outcomes in truncations at the match point are all stable in the college admissions problem. Further, all true stable matchings can be achieved in both rematching proof and strong equilibrium in truncations at the match point. We show that any Nash equilibrium in truncations admits one and only one matching, stable or not. Therefore, the core at a Nash equilibrium in truncations must be small. But examples exist such that the set of stable matchings with respect to a Nash equilibrium may contain more than one matching. Nevertheless, each Nash equilibrium can only admit at most one true stable matching. If, indeed, there is a true stable matching at a Nash equilibrium, then the only possible equilibrium outcome will be the true stable matching, no matter how different are players' equilibrium strategies from the true preferences and how many other unstable matchings are there at that Nash equilibrium. Thus, we show that a necessary and sufficient condition for the stable matching rule to be implemented in a subset of Nash equilibria by the direct revelation game induced by a stable mechanism is that every Nash equilibrium profile in that subset admits one and only one true stable matching. Received: 30 December 1998 / Accepted: 12 October 2001 This paper is a revision of the paper “Manipulation and Stability in a College Admissions Problem” circulated since 1994. I thank Rich McLean, Abraham Neyman, Mark Satterthwaite, Sang-Chul Suh, and Tetsuji Yamada for helpful discussions. I thank the associate editor and the two anonymous referees for their helpful comments that have greatly improved the paper. I am grateful to the Kellogg G.S.M. at the Northwestern University for the hospitality for my visit. Any errors are mine.     

A one-sided many-to-many matching problem

This study discusses a one-sided many-to-many matching model wherein agents may not be divided into two disjoint sets. Moreover, each agent is allowed to have multiple partnerships in our model. We restrict our attention to the case where the preference of each agent is single-peaked over: (i) the total number of partnerships with all other agents, and (ii) the number of partnerships that the agent has with each of the other agents. We represent a matching as a multigraph, and characterize a matching that is stable and constrained efficient. Finally, we show that any direct mechanism for selecting a stable and constrained efficient matching is not strategy-proof.     

When do stable roommate matchings exist? A review

We compare different preference restrictions that ensure the existence of a stable roommate matching. Some of these restrictions are generalized to allow for indifferences as well as incomplete preference lists, in the sense that an agent may prefer remaining single to matching with some agents. We also introduce a new type of cycles and in greater detail investigate the domain of preferences that have no such cycles. In particular, we show how the absence of these cycles relates to the “symmetric utilities hypothesis” by Rodrigues-Neto (J Econ Theory 135:545–550, 2007) when applied to roommate problems with weak preferences.     

Wealth effects of time variation in investor risk preferences

We investigate the source of risk premiums: individual risk preferences. By examining the wealth characteristics of agents of different risk preferences, we study the financial incentive of investors to demonstrate different risk preferences. To accomplish this, we model the stock market utilizing artificial adaptive agents. If investors have incentive to vary their risk preferences, or if investors of a constant risk preference vary the way they participate in the market under different market conditions, this could lead to time variation in market risk premiums. We find that agents have significant incentive to demonstrate different risk preferences under different market conditions.(JEl G12)     

The substitutes condition and the lattice structure of the set of stable allocations

In the many-to-one matching model with contracts, I show that there is no restriction on preferences weaker than substitutable preferences which guarantees that the set of stable allocations is a lattice. Thus, when contracts are not substitutes, removing agents from the economy may decrease the payoffs to existing agents on both sides of the market.     

Coalition-enhancing fiscal policies in an open economy: A CES framework of Gale’s transfer paradox

The motivation of our paper comes from David Gale’s seminal work in 1974. He constructed an example of the “transfer paradox” based on three Leontief functions. The transfer paradox is that when there is a set of agents in the home country and that the home country is trading with other countries, then certain public lump-sum tax transfer plans could make all agents in the home country better off. Our contributions are as follows. First, we show that such an example can be constructed with three smooth CES utility functions. Second, we establish the three crucial conditions for the existence of the transfer paradox: (1) the donor (a taxpayer) has stronger preference for the foreign good than the recipient; (2) the donor is ex-ante wealthier than the recipient; (3) the elasticity of substitution of the foreign country’s preference is strictly less than one.     

Implementation of stable solutions in a restricted matching market

I analyze the admission mechanism used in Spanish universities. The system is open to strategic manipulation. This is because students are not allowed to express the whole list of available options. However, the mechanism implements the set of stable matchings in Nash equilibrium and the student's optimum in strong equilibrium. The mechanism also implements the students' optimum, in Nash equilibrium, under the class of “non-reverse” preferences. All these properties come from the fact that colleges do not have the opportunity to misrepresent their preferences. Received: 30 June 1995 / Accepted: 31 January 1997     

Closure and preferences

We investigate the results of Kreps (1979), dropping his completeness axiom. As an added generalization, we work on arbitrary lattices, rather than a lattice of sets. We show that one of the properties of Kreps is intimately tied with representation via a closure operator. That is, a preference satisfies Kreps’ axiom (and a few other mild conditions) if and only if there is a closure operator on the lattice, such that preferences over elements of the lattice coincide with dominance of their closures. We tie the work to recent literature by Richter and Rubinstein (2015).     

Gross substitutability of point-to-set correspondences

In this paper the notion of gross substitutability for the multi-valued case is studied. It is proved that, if in a pure exchange equilibrium model gross substitutability and some auxiliary conditions prevail, then (a) the set of equilibria is a Cartesian product of a convex set of equilibrium resource allocations and a convex cone of equilibrium prices; hence all equilibria are equiadvantageous for every trader; (b) the weak axiom of revealed preference holds in any equilibrium; (c) any equilibrium is stable with respect to reallocations of initial resources. Some situations in which Walras' law does not hold are considered as well.     

A note on strategy-proofness from the doctor side in matching with contracts

In a general one-to-many matching model with contracts, Hatfield and Milgrom (Ame Econ Rev 95:913–935, 2005) show that the doctor optimal stable rule is strategy-proof from the doctor side. We strengthen their result by showing that this rule is in fact the unique stable rule that is strategy-proof from the doctor side.     

Testable implications of general equilibrium models: An integer programming approach

Focusing on the testable revealed preference restrictions on the equilibrium manifold, we show that the rationalizability problem is NP-complete. Subsequently, we present a mixed integer programming (MIP) approach to characterize the testable implications of general equilibrium models. Attractively, this MIP approach naturally applies to settings with any number of observations and any number of agents. This is in contrast with existing approaches in the literature. We also demonstrate the versatility of our MIP approach in terms of dealing with alternative types of assignable information. Finally, we illustrate our methodology on a data set drawn from the US economy. In this application, an important focus is on the discriminatory power of the rationalizability tests under study.     

Marsaglia’s lattice test and non-linear congruential pseudo random number generators

Sequences of integers defined by a non-linear recursive congruential pseudo random number generator with prime modulusp and maximal period length are divided into vectors ofd consecutive numbers. The lattice spanned by these vectors is studied. i.e. the minimal lattice which contains all these vectors. It is shown that this lattice coincides with the full integer lattice, at least ford=2 andd=3, i.e. non-linear generators pass Marsaglia’s lattice test at least ford ⩽ 3. For a special class of non-linear generators introduced in Eichenauer and Lehn (1986) it is proved that these generators pass the test even for dimensionsd ⩽ (p − 1)/2. Supported by Deutsche Forschungsgemeinschaft.     

Modeling collective adaptive agent design and its analysis in Barnga game

This paper explores the collective adaptive agent that adapts to a group in contrast with the individual adaptive agent that adapts to a single user. For this purpose, this paper starts by defining the collective adaptive situation through an analysis of the subject experiments in the playing card game, Barnga, and investigates the factors that lead the group to the collective adaptive situation. Intensive simulations using Barnga agents have revealed the following implications: (1) the leader who takes account of other players’ opinions contributes to guide players to the collective adaptation situation, and (2) an appropriate role balance among players (i.e., the leader, the claiming and quiet players, which make the most and least number of corrections of the leader’s decision) is required to derive the collective adaptive situation.