  Social choice functions (SCFs) map the preferences of a group of agents over
some set of alternatives to a non-empty subset of alternatives. The
Gibbard-Satterthwaite theorem has shown that only extremely restrictive SCFs
are strategyproof when there are more than two alternatives. For set-valued
SCFs, or so-called social choice correspondences, the situation is less clear.
There are miscellaneous - mostly negative - results using a variety of
strategyproofness notions and additional requirements. The simple and intuitive
notion of Kelly-strategyproofness has turned out to be particularly compelling
because it is weak enough to still allow for positive results. For example, the
Pareto rule is strategyproof even when preferences are weak, and a number of
attractive SCFs (such as the top cycle, the uncovered set, and the essential
set) are strategyproof for strict preferences. In this paper, we show that, for
weak preferences, only indecisive SCFs can satisfy strategyproofness. In
particular, (i) every strategyproof rank-based SCF violates Pareto-optimality,
(ii) every strategyproof support-based SCF (which generalize Fishburn's C2
SCFs) that satisfies Pareto-optimality returns at least one most preferred
alternative of every voter, and (iii) every strategyproof non-imposing SCF
returns the Condorcet loser in at least one profile. We also discuss the
consequences of these results for randomized social choice.
