数理解析研究所講究録
第 1788 巻 2012 年 141-146

141

Why does manipulation of social choices matter?
Shin Sato
Faculty of Economics, Fukuoka University

8-19-1 Nanakuma, Jonan-ku, Fukuoka, JAPAN 814-0180
E-mail: shinsato@adm.fukuoka-u.ac.jp

January 30, 2012

Abstract
I discuss why nonmanipulation of social choices is an important area ofresearch.

Keywords: manipulation, social choice, strategy-proofness.

JEL classification: D71.

1 Introduction
In this article, I discuss reasons why we consider nonmanipulability to be an important property in the context of social choice. Nonmanipulability of a social

choice rule (simply, a rule) has been one of the most important topics in the theoryof social choice,1 but its significance might not be clear to some researchers outside the field. As a researcher of nonmanipulability, I try to explain why I believenonmanipulability to be an important property of rules.
In Section 2, I formally define the most famous formulation of nonmanipula-bility, i.e, stmtegy-proofi2ess. In Section 3, I discuss the significance of nonmanipulability and recent researches.

lSee Barber\‘a (2010) for a survey.

142

2 Basic notation and definitions
Let $N=\{1, \ldots, n\}$ be a finite set of agents, and $X$ be a finite set of altematives. For example, in the context of voting, $N$ is a set of voters and $X$ is a set ofcandidates. Let

be the set of all linear orders on $X$ . Elements of$\mathcal{L}$preferences. For each $i\in N$ , each Rgthat for agent$i,$$x$is at least as good as$R=(R_{1}, \ldots, R_{n})$, where$R_{\dot{\eta}}\in \mathcal{L}$profiles. A $mle$ is a function from$\in \mathcal{L}$$y^{2}$, and each $x,$ $y\in X,$

Let$\mathcal{L}^{N}$

represent$xR_{\dot{\eta}}y$means

denote the set of all -mples

for each $i\in N$ . Elements of$\mathcal{L}^{N}$$\mathcal{L}$$n$$\mathcal{L}^{N}$

are preference

into $X$ . Generic notation for a rule is .
$f$

We say that agent manipulates a social choice if$i$(i) he reports a false preference relation, and(ii) as a result, a social choice changes from the one under the true preference

relation.
Thus, generally, misrepresentation is not equivalent to manipulation. (Misrepre-sentation does not necessarily change the social choice.)
A rule is nonmanipulable if each agent never manipulates a social choice undersome assumption on agents’ behavior.

Assumption (throughout the paper): Given $R_{-i}=(R_{1}, \ldots, h_{-1}, \kappa_{+1}, \ldots, R_{n})$ ,agent whose true preference relation is$i$$R_{\dot{\eta}}$reports a false preference relation$R_{i}’$

only if $f(R_{i}’, R_{-i})\neq f(R_{\dot{\eta}}, R_{-i})$ .
Under this assumption, misrepresentation is equivalent to manipulation.
A representative notion of nonmanipulability is strategy-proofness.
A mle $f$ is strategy-proof if for each$R\in \mathcal{L}^{N}$, each $i\in N$ , and each$f(R)R_{\dot{\eta}}f(R_{i}’, R_{-i})$$R_{i}’\in \mathcal{L}$,,2Each linear order can be considered as a ranking of the altematives without any ties between
distinct altematives. Thus, $xR_{i}y$ and $yR_{4}x$ if and only if $x=y$ .

143where$(R_{i}’, R_{-i})$is the preference profile obtained by replacing

In the above definition of strategy-proofness,preference relation, and$R_{i}’$$R_{i}$$R$$i$

in $R$ by$R_{i}^{l}$.

is interpreted as agent ’s true$i$is interpreted as agent ’s false preference relation.
$i$Then, the relation $f(R)R_{\eta}\cdot f(R_{i}’, R_{-i})$ says that reportingagent$R_{\dot{\eta}}$$R_{i}’$

is not beneficial for

regardless of what the other agents report. (Remember that the choice ofwas arbitraly.) It is reasonable to assume that the agents report their preferences

sincerely when misrepresentation of preferences is not profitable. Thus, strategyproofiness is a property which makes the mle designer reasonably conclude that therule is nonmanipulable.
It would be safe to say that the Gibbard-Satterthwaite theorem (Gibbard, 1973;Satterthwaite, 1975) is the starting point of the theory of manipulation. The theo-rem says that under mild conditions, strategy-proofness is achieved only by dictatorship. Because of its negative implication, the theorem is called an impossibility
theorem.

3 Discussion
3.1 Designer’s objectives
I do not intend to claim that nonmanipulability should be a universally criticalproperty of a rule. Whether nonmanipulability is a critical property of a rule or not

depends on the objective of the mle designer. I consider the following two types ofobjectives.
First, consider the designer who wants each social choice to have some “nice”

relation to the agents’ true preferences. For him, a rule describes a desirable relationship between the agents’ preferences and social choices. To achieve the $mle$ , itis necessary to elicit true preferences from the agents.
On the other hand, if the designer’s objective is to construct a rule which re-144
sponds “nicely” to the reported preferences, then nonmanipulability is not an important property at all. For the designer, a mle describes a desirable relationshipbetween the reported preferences and social choices. Thus, there is no need to elicit
tme preferences from the agents.

