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.     

Exchange-proofness or divorce-proofness? Stability in one-sided matching markets

Two stability concepts for one-sided matching markets are analyzed: Gale-Shapley stability and ξ-stability. The first one applies best to markets where no status quo allocation is considered, whereas the second one is a solution to be used when property rights are allowed. A common problem of existence is shared by both solution concepts. Hence, we study economic environments where this problem does not exist, and present a family of agents’ preferences for which existence is guaranteed for both Gale-Shapley stable and ξ-stable outcomes. This work was finished while the author was visiting Duke University, whose hospitality is gratefully acknowledged. Swveral discussions with Salvador Barberà, Hervé Moulin and Marilda Sotomayor and some advice by an anonymous referee were specially useful. This work is partially supported by Grants PB 92-0590 and PB 93-0938 from the DGICYT, the Spanish Ministery of Educación Ciencia, and the Institut Valencià d’Investigacions Econòmiques.     

Implementation in generalized matching problems

We search for (Nash) implementable solutions on a class of one-to-one matching problems which includes both the housing market (Shapley and Scarf, Journal of Mathematical Economics, 1974, 1, 23–28) and marriage problems (Gale and Shapley, American Mathematical Monthly, 1962, 69, 9–15). We show that the core correspondence is implementable. We show, furthermore, that any solution that is Pareto efficient, individually rational, and implementable is a supersolution of the core correspondence. That is, the core correspondence is the minimal solution that is Pareto efficient, individually rational, and implementable. A corollary of independent interest in the context of the housing market is that the core correspondence is the only single-valued solution that is Pareto efficient, individually rational, and implementable.     

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     

Dynamics,stability, and foresight in the Shapley–Scarf housing market

While most of the literature starting with Shapley and Scarf (1974) have considered a static exchange economy with indivisibilities, this paper studies the dynamics of such an economy. We find that both the dynamics generated by competitive equilibrium and the one generated by the weak dominance relation, converge to a set of allocations we define as strictly stable, which we can show to exist. Moreover, we show that even when only pairwise exchanges between two traders are allowed, the strictly stable allocations are attained eventually if traders are sufficiently farsighted.     

Fairness and implementability in allocation of indivisible objects with monetary compensations

This paper introduces a general framework for the fair allocation of indivisible objects when each agent can consume at most one (e.g., houses, jobs, queuing positions) and monetary compensations are possible. This framework enables us to deal with identical objects and monotonicity of preferences in ranking objects. We show that the no-envy solution is the only solution satisfying equal treatment of equals, Maskin monotonicity, and a mild continuity property. The same axiomatization holds if the continuity property is replaced by a neutrality property.     

On top responsiveness and strict core stability

Alcalde and Revilla [Journal of Mathematical Economics 40 (2004) 869–887] introduce a top responsiveness condition on players’ preferences in hedonic games and show that it guarantees the existence of a core stable partition. In the present note we strengthen this observation by proving that under top responsiveness even the strict core is non-empty.     

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.     

Bilateral matching with Latin squares

We develop a general procedure to construct pairwise meeting processes characterized by two features. First, in each period the process maximizes the number of matches in the population. Second, over time agents meet everybody else exactly once. We call this type of meetings “absolute strangers.” Our methodological contribution to economics is to offer a simple procedure to construct a type of decentralized trading environments usually employed in both theoretical and experimental economics. In particular, we demonstrate how to make use of the mathematics of Latin squares to enrich the modeling of matching economies.     

Achieving the first best in sequencing problems

Abstract. In a sequencing problem with linear time cost, Suijs (1996) proved that it is possible to achieve first best. By first best we mean that one can find mechanisms that satisfy efficiency of decision, dominant strategy incentive compatibility and budget balancedness. In this paper we show that among a more general and natural class of sequencing problems, sequencing problems with linear cost is the only class for which first best can be achieved. Received: 2 December 1999/Accepted: 9 May 2001     

Reduction-consistency in collective choice problems

We consider the problem of choosing a subset of a feasible set over which each agent has a strict preference. We propose an invariance property, reduction-consistency, of choice rules and study its implications. The property is a natural expression for the problems of a general principle of consistency having been studied extensively in resource allocation problems. We show that no scoring rule satisfies reduction-consistency, and base a characterization of the top rule on the property. We also investigate the minimal extension of a rule needed to recover reduction-consistency, and identify the minimal extensions of several rules including the Borda and plurality rules.     

A social choice function implementable via backward induction with values in the ultimate uncovered set

We prove the existence of a social choice function implementable via backward induction which always selects within the ultimate uncovered set. Whereas the uncovered set is the set of maximal elements of the covering relation, the ultimate uncovered set is the set obtained by iterative application of this covering operation. Dutta and Sen (1993) showed that any social choice function which is the solution of a generalized binary voting procedure is implementable via backward induction. Our result follows from Dutta and Sen's theorem, in that we construct a binary voting procedure always selecting within the ultimate uncovered set. We use the classical multistage elimination procedure, which always selects an alternative within the uncovered set. When this procedure is also used to select among all of the possible agendas or orderings of alternatives within the procedure, the alternative selected (from the agenda selected) will be within the uncovered set of the uncovered set. Our result follows from repeated application of this construction. Intuitively, the procedure constructed consists of requiring agents to vote on how they should vote and so on. Received: 7 April 1997 / Accepted: 15 October 1998     

