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.     

Random mechanisms for house allocation with existing tenants

We study the house allocation problem with existing tenants: $n$ houses (stand for “indivisible objects”) are to be allocated to $n$ agents; each agent needs exactly one house and has strict preferences; $k$ houses are initially unowned; $k$ agents initially do not own houses; the remaining $n-k$ agents (the so-called “existing tenants”) initially own the remaining $n-k$ houses (each owns one). In this setting, we consider various randomized allocation rules under which voluntary participation of existing tenants is assured and the randomization procedure either treats agents equally or discriminates against some (or all) of the existing tenants. We obtain two equivalence results, which generalize the equivalence results in Abdulkadiroğlu and Sönmez (1999) and Sönmez and Ünver (2005).     

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.     

Eliciting the socially optimal allocation from responsible agents

We consider designing a mechanism to allocate objects among agents without monetary transfers. There is a socially optimal allocation, which is commonly known by the agents but not observable by the designer. The designer possibly has information about the existence of responsible agents. A responsible agent, when indifferent between his objects at two different allocations, prefers the first allocation to the second if the first allocation is closer to the optimal allocation than the second, in the sense that all the agents who are allocated their optimal objects in the second allocation are allocated their optimal objects also in the first allocation, and there is at least one more agent in the first allocation receiving his optimal object. We show that, if the designer knows that there are at least three responsible agents, even if the identities of the responsible agents are not known, the optimal allocation can be elicited.     

Ex-post incentive compatible and individually rational assignments in housing markets with interdependent values

This paper presents a model for housing markets with interdependent values. We introduce private information on the quality of a house (i.e., high or low), which is known only to the initial owner. Interdependency means that the ex-post preference of an agent depends on the private information of the other agents with regard to the quality of houses. We prove that on a domain satisfying a richness condition, the no-trade rule is the only rule that satisfies ex-post incentive compatibility and ex-post individual rationality.     

No-envy,solidarity, and strategy-proofness in the queueing problem

Given a group of agents, the queueing problem is concerned with finding the order to serve agents and the monetary transfers they should receive. In this paper, we characterize interesting subfamilies of the VCG mechanisms by investigating the implications of either no-envy or solidarity requirements. First, we present a characterization of the strategy-proofand envy-freemechanisms. Next, we present characterizations of VCG mechanisms satisfying one of two different formulations of cost monotonicity or population monotonicity. Finally, we show that among the envy-free and strategy-proof mechanisms, the only ones that satisfy one of two formulations of cost monotonicity or population monotonicity are extensions of the pivotal or the reward-based pivotal mechanisms.     

Influence in private-goods allocation

We reinterpret the ‘bossiness’ of a private-goods allocation rule (Satterthwaite and Sonnenschein, 1981) as the ability of an agent to ‘influence’ another’s welfare with no change to her own welfare. In applications where non-bossiness is not possible, we propose simple conditions on (1) which agents may have influence (acyclicity and preservation), and (2) the welfare consequences of influence (positivity and oppositeness). We apply these conditions to three well-known bossy rules: the ‘Vickrey rule’ in single-object auctions (Vickrey, 1961) (acyclic, positive), the ‘doctor-optimal stable rule’ in matching with contracts (Hatfield and Milgrom, 2005) (acyclic, positive, preserving) and ‘generalised absorbing top-trading cycles (GATTC) rules’ in housing markets with indifferences in preferences (Aziz and Keijzer, 2011) (acyclic, opposite, preserving). Under mild restrictions, we show how the nature of influence under a strategy-proof rule determines whether or not it satisfies weak group-strategy-proofness (requires acyclicity and either positivity or preservation), weak Maskin monotonicity (acyclicity and positivity) and Pareto-efficiency (acyclicity and oppositeness). In addition, we propose an influence-related generalisation of the efficiency-adjusted deferred acceptance mechanism in school choice (Kesten, 2010), and characterise influence for strategy-proof GATTC rules in housing markets.     

Strategy-proofness and population-monotonicity for house allocation problems

We study a simple model of assigning indivisible objects to agents, such as dorm rooms to students, or offices to professors, where each agent receives at most one object and monetary compensations are not possible. For these problems population-monotonicity, which requires that agents are affected by population changes in the same way, is a compelling property because tentative assignments are made in many typical situations, which may have to be revised later to take into account the changing population. We completely describe the allocation rules satisfying population-monotonicity, strategy-proofness, and efficiency. The characterized rules assign the objects by an iterative procedure in which at each step no more than two agents “trade” objects from their hierarchically specified “endowments.”     

Resource-envy-free and efficient allocations: A new solution for production economies with dedicated factors

I consider the problem of determining an equitable and efficient allocation of resources in production economies with factors which must be dedicated to production and cannot be consumed directly. First, I show that in such economies envy-free and efficient allocations exist under standard assumptions. However, I argue this notion of fairness is unsuitable for the present context. I then introduce a new notion of fairness, which I call resource-envy-freeness. First, I associate with each consumption bundle its resource footprint consisting of the vector of factors used to produce it. I then show that preferences over consumption bundles can be extended to preferences over factor bundles. An allocation is resource-envy-free if no agent prefers another agent’s resource footprint to its own. The analysis of resource-envy-free allocations in production is exactly analogous to the analysis of envy-free allocations in exchange. I establish that resource-envy-free and efficient allocations exist under standard assumptions, and I demonstrate that such allocations are intuitively appealing.     

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     

