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.     

Restricted houseswapping games

Restricted houseswapping games (RHGs) are a generalization of ‘one-sided matching games’, in which we specify a class II* of ‘allowable’ simple trading cycles. The cores of such games may be empty. Given II*, all possible closed RHGs have non-empty cores of II* is ‘strongly balanced’. Examples include the one-sided matching markets (^{Shapley and Scarf. Journal of Mathematical Economics 1974. 1. 23–37}. ^{Tijs et al., OR Spektrum 1984, 6, 119–123}; ^{Quinzii, International Journal of Game Theory 1984, 13, 41–60}) and the two-sided matching markets (^{Gale and Shapley. American Mathematical Monthly 1962. 69, 9–16}; ^{Shapley and Shubik, International Journal of Game Theory 1972, 1, 111–130}: and ^{Demange and Gale Econometrica 1985, 53, 873–888}).We then consider the subclass of RHGs in which there is no transferable resource. In this case, a weaker condition on II*, called ‘weak balancedness’, is sufficient to guarantee core non-emptiness. In addition, if II* is not weakly balanced, then there exists a preference profile such that the strict core of the resultant game is empty.Several other examples are given of II* that are (a) strongly balanced: (b) weakly balanced but not strongly balanced: and (c) not even weakly balanced.Finally, we discuss the issues of equilibrium definition, existence, and core-equilibrium allocation equivalence in RHGs.     

Virtual Nash implementation with admissible support

A social choice correspondence (SCC) is virtually implementable if it is ?$?$-close (in the probability simplex) to some (exactly) implementable correspondence [Abreu, D., Sen, A., 1991. Virtual Implementation in Nash Equilibrium. Econometrica 59, 997–1021] proved that, without restriction on the set of alternatives receiving strictly positive probability at equilibrium, every SCC is virtually implementable in Nash Equilibrium. We study virtual implementation when the supports of equilibrium lotteries are restricted. We provide a necessary and sufficient condition, imposing joint restrictions on SCCs and admissible supports. Next, we discuss how to construct supports, and we underline an important difficulty. Finally, we study virtual implementation when the support is restricted to the efficient or individually rational alternatives.     

The coordinate-wise core for multiple-type housing markets is second-best incentive compatible

We consider the generalization of Shapley and Scarf’s (1974) [Shapley, L., Scarf’s, H., 1974. On cores and indivisibility. Journal of Mathematical Economics 1, 23–37.] model of trading indivisible objects (houses) to so-called multiple-type housing markets. We show that the prominent solution for these markets, the coordinate-wise core rule, is second-best incentive compatible.     

A topological invariant for competitive markets

