An "Invisible Hand" in Votes
Hirofumi Yamamura
July 9, 2008, revised December 24, 2008

Abstract
We consider the problem of choosing a policy from a one-dimensional policy set
in which voters have single-peaked preferences. The purpose of this paper is to analyze the consequences of strategic votes under any given voting rule satisfying somenatural conditions; peak-only, unrestricted range, anonymity, continuity and weak(or strict) monotonicity. We show that, under any such rule, strategic votes must
result in an outcome recommended by a generalized median voter rule. Our results
suggest the existence of an “invisible hand” in votes through which strategic votes
lead to a “reasonable” outcome.
JEL Classi…cation: D78, D72, C70.
Key words: Generalized median voter rule, Average voting rule, Strategic manipulation, Existence of a strong Nash equilibrium, Coalition-proof Nash equilibrium,
Uniqueness of a Nash equilibrium, Implementation.

1

Introcuction

We consider the problem of choosing a policy from a one-dimensional policy set in which
voters have single-peaked preferences (Black [8]). In this environment, it is well known
that there exist strategy-proof, e¢ cient and anonymous voting rules, contrary to the
Gibbard-Satterthwaite theorem (Gibbard [16]; Satterthwaite [34]). A typical example ofsuch a rule is the median voter rule, which chooses the median of voters’peaks. Moreover,Moulin [28] provided a characterization of strategy-proof voting rules. He showed that avoting rule is strategy-proof, e¢ cient, and anonymous if and only if it is a “generalized
JSPS Research Fellow / Department of Social Engineering, Graduate School of Decision Science andTechnology, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku, Tokyo, 152-8552, Japan;
yamamura-h@soc.titech.ac.jp

1

median voter rule,” which chooses the median of n voters’ peaks and n

1 exogenous

parameters. Because of the existence of “reasonable” and strategy-proof voting rules,
many studies on this environment have focused on strategy-proof voting rules1 .
On the other hand, we have not paid much attention to what happens when a strategically manipulable voting rule is given. The purpose of this paper is to analyze theconsequence of strategic votes under any given voting rule that satis…es some naturalrequirements2 . The requirements we imposed on voting rules are peak-only, unrestricted
range, anonymity, continuity and weak (or strict) monotonicity. Through the analysis ofstrategic votes under a given voting rule, we obtain the two results described below.
First, we show that under any voting rule that satis…es all of these properties, containing a strict monotonicity condition, the set of Nash, coalition-proof Nash and strong-Nashequilibrium outcomes must be equivalent to an outcome recommended by a particular
generalized median voter rule (Theorem 1, (1).) Furthermore, we …nd that the set ofNash equilibria is “almost always” a singleton (Theorem 1, (3).) Second, we show thatwhen a strict monotonicity condition is weakened to a weak monotonicity condition, theset of coalition-proof Nash and strong-Nash equilibrium outcomes will still be equivalent
to a generalized median voter rule, while the set of Nash equilibrium outcomes no longer
coincides with a generalized median voter rule (Theorem 2, (1).)
Renault and Trannoy [30] [31] analyzed the properties of the average voting rule andshowed that the set of Nash and strong-Nash equilibrium outcomes under the averagevoting rule must be equivalent to a generalized median voter rule. This result can beobtained as a corollary of our Theorem 1, because the average voting rule satis…es theconditions on rules including strict monotonicity. Moreover, by applying our Theorem 2,
we can still expect the consequence of strategic votes under a voting rule that satis…es
weak monotonicity, but not strict monotonicity, for example, any generalized medianvoter rule.
Our two theorems reveal a strong position that generalized median voter rules possess.
Even if we do not use a generalized median voter rule, voters’ strategic votes result ina median voter rule, as if led by an “invisible hand (Smith [35]).” Since a generalized
median voter rule satis…es some desirable properties, such as e¢ ciency and anonymity,
this “invisible hand”has a role in ensuring a reasonable outcome. At the same time, our1
See for example, Barbera, Gul, and Stachetti [6], Ching [13], and so on. Sprumont [37], Barbera [5]and Jackson [19] o¤er surveys in this literature.
2
There have been some studies that analyzes the consequence of strategic manipulations in several
economic models. See, for example, Hurwicz [17] and Otani and Sicilian [29] in divisible goods economies,
Tadenuma and Thomson [38] and Fujinaka and Sakai [15] in indivisible goods economies, Bochet andSakai [9] in the division problem with single-peaked preferences.

2

theorems also have a negative aspect. They reveal that we cannot achieve any outcome,such as the average of voters’ peaks, other than what a generalized median voter rulechooses. Whatever rule we use, we cannot escape from generalized median voter rules.
In the context of implementation theory, Theorem 1 shows that a strictly monotone
voting rule can be regarded as a mechanism that implements a generalized median voter
rule in Nash equilibria with two good properties; uniqueness of Nash equilibrium androbustness to coalitional deviations3 . In particular, uniqueness of Nash equilibrium is
an attractive property for Nash implementation. When there are multiple Nash equilibria as in many other Nash type mechanisms, it is di¢ cult for voters to play a Nashequilibrium without communication even if voters expect the consequence of votes basedon Nash equilibria, because voters cannot determine which Nash equilibrium is played
without communication. In order to resolve such a problem, one solution is to construct
a mechanism in which uniqueness of Nash equilibrium is assured. In a mechanism witha unique Nash equilibrium, Nash equilibrium can have a role to be a focal point amongvoters.
One might say we do not need to consider Nash implementation of a generalized
median voter rule, because a strategy-proof rule, such as a generalized median voter
rule, must induce sincere voting. However, experimental studies, such as Kawagoe andMori [21], Attiyeh, Franciosi and Isaac [3], and Cason, Saijo, Sjostrom and Yamato [11]observe that strategy-proof mechanisms do not always work well because many subjects
actually do not reveal true information. Saijo, Sjostrom and Yamato [32] point out thatstrategy-proof mechanisms sometimes fail to induce truth-telling because many of them
have Nash equilibria that produce undesireble outcomes. To cope with such a fault of astrategy-proof mechanisms, they require double implementation in Nash and dominant
strategy equilibrium called secure implementation. However, they also …nd that in the
one-dimensional voting plobrem with single-peaked preferences, any generalized voter
rule has Nash equilibria that cause ine¢ cient outcomes. That is, there exists no e¢ cient,
anonymous and secure voting rule.
Thus, we have two ways to implement a generalized median voter rule. One way is
to use a strategy-proof rule that has bad Nash equilibria. The other way is to use a rulethat is not strategy-proof but can Nash implement the former. Our results imply thatstrictly monotone voting rules correspond to latter. If the problem of bad Nash equilibria
of a generalized median voter rule is serious, a strictly monotone voting rules can be a
3

