is,
R F = ∣Λ^ ∈ 2κ I ther eexists P ∈ P SuchthatF (F) = A^}
Denote by Rf the set of chosen objects; namely,
Rf = {x ∈ K I x ∈ XforsomeX ∈ Rr} ■
Definition 2 A social choice function F: Pn —> 2κ is Inanipulable if there
exist P = (Pi,..., Pn) ∈P". i ∈ N, and Pi ∈P such that F (Pf P_f) PiF (F).
A social choice function on P is strategy-proof if it is not manipulable.
Definition 3 A social choice function F: Pn —> 2κ is dictatorial if there
exists i ∈ N such that F (F) = t-rf (Pf) for all P ∈P".
The Gibbard-Satterthwaite theorem states that any social choice function
on P will be either dictatorial or its range will have only two elements. It
would apply directly if any individual preference over the sets of objects were
in the domain. However, there are many situations were agents’ preferences
have specific structure due to the nature of the set of objects, and this struc-
ture may impose meaningful restrictions on the way agents rank subsets of
objects. We will be interested in two natural domains of preferences: those
that are separable and those that are additive.
Definition 4 A preference Pi on 2κ is additive if there exists a function
ui,. K -t R such that for all X, Y Ç K
XPiY if and only if∑ ui (χ) >∑ui (у)
xζX y&
The set of additive preferences will be denoted by A.
An agent i has separable preferences Pi if the division between good ob-
jects ({x}Piφ) and bad objects (βPi{x}) guides the ordering of subsets in the
sense that adding a good object leads to a better set, while adding a bad
object leads to a worse set. Formally,