Strategy-proofness in many-to-one matching problems

We search forstrategy-proof solutions in the context of (many-to-one) matching problems (Gale and Shapley, 1962). In this model, whenever the firms can hire as many workers as they want (the capacities are unlimited) the stable set is a singleton. There exists aPareto efficient, individually rational, andstrategy-proof matching rule if and only if the capacities are unlimited. Furthermore, whenever the capacities unlimited, the matching rule which selects the unique stable matching is the only matching rule that isPareto efficient, individually rational, andstrategy-proof.     

Buyers' and sellers' cartels on markets with indivisible goods

This paper analyzes the formation of cartels of buyers and sellers in a simple model of trade inspired by Rubinstein and Wolinsky's (1990) bargaining model. When cartels are formed only on one side of the market, there is at most one stable cartel size. When cartels are formed sequentially on the two sides of the market, there is also at most one stable cartel configuration. Under bilateral collusion, buyers and sellers form cartels of equal sizes, and the cartels formed are smaller than under unilateral collusion. Both the buyers' and sellers' cartels choose to exclude only one trader from the market. This result suggests that there are limits to bilateral collusion, and that the threat of collusion on one side of the market does not lead to increased collusion on the other side.     

Uniform allocation and reallocation revisited

Thomson (1995a) proved that the uniform allocation rule is the only allocation rule for allocation economies with single-peaked preferences that satisfies Pareto efficiency, no-envy,one-sided population-monotonicity, and replication-invariance on a restricted domain of single-peaked preferences. We prove that this result also holds on the unrestricted domain of single-peaked preferences. Next, replacing one-sided population-monotonicity by one-sided replacement-domination yields another characterization of the uniform allocation rule, Thomson (1997a). We show how this result can be extended to the more general framework of reallocation economies with individual endowments and single-peaked preferences. Following Thomson (1995b) we present allocation and reallocation economies in a unified framework of open economies. Received: 20 February 1999 / Accepted: 15 February 2000     

Strategy-proof allocation when preferences are single-plateaued

Abstract. We consider private good economies with single-plateaued preferences. A solution selects for each preference profile a non-empty set of allocations. An agent strictly prefers a set of allocations to another set of allocations if and only if he strictly prefers any allocation in the first set to any in the second set according to his single-plateaued preference relation. We characterize the class of sequential-allotment solutions by essentially single-valuedness, Pareto-indifference, and coalitional stragety-proofness. These solutions are the Pareto-indifferent extensions of the solutions studied by Barberà et al. 1997. Received: 9 May 2000 / Accepted: 1 May 2001     

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.     

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.     

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.     

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.     

A study of proportionality and robustness in economies with a commonly owned technology

Abstract. Studying one-input one-output economies, we say that an allocation is proportional if the input-output ratio is identical among agents and if each agent maximizes her welfare given this ratio. We propose three equity axioms based on this definition, and we use them to compare the main solutions to this simple equity problem. We also combine efficiency, robustness axioms and our proportionality axioms to characterize two solutions. Received: 11 June 1997 / Accepted: 26 May 2000     

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 characterization and an impossibility of finite length anonymity for infinite generations

In the context of ranking infinite utility streams, the impartiality axiom of finite length anonymity requires the equal ranking of any two utility streams that are equal up to a finite length permutation ( Fleurbaey and Michel, 2003). We first characterize any finite length permutation as a composition of a fixed step permutation and an “almost” fixed step permutation. We then show that if a binary relation satisfies finite length anonymity, then it violates all the distributional axioms that are based on a segment-wise comparison. Examples of those axioms include the weak Pareto principle and the weak Pigou-Dalton principle.     

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.     

Strategyproof multiple assignment using quotas

The allocation of heterogeneous and indivisible objects is considered where there is no medium of exchange. We characterize the set of strategyproof, nonbossy, Pareto-optimal, and neutral social choice functions when preferences are monotonic and quantity-monotonic. The characterized sets of social choice functions are sequential; agents are assigned their favorite objects among the objects not given to others before them, subject to a quota. Received: 5 January 1999 / Accepted: 14 June 1999     

Proportionally adjusted marginal pricing method to share joint costs

We consider the cost sharing problem with divisible demands of heterogeneous goods. We propose a cost sharing method called Proportionally Adjusted Marginal Pricing (PAMP) method. PAMP is a nonadditive (in the cost function) extension of average cost pricing. We introduce an axiom called Local Independence (LI) and use LI together with Continuity, Proportionality, and Scale Invariance to characterize PAMP. Received: 23 March 2001 / Accepted: 16 November 2001 I thank Yves Sprumont, Hervé Moulin, and Ahmet Alkan for discussions, comments and suggestions. Thanks also go to the associate editor and the referees, whose comments and suggestions greatly improve the paper.     

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     

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     

Capabilities and utilities

This paper deals with the problem of looking for resource allocation mechanisms which would be accepted as just in Sen's capabilities framework. We start by suggesting a way of simplifying Sen's idea of capability by using acapability index which measures the ability of a person to function. Then we look for mechanisms providing allocations which could be deemedjust, in pure distribution problems. An allocation will be called just when its corresponding capabilities are leximin suprema. We provide a characterization result of this mechanism in a framework which mimics Roemer's bargaining in economic environments, in which the role of utility functions is now played by capability indices. When a positive relationship between capability indices and utilities exist, just allocations are optimal in utility terms.     

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.