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.     

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.     

Implementation of the recursive core for partition function form games

In partition function form games, the recursive core (r-core) is implemented by a modified version of Perry and Reny’s [Perry, M., Reny, P., 1994. A non-cooperative view of coalition formation and the core. Econometrica 62, 795-817] non-cooperative game. Specifically, every stationary subgame perfect Nash equilibrium (SSPNE) outcome is an r-core outcome. With the additional assumption of total r-balancedness, every r-core outcome is an SSPNE outcome.     

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.     

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.     

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.     

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.     

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.     

A mechanism implementing the proportional solution

We consider the problem of a commonly owned technology which transforms a single input into a single output. We are interested in implementing a social choice rule called theproportional solution. We introduce a mechanism which implements the proportional solution in Nash, strong (Nash) and undominated Nash equilibria. In the mechanism each agent announces only two numbers which can be interpreted as the total output and her share of the total input-output combination. This paper was originally titled "Doubly implementing the proportional solution." I would like to thank my advisor William Thomson for his detailed comments and suggestions. I would also like to thank Jeffrey Banks and Sung-Whee Shin for their comments. Two anonymous referees and an editor’s comments improved this paper substantially.     

Single-peakedness and coalition-proofness

We prove that multidimensional generalized median voter schemes are coalition-proof. Received: 16 July 1998 / Accepted 23 March 1999     

Public good provision and the Smith Process

An existing public good provision mechanism known as the Smith Process (SP) is extended to allow for non-zero fixed cost, non-constant marginal cost and imperfectly divisible output. Two versions of SP are considered: unrestricted (USP) and restricted with a unanimity rule (RSPU). USP implements efficient choice provided the gap between marginal and average cost is sufficiently low. RSPU relaxes the conditions for efficient implementation but increases the set of equilibria involving inefficient choice. Furthermore, if weakly dominated strategies are eliminated, then non-provision is no longer an equilibrium under RSPU but continues to be one under USP.     

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.     

Multi-agent bilateral bargaining and the Nash bargaining solution

This paper studies a bargaining model where n   players negotiate how to share a pie through (n−1)$(n-1)$ bilateral bargaining sessions. In each session, two players bargain for a partial agreement that specifies who exits and who moves on to the next session (if there is any) via the alternating-proposal framework of Rubinstein [Rubinstein, A., 1982. Perfect equilibrium in a bargaining model. Econometrica 50, 97–109]. We consider two bargaining procedures under which the subgame perfect equilibrium outcomes converge to the Nash [Nash, J., 1950. The bargaining problem. Econometrica 18, 155–162] bargaining solution for the corresponding bargaining problem as the players’ discount factor goes to one. Hence, the model studied here provides a non-cooperative foundation for the Nash cooperative bargaining solution in the multilateral case.     

Stable and efficient bargaining networks

Abstract. We examine a bargaining game among players connected by a network, where successively potential partners negotiate over terms of a project. For any network structure and ordering of selection of bargaining partners, there is a unique subgame perfect equilibrium outcome which coincides with the standard Rubinstein split. Based on this, we derive expected payoffs for players as a function of the network. We the characterize the pairwise stable and efficient bargaining networks. These two sets do not always coincide and in many situations pairwise stable networks are over-connected. Received: 10 April 2001 / Accepted: 17 January 2002 I am indebted to Matthew Jackson for suggesting this paper. I also thank Bernard Caillaud, Sanjeev Goyal, and the seminar participants at Universidad de Alicante, Universidad Carlos III de Madrid, CEMFI (Madrid), Universitat Autònoma de Barcelona, Erasmus University of Rotterdam, Universitat Pompeu Fabra (Barcelona) and CERAS (Paris) for helpful comments. This paper was written while at Universitat Pompeu Fabra and CERAS. Financial support from the Spanish Ministry of Education through research grant DGESIC PB96-0302, and from the Ecole Nationale des Ponts et Chaussées, Paris is gratefully acknowledged. All errors are of course mine.     

The not-so-secret-agent: Professional monitors,hierarchies and implementation

Abstract. It is well-known that, when agents in an organization possess private information that is unverifiable by an outside party, games where agents simply announce their information can have multiple equilibria that may impede the successful implementation of the organization's objectives. We show that the introduction of a professional monitor (e.g. auditor, regulator, supervisor) can help to destroy the “bad' equilibria when agents have private information but have incomplete info rmation about others' information. Received: 21 May 1998 / Accepted: 26 May 2000     

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     

The hybrid equilibria and core selection in exchange economies with externalities

This paper introduces a hybrid equilibrium concept that combines the elements of cooperative and non-cooperative behaviors in an exchange economy with externalities. For a fixed coalition structure (or a partition of traders), the hybrid equilibrium is a price and consumption bundle such that each coalition chooses a core solution from its budget set and the consumption bundles are feasible. It becomes the competitive equilibrium when the position is the finest, and it selects a core allocation when the partition is the coarsest. The paper provides sufficient conditions for the existence of a hybrid equilibrium for any coalition structure.     

A noncooperative approach to the Mas-Colell bargaining set

We propose an extensive form game to give a noncooperative interpretation of the Mas-Colell bargaining set for transferable utility games. Based on the objection and counterobjection in the sense of the Mas-Colell bargaining set, a bilateral negotiation is designed in our model. We show that the equilibrium outcomes of our extensive form game coincide with the Mas-Colell bargaining set in the supperadditive environments.     

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