Individual versus group strategy-proofness: when do they coincide?

A social choice function is group strategy-proof on a domain if no group of agents can manipulate its final outcome to their own benefit by declaring false preferences on that domain. Group strategy-proofness is a very attractive requirement of incentive compatibility. But in many cases it is hard or impossible to find nontrivial social choice functions satisfying even the weakest condition of individual strategy-proofness. However, there are a number of economically significant domains where interesting rules satisfying individual strategy-proofness can be defined, and for some of them, all these rules turn out to also satisfy the stronger requirement of group strategy-proofness. This is the case, for example, when preferences are single-peaked or single-dipped. In other cases, this equivalence does not hold. We provide sufficient conditions defining domains of preferences guaranteeing that individual and group strategy-proofness are equivalent for all rules defined on the

On Strategy-proofness and symmetric single-peakedness

We characterize the class of strategy-proof social choice functions on the domain of symmetric single-peaked preferences. This class is strictly larger than the set of generalized median voter schemes (the class of strategy-proof and tops-only social choice functions on the domain of single-peaked preferences characterized by Moulin (1980)) since, under the domain of symmetric single-peaked preferences, generalized median voter schemes can be disturbed by discontinuity points and remain strategy-proof on the smaller domain. Our result identifies the specific nature of these discontinuities which allow to design non-onto social choice functions to deal with feasibility constraints.

Two necessary conditions for strategy-proofness: on what domains are they also sufficient?

A social choice function may or may not satisfy a desirable property depending on its domain of definition. For the same reason, different conditions may be equivalent for functions defined on some domains, while different in other cases. Understanding the role of domains is therefore a crucial issue in mechanism design. We illustrate this point by analyzing the role of different conditions that are always related, but not always equivalent to strategy-proofness. We define two very natural conditions that are necessary for strategy-proofness: monotonicity and reshuffling invariance. We remark that they are not always sufficient. Then, we identify a domain condition, called intertwinedness, that ensures the equivalence between our two conditions and that of strategy-proofness. We prove that some important domains are intertwined: those of single-peaked preferences, both with public and private goods, and also those arising in simple models of house allocation. We prove that other necessary conditions for strategy-proofness also become equivalent to ours when applied to functions defined on intertwined domains, even if they are not equivalent in general. We also study the relationship between our domain restrictions and others that appear in the literature, proving that we are indeed introducing a novel proposal.

Strategy-proofness makes the difference: deferred-acceptance with responsive priorities

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB)procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

Strategy-proofness and essentially single-valued cores revisited

We consider general allocation problems with indivisibilities where agents' preferences possibly exhibit externalities. In such contexts many different core notions were proposed. One is the gamma-core whereby blocking is only allowed via allocations where the non-blocking agents receive their endowment. We show that if there exists an allocation rule satisfying ‘individual rationality’, ‘efficiency’, and ‘strategy-proofness’, then for any problem for which the gamma-core is non-empty, the allocation rule must choose a gamma-core allocation and all agents are indifferent between all allocations in the gamma-core. We apply our result to housing markets, coalition formation and networks.

Object allocation via deferred-acceptance: strategy-proofness and comparative statics

