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

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.

On group strategy-proof mechanisms for a many-to-one matching model

For the many-to-one matching model in which firms have substitutable and quota q-separable preferences over subsets of workers we show that the workers-optimal stable mechanism is group strategy-proof for the workers. In order to prove this result, we also show that under this domain of preferences (which contains the domain of responsive preferences of the college admissions problem) the workers-optimal stable matching is weakly Pareto optimal for the workers and the Blocking Lemma holds as well. We exhibit an example showing that none of these three results remain true if the preferences of firms are substitutable but not quota q-separable.

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.

A maximal domain of preferences for tops-only rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, continuity, and "tops-onlyness". These domains (called weakly single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.

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

Approval voting ion dichotomous preferences

The aim of this paper is to find normative foundations of Approval Voting. In order to show that Approval Voting is the only social choice function that satisfies anonymity, neutrality, strategy-proofness and strict monotonicity we rely on an intermediate result which relates strategy-proofness of a social choice function to the properties of Independence of Irrelevant Alternatives and monotonicity of the corresponding social welfare function. Afterwards we characterize Approval Voting by means of strict symmetry, neutrality and strict monotonicity and relate this result to May's Theorem. Finally, we show that it is possible to substitute the property of strict monotonicity by the one efficiency of in the second characterization.

Efficient priority rules

We study the assignment of indivisible objects with quotas (houses, jobs, or offices) to a set of agents (students, job applicants, or professors). Each agent receives at most one object and monetary compensations are not possible. We characterize efficient priority rules by efficiency, strategy-proofness, and renegotiation-proofness. Such a rule respects an acyclical priority structure and the allocations can be determined using the deferred acceptance algorithm.

Organisational structure, communication and group ethics

This paper investigates experimentally how organisational decision processes affect the moral motivations of actors inside a firm that must forego profits to reduce harming a third party. In a "vertical" treatment, one insider unilaterally sets the harm-reduction strategy; the other can only accept or quit. In a "horizontal" treatment, the insiders decide by consensus. Our 2-by-2 design also controls for communication effects. In our data, communication makes vertical firms more ethical; voice appears to mitigate "responsibility-alleviation" in that subordinates with voice feel responsible for what their firms do. Vertical firms are then more ethical than the horizontal firms for which our bargaining data reveal a dynamic form of responsibility-alleviation and our chat data indicate a strong "insider-outsider" effect.

The unbounded dead-end depth propertie is not a group invariant

Vegeu el resum a l'inici del document del fitxer adjunt

Examples of retracts in a free group that are not the fixed subgroup of any group of automorphisms

Let F be a free group of rank at least three. We show that some retracts of F previously studied by Martino-Ventura are not equal to the fixed subgroup of any group of automorphisms of F. This shows that, in F, there exist subgroups that are equal to the fixed subgroup of some set of endomorphisms but are not equal to the fixed subgroup of any set of automorphisms. Moreover, we determine the Galois monoids of these retracts, where, by the Galois monoid of a subgroup H of F, we mean the monoid consisting of all endomorphisms of F that fix H.

The automorphism group of a free-by-cyclic group in rank 2

Vegeu el resum a l'inici del document del fitxer adjunt

Growth of positive words and lower bounds of the growth rate for Thompson's group (F)p

Vegeu el resum a l'inici del document del fitxer adjunt.

Computational explorations in Thompson's group F

Here we describe the results of some computational explorations in Thompson's group F. We describe experiments to estimate the cogrowth of F with respect to its standard finite generating set, designed to address the subtle and difficult question whether or not Thompson's group is amenable. We also describe experiments to estimate the exponential growth rate of F and the rate of escape of symmetric random walks with respect to the standard generating set.