Strategy-proof and individually rational social choice functions for public good economies: A note

Summary. Serizawa [3] characterized the set of strategy-proof, individually rational, no exploitative, and non-bossy social choice functions in economies with pure public goods. He left an open question whether non-bossiness is necessary for his characterization. We will prove that non-bossiness is implied by the other three axioms in his characterization. Received: October 17, 1997; revised version: January 19, 1998     

Efficient strategy-proof exchange and minimum consumption guarantees

For exchange economies with classical economic preferences, it is shown that any strategy-proof social choice function that selects Pareto optimal outcomes cannot guarantee everyone a consumption bundle bounded away from the origin. This result demonstrates that there is a fundamental conflict between efficiency and distributional goals in exchange economies if the social choice rule is required to be strategy-proof.     

Strategy-Proof Probabilistic Mechanisms in Economies with Pure Public Goods

Public good economies where agents are endowed with strictly convex continuous single-peaked preferences on a convex subset of Euclidean space are considered. Such an economy arises for instance in the classical problem of allocating a given budget to finance the provision of several public goods where the agents have monotonically increasing strictly convex continuous preferences. A probabilistic mechanism assigns a probability distribution over the feasible alternatives to any profile of reported preferences. The main result of the paper establishes that any strategy-proof (in the sense of A. Gibbard, Econometrica45 (1977), 665-681) and unanimous mechanism must be a random dictatorship. Journal of Economic Literature Classification Numbers: D70, D71, H40, C60.     

Second-best efficiency of allocation rules: strategy-proofness and single-peaked preferences with multiple commodities

We study strategy-proof allocation rules in economies with perfectly divisible multiple commodities and single-peaked preferences. In this setup, it is known that the incompatibility among strategy-proofness, Pareto efficiency and non-dictatorship arises in contrast with the Sprumont (Econometrica 59:509–519, 1991) one commodity model. We first investigate the existence problem of strategy-proof and second-best efficient rules, where a strategy-proof rule is second-best efficient if it is not Pareto-dominated by any other strategy-proof rules. We show that there exists an egalitarian rational (consequently, non-dictatorial) strategy-proof rule satisfying second-best efficiency. Second, we give a new characterization of the generalized uniform rule with the second-best efficiency in two-agent case.     

On the nature of equilibria in a Downsian model with candidate valence

We analyze mechanisms that are used to allocate dormitory rooms to students at college campuses. Students consist of newcoming freshmen, who do not currently occupy any rooms, and more senior students each of whom occupies a room from the previous year. In addition to the rooms already occupied by the existing tenants, there are vacated rooms by the graduating class. Students have strict preferences over dormitory rooms. Each student shall be assigned a dormitory room in an environment where monetary transfers are not allowed. An existing tenant can move to another room as a result of the assignment. We show that you request my house–I get your turn mechanisms are the only mechanisms that are Pareto-efficient, individually rational, strategy-proof, weakly neutral, and consistent.     

Secure implementability under Pareto-efficient rules in linear production economies with classical preferences

This paper studies secure implementability (Saijo et al. (2007) “Secure Implementation,” Theoretical Economics 2, pp.203–229) in linear production economies with classical preferences. Although secure implementability is in general stronger than the combination of strategy-proofness and non-bossiness (Satterthwaite and Sonnenschein (1981) “Strategy-Proof Allocation Mechanisms at Differentiable Points,” Review of Economic Studies 48, pp.587–597), this paper shows that both properties are equivalent under Pareto-efficient rules in the economies. In addition, this paper characterizes securely implementable and Pareto-efficient rules in the economies when the number of agents is two.     

Subgame-perfect implementation of bargaining solutions

We study house allocation problems introduced by L. Shapley and H. Scarf (1974, J. Math. Econ.1, 23–28). We prove that a mechanism (a social choice function) is individually rational, anonymous, strategy-proof, and nonbossy (but not necessarily Pareto efficient) if and only if it is either the core mechanism or the no-trade mechanism, where the no-trade mechanism is the one that selects the initial allocation for each profile of preferences. This result confirms the intuition that even if we are willing to accept inefficiency, there exists no interesting strategy-proof mechanism other than the core mechanism. Journal of Economic Literature Classification Numbers: C71, C78, D71, D78, D89.     

On the generic impossibility of truthful behavior: A simple approach

