Formal preliminaries
The standard social choice framework is the following. Consider a set X of social states (or states of the world). These social states must be interpreted as extremely detailed descriptions of a-temporal situations.
In particular, a given social state will include descriptions of characteristics pertaining to agents. Preferences over X are binary relations that are assumed to be complete. The preference relation for social states x and y will be denoted by x s y and it will mean x is at least as good as y. The asymmetric part (strict preference), x is better than y, will be denoted by x s y and defined, given completeness, by not y s x, and the symmetric part (indifference) will be denoted by x ~ y and defined by x s y and y s x. The preference ' is said to be complete if, for all x and y in X, either x s y or y s x; x and y are always comparable. The set of agents will be denoted by N. Each individual (agent) has a preference that is a complete preorder over X. Her preference is a transitive binary relation. If she finds x as least as good as y and y at least as good as z, then she must find x at least as good as z. One should note that in this case both the strict preference relation and the indifference relation are also transitive. Individual i’s preference will be denoted by ' i. In the following analysis, the social preference, denoted by ss S, will be assumed to be complete, and will satisfy some rationality conditions. We will consider three different conditions:1. Transitivity: for all x, y and z in X, x >s y and y 's z 1 x >s z.
2. Quasi-transitivity: for all x, y and z in X, x >s y and y >s z 1 x >s z.
3. >-acyclicity: there is no finite subset of X, {x1,..., xk}, for which x1 >s x2, x2 >s x3,..., xk-1 >s xk and xk >s x1.
A complete binary relation satisfying transitivity is a complete preorder.
In this case the social preference has the same characteristics as the individual preferences. When the set of social states X is finite, it means that the social states can be ranked from a top element to a bottom element with possible ties.Let P be the set of complete preorders over X. The agents’ preferences are given by a profile π which is a function from the set of individuals N into P. This is a kind of labelling operation. It assigns a complete preorder to each individual. When N is finite of size n, we have the usual list of individual preferences ('1,..., 'n). We will consider two types of aggregation rules. They will be called respectively aggregation functions and social choice functions (the definition of a social choice function will be given in the sub-section devoted to the Gibbard-Satterthwaite theorem).
An aggregation function is a function f which associates to each possible profile π a social preference 's over X. When the social preference 's is a complete preorder, the aggregation function is the classical Arrovian “social welfare function” (Arrow 1951). In the double finite case (the set of individuals and the set of social states being finite), given a complete ranking of the social states by each individual, a social welfare function gives a complete ranking of the social states at the social/collective level. Individual and social rationalities are identical. When 's is complete and satisfies > -acyclicity, the aggregation function, following Sen (1970b), will be called a “social decision function” and, when it satisfies quasi-transitivity, it will be called a “QT-social decision function”.