This paper summarizes the concepts of global cones and limited arbitrage introduced in Chichilnisky (Economic Theory, 1995, 5, 79–108), and the corresponding results establishing that limited arbitrage is necessary and sufficient for the existence of a competitive equilibrium and for the compactness of Pareto frontier (announced in Chichilnisky (American Economic Review, 1992, 84, 427–434, and Chichilnisky (Bulletin of the American Mathematical Society, 1993, 29, 189–207). Using the same global cones I extend my earlier results to encompass ‘mixed economies’ based on Chichilnisky (CORE Discussion Paper No. 9527, 1995). I introduce a topological invariant for competitive markets which deepens the concept of limited arbitrage. This invariant encodes exact information on the equilibria and on the social diversity of the economy and all its subeconomies, and predicts a failure of effective demand.     

Generic properties of the core and equilibria of pure exchange economies

We show that for an open dense set of markets with a continuum of traders the number of equilibrium allocations [which by the celebrated theorem of ^{Aumann (Econometrica. 1964, 32. 39–50)} coincide with the core allocations for such markets are finite. This presents a limiting case result that complements similar asymptotic theorems for cores of large economies proved by ^{Bewley (Econometrica 1973, 41, 425–454)}, and ^{Dierker (Journal of Mathematical Economics 1975, 2. 155–169)}. If we require that the measure on the space of agents be one with a finite number of atoms of equal weight, our reasoning recovers the classical results obtained by ^{Debreu (Econometrica. 1970. 38, 387–392)} for economies with a finite number of agents.     

Arbitrage, equilibrium, and gains from trade: A counterexample

We present a counterexample to a theorem due to Chichilnisky (Bulletin of the American Mathematical Society, 1993, 29, 189–207; American Economic Review, 1994, 84, 427–434). Chichilnisky's theorem states that her condition of limited arbitrage is necessary and sufficient for the existence of an equilibrium in an economy with unbounded short sales. Our counterexample shows that the condition defined by Chichilnisky is not sufficient for existence of equilibrium. We also discuss difficulties in Chichilnisky (Economic Theory, 1995, 5, 79–107).     

Preference revelation games and strong cores of allocation problems with indivisibilities

This note considers the equilibrium outcomes of the preference revelation games in the general model of indivisible good allocation introduced by [Sönmez, T., 1999. Strategy-proofness and essentially single-valued cores. Econometrica 67, 677–689]. We adopt the concepts of coalitional equilibria and cores which are both defined in terms of the weak deviation or blocking by a prescribed class of admissible coalitions. We prove that if the solution which induces preference revelation games is individually rational and Pareto optimal and the class of admissible coalitions is “monotonic,” then the set of coalitional equilibrium outcomes coincides with the core. And we point out that the preceding analysis in the context of marriage problems [Gale, D., Shapley, L., 1962. College admissions and the stability of marriage. American Mathematical Monthly 69, 9–15] is hardly extended to the general model.     

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.     

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.     

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.     

Efficiency and truthfulness with Leontief preferences. A note on two-agent,two-good economies

In exchange economies where agents have private information about their preferences, strategy-proof and individually rational social choice functions are in general not efficient. We provide a restricted domain, namely the set of preferences representable by Leontief utility functions, where there exist mechanisms which are strategy-proof, efficient and individually rational. In two-agent, two-good economies we are able to provide an even stronger result. We characterize the class of efficient and individually rational social choice functions, which are fully implementable in truthful strategies.Received: 28 April 2003, Accepted: 23 June 2003, JEL Classification: D51, D71The author thanks Matthew Jackson, Jordi Massó and James Schummer for fruitful discussions, William Thomson for many valuable comments on an earlier version. A particular thank to Salvador Barberá for his fundamental help.     

No unbounded arbitrage,weak no market arbitrage and no arbitrage price system conditions; Equivalent conditions

Page and Wooders [Page Jr., F.H., Wooders, M., 1996. A necessary and sufficient condition for compactness of individually rational and feasible outcomes and existence of an equilibrium. Economics Letters 52, 153–162] prove that the no unbounded arbitrage (NUBA), a special case of a condition in Page [Page, F.H., 1987. On equilibrium in Hart’s securities exchange model. Journal of Economic Theory 41, 392–404], is equivalent to the existence of a no arbitrage price system (NAPS) when no agent has non-null useless vectors. Allouch et al. [Allouch, N., Le Van, C., Page F.H., 2002. The geometry of arbitrage and the existence of competitive equilibrium. Journal of Mathematical Economics 38, 373–391] extend the NAPS introduced by Werner [Werner, J., 1987. Arbitrage and the existence of competitive equilibrium. Econometrica 55, 1403–1418] and show that this condition is equivalent to the weak no market arbitrage (WNMA) of Hart [Hart, O., 1974. On the existence of an equilibrium in a securities model. Journal of Economic Theory 9, 293–311]. They mention that this result implies the one given by Page and Wooders [Page Jr., F.H., Wooders, M., 1996. A necessary and sufficient condition for compactness of individually rational and feasible outcomes and existence of an equilibrium. Economics Letters 52, 153–162]. In this note, we show that all these conditions are equivalent.     

Nash bargaining in ordinal environments

We analyze the implications of Nash’s (Econometrica 18:155–162, 1950) axioms in ordinal bargaining environments; there, the scale invariance axiom needs to be strenghtened to take into account all order-preserving transformations of the agents’ utilities. This axiom, called ordinal invariance, is a very demanding one. For two-agents, it is violated by every strongly individually rational bargaining rule. In general, no ordinally invariant bargaining rule satisfies the other three axioms of Nash. Parallel to Roth (J Econ Theory 16:247–251, 1977), we introduce a weaker independence of irrelevant alternatives (IIA) axiom that we argue is better suited for ordinally invariant bargaining rules. We show that the three-agent Shapley–Shubik bargaining rule uniquely satisfies ordinal invariance, Pareto optimality, symmetry, and this weaker IIA axiom. We also analyze the implications of other independence axioms.     

Impossibility of Nash implementation in two-person economies

In this note, we prove two impossibility results of Nash implementation in two-person economies. First, we will show the non-existence of continuous and balanced mechanisms which implement the Walrasian correspondence. Second, by adding a convexity assumption of mechanisms, we present the impossibility of continuous implementation of Pareto optimal and individually rational allocations in balanced way. Received: 16 April 1996 / Accepted: 25 April 1997     

Double implementation of the ratio correspondence by a market mechanism

To overcome deficits of the Lindahl solution concept when the economy does not exhibit constant returns to scale, Kaneko (1977a) introduced the concept of aratio equilibrium. Theratio correspondence selects for each economy its set of ratio equilibrium allocations. In this paper we provide a simple market game thatdouble implements the ratio correspondence in Nash and strong equilibria.     

Switching from complete to incomplete information

We construct an elementary mechanism [Dutta, B., Sen, A., Vohra, R., 1995. Nash implementation through elementary mechanisms in economic environments. Review of Economic Design 1, 173–203] that Nash implements the constrained Walrasian correspondence. We extend it to incomplete and non-exclusive information economies by enlarging the message space of agents. In addition, measurability restrictions on allocations with respect to prices proper to constrained rational expectations equilibria are imposed in the outcome function. We show that by imposing such restrictions, the mechanism Bayesian implements the constrained rational expectations equilibrium correspondence. This result shows game-theoretic connections between these two market equilibrium concepts. However, these connections are obtained at the price of strong restrictions on the behavior of agents.     

Groves mechanisms and communication externalities

We put forward a model of private goods with externalities. Agents derive benefit from communicating with each other. In order to communicate they need to operate on a common platform. Adopting new platforms is costly. We first provide an algorithm that determines the efficient outcome. Then we prove that no individually rational and feasible Groves mechanism exists. We provide sufficient conditions that determine when an individually rational Groves mechanism runs a deficit and we characterize the individually rational Groves mechanism that minimizes such deficit whenever it occurs. Moreover, for 2-agent economies, we single out the only feasible and symmetrical Groves mechanism that is not Pareto dominated by another strategy-proof, feasible and symmetrical mechanism.     

Optimal selling mechanisms for multiproduct monopolists: incentive compatibility in the presence of budget constraints

We analyze the nonlinear pricing problem faced by an incomplete information monopolist operating in a market populated by agents with budget constraints. We show that if other goods are available and if the monopolist's goods are nonessential relative to other goods, then there exists an optimal, individually rational, and incentive compatible selling mechanism for the monopolist (Theorem 1). Moreover, we show that a solution to all such nonlinear pricing problems exists if and only if the monopolist's goods are nonessential (Theorem 2). In the absence of nonessentiality, we show that if the monopolist's profit function is independent of quantity (e.g., if all costs are fixed), then an optimal selling mechanism exists (Theorem 3). Finally, we show that if there is reporting (of types by agents) and partial recognition of types (by the monopolist), then an optimal selling mechanism exists, even in the absence of nonessentiality, provided agents' utility functions are affine and continuous in goods (Theorem 4).     

Efficient outcomes in a repeated agency model without discounting

The basic result of repeated principal-agent models in which neither the principal nor the agent discounts the future is that the set of individually rational, Pareto efficient utility allocations of the associated single-period model without moral hazard coincide with the efficient outcomes in the repeated principal-agent model with moral hazard. This result is established here in a more general setting than that found in the literature; this is done with a simple alternative proof that highlights the roles of Pareto efficiency and the lack of discounting.