Summary We provide an elementary proof showing how in economies with an arbitrary number of agents an arbitrary number of public goods and utility functions quasi-linear in money, any efficient and individually rational mechanism is not strategy-proof for any economy satisfying a mild regularity requirement.The authors wish to thank William Thomson, Salvadpr Barberá, José Angel Silva and an anonymous referee for helpful comments. The remaining errors are our exclusive responsibility. Financial support from DGICYT under project PB 91-0756 and the Instituto Valenciano de Investigaciones Económicas is gratefully acknowledged.     

Top dominance and the possibility of strategy-proof stable solutions to matching problems

Summary This paper explores the possibility of designing strategy-proof mechanisms yielding satisfactory solutions to the marriage and to the college admissions problem. Our first result is negative. We prove that no strategy-proof mechanism can always choose marriages that are individually rational and Pareto efficient. This strengthens a result by Roth (1982) showing that strategy-proof mechanisms cannot always select stable marriages. The result also applies, a fortiori, to college admissions. Since finding difficulties with strategy-proofness is quite an expected result, we then address a second question which is classical within the incentives literature. Are there restrictions on the preferences of agents under which strategy-proof and stable mechanisms do exist? We identify a nontrivial restriction on the domain of preferences, to be called top dominance, under which there exist strategy-proof and stable mechanisms for both types of matching problems. The mechanisms turn out to be exactly those that derive from the most classical algorithms in the literature; namely, the women's optimal, the men's optimal and the student's optimal. Finally, top dominance is shown to be essentially necessary, as well as sufficient, for the existence of strategy-proof stable matching mechanisms.This work is partially supported by grant PB 89-0294, from the Directión General de Investigatión Ciencia y Tecnología of the Spanish Ministerio de Educación y Ciencia. Salvador Barberà is also grateful to the Instituto de Estudios Fiscales. This research was initiated while both authors were visting GREMAQ, Université des Sciencies Sociales, Toulouse, whose hospitality is gratefully acknowledged. The paper extends results that were circulated as GREMAQ W.P. 91.22.232. We are grateful to Matthew Jackson and Marilda Sotomayor for their comments.     

Bribe-proof rules in the division problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents with single-peaked preferences. A rule maps preference profiles into n shares of the amount to be allocated. A rule is bribe-proof if no group of agents can compensate one of its subgroups to misrepresent their preferences and, after an appropriate redistribution of their shares, each obtains a weakly preferred share and all agents in the misrepresenting subgroup obtain a strictly preferred share. We characterize all bribe-proof rules as the class of Pareto efficient, strategy-proof, and weakly replacement monotonic rules. This class is larger than the set of sequential allotment rules identified in Barberà et al. [Barberà, S., Jackson, M., Neme, A., 1997. Strategy-proof allotment rules. Games Econ. Behav. 18, 1–21].     

Egalitarian division under Leontief Preferences

We consider the problem of fairly dividing $l$ divisible goods among $n$ agents with the generalized Leontief preferences. We propose and characterize the class of generalized egalitarian rules which satisfy efficiency, group strategy-proofness, anonymity, resource monotonicity, population monotonicity, envy-freeness and consistency. On the Leontief domain, our rules generalize the egalitarian-equivalent rules with reference bundles. We also extend our rules to agent-specific and endowment-specific egalitarian rules. The former is a larger class of rules satisfying all the previous properties except anonymity and envy-freeness. The latter is a class of efficient, group strategy-proof, anonymous and individually rational rules when the resources are assumed to be privately owned.     

Non-Dummy Agents in Pure Exchange Economies

We introduce a very fundamental and important axiom of the non-dummy. This states that each agent can change the outcome of the mechanism at some preference profile, thus guaranteeing every agent the minimum right to affect the social decision. We study the possibility of strategy-proof, efficient and non-dummy mechanisms in pure exchange economies. We provide two new interesting classes of such mechanisms. The results shed light on the structure of strategy-proof and efficient mechanisms, and should promote a complete characterization of those mechanisms in pure exchange economies with three or more agents.     

Pairwise kidney exchange

The literature on exchange of indivisible goods finds natural application in the exchange of live donor kidneys for transplant. However, in kidney exchange, there are constraints on the size of exchanges. Initially, kidney exchanges are likely to be between just two patient-donor pairs. We show that, although this constraint eliminates some potential exchanges, there is a wide class of constrained-efficient mechanisms that are strategy-proof when patient-donor pairs and surgeons have 0-1 preferences. This includes deterministic mechanisms that accommodate the priority setting that organ banks currently use to allocate cadaver organs, and stochastic mechanisms that allow distributive justice issues to be addressed.     