A note on the multiple partners assignment game

In the assignment game of Shapley and Shubik [Shapley, L.S., Shubik, M., 1972. The assignment game. I. The core, International Journal of Game Theory 1, 11–130] agents are allowed to form one partnership at most. That paper proves that, in the context of firms and workers, given two stable payoffs for the firms there is a stable payoff which gives each firm the larger of the two amounts and also one which gives each of them the smaller amount. Analogous result applies to the workers. Sotomayor [Sotomayor, M., 1992. The multiple partners game. In: Majumdar, M. (Ed.), Dynamics and Equilibrium: Essays in Honor to D. Gale. Mcmillian, pp. 322–336] extends this analysis to the case where both types of agents may form more than one partnership and an agent's payoff is multi-dimensional. Instead, this note concentrates in the total payoff of the agents. It is then proved the rather unexpected result that again the maximum of any pair of stable payoffs for the firms is stable but the minimum need not be, even if we restrict the multiplicity of partnerships to one of the sides.     

Erratum to “Do pure indivisibilities prevent core equivalence? Core equivalence theorem in an atomless economy with purely indivisible commodities only” [J. Math. Econ. 41 (4–5) (2005) 571–601]

We consider a pure exchange economy with a continuum of agents and finitely many indivisible commodities. Every commodity can be consumed only in integer amounts. Thus, agents’ preferences are locally satiated and no commodity bundle has necessarily local cheaper points. We introduce a core which is an intermediate concept between the strong core and the weak core. In our economy, this core is the most natural concept in the sense that it coincides with the set of all exactly feasible Walras allocations.     

Defining efficient policies in a general equilibrium model: a multi-objective approach

Macroeconomic policy makers are typically concerned with several indicators of economic performance. We thus propose to tackle the design of macroeconomic policy using Multicriteria Decision Making (MCDM) techniques. More specifically, we employ Multi-objective Programming (MP) to seek so-called efficient policies. The MP approach is combined with a computable general equilibrium (CGE) model. We chose use of a CGE model since it has the dual advantage of being consistent with standard economic theory while allowing one to measure the effect(s) of a specific policy with real data. Applying the proposed methodology to Spain (via the 1995 Social Accounting Matrix) we first quantified the trade-offs between two specific policy objectives: growth and inflation, when designing fiscal policy. We then constructed a frontier of efficient policies involving real growth and inflation. In doing so, we found that policy in 1995 Spain displayed some degree of inefficiency with respect to these two policy objectives. We then offer two sets of policy recommendations that, ostensibly, could have helped Spain at the time. The first deals with efficiency independent of the importance given to both growth and inflation by policy makers (we label this set: general policy recommendations). A second set depends on which policy objective is seen as more important by policy makers: increasing growth or controlling inflation (we label this one: objective-specific recommendations).     

Multiplicity of mixed equilibria in mechanisms: A unified approach to exact and approximate implementation

We characterize full implementation of social choice sets in mixed-strategy Bayesian equilibrium. Our results concern both exact and virtual mixed implementation. For exact implementation, we identify a strengthening of Bayesian monotonicity, which we refer to as mixed Bayesian monotonicity. It is shown that, in economic environments with at least three agents, mixed Bayesian implementation is equivalent to mixed Bayesian monotonicity, incentive compatibility and closure. For implementing a social choice function, the case of two-agents is also covered by these conditions and mixed Bayesian monotonicity reduces to Bayesian monotonicity. Following parallel steps, mixed virtual implementation is shown to be equivalent to mixed virtual monotonicity, incentive compatibility and closure. The key condition, mixed virtual monotonicity, is argued to be very weak. In particular, it is weaker than Abreu–Matsushima’s measurability, thereby implying that: (1) virtual implementation in mixed Bayesian equilibrium is more permissive than virtual implementation in iteratively undominated strategies, and (2) non-regular mechanisms are essential for the implementation of rules in that gap.     

The foundation of stability in extensive games with perfect information

This paper studies the decision-theoretic foundation for the notion of stability in the dynamic context of strategic interaction. We formulate and show that common knowledge of rationality implies a “stable” pattern of behavior in extensive games with perfect information. In the “generic” case, our approach is consistent with Aumann’s [Aumann, R.J., 1995. Backward induction and common knowledge of rationality. Games and Economic Behavior 8, 6–19] result that common knowledge of rationality leads to the backward induction outcome.     

The Walras core of an economy and its limit theorem

The Walras core of an economy is the set of allocations that are attainable for the consumers when their trades are constrained to be based on some agreed price system, such that no alternative price system exists for any sub-coalition that allows all members to trade to something better. As compared with the Edgeworth core, both coalitional improvements and being a candidate allocation for the Walras core become harder. The Walras core may even contain allocations that violate the usual Pareto efficiency. Nevertheless, the competitive allocations are the same under the two theories, and the equal-treatment Walras core allocations converge under general conditions to the competitive allocations in the process of replication.     

Implementation of voting operators

We show that a theory of implementation can be developed in the Aizerman–Aleskerov framework, capturing the main ideas regarding Nash implementation in the Arrovian case. In fact we obtain the counterparts of the results of [Maskin, E., 1977. Nash Equilibrium and Welfare Optimality. MIT, Mimeo] and [Moore, J., Repullo, R., 1990. Nash implementation. A full characterization. Econometrica 58, 1038–1100] in the new framework.