We study the problem of assigning indivisible and heterogenous objects (e.g., houses, jobs, offices, school or university admissions etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We consider mechanisms satisfying a set of basic properties (unavailable-type-invariance, individual-rationality, weak non-wastefulness, or truncation-invariance). In the house allocation problem, where at most one copy of each object is available, deferred-acceptance (DA)-mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm. For house allocation we show that DA-mechanisms are characterized by our basic properties and (i) strategy-proofness and population-monotonicity or (ii) strategy-proofness and resource-monotonicity. Once we allow for multiple identical copies of objects, on the one hand the first characterization breaks down and there are unstable mechanisms satisfying our basic properties and (i) strategy-proofness and population-monotonicity. On the other hand, our basic properties and (ii) strategy-proofness and resource-monotonicity characterize (the most general) class of DA-mechanisms based on objects' fixed choice functions that are acceptant, monotonic, substitutable, and consistent. These choice functions are used by objects to reject agents in the agent-proposing deferred-acceptance-algorithm. Therefore, in the general model resource-monotonicity is the «stronger» comparative statics requirement because it characterizes (together with our basic requirements and strategy-proofness) choice-based DA-mechanisms whereas population-monotonicity (together with our basic properties and strategy-proofness) does not.

Strategy-proof social choice

This paper surveys the literature on strategy-proofness from a historical perspective. While I discuss the connections with other works on incentives in mechanism design, the main emphasis is on social choice models. This article has been prepared for the Handbook of Social Choice and Welfare, Volume 2, Edited by K. Arrow, A. Sen and K. Suzumura

Group strategy-proof social choice functions with binary ranges and arbitrary domains: characterization results

We define different concepts of group strategy-proofness for social choice functions. We discuss the connections between the defined concepts under different assumptions on their domains of definition. We characterize the social choice functions that satisfy each one of them and whose ranges consist of two alternatives, in terms of two types of basic properties.

Efficient Strategy-Proof Allocation Functions in Linear Production Economies

In a linear production model, we characterize the class of efficient and strategy-proof allocation functions, and the class of efficient and coalition strategy-proof allocation functions. In the former class, requiring equal treatment of equals allows us to identify a unique allocation function. This function is also the unique member of the latter class which satisfies uniform treatment of uniforms.

Strategy-proof tie-breaking

We study a general class of priority-based allocation problems with weak priority orders and identify conditions under which there exists a strategy-proof mechanism which always chooses an agent-optimal stable, or constrained efficient, matching. A priority structure for which these two requirements are compatible is called solvable. For the general class of priority-based allocation problems with weak priority orders,we introduce three simple necessary conditions on the priority structure. We show that these conditions completely characterize solvable environments within the class of indifferences at the bottom (IB) environments, where ties occur only at the bottom of the priority structure. This generalizes and unifies previously known results on solvable and unsolvable environments established in school choice, housing markets and house allocation with existing tenants. We show how the previously known solvable cases can be viewed as extreme cases of solvable environments. For sufficiency of our conditions we introduce a version of the agent-proposing deferred acceptance algorithm with exogenous and preference-based tie-breaking.

Strategy-proof choice of acts : a preliminary study

We model social choices as acts mapping states of the world to (social) outcomes. A (social choice) rule assigns an act to every profile of subjective expected utility preferences over acts. A rule is strategy-proof if no agent ever has an incentive to misrepresent her beliefs about the world or her valuation of the outcomes; it is ex-post efficient if the act selected at any given preference profile picks a Pareto-efficient outcome in every state of the world. We show that every two-agent ex-post efficient and strategy-proof rule is a top selection: the chosen act picks the most preferred outcome of some (possibly different) agent in every state of the world. The states in which an agent’s top outcome is selected cannot vary with the reported valuations of the outcomes but may change with the reported beliefs. We give a complete characterization of the ex-post efficient and strategy-proof rules in the two-agent, two-state case, and we identify a rich class of such rules in the two-agent case.

Strategy-proof choice of acts : a preliminary study

We model social choices as acts mapping states of the world to (social) outcomes. A (social choice) rule assigns an act to every profile of subjective expected utility preferences over acts. A rule is strategy-proof if no agent ever has an incentive to misrepresent her beliefs about the world or her valuation of the outcomes; it is ex-post efficient if the act selected at any given preference profile picks a Pareto-efficient outcome in every state of the world. We show that every two-agent ex-post efficient and strategy-proof rule is a top selection: the chosen act picks the most preferred outcome of some (possibly different) agent in every state of the world. The states in which an agent’s top outcome is selected cannot vary with the reported valuations of the outcomes but may change with the reported beliefs. We give a complete characterization of the ex-post efficient and strategy-proof rules in the two-agent, two-state case, and we identify a rich class of such rules in the two-agent case.