Maximal Domain of Preferences in the Division Problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, then the uniform allocation rule is the unique strategy-proof, efficient, and anonymous rule. We identify the maximal set of preferences, containing the set of single-peaked preferences, under which there exists at least one rule satisfying the properties of strategy-proofness, efficiency, and strong symmetry. In addition, we show that our characterization implies a slightly weaker version of Ching and Serizawa's (1998) result. Journal of Economic Literature Classification Numbers: D71, D78, D63.     

Bribe-proof rules in the division problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents with single-peaked preferences. A rule maps preference profiles into n shares of the amount to be allocated. A rule is bribe-proof if no group of agents can compensate one of its subgroups to misrepresent their preferences and, after an appropriate redistribution of their shares, each obtains a weakly preferred share and all agents in the misrepresenting subgroup obtain a strictly preferred share. We characterize all bribe-proof rules as the class of Pareto efficient, strategy-proof, and weakly replacement monotonic rules. This class is larger than the set of sequential allotment rules identified in Barberà et al. [Barberà, S., Jackson, M., Neme, A., 1997. Strategy-proof allotment rules. Games Econ. Behav. 18, 1–21].     

Statistical Equilibrium Wealth Distributions in an Exchange Economy with Stochastic Preferences

We describe an exchange market consisting of many agents with stochastic preferences for two goods. When individuals are indifferent between goods, statistical mechanics predicts that goods and wealth will have steady-state gamma distributions. Simulation studies show that gamma distributions arise for a broader class of preference distributions. We demonstrate this mathematically in the limit of large numbers of individual agents. These studies illustrate the potential power of a statistical mechanical approach to stochastic models in economics and suggest that gamma distributions will describe steady-state wealths for a class of stochastic models with periodic redistribution of conserved quantities. Journal of Economic Literature Classification Numbers: C15, C62, C73, D3, D5.     

Group incentive compatibility for matching with contracts

Hatfield and Milgrom [Hatfield, John William, Milgrom, Paul R., 2005. Matching with contracts. Amer. Econ. Rev. 95, 913–935] present a unified model of matching with contracts, which includes the standard two-sided matching and some package auction models as special cases. They show that the doctor-optimal stable mechanism is strategy-proof for doctors if hospitals' preferences satisfy substitutes and the law of aggregate demand. We show that the doctor-optimal stable mechanism is group strategy-proof for doctors under these same conditions. That is, no group of doctors can make each of its members strictly better off by jointly misreporting their preferences. We derive as a corollary of this result that no individually rational allocation is preferred by all the doctors to the doctor-optimal stable allocation.     

Efficiency, monotonicity and rationality in public goods economies

Summary. In economies with public goods, we identify a necessary and sufficient condition for the existence of cost monotonic, Pareto optimal and individually rational mechanisms. These exist if and only if the preferences of the agents satisfy what we call the equal ordering property. We also show that when this condition holds the egalitarian equivalent correspondence is the only cost monotonic selection from the core of the economy. Furthermore, it is unambiguous in the sense that the agents are indifferent among all the allocations in it. Received: February 26, 1996; revised version: January 31, 1997     

Existence and Welfare Properties of Equilibrium in an Exchange Economy with Multiple Divisible and Indivisible Commodities and Linear Production Technologies

In this paper we consider a class of economies with a finite number of divisible commodities, linear production technologies, and indivisible goods and a finite number of agents. This class contains several well-known economies with indivisible goods and money as special cases. It is shown that if the utility functions are continuous on the divisible commodities and are weakly monotonic both on one of the divisible commodities and on all the indivisible commodities, if each agent initially owns a sufficient amount of one of the divisible commodities, and if a “no production without input”-like assumption on the production sector holds, then there exists a competitive equilibrium for any economy in this class. The usual convexity assumption is not needed here. Furthermore, by imposing strong monotonicity on one of the divisible commodities we show that any competitive equilibrium is in the core of the economy and therefore the first theorem of welfare also holds. We further obtain a second welfare theorem stating that under some conditions a Pareto efficient allocation can be sustained by a competitive equilibrium allocation for some well-chosen redistribution of the total initial endowments. Journal of Economic Literature Classification Numbers: D4, D46, D5, D51, D6, D61.     

Core is manipulable via segmentation

Any allocation rule that picks only core allocations is manipulable via segmentation. That is, there exists an economy with a coalition of agents such that, once this coalition splits momentarily from the rest of the economy and institutes the allocation rule within itself, no matter which individually rational sub-allocation the complementary coalition picks, when we paste all the agents back together at their new endowments and apply the allocation rule to this “collage” economy, each member of the former coalition will be strictly better off than under direct application of the allocation rule to the original economy.