Weighted majoritarian rules for the location of multiple public facilities

We consider collective decision problems given by a profile of single-peaked preferences defined over the real line and a set of pure public facilities to be located on the line. In this context, Bochet and Gordon (2012) provide a large class of priority rules based on efficiency, object-population monotonicity and sovereignty. Each such rule is described by a fixed priority ordering among interest groups. We show that any priority rule which treats agents symmetrically — anonymity — respects some form of coherence across collective decision problems — reinforcement — and only depends on peak information — peak-only — is a weighted majoritarian rule. Each such rule defines priorities based on the relative size of the interest groups and specific weights attached to locations. We give an explicit account of the richness of this class of rules.     

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     

A play-the-winner-type urn design with reduced variability

We propose a new adaptive allocation rule, the drop-the-loser, that randomizes subjects in the course of a trial comparing treatments with dichotomous outcomes. The rule tends to assign more patients to better treatments with the same limiting proportion as the randomized play-the-winner rule. The new design has significantly less variable allocation proportion than the randomized play-the-winner rule. Decrease in variability translates into a gain in statistical power. For some values of success probabilities the drop-the-loser rule has a double advantage over conventional equal allocation in that it has better power and assigns more subjects to the better treatment. Acknowledgments. I thank Stephen Durham, the associate editor, and the referees for their helpful suggestions.     

A continuous double implementation of the constrained Walras equilibrium

We provide a continuous and feasible double implementation of the Walras equilibrium. In our game form the set of traders is partitioned intok subsets,k>-2, and for each member of the partition there is an (outside) auctioneer. Also, each agent announces a price-allocation pair so that all agents become price takers. The outcome allocation is defined as the feasible (and budget balanced) allocation which is closest to the aggregate announced allocation. No assumptions are made on the preferences of the traders.     

An equity characterization of second price auctions when preferences may not be quasilinear

In a single item auction model that allows non-quasilinear preferences, we show that an auction rule satisfies weak envy-freeness for equals, strategy-proofness, and nonimposition if and only if it is a (generalized) second price auction. This characterization is established on a wide class of preference domains, including the quasilinear domain, a positive income effect domain, and a negative income effect domain.     

Condorcet efficiency of positional voting rules with single-peaked preferences

Consider a three-alternative election with n voters and assume that preferences are single-peaked. LetC(λ,n) be the Condorcet efficiency of the rule that assigns 1,λ and 0 points (respectively) to each first, second and third place vote. An exact representation is obtained forC(λ,∞). This relation shows that Borda rule (λ=1/2) is not the most efficient rule. In addition to this result, exact closed form relations are provided forC(0,n),C(1/2,n) andC(1,n). All these relations are obtained by assuming that every admissible configuration of preferences is equally likely to occur. This research was supported in part by the Swedish Insitute     

Euclidean preferences

This note is devoted to the question: how restrictive is the assumption that preferences be Euclidean in d dimensions. In particular it is proven that any preference profile with I individuals and A alternatives can be represented by Euclidean utilities with d   dimensions if and only if d≥min?(I,A−1)$d\ge \min ?(I\text{,}A-1)$. The paper also describes the systems of A points which allow for the representation of any profile over A alternatives, and provides similar results when only strict preferences are considered. These findings contrast with the observation that if preferences are only required to be convex then two dimensions are always sufficient.     

The structure of decision schemes with cardinal preferences

This paper replacesGibbard’s (Econometrica 45:665-681, 1977) assumption of strict ordinal preferences by themore natural assumption of cardinal preferences on the set pure social alternatives and we also admit indifferences among the alternatives. By following a similar line of reasoning to the Gibbard-Satterthwaite theoremin the deterministic framework, we first show that if a decision scheme satisfies strategy proofness and unanimity, then there is an underlying probabilistic neutrality result which generates an additive coalitional power function. This result is then used to prove that a decision scheme which satisfies strategy proofness and unanimity can be represented as a weak random dictatorship. A weak random dictatorship assigns each individual a chance to be a weak dictator. An individual has weak dictatorial power if the support of the social choice lottery is always a subset of his/her maximal utility set. In contrast to Gibbard’s complete characterization of randomdictatorship, we also demonstrate with an example that strategy proofness and unanimity are sufficient but not necessary conditions for a weak random dictatorship.     

Global analysis and economics III: Pareto Optima and price equilibria

Among other things a global version of the fundamental theorem of welfare economics is proved. One starts with a pure exchange economy with fixed total resources where hypotheses of differentiability, convexity, and monotonicity are made on the utility functions. Let ? be the set of price equilibria where the initial allocation coincides with the final one. Then the map which assigns to such a price equilibrium, the corresponding allocation is a diffeomorphism (a complete correspondence) between ? and the set of Pareto Optima.     

Bilateral redistribution

We explore the implications of three basic and intuitive axioms for income redistribution problems: continuity, no transfer paradox and stability. The combination of the three axioms characterizes in the two-agent case a large family of rules, which we call threshold rules. For each level of total income in society, a threshold is considered for each agent. It is impossible for both agents to be below their respective thresholds. If an agent’s income is below the threshold, the difference is redistributed from the other agent; otherwise, the rule imposes laissez-faire.