There is no theory according to which one of the two attitudes of the designer issuperior to the other. Thus, whether nonmanipulability matters or not depends onthe designer’s subjective opinion about what a social choice should be related to.
Nevertheless, in the following, I argue that economists, or more broadly, social sci-entists tend to take the former viewpoint, and this is the reason why manipulation
is a significant subject of research.

3.2 Need for true preferences
Many axioms of mles refer to agents’ preferences. As a representative example,
consider Pareto efficiency. For each$R\in \mathcal{L}^{N},$efficient) if there is no $y\in X\backslash \{x\}$ such that
$R_{\dot{\eta}}$

is a linear order. Because$x$and$y$

to $y.)$ A mle $f$ is efficient if for each$x\in X$ is Pareto$xR_{\dot{\eta}}y$are distinct,$R\in \mathcal{L}^{N},$for each $i\in N$ . (Remember that$xR_{\dot{\eta}}y$$f(R)$ issimple arguments show that we usually interpret

efficient (simply,$R_{\dot{\eta}}$means that is preferred$x$efficient.3 The following

as agent ’s tme preferences$i$when we discuss efficiency of altematives.

Let each agent choose one linear order
$i$

that

$R_{\dot{\eta}}$$R_{\dot{\eta}}$randomly Rom$\mathcal{L}$. (It is possible

happens to be the agent ’s tme preference relation, but generally, it is not$i$necessarily the tme one.) Let $R$ be the profile of them. Each preference relation

in $R$ is nothing to do with agents’ tme preferences. Then, most researchers would

agree that finding an efficient altemative with respect to $R$ is just a mathematical
exercise, and that as economists, we do not put an importance on such exercises.

3This notion is often called weak Pareto efficiency. Because we do not consider weak orders,
there is no difference between Pareto efficiency and weak Pareto efficiency in this article.

145
We are interested in realizing an efficient altemative with respect to a profile $R$ onlyif

$R_{1},$$\ldots,$$R_{n}$

are agents’ true preferences. Therefore, we need to elicit information

on tme preferences from the agents.

4 Present situation and recent researches
Strategy-proofiness has been a central axiom for nonmanipulability. However, inmany situations, we have impossibility results with strategy-proofness, i.e., every
acceptable or plausible mle violates stmtegy-proofness. Thus, we cannot recommend mles based on strategy-proofness. Although impossibility theorems shouldbe the starting point for further researches, unfortunately, we do not have satisfactory solutions to many of them. Manipulation is a serious problem in social choice,and we cannot deviate from making social choice. Therefore, we have to find aclass of acceptable mles which are less susceptible to manipulation.
There are several lines of researches. Maus, Peters, and Storcken (2007a,b,c,d)count the number of the profiles at which profitable $mi$ srepresentation occur. Barbie, Puppe, and Tasn\’adi (2006) and Sanver (2009) find domains under which fixedmles are strategy-proof. Campbell and Kelly (2009, 2010) consider gains andlosses from manipulation. Sato (2011a,b) considers the reluctance to make largelies. However, it is clear that there is still much to be done.

References
Barber\‘a, Salvador (2010) Strategyproof social choice. In: Arrow, Kenneth J.; Sen,Amartya; Suzumura, Kotaro (eds) Handbook of social choice and welfare, vol2. North-Holland, Amsterdam, chapter 25, pp 731-831.
Barbie, Martin; Puppe, Clemens; Tasn\’adi, Attila (2006) Non-manipulable domains

for the Borda count. Economic Theory 27, 411-430.

146
Campbell, Donald E.; Kelly, Jerry S. (2009) Gains from manipulating social choicemles. Economic Theory 40, 349-371.
Campbell, Donald E.; Kelly, Jeny S. (2010) Losses due to manipulation of socialchoice mles. Economic Theory 45, 453-467.
Gibbard, Allan (1973) Manipulation of voting scheme: A general result. Econo-metrica 41, 587-601.
Maus, Stefan; Peters, Hans; Storcken, Ton (2007a) Minimally manipulable anony-mous social choice functions. Mathematical Social Sciences 53, 239-254.
Maus, Stefan; Peters, Hans; Storcken, Ton (2007b) Minimal manipulability: Una-

nimity and nondictatorship. Joumal of Mathematical Economics 43, 675-691.
Maus, Stefan; Peters, Hans; Storcken, Ton (2007c) Anonymous voting and mini-

mal manipulability. Joumal of Economic Theory 135, 533-544.
Maus, Stefan; Peters, Hans; Storcken, Ton (2007d) Minimal manipulability:

Anonymity and unanimity. Social Choice and Welfare 29, 247-268.
Sanver, M. Remzi (2009) Strategy-proofness of the plurality mle over restricteddomains. Economic Theory 39, 461-471.
Sato, Shin (2011a) A sufficient condition for the equivalence of strategy-proofness

and nonmanipulability by preferences adjacent to the sincere one. Mimeo,Fukuoka University.
Sato, Shin (2011b) Strategy-proofness and the reluctance to make large lies: Thecase of weak orders. Forthcoming in Social Choice and Welfare.
Satterthwaite, Mark A. (1975) Strategy-proofness and Anow’s conditions: Exis-tence and correspondence theorems for voting procedures and social welfare

functions. Joumal of Economic Theory 10, 187-217.