There are some studies considering unique Nash implementation, such as Abreu and Sen [2], Abreu
and Matsushima [1], Sjostrom [33], and Trockel [39]. However, the necessary and su¢ cient condition for
unique Nash implementation has not been speci…ed. This paper investigates a new environment in whicha social choice rule can be implemented in a unique Nash equilibrium.

3good alternative.
The rest of this paper is organized as follows: in section 2, we introduce the modeland de…nitions; in section 3, we indicate our main result; in section 4, we interpret our
results; and in section 5, we state our conclusions.

2

Notation

2.1

Basic De…nitions

Let N

f1; 2;; ng be the set of voters. A[a; b] denotes the policy set. We assume

that this policy set A is a closed interval. For each voter i2N , i has a complete, transitive,
and single-peaked preference Ri over A. The symmetric and asymmetric parts of Ri aredenoted by Ii and Pi respectively. A preference relation Ri over A is said to be singlepeaked if there exists a peak p(Ri ) 2 [a; b] such that for each c; d 2 [a; b] c < dimplies dPi c and p(Ri )preferences4 .

c < d implies cPi d. Let Ri be the set of i’s single-peaked

A voting rule, denoted by f , is a function f :each preference pro…le R

2.2

p(Ri )Q

i2N Ri ! A which associates with

fRi gi2N a policy f (R) 2 A.

“Peak-Only” Voting Rules and their Properties

Throughout this paper, we pay attention to peak-only voting rules. A voting rule f is said
to be peak-only if for any R; R0 , f (R) = f (R0 ) whenever p(Ri ) = p(Ri0 ), for any i 2 N .
Q
If a voting rule is peak-only, we can regard a voting rule f : i2N Ri ! A as a function

f : [a:b]N ! A, that associates with each peak pro…le p 2 [a:b]N a policy f (p) 2 A.

In this paper, we additionally impose several natural conditions on peak only voting

rules. They are listed as follows.
Unrestricted Range5 : For any c 2 A, there exists p 2 [a; b]N such that f (p) = c.
Anonymity: For any p; p0 2 [a; b]N , such that 9i; j 2 N such that pi = p0j , pj = p0i andpk = p0k , 8k 2 N n fi; jg, f (p) = f (p0 ):1
Own-Peak Continuity: For any i 2 N , any p i 2 [a; b]N=fig , and any fpm
i gm=1such that lim pm= pi , lim f (pmi ; p i ) = f (pi ; p i ).
m!1 i
m!1
4
5

Note that we do not assume continuity of Ri .
Ching [13] calls this condition “voter sovereignty.”

4[a; b]

Own-Peak Weak Monotonicity: For any p 2 [a; b]N , any i 2 N , and any p0i
f (p0i ; p i )pi ,f (p).

Own-Peak Strict Monotonicity: For any p 2 [a; b]N , any i 2 N , and any p0i > pi ,f (p0i ; p i ) > f (p).

