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.     

On preferences over subsets and the lattice structure of stable matchings

This paper studies the structure of stable multipartner matchings in two-sided markets where choice functions are quotafilling in the sense that they satisfy the substitutability axiom and, in addition, fill a quota whenever possible. It is shown that (i) the set of stable matchings is a lattice under the common revealed preference orderings of all agents on the same side, (ii) the supremum (infimum) operation of the lattice for each side consists componentwise of the join (meet) operation in the revealed preference ordering of the agents on that side, and (iii) the lattice has the polarity, distributivity, complementariness and full-quota properties. Received: 5 March 1999 / Accepted: 12 May 2000     

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.     

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     

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     

A non-cooperative interpretation of bargaining sets

This paper provides a non-cooperative interpretation for bargaining sets concepts in economic environments. We investigate the implementability of the Aumann-Maschler and Mas-Colell bargaining sets, and provide mechanisms whose subgame perfect equilibrium outcomes realize these sets. These mechanisms, in contrast to general mechanisms suggested in the implementation literature, have a natural structure closely related to that of the rationale underlying the bargaining sets. Furthermore, the strategy sets consist mainly of allocations and coalitions (thus avoiding any reference to preference parameters) and are finite dimensional. Received: 17 February 1997 / Accepted: 2 February 1999     

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.     

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     

Natural and double implementation of public ownership solutions in differentiable production economies

This paper examines the implementation of two public ownership solutions in convex production economies with differentiable production functions. The two public ownership solutions we focus on are the proportional and equal benefit solutions. Two “natural” mechanisms which doubly implement the proportional and equal benefit solutions respectively in Nash and strong Nash equilibria are proposed without assuming free disposal. Received: 7 May 1996 / Accepted: 1 December 1998     

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     

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.     

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     

Single-peakedness and coalition-proofness

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

RJVs in product innovation and cartel stability

Abstract. We characterise the interplay between firms' decision in product development undertaken through a research joint venture (RJV), and the nature of their ensuing market behaviour. Participant firms in an RJV face a trade-off between saving the costs of product innovation by developing similar products to one another, e.g., by sharing most of the basic components of their products, and investing higher initial efforts in product innovation in order to develop more distinct products. We prove that the more the firms' products are distinct and thus less substitutable, the easier their collusion is to sustain in the marketing supergame, either in prices (Bertrand) or in quantities (Cournot). This gives rise to a non-monotone dependence of firms' product portfolio upon their intertemporal preferences. Received: 1 October 1998 / Accepted: 14 December 2002 We thank the seminar audience at Centre for Industrial Economics, University of Copenhagen, where all three authors were affiliated at the time we presented the first draft of this paper, and also the two anonymous referees for Review of Economic Design for their detailed comments. The usual disclaimer applies.     

Taxation in an economy with private provision of public goods

This paper analyses the effects of taxation and subsidies in an economy with private provision of a public good. It is shown that in a situation where all individuals contribute, taxation affects the equilibrium allocation if and only if at least one individual's voluntary contribution to the public good has an impact on the aggregate tax payments of the others. We then consider linear nonneutral tax-subsidy schemes and analyse efficiency and uniqueness of the resulting Nash equilibria. We show that an efficient Nash equilibrium, where all individuals contribute, will in general not be unique, and establish a non-uniformity property which a tax-subsidy scheme must fulfil in order to induce a unique interior equilibrium that is efficient. Throughout the paper it is assumed that individuals fully understand and take into account the government's budget constraint. Received: 3 November 1997 / Accepted: 23 March 1999     

Implementation with partial verification

This paper examines the implementability of social choice functions when only partial verification of private information is possible. Green and Laffont (1986) used this framework to derive a necessary and sufficient condition for the revelation principle to continue to hold with partial verification. We provide economically interesting characterizations of this condition, which suggest that it may be too restrictive. This leads us to consider implementation (not necessarily truthful) in general, when there is partial verification. We consider the case where compensatory transfers are allowed, giving the mechanism designer further leeway. We show how partial verification may allow efficient implementation of bilateral trade, where it would otherwise not be possible. Received: 1 August 1998 / Accepted: 5 September 2000     

Auctions with endogenous participation

We study endogenous-participation auctions where bidders only know the number of potential participants. After seeing their values for the object, potential participants decide whether or not to enter the auction. They may not want to enter the auction since they have to pay participation costs. We characterize equilibrium bidding strategies and entry decisions for both first- and second-price sealed-bid auctions when participation is endogenous. We show that there is a pure strategy entry equilibrium where only bidders with values greater than a certain cut-off point actually bid. In this context, both types of auctions generate the same expected revenue. We also show that, contrary to the predictions of the fixed number of bidders literature, the seller's expected revenue may decrease when the number of potential participants increases. In addition, we show that it is optimal for the seller to charge an entry fee, which contrasts with results from the existing literature on auctions with entry. As in the fixed-n literature, we show that first-price auctions generate more expected revenue than second-price auctions when buyers are risk-averse. Finally, we characterize the optimal auction – the auction that maximizes the seller's expected revenue – by using a direct revelation mechanism. The optimal auction involves a reserve price larger than the optimal reserve price in the fixed-n literature. The winner's payment is the second highest bid less the participation cost and losers receive a subsidy equal to the participation cost. Received: 17 August 1998 / 21 September 1999     

On durable goods monopolies and the Coase-Conjecture

Consider the durable goods monopoly game with uniformly distributed consumers' valuations. To establish the Coase-Conjecture in this context takes an infinite time horizon and a negligible delay between market rounds. An infinite time horizon or patience of market participants alone are not sufficient for the Coase-Conjecture, nor is an arbitrarily small delay between price offers within a finite time horizon. Received: 20 March 1996 / Accepted: 15 December 1997     

Network formation with sequential demands

This paper introduces a non-cooperative game-theoretic model of sequential network formation, in which players propose links and demand payoffs. Payoff division is therefore endogenous. We show that if the value of networks satisfies size monotonicity, then each and every equilibrium network is efficient. The result holds not only when players make absolute participation demands, but also when they are allowed to make link-specific demands.