We illustrate some peak only voting rules that satisfy the conditions above.
The median voter rule: Suppose that the number of voters is odd. For each R 2
Q; p(Rn )); where m(x1 ;; xn ) denotes the median ofi2N Ri , f (R) = m(p(R1 );x1 ;; xn .

Generalized Median Voter Rule: There exist a1 ;; an 1 2 [a:b] ; such that for eachQ
R 2 i2N Ri , f (R) = m(p(R1 );; p(Rn ); a1 ;; an 1 ), where m(x1 ;; xn ; xn+1 ;;x2n 1 ) denotes the median of x1 ,, xn , xn+1 ,The average voting rule: For each R 2

Q, x2n 1 .

i2N Ri , f (R) =P

i2N p(Ri )n:Generalized average voting rule: There exists a continuous and strictly increasing
Q
function g : [na:nb] ! [a; b] such that g(na) = a; g(nb) = b, and for each R 2 i2N Ri ,P
f (R) = g( i2N p(Ri )):It can be easily checked that both generalized median voter rules and generalized
average voting rules satisfy unrestricted range, anonymity, own-peak continuity, and ownpeak weak monotonicity. On the other hand, generalized median voter rules do not satisfy
own-peak strict monotonicity, while generalized average voting rules satisfy it.
These properties are similar to those Bochet and Sakai [9] imposed on division rulesin the context of the division problem with single-peaked preferences. However, ourproperties are slightly di¤erent from them, because we replace e¢ ciency6 , which Bochet
and Sakai [9] imposed on division rules, with unrestricted range. It is clear that e¢ ciency
implies unrestricted range. We can obtain the same results even if e¢ ciency is weakened
to unrestricted range.
6

In the problem of one-dimensional voting, we can easily be checked that a rule f satis…es e¢ ciency
if and only if for any p 2 [a; b]N , there exists i; j 2 N , such that p(Ri ) f (p) p(Rj ).

5

2.3

Equilibrium Concepts

Under a voting rule f , each voter reports his own preference (or peak) and a policy isdecided according to the reported preference (or peak) pro…le. Then, each voter will
vote strategically so as to satisfy his own preference as much as possible. We expect theconsequences of strategic votes based on Nash equilibrium or its re…nements: coalitionproof Nash equilibrium and strong Nash equilibrium.
Given a peak-only rule f : [a; b]N ! A and a “true” preference pro…le R
Nv (f; R)fRi gi2I , letnox 2 [a; b]N j : 9i 2 N such that 9x0i 2 [a; b] ; f (x0i ; x i )Pi f (x)be the set of Nash equilibrium voting pro…les andN (f; R)f (Nv (f; N ))be the set of Nash outcomes of a voting rule f under a preference pro…le R.
We moreover introduce the concepts of coalition-proof Nash equilibrium (Bernheim,
Peleg and Whinston [7]) and strong Nash equilibrium (Aumann [4]), which take coalitional
deviations into consideration. When all voters can communicate with one another anddeviate coalitionally, it may be more natural to expect the consequences based on strongor coalitional-proof Nash equilibria than based on Nash equilibria.
First, let us de…ne a coalitional-proof Nash equilibrium. We say a coalition S

N

has a credible deviation x0S 2 [a; b]S at a voting pro…le x, if f (x0S ; x S ) Pi f (x), 8i 2 S
and there is no T S, T 6= S such that T has a credible deviation at (x0S ; x S ). A voting
pro…le x is a coalition-proof Nash equilibrium if there is no coalition that has a credible
deviation at x. The set of coalitional-proof Nash voting pro…les CNv (f; R) is de…ned asfollows.
CNv (f; R)nx 2 [a; b]N j : (9SoN such that S has a credible deviation at x) :Let
CN (f; R)f (CNv (f; N ))be the set of coalitional-proof Nash outcomes.
Next, let us de…ne a strong Nash equilibrium. We say a coalition S

N has adeviation x0S 2 [a; b]S at a voting pro…le x, if f (x0S ; x S ) Pi f (x), 8i 2 S. A voting pro…lex is a strong Nash equilibrium if there is no coalition that has a deviation at x. Then,6the set of strong Nash voting pro…les SNv (f; R) is de…ned as
SNv (f; R)nx 2 [a; b]N j : (9SoN such that S has a deviation at x:) ;andSN (f; R)f (SNv (f; R))

denotes the set of strong Nash outcomes.
By the de…nitions of these three equilibrium concepts, we can easily check that
SN (f; R)3

CN (f; R)

N (f; R); for any f and any R:

Results

The purpose of this paper is to analyze the consequence of strategic votes under any
given voting rule satisfying the properties introduced above. Before we proceed to our
discussion, we introduce nNf : [a; b]

1 numbers that are useful for our analysis. Given a rule

! A, for each k 2 f1; 2;fk;n

1g, de…ne fk 2 [a; b] asf (b;; b; a;; a):| {z } | {z }kn kThis fk indicates an outcome when k voters vote for the upper bound of the policy set
and the rest of voters vote for the lower bound. These n

1 numbers f1 ,,fn 1 help us

analyze the consequence of strategic votes, because they actually play the roles of n1

exogenous parameters of a generalized median voter rule.
Now, we provide our results of the analysis of strategic votes. Throughout this section,
we assume without a loss of generality that p(R1 )p(Rn ).

Proposition 1. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak weak monotonicity. Then, for any R 2 R,
there exists a voting pro…le x 2 SNv (f; R) such thatf (x ) = m(p(R 1 );; p(R n ); f 1 ;; f n 1 ):Proof of Proposition 1.
Case 1. fi 2 N j p(Ri ) = m(p(R1 );; p(Rn ); f1 ;7

; fn 1 )g = .

Since fj j fj = m(p(R1 );fj; p(Rn ); f1 ;; fn 1 )g =6

by the assumption and f1

fn 1 by own-peak weak monotonicity of f , there exists j 2 f1;

such thatjfi 2 N j p(Ri ) < fj gj + (jThen, since fj = m(p(R1 );1) = jfi 2 N j p(Ri ) > fj gj + (n; p(Rn ); f1 ;

1

;n

1g

j)7 :

; fn 1 ),we obtainjfi 2 N j p(Ri ) < fj gj = n

j and jfi 2 N j p(Ri ) > fj gj = j:

Let us consider the following voting pro…le x 2 [a; b]N such thatxi = a; 8i 2 f1;;n

jg and xi = b; 8i 2 fn

j + 1;; ng :

By de…nition of fj ,f (x) = fj = m(p(R1 );; p(Rn ); f1 ;; fn 1 ):We shall show that this voting pro…le x 2 [a; b]N is a strong Nash equilibrium. Suppose

there exist S

N and yS 2 [a; b]S such that f (yS ; x S )Pi f (x), 8i 2 S. We moreover

assume without a loss of generality that f (yS ; x S ) < f (x). Then,S

f1;

because f (x)Pi f (yS ; x S ), 8i 2 fn

j + 1;f (yS ; x S )

;n

jg ;

; ng : However, since xi = 0; 8i 2 S,

f (x), 8yS 2 [a; b]S ;by own-peak weak monotonicity, which contradicts f (yS ; x S ) < f (x). Hence, x 2 [a; b]Nmust be a strong Nash equilibrium.

Case 2. fi 2 N j p(Ri ) = m(p(R1 );; p(Rn ); f1 ;By assumption, there exists i 2 N such thatjfj 2 f1;7;n

1g j fjp(Ri )gj+(i 1) = jfj 2 f1;

Given a …nete set X, jXj denotes the cardinality of X:

8; fn 1 )g =6.

;n

1g j fjp(Ri )gj+(n i):

Then, since p(Ri ) = m(p(R1 );; p(Rn ); f1 ;; fn 1 ), we have

fn i

fn i+1 :p(Ri )Let us consider the following voting pro…le x i 2 [a; b]N=fig such thatxk = a; 8k 2 f1;;i

1g , and xk = b; 8k 2 fi + 1;

; ng .

Then, by own peak monotonicity, for any x0i 2 [a; b]f (a; x i ) = fn i

f (x0i ; x i )fn i+1 = f (b; x i );so there exists xi 2 [a; b] such that f (xi ; x i ) = p(Ri ) by own peak continuity. We shallshow that this voting pro…le x = (xi ; x i ) is a strong Nash equilibrium.

Suppose there exist S N and yS 2 [a; b]S such that f (yS ; x S )Pi f (x), 8i 2 S. We

moreover suppose without loss of generality f (yS ; x S ) < f (x). Then,S
because f (x)Rk f (yS ; x S ), 8k 2 fi;
f (yS ; x S )

f1; ;

i

1g ;

; ng. On the other hand, since xi = 0; 8i 2 S,
f (x), 8yS 2 [a; b]S

by own-peak weak monotonicity, which contradicts f (yS ; x S ) < f (x). Hence, x 2 [a; b]Nmust be a strong Nash equilibrium.

Proposition 1 establishes the existence of a strong Nash equilibrium whose outcome
corresponds to the median of n voters’peaks and n 1 parameters de…ned as f1 ,; and

fn 1 . The proof of Proposistion 1 is constructive. First, focus on the outcome m 2 [a; b]

which is the median of p(R1 ) ,Nx 2 [a; b],p(Rn ), f1 ,, fn 1 . Next, construct a voting pro…lesuch that

8
>
>
a
>
<
xi = xi such that f (x) = m(p(R1 );
>
>
>
:b

if p(Ri ) < m; p(Rn ); f1 ;; fn 1 ) if p(Ri ) = m
if p(Ri ) > m

and show that this voting pro…le x is a Nash equilibrium
Note that in the literature of non-cooperative game theory considering coalitional

9deviations, Proposition 1 reveals a new su¢ cient condition for the existence of a strong
Nash equilibrim. Su¢ cient conditions for the existence of a strong Nash equilibrium areprovided by several studies, such as Ichiishi [18] and Konishi, Breton, and Weber [23];however, we can apply none of them because our case does not satisfy any of them.

Proposition 2. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak weak monotonicity. Then, for any R 2 R,
and any x 2 CNv (f; R),f (x ) = m(p(R 1 );; p(R n ); f 1 ;; f n 1 ):Proof of Proposition 2. Suppose there exists x 2 CNv (f; R) such that f (x) >m(p(R1 );; p(Rn ); f1 ;; fn 1 ). LetS

fi 2 N j pim(p(R1 );T

fj 2 f1;;n

1g j fj; p(Rn ); f1 ;m(p(R1 );; fn 1 )g = f1;; p(Rn ); f1 ;; ig and; fn 1 )g = f1;; jg :

Consider x0S 2 [a; b]S such that x0i = a; 8i 2 S. Then, we havef (x0S ; x S )because jSj+jT j = i+jsuch thatf (a;; a; xk ;fn i

m(p(R1 );; p(Rn ); f1 ;; fn 1 ) < f (x);n, by the de…nition of m. Hence, there must exist k 2 f1;; xn ) = f (x), and f (a;; ig; a; xk+1 ;; xn ) < f (x):if f (a;; a; a; xk+1 ;; xn ) > p(Rk ); xn ) = p(Rk ) if f (a;; a; a; xk+1 ;; xn )Take x00k 2 [a; b] such that8<ax00k =:c; such that f (a;Then, since p(P1 )f (a;Next, we show that (a;; a; c; xk+1 ;p(Rk )f (a;; a; x00k ; xk+1 ;; a; x00k ; xk+1 ;; xn ) < f (x),; xn )Pi f (x), 8i 2 f1;; kg .

; a; x00k ) is a credible deviation of S 0

f1;

10

; k 0 g at x. Letp(Rk )

y(a;; a; x00k :x S 0 ).

If f (a;; a; xk+1 ;; xn ) > p(Rk ), thenf (zS 0 ; y S 0 ), 8zS 0 2 [a; b]S

f (y)

0

by own-peak weak monotonicity, so
0

S, 8yS 0 2 [a; b]S , 8i 2 S 0

f (y)Ri f (zS 0 ; y S 0 ), 8S 0
Hence, there exists no S 00

S 0 that has a credible deviation at y. Thus, (a;must be a credible deviation of S 0
If f (a;; a; xk+1 ;; xn )

f1;; a; x00k ); kgat x which contradicts x 2 CNv (f; R).

p(Rk ), then0f (y)Rk f (zS 0 ; xS ), 8zS 0 2 [a; b]S ,because f (y) = p(Rk ). Hence, if there exists S 00

S 0 that has a credible deviation at y,then k 2= S 00 . However, by own-peak weak monotonicity,f (zf1;;ng )f (y); 8zf1;

f1;;k 1g 2 [a; b];k 1g;k 1g ; yfk;

;ng ), 8zf1;

f1;;k 1g 2 [a; b];k 1g;k 1g ; yfk;;

which implies
f (y)Ri f (zf1;
Hence, there exists no S 00

S 0 that has a credible deviation at y. Thus, (a;must be a credible deviation of S 0

f1;

Therefore, if x 2 CNv (f; R), then f (x); a; x00k ); kg at x, which contradicts x 2 CNv (f; R).

m(p1 ;; pn ; f1 ;We can similarly show that if x 2 CNv (f; R), then f (x); fn 1 ).

m(p1 ;; pn ; f1 ;; fn 1 ):Proposition 1 and Proposition 2 together chatacterize coalitional proof Nash andstrong Nash outcomes. As a direct consequence of Proposition 1 and Proposition 2, we
can state that if a voting rule satis…es unrestricted range, anonymity, own-peak continuity,and own-peak weak monotonicity, thenSN (f; R) = CN (f; R) = fm(p(R1 );; p(Rn ); f1 ;which implies that strategic votes must result in m(p(R1 );; fn 1 )g ;; p(Rn ); f1 ;; fn 1 ) whencommunication among voters are allowed.
As a next step, we check whether any Nash outcome is equivalent to m(p(R1 );11; p(Rn );f1 ;; fn 1 ) or not. Generally speaking, this equivalence does not hold. The following

Example 1 establises the di¤erence between Nash outcomes and m(p(R1 );; p(Rn ); f1 ;;fn 1 ).

Example 1. Let N

f1; 2; 3g and f (x) = m(x1 ; x2 ; x3 ). Then, for any x 2 A,

(x; x; x) is always a Nash equiribrium, because for any i 2 f1; 2; 3g and any x0i 2 A,xm(x0i ; x i ) = x. Therefore, for any R 2 R, N (f; R) = A.

In order to establish the equivalence between Nash outcomes and m(p(R1 );f1 ;; p(Rn );; fn 1 ), we have to impose own-peak strict monotonicity on voting rules addition-

ally.

Proposition 3. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted

range, anonymity, own-peak continuity, and own-peak strict monotonicity. Then, for
any R 2 R, any x 2 N (f; R)
f (x) = m(p(R 1 );; f n 1 ):; p(R n ); f 1 ;Proof of Proposition 3. Suppose there exists x 2 Nv (f; R) such that f (x) > m(p1 ;f1 ;; pn ;; fn 1 ). LetSTfi 2 N j p(Ri )fj 2 f1;;nm(p(R1 );1g j fj; p(Rn ); f1 ;m(p(R1 );; fn 1 )g = f1;; p(Rn ); f1 ;; ig , and; fn 1 )g = f1;

First, let us show that xi = a, 8i 2 S if f (x) > m(p1 ;; jg :; p n ; f1 ;; fn 1 ) and0x 2 Nv (f; R). Suppose xi > a 9i 2 S. Then, there exists xi 2 (a; xi ) such thatp(Ri ) < f (x0i ; x i ) < f (x);by own-peak strict monotonicity and own-peak continuity. Hence,f (x0i ; x i )Pi f (x);which contradicts x 2 Nv (f; R).

12

However, if xi = a 8i 2 S,
f (x)

fn i

m(p(R1 );because jSj+jT j = i+j; p(Rn ); f1 ;; fn 1 ), 8xN nS 2 [a; b]N nSn, which contradicts f (x) > m(p(R1 );; p(Rn ); f1 ;; fn 1 ).

Hence, we obtain for any x 2 Nv (f; R),f (x)m(p(R1 );; p(Rn ); f1 ;; fn 1 );We can similarly show that for any x 2 Nv (f; R);f (x)m(p(R1 );; p(Rn ); f1 ;; fn 1 ):Combining Proposition 3 with Proposition 1, we establish the equivalence among
Nash outcomes, coalition-proof Nash outcomes and the strong Nash outcomes if a voting
rule additionally satis…es own-peak strict monotonicity. They together imply that if avoting rule satis…es unrestricted range, anonymity, own-peak continuity, and own-peakstrict monotonicity, thenSN (f; R) = CN (f; R) = N (f; R) = fm(p(R1 );; p(Rn ); f1 ;; fn 1 )g :Hence, under a strictly monotone voting rule, strategic votes must result in m(p(R1 );p(Rn ); f1 ;;; fn 1 ), whether voters is allowed to communicate with one another or not.

Proposition 4. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak weak monotonicity. Then, for any R 2 R,
SNv (f; R) = CNv (f; R):

Proof of Proposition 4. It is su¢ cient to show that there must exist S 0Na credible deviation at x 2 [a; b] , whenever there exists SN

x 2 [a; b] . Suppose that S

N which has

N which has a deviation atS

N has a deviation y 2 [a; b] at x 2 [a; b]N . We moreover

assume without a loss of generality f (yS ; x S ) < f (x). Then, for any i 2 S, p(Ri ) < f (x).
Let S

fi1 ;

; ik g such that pi1

pik : Consider yS 2 [a; b]S , such that yi = a,13

8i 2 S. Then, there must exist h 2 f1;
f (yi )i2fi1 ;;ih

f (yi )i2fi1 ;Let S 0

zih =

8
<a

fi1 ;

1g

; kgsuch that

; (xi )i2N=fi1 ;;ih;ih g ; (xi )i2N=fi1 ;

1g

;ih g

= f (x), and< f (x); ih g and take (zi )i2S 0 such that zi = a, 8i 2 fi1 ;; ih 1 g, andif f fzi gi2S 0 =fih g ; a; fxi gi2N=S 0 > p(Rih ):c; such that f fz g 0
i i2S =fih g ; c; fxi gi2N=S 0 = p(Rih ) if f fzi gi2S 0 =fih g ; a; fxi gi2N=S 0

We can show that fzi gi2S 0 is a credible deviation of S 0 at x in a similar way with the proofof Proposition 2.

Proposition 4 states a voting pro…le x is a strong Nash equilibrium whenever x is acoalition-proof Nash equilibrium. Note that by Proposition 1 and Proposition 4 we …nd
a new su¢ cient condition for the equivalence between strong Nash and coalition-proof
Nash equilibria. Konishi, Breton, and Weber [24] showed su¢ cient conditions for theequivalence between these two solutions, but we cannot apply them to our case.

Proposition 5. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak strict monotonicity. Then, for any R 2
R, any x 2 N (f; R)

SNv (f; R) = CNv (f; R) = Nv (f; R):

Proof of Proposition 5. It su¢ ces to show that x 2= Nv (f; R) whenever x 2= SNv (f; R).

Suppose that S

N has a deviation y 2 [a; b]S at x 2 [a; b]N . We moreover assume

without a loss of generality f (yS ; x S ) < f (x). Then, by own-peak strict monotonicity,
there exists i 2 S such that yi < xi and P (Ri ) < f (x). By own-peak strict monotonicity

and own-peak continuity, there exists zi 2 (yi ; xi ) such that f (zi ; x i ) 2 (P (Ri ); f (x)).
Hence, f (zi ; x i )Pi f (x), that implies x 2= Nv (f; R).

Proposition 5 states that the set of Nash equilibria is also equivalent to that of strong
Nash and coalition-proof Nash equilibria if a voting rule additionally satis…es own-peakstrict monotonicity.

14p(Rih )

Proposition 6. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted

range, anonymity, own-peak continuity, and own-peak strict monotonicity. Then, for any
R 2 R, such that jfi 2 N j p(Ri ) = m(p(R1 );; p(Rn ); f1 ;; fn 1 )gj

1; Nv (f; R) isa singleton.

Proof of Proposition 6. Since non-emptiness of Nv (f; R) has been proved in Proposition 1, it su¢ ces to show that Nv (f; R) is a singleton.
Case 1. fi 2 N j p(Ri ) = m(p(R1 );Let S

fi 2 N j p(Ri ) < m(p(R1 );; p(Rn ); f1 ;; fn 1 )g = .

; p(Rn ); f1 ;; fn 1 )g = f1;

then by Proposition 4,

f (x) = m(p(R1 );; p(Rn ); f1 ;; ig. If x 2 Nv (f; R),; fn 1 ):If x 2 Nv (f; R), then we must have xi = a, 8i 2 S, because for any x0i 6= a;p(Ri ) < f (x) < f (x0i ; x i );which implies that f (x)Pi f (x0i ; x i ).
Similarly, we have xi = b, 8i 2 N=S. Thus, if x 2 Nv (f; R), then xi = a, 8i 2 S andxi = b, 8i 2 N=S. .

Case 2. jfi 2 N j pi = m(p1 ;; pn ; f1 ;; fn 1 )gj = 1

Take i 2 N such that p(Ri ) = m(p(R1 );; p(Rn ); f1 ;; fn 1 ). Then, if x 2 Nv (f; R),

we must havexi = a; 8k 2 f1;
because p(Rk ) < f (x) = m(p(R1 );larly, if x 2 Nv (f; R),;i; p(Rn ); f1 ;xk = b; 8k 2 fi + 1;

1g ;; fn 1 ), 8k 2 f1;;i

1g. Simi-; ng :

Thus, we obtain that if x 2 Nv (f; R), thenf (x i ; a) = fn if (x)fn i+1 = f (x i ; b):

By own-peak strict monotonicity and own-peak continuity, there exists a unique xi 2 [a; b]such thatf (xi ; x i ) = pi 2 [fn i ; fn i+1 ] :15

Since f (x0i ; x i ) 6= pi , for any x0i 6= xi , f (xi ; x i )Pi f (x0i ; x i ), which indicates that xi = xi ,if x 2 Nv (f; R). Therefore, if x 2 Nv (f; R), thenx = (a;; a; xi ; b;

; b):

Proposition 6 ensures uniqueness of Nash equilibrium under a strictly monotone voting rule. Since the case jfi 2 N j p(Ri ) = m(p(R1 );; p(Rn ); f1 ;; fn 1 )gj

2 holds

are non-generic, the set of Nash equilibrium voting pro…les is “almost always”a singleton.
However, there may be multiple Nash equilibria if there are not less than 2 persons whose
peaks agree with the median of p(R1 );; p(Rn ); f1 ;; fn 1 . The following Example

2 illustrates the case in which there are multiple Nash equilibria.

Example 2. Let N

x1 +x2 +x3.
f1; 2; 3g, p(R1 ) = p(R2 ) = p(R3 ) = a+b2 and f (x) =3Then, we can easily check that for any x such that x1 +x32 +x3 =

a+b
2 ,

x is a Nashequilibrium.

Now, we summarize our analysis on the consequence of strategic votes as the following
Therem 1 and Theorem 2.

Theorem 1. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak strict monotonicity. Then, for any R 2

R, the following (1), (2), and (3) hold.

(1) SN (f; R) = CN (f; R) = N (f; R) = fm(p(R1 );(2) SNv (f; R) = CNv (f; R) = Nv (f; R) 6= :; p(Rn ); f1 ;(3) Nv (f; R) is a singleton if jfi 2 N j p(Ri ) = m(p(R1 );; fn 1 )g.

; p(Rn ); f1 ;; fn 1 )gj

1.

Proof of Theorem 1. (1) is implied by Proposition 1 and Proposition 3. (2) is implied
by Proposition 1 and Proposition 5. Proposition 6 directly implies (3).
Theorem 2. Let f : [a; b]N ! A be any voting rule that satis…es unrestricted range,

anonymity, own-peak continuity, and own-peak weak monotonicity. Then, for any R 2 R,
the following (1) and (2) hold.

(1) SN (f; R) = CN (f; R) = fm(p(R1 );; p(Rn ); f1 ;16

; fn 1 )g :

(2) SNv (f; R) = CNv (f; R) 6= :Proof of Theorem 2. (1) is implied by Proposition 1 and Proposition 2. (2) is implied
by Proposition 1 and Proposition 4.

4

Discussions

4.1

Implementation of Generalized Median Voter Rules

Theorem 1 reveals that any genaralized median voter rule m(p(R1 ;such that a < a1 <; p(Rn ); a1 ;; an 1 );< an 1 < b can be triply implemented in strong Nash, coalition-

proof Nash, and Nash equilibria by a strictly monotone voting rule. For example, let usPuse a generalized average voting rule f (x) = g( i2N xi ) such that g((n k)a + kb) = ak ,for each k 2 f1;;n1g. Then, by Theorem 1, any Nash, coalition-proof Nash, andstrong Nash equilibrium of this generalized median rule must result in the median ofp(R1 ),; p(Rn ); a1 ;; an 1 . Moreover, a strictly monotone rule has attractive prop-

erties as a Nash mechanism: uniqueness of Nash equilibrium and robustness to coalitional
deviations. When uniqueness of Nash equilibrium is assured, the unique equilibrium canhave a role of a focal point among voters. When a mechanism can triply implementation a social choice rule in strong Nash, coalition-proof Nash, and Nash equilibria, social
planners need not be worried about coalitional deviations, as well as individual deviations.
In addition, Kawasaki and Yamamura [22] …nd out that the uniquie Nash equilibrium under a generalized average voting rule is dynamically stable in the sense similar to
Cournot stability, by using the theory of potential games 8 . It is known that under a potential game, any best response path converges to Nash equilibria (Monderer and Shapley[27]; Jensen [20]). They show that a voting situation under a generalized average voting
rule is a kind of a potential game and so that stability of Nash equilibrium is assured.
They also point out that generalized median voter rules do not have this property.
One might think that we do not have to study Nash implementation of generalized
median voter rules because they must induce truth-telling. However, this expectation isdenied by experimental studies, such as Kawagoe and Mori [21], Attiyeh, Franciosi and
8

Note that the class of generalized average voting rules is a subclass of strictly monotone voting rules.
Kawasaki and Yamamura [22] showed only stability of generalized average voting rules. However, it canbe easily checked that the class of rules that can be Nash implemented by a generalized average voting
rule is equivalent to the class of rules that can be Nash implemented by a strictly monotone voting rule.

17

Isaac [3], and Cason, Saijo, Sjostrom and Yamato [11]. They observe that few subjects
reveal true information under some strategy-proof mechanisms.
Saijo, Sjostrom and Yamato [32] point out that this is because many strategy-proof
mechanisms has a drawback of having Nash equilibria that cause undesireble outcomes.
They also show that any generalized median voter rule has this drawback. For example,
as seen in Example 1, the set of Nash outcomes under the median voter rule covers theentire policy set. This means that a direct revelation mechanism of the median voter rulefails to implement itself in Nash equilibria.
Confronting such a fault of a direct revelation mechanism of a generalized median voter
rule, we have two ways to implement it. One way is to keep using a direct revelation
mechanism. Though it has bad Nash equilibria that cause undesirable outcomes, it
implements itself in that dominant strategy equilibria. The other way is to use a strictly
monotone voting rule. Though it is not strategy-proof, it can exclude bad Nash equilibria.
Especially, a generalized average voting rule ensures that voters learn to play a Nashequilibrium. We need to explore laboratory experiments to observe how serious the
problem of bad Nash equibibria of a generalized median voter is and which works better9 .
The comparison among rules mentioned here is summarized by the following table 1.

Table 1: Comparison of Voting Rules
Generalized

Generalized

StrictlyMedian Rules

Average Rules

Monotone Rules

Strategy-proofness

yes

no

no

Nash Implemantation

no

yes

yes

Uniqueness of NE

no

yes

yes

Dynamic Stability of NE

no

yes

Robustness to Coalitional Deviations

yes

yes

4.2

yes

Relation to Dasgupta-Hammond-Maskin Theorem

Dasguputa, Hammond, and Maskin [14] proved that a single-valued social choice rule
must be strategy-proof if and only if it satis…es Maskin monotonicity, a necessary condi9

Bochet, Saijo, Sakai, Yamamura and Yamato [10] conduct an experiment for the division problem withsingle-peaked preferences to compare the performance of the uniform rule with that of the proportional
rule that Nash implements the uniform rule. They observe that the proportional rule sometimes yields
the outcomes closer to the uniform allocation than the uniform rule. They report this …nding in an
incomplete information setting in which each subject is imformed of only his own payo¤ function.

18

tion for Nash implementation (Maskin [25] [26].) Hence, it is not unnatural to regard our
results as a corollary of Dasgupta, Hammond, and Maskin [14] and Moulin [28], because
any Nash implementable and single-valued social choice rule must be strategy-proof.
However, this intuition is not correct for the reasons given below.
First, the unique existence of Nash equilibrium outcomes in a strict monotone rule is
not derived from Dasgupta, Hammond and Maskin [14]. Second, even if there exists a
unique Nash equilibrium outcome, Dasgupta-Hammond-Maskin theorem cannot conclude
that this unique outcome is e¢ cient or anonymous, because there are some strategy-proof
rules that are not e¢ cient and anonymous10 .

4.3

Comparison with Bochet and Sakai [9]Bochet and Sakai [9] analyzed the consequence of strategic manipulations in the division
problem with single-peaked preferences under a given division rule and obtained thefollowing two results.
(1) Under any division rule satisfying own-peak strict monotonicity, e¢ ciency, and some
supplementary conditions, the set of strong Nash, e¢ cient Nash, and Nash equilibriumoutcomes coincides with the uniform rule, which is the unique division rule satisfying
strategy-proofness, e¢ ciency, and anonymity (Sprumont [36]; Ching [12].)(2) When own-peak strict monotonicity is weakened to own-peak weak monotonicity,
the set of strong Nash and e¢ cient Nash equilibrium outcomes still coincides with theuniform rule.
Our results are similar to those of Bochet and Sakai [9], because both their paper andthis paper show the equivalence between the consequence of strategic manipulations ande¢ cient, anonymous, and strategy-proof rules. However, our results are slightly di¤erent
from theirs. The di¤erences are summarized as follows:First, we have provided a su¢ cient condition for uniqueness of Nash equilibria, while
they did not. Finding mechanisms that “almost always” has a unique Nash equilibrium
is potentially one of our main …ndings. Second, we prove the general equivalence between
the set of coalition-proof Nash equilibrium outcomes and a generalized median voter rule.
Though they also suggest this equivalence, they leave this question open. Third, as statedin section 2.2, they impose e¢ ciency on division rules, while we impose only unrestricted
range instead of e¢ ciency on voting rules.
On the other hand, we cannot show the equivalence between the set of e¢ cient Nashequilibrium outcomes and a generalized median voter rule. As seen in example introduced
10
For example, consider voting rules f and g such that f (x) = xi , g(x) = c, for each x 2 [a; b]N : Clearlyboth f and g are strategy-proof, but f fails anonymity and g fails e¢ ciency.

19

in Section 4.1, a weakly monotone voting rule can have e¢ cient Nash equilibria whatcauses outcomes other than what a generalized median voter rule chooses.

5

Concluding Remarks

Through the analysis of strategic votes, we reveal the strong position that generalized
median voter rules possess. They are not only strategy-proof but also always expected
as an outcome of strategic manipulation under any given voting rule satisfying mild
conditions. Since generalized median voter rules are e¢ cient and anonymous, if onlye¢ ciency and anonymity matter, we can conclude that individual voting activities leadto an ethically desirable outcome through an “invisible hand.” However, this result also
has a negative aspect. This "invisible hand" makes us unable to escape from a generalized
median voter rule, whatever rule we use.
In the context of implementation theory, we …nd out that any generalized median voter
rule m(p(R1 );; p(Rn ); a1 ;; an 1 );such that a < a1 << an 1 < b, can be Nash

implemented by a strictly monotone voting rule that has good properties: uniquenessof Nash equilibrium and robustness to coalitional deviations. However, this mechanism
does not have a dominant strategy as in the direct revelation mechanism of a generalized
median voter rule. On the other hand, as pointed by Saijo, Sjostrom and Yamato [32],since a direct revelation mechanism of a generalized median voter rule has “bad” Nashequilibria that cause undesirable outcomes, it does not implement itself in Nash equilibria.
As shown by Saijo, Sjostrom and Yamato [32], any generalized median voter rulecannot be doubly implemented in both Nash and dominant strategy equilibria. Then, inorder to implement it, we should use either a Nash mechanism or a strategy-proof mechanism as a second best way. It is theoretically and empirically unclear which mechanism
works better to implement a generalized median voter rule. To study this issue, we needto explore laboratory experiments as done by Cason, Saijo, Sjostrom and Yamato [11]and Bochet, Saijo, Sakai, Yamamura and Yamato [10].

Acknowledgement. I am grateful to Herve Moulin, Tatsuyoshi Saijo, Tomas Sjostrom,John Weymark and Takehiko Yamato for their valuable advices and discussions. I also
thank participants of the 9th International Meeting of the Society for Social Choice andWelfare at Concordia University, the 27th Arne Ryde Symposium at Lund University,and seminars at UCSD, Tokyo Institute of Technology and Waseda University for helpfulcomments. This research is …nancially supported by the Society for Promotion of Science
under Grand-in-Aid for JSPS Fellows 20009834, which is gratefully acknowledged.
20References[1] Abreu, D. and Matsushima, H. (1992) “Virtual Implementation in Iteratively Undominated Strategies: Complete Information,” Econometrica, 60, pp. 993-1008.
[2] Abreu, D. and Sen, A. (1991) “Virtual Implementation in Nash Equilibrium,”Econometrica, 59, pp. 997-1021.
[3] Attiyeh, G., Franciosi, R. and Isaac, R.M. (2000) "Experiments with the pivotal
process for providing public goods," Public Choice, 102, pp. 95-114.
[4] Aumann, R. (1959) “Acceptable Points in General Cooperative n-Person Games,”in
Kuhn, H.W., and Luce, R.D., eds. Contribution to the Theory of Games, pp.287-324,
Princeton University Press.
[5] Barbera, S. (2001) “An Introduction to Strategy-Proof Social Choice Functions,”
Social Choice and Welfare, 18, 619-653.
[6] Barbera, S., Gul, F., and Stachetti, E. (1994) “Generalized Median Voter Schemes
and Committees,” Journal of Economic Theory, 61, 262-89.
[7] Bernheim, D., Peleg, B., and Whinston, M. (1987) “Coalition-Proof Nash Equilibria
I. Concepts,” Journal of Economic Theory, 42, 1-12.
[8] Black, D. (1948) “On the Rationale of Group Decision Making,”Journal of Political
Economy, 56, pp. 23-34.
[9] Bochet, O. and Sakai, T. (2007) “Preference Manipulations Lead to the Uniform
Rule,” mimeo.
[10] Bochet, O., Saijo, T., Sakai, T., Yamamura, H. and Yamato, T. (2008) "Manipulation of Preferences in Rationing Problems: Experimental Evidence," mimeo.
[11] Cason, T., Saijo, T., Sjostrom, T., and Yamato, T. (2006) “Secure Implementation
Experiments: Do Strategy-Proof Mechanisms Really Work?,”Games and Economic
Behavior, 57, pp. 206-235.
[12] Ching, S. (1994) “An Alternative Characterization of the Uniform Rule,” Social
Choice and Welfare, 40, pp. 57-60.
[13] Ching, S. (1997) “Strategy-Proofness and ‘median voters,”’International Journal ofGame Theory, 26, pp. 473-490.
21

[14] Dasgupta, P., Hammond, P., and Maskin, E. (1979) “The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility,” Review of
Economic Studies, 46, pp. 185-216.
[15] Fujinaka, Y. and Sakai, T. (2007). "The manipulability of fair solutions in assignmentof an indivisible object with monetary transfers," Jourlal of Public Economic Theory,9, pp. 993-1011.
[16] Gibbard, A. (1973) “Manipulation of Voting Schemes: A General Result,” Econometrica, 41, pp. 587-601.
[17] Hurwicz, L. (1978). “On the Interaction between Information and Incentives in Organization,”in Communications and Interactions in Society (Eds. by K. Krippendorf),
New York, Scienti…c Publishers.
[18] Ichiishi, T. (1993) “The Cooperative Nature of the Firm,” Cambridge University
Press.
[19] Jackson, M.O. (2003) “Mechanism Theory,” in Optimization and Operations Research, (Eds. by U. Derigs), in the Encyclopedia of Life Support Systems, EOLSS
Publishers.
[20] Jensen, M. K. (2007) "Stability of Pure Strategy Nash Equilibrium in Best-reply
Potential Games," mimeo.
[21] Kawagoe, T., and Mori, T. (2001). "Can the pivotal mechanism induce truth-telling?
An experimental study," Public Choice 108, pp. 331-354.
[22] Kawasaki, R. and Yamamura, H. (2008) "Poteitial Mechanisms in Single-Peaked
Environments: Average Rules and Proportional Rules," mimeo.
[23] Konishi, H., Breton, M., and Weber, S. (1997a) “Equilibria in a Model with Partial
Rivalry,” Journal of Economic Theory, 72, pp. 225-237.
[24] Konishi, H., Breton, M., and Weber, S. (1997b) “Equivalence of Strong and
Coalition- Proof Nash Equilibria in Games without Spillovers,” Economic Theory,9, pp. 97-113.
[25] Maskin, E. (1979) “Incentive Schemes Immune to Group Manipulation,” mimeo.
[26] Maskin, E. (1999) “Nash Equilibrium and Welfare Optimality,”Review of Economic
Studies, 66, pp. 23-38.
22

[27] Monderer, D. and Shapley, L. S., 1996. Potential Games. Games and Economic
Behavior, 14, pp. 124-143.
[28] Moulin, H. (1980) “On Strategy-Proofness and Single Peakedness,” Public Choice,35, pp. 437-455.
[29] Otani, Y. and Sicilian, J. (1982). "Equilibrium and Walras Preference Game," Journal of Economic Theory, 29, pp. 365-374.
[30] Renault, R. and Trannoy, A. (2004) “Assesing the Extent of Strategic Manipulations
for the Average Voting Rule,” mimeo.
[31] Renault, R. and Trannoy, A. (2005) “Protecting Minorities through the Average
Voting Rule,” Journal of Public Economic Theory, 7, pp. 169-199.
[32] Saijo, T., Sjostrom, T., and Yamato, T. (2007) “Secure Implementaion,”Theorecial
Economics, 2, pp. 203-229.
[33] Sjostrom, T. (1994) “Implementation in Undominated Nash Equilibria without Integer Games,” Games and Economic Behavior, 6, pp. 502-511.
[34] Satterthweite, M.A. (1975) “Strategy-Proofness and Arrow’s Conditions: Existence
and Corresponding Theorems for Voting Procedures and Social Welfare Functions,”
Journal of Economonic Theory, 10, pp. 187-217.
[35] Smith, A. (1776) “An Inquiry into the Nature and Causes of the Wealth of Nations,”
University of Chicago Press.
[36] Sprumont, Y. (1991) “The Division Problem with Single-Peaked Preferences: A
Characterization of the Uniform Allocation Rule,” Econometrica, 59, pp. 509-519.
[37] Sprumont, Y. (1995) “Strategy-Proof Collective Choice in Economic and Political
Enviornments,” Canadian Journal of Economics, 28, pp. 68-107.
[38] Tadenuma, K. and Thomson, W. (1995). "Games of Faie Division," Games andEconomic Behavior 9, pp. 191-204.
[39] Trockel, T. (1999) “Unique Nash Implementation for a Class of Bargaining Solutions,” International Game Theory Review, 1, pp. 267-272.

23