GCOE Discussion Paper Series
Global COE Program

Human Behavior and Socioeconomic Dynamics
Discussion Paper No.49

Candidate Stable Voting Rules for Separable Orderings

Kentaro Hatsumi

May 2009

GCOE Secretariat
Graduate School of Economics

OSAKA UNIVERSITY

1-7 Machikaneyama, Toyonaka, Osaka, 560-0043, Japan

Candidate Stable Voting Rules
for Separable Orderings∗
Kentaro Hatsumi†First Version: January 22, 2009This Version: April 23, 2009

Abstract: We consider the election model in which voters choose a subset from the set of candidates. Both voters and candidates are assumed topossess preferences with separable strict orderings. We investigate a rule satisfying candidate stability, which is the requirement to deter any candidatefrom strategic withdrawal. We show that a rule satisﬁes candidate stability
if and only if it satisﬁes independence of the selection for each candidate.
Keywords: multiple-winner election, strategic candidacy, separable preference, voting by committees
JEL Classiﬁcation Numbers: D71, D72∗

I thank Shigehiro Serizawa, William Thomson and other seminar participants at Universities of Osaka and Rochester for their helpful comments and suggestions. I gratefully
acknowledge the ﬁnancial support from the Japan Society for the Promotion of Science
via the Research Fellowship for Young Scientist.
†
Institute of Social and Economic Research, Osaka University. 6-1, Mihogaoka, Ibaraki,
567-0047, Japan. E-Mail: hatsumi at iser.osaka-u.ac.jp1

1

Introduction

This paper investigates the election model in which voters can select any
subset from the set of candidates. Examples are where the members ofa club select new comers, or where the executive committee of a society
select new members. Barberà et al. (1991) ﬁrst study this model under
the assumption that voters possess preferences with separable strict orderings over the power set of the sets of candidates. In this paper, we extend
their model so that not only voters but candidates have preferences and theactual running candidates is variable, and we investigate a rule satisfying“candidate stability”. Candidate stability requires that for any candidate,standing in the election with any set of running candidates is at least as desirable as withdrawing from it. Dutta et al. (2001) suggests the importanceof this property as a basis of the study for any election model. If an election
rule satisﬁes candidate stability, all candidates may stand in the election. If
an election rule does not satisfy candidate stability, candidates’ strategies
whether to run the election at the pre-election stage may aﬀect the rule andhence the rule designer has to take it into account.
Dutta et al. (2001) ﬁrst study this property in the single-winner election
where preferences are unrestricted, and shows that a rule satisfying candidate stability and unanimity is only dictatorial.1 By comparison, our main
result is a possibility result. We show that a rule satisﬁes candidate stability
if and only if it satisﬁes the following independence condition. Suppose in
the election with some set of running candidates and some preference proﬁleof voters, a candidate wins. Then she also should win in the election withany set of running candidates she belongs to and any preference proﬁle thatis equivalent to the previous proﬁle in the comparison of herself and the nulloutcome. This is a quite parallel work to Barberà et al. (1991). They impose
strategy-proofness, which requires non-manipulability by voters, and derive
independence of the selection for each candidate as a part of voting by committees that they characterize. Meanwhile, we impose non-manipulabilityof candidates and derive the similar independence condition.
Related literature includes Berga et al. (2004, 2006). They consider
similar models to ours in which voters are existing members of a society and1

We omit the descriptions of standard properties in Introduction. See them in theoriginal literature.

2

have exit options. They study stability of the existing members while we
focus on the stability of candidates as new entrants. Literature on candidate stability includes Ehlers and Weymark (2003), Eraslan and McLennan(2004), Rodrı́guez-Álvarez (2005, 2006), and Samejima (2005, 2007).
The structure of the rest of this paper is as follows. Section 2 states themodel and the main result. Section 3 gives a short discussion and conclusion.
The appendix includes the proof of the main result.

2

The model and the result

Let C ≡ {1, 2, · · · , c} be the set of (prospective) candidates with c ≥ 1.
We refer to a candidate who actually stands on the election as a runningcandidate. Let V ≡ {c + 1, c + 2, · · · , c + v} be the set of voters withv ≥ 1. For simplicity, we assume C ∩ V = Ø. For a voter or a candidate
i ∈ C ∪ V , let Pi denote her preference, which is a complete, transitive,
and asymmetric binary relation over 2C . We assume that any preference Pi
satisﬁes the following restrictions.
Separability: For all i ∈ C ∪ V , all x ∈ C, and all Y ⊆ C\{x}, we haveY ∪ {x} Pi Y ⇐⇒ {x} Pi Ø.
Additivity: Pi has an additive numerical representation.2
We refer to a preference satisfying separability and additivity as an additively separable preference. Let DS denote the domain of all such preferences. All preferences of voters are assumed to be in the domain DS .
In addition to additive separability, we impose another restriction on thepreferences of the candidates: for all x ∈ C, {x} Px Ø. Since without it, theconcept of “candidate stability” is not meaningful, we refer to it as the minimal restriction for candidates’ preferences. Let DM denote the domain of
all additively separable preferences satisfying the restriction. A preference
proﬁle is a c + v tuple of preferences P = (P1 , · · · , Pc , Pc+1 , · · · , Pc+v ) ∈c × D v . Let i, j ∈ C ∪ V . Let (P 0 , P ) ∈ D c × D v denote the preference
DM
−i
i
S
M
S
c ×D vproﬁle obtained from P by replacing Pi with Pi0 , (Pj00 , Pi0 , P{−i,j} ) ∈ DM
S

denote the proﬁle obtained from (Pi0 , P−i ) by replacing Pj with Pj00 , and soon. Let Pi |X denote the preference relation over X ⊆ C induced by Pi ∈ DS .
2

Separability and additivity are independent in our deﬁnition. See Barberà et al.
(1991) and Berga et al. (2004) for examples of that separability does not imply additivity.

3

Similarly, let P |X denote the preference proﬁle over X ⊆ C induced byc × Dv .
P ∈ DMS
c × D v → 2C . Following Dutta et
A rule is a function ϕ : 2C × DMS

al. (2001), a rule ϕ is assumed to satisfy the following three properties.
First, winners should be chosen from the set of running candidates. Second,
only voters’ preferences matter. Third, only preferences over the runningcandidates matter.
c × D v , we have ϕ(X, P ) ⊆ X.
Feasibility: For all X ∈ 2C and all P ∈ DM
S

Independence of nonvoters’ preferences: For all X ∈ 2C and all P, P 0 ∈c × D v such that for all i ∈ V , P = P 0 , we have ϕ(X, P ) = ϕ(X, P 0 ).
DM
i
i
S

Independence of irrelevant alternatives: For all X ∈ 2C and all P, P 0 ∈c × D v such that P | = P 0 | , we have ϕ(X, P ) = ϕ(X, P 0 ).
DM
X
X
S

The formal deﬁnition of “candidate stability” of a rule is given as follows.
c ×
Candidate stability: For all X ∈ 2C \{Ø}, all x ∈ X, and all P ∈ DM

DSv , we have ϕ(X, P ) Px ϕ(X\{x}, P ) or ϕ(X, P ) = ϕ(X\{x}, P ).3
We claims that candidate stability is equivalent to the following independence condition. Suppose that for some set of running candidates andsome preference proﬁle, a candidate wins. Then she also should win for any
set of running candidates she belongs to and any preference proﬁle that isequivalent to the previous proﬁle in the comparison of herself and the nulloutcome.
Independence: For all X, Y ∈ 2C \{Ø}, all x ∈ C such that x ∈ X andc × D v such that P |0x ∈ Y , and all P, P 0 ∈ DM{{x},Ø} = P |{{x},Ø} , we haveSx ∈ ϕ(X, P ) ⇐⇒ x ∈ ϕ(Y, P 0 ).

Proposition 1. A rule satisﬁes candidate stability if and only if it satisﬁes
independence.4
Proof of Proposition 1. See the appendix.

3

The original deﬁnition of candidate stability in Dutta et al. (2001) is slightly weaker
than ours in the sense that they consider stability only when running candidates equalcandidates (i.e., X = C). Our deﬁnition of candidate stability is similar to “no-exitstability” in Samejima’s (2007) model with single-peaked preference domain.
4
Ju (2003) extends Barberà et al.’s (1991) model to allow indiﬀerences of voters’ preferences. This proposition holds even in Ju’s (2003) model. The proof is the same.

4

The intuition behind the proof is as follows. Since we impose the minimal restriction on candidate preferences, there exists a candidate who prefers
another candidate to win no matter whether the other candidates, including
herself, are elected. There also exists a candidate who prefers another candidate not to win no matter whether the other candidates, including herself,
are elected. If independence is violated, a candidate with such a preference
may be better oﬀ by not running. This violates candidate stability.

3

Discussion and concluding remarks

Before concluding this paper, we note that if we drop the minimal restriction
for candidates’ preferences and impose a stronger but natural restriction for∗ ( Dthem, Proposition 1 fails. Let DM
M be the domain of all additively

separable preferences satisfying the following restriction for candidates. For
all x ∈ C and all Px ∈ DS∗ , {x} Px Ø and for all y ∈ C\{x}, {x} Px {y}. This
states that any candidate prefers herself to any other candidate. A counterexample to the equivalent statement of Proposition 1 in this domain is thefollowing.
Example 1. Let C ≡ {1, 2} and V ≡ {3}. Let ϕ be a rule such that∗2 × D , 1 ∈ ϕ(C, P ) and 1 ∈ ϕ({1}, P ),(i) for any P ∈ DM
3S(ii) if {1} P3 Ø, 2 ∈ ϕ(C, P ) and if Ø P3 {1}, 2 6∈ ϕ(C, P ), and∗2 × D , 2 ∈ ϕ({2}, P ).
(iii) for any P ∈ DM
S

Then ϕ satisﬁes candidate stability, however, it does not satisfy independence.
The question how candidate stability works on the domain DS∗ is open.
We hope that this paper will help further research on candidate stability.

Appendix
Before proving Proposition 1, we introduce one property and three lemmas.
The next property is taken from Eraslan and McLennan (2004).
Strong candidate stability: For all X ∈ 2C \{Ø}, all x ∈ X and allc × D v , we have ϕ(X, P )\{x} = ϕ(X\{x}, P ).5
P ∈ DMS
5

The deﬁnition of strong candidate stability in Eraslan and McLennan (2004) is slightly
diﬀerent from ours since their model does not allow the outcome of empty set.

5

Lemma 1. A rule satisﬁes candidate stability if and only if it satisﬁes strong
candidate stability.
Proof of Lemma 1. Since the if part of proposition is obvious, we only show
the only if part.
Note that strong candidate stability is equivalent to the requirement thatc × D v , (i) ϕ(X, P )\{x} ⊆for all X ∈ 2C \{Ø}, all x ∈ X, and all P ∈ DM
S

ϕ(X\{x}, P ) and (ii) ϕ(X\{x}, P ) ⊆ ϕ(X, P )\{x}. At ﬁrst, suppose, on
the contrary, that ϕ satisﬁes candidate stability but not (i). Then therec × D v such that ϕ(X\{x}, X) (exist X ∈ 2C \{Ø}, x ∈ X, and P ∈ DM
S

ϕ(X, P )\{x}. Let y ∈ ϕ(X, P )\({x} ∪ ϕ(X\{x}, P )). Let Px0 ∈ DM be suchthat for all Y, Z ⊆ X with y ∈ Y and y 6∈ Z, Z Px0 Y . Then ϕ(X\{x}, P ) Px0ϕ(X, P ). By independence of nonvoters’ preferences, ϕ(X\{x}, Px0 , P−x ) Px0ϕ(X, Px0 , P−x ). This contradicts candidate stability. Hence our supposition
is incorrect.
Next, suppose, on the contrary, that ϕ satisﬁes candidate stability but
c × D v such
not (ii). Then there exist X ∈ 2C \{Ø}, x ∈ X, and P ∈ DM
S

that ϕ(X, P )\{x} ( ϕ(X\{x}, P ). Let y ∈ ϕ(X\{x}, P ))\ϕ(X, P ). Let
Px0 ∈ DM be such that for all Y, Z ⊆ X with y ∈ Y and y 6∈ Z, Y Px0 Z.
Then ϕ(X\{x}, P ) Px0 ϕ(X, P ). By independence of nonvoters’ preferences,ϕ(X\{x}, Px0 , P−x ) Px0 ϕ(X, Px0 , P−x ). This contradicts candidate stability.
Hence our supposition is incorrect.
Lemma 2. If a rule ϕ satisﬁes candidate stability, then for all X ∈ 2C withc × D v , we have x ∈ ϕ(X, P ) ⇐⇒ x ∈|X| ≥ 2, all x, y ∈ X and all P ∈ DM
S

ϕ(X\{y}, P ).
Proof of Lemma 2. This is direct from Lemma 1.
Lemma 3. If ϕ satisﬁes candidate stability, then for all X ∈ 2C withc × D v , all i ∈ V and all P 0 ∈ D such
|X| ≥ 2, all x ∈ X, all P ∈ DM
Si
S

that for a candidate y ∈ X\{x}, Pi |{{y},Ø} 6= Pi0 |{{y},Ø} and for all othercandidates z ∈ X\{y}, Pi |{{z},Ø} = Pi0 |{{z},Ø} , we have x ∈ ϕ(X, P ) ⇐⇒x ∈ ϕ(X, Pi0 , P−i ).

Proof of Lemma 3. Let ϕ be a rule satisfying candidate stability. Let X ∈c × D v , i ∈ V and P 0 ∈ D saﬁsfy the hypothe2C , x ∈ X, P ∈ DM
SiS

sis of Lemma 3. Suppose, on the contrary, that x ∈ ϕ(X, P ) but x 6∈
ϕ(X, Pi0 , P−i ). By strong candidate stability, ϕ(X, P )\{y} = ϕ(X\{y}, P )6and ϕ(X, Pi0 , P−i )\{y} = ϕ(X\{y}, Pi0 , P−i ). Thus, x ∈ ϕ(X\{y}, P ) andx 6∈ ϕ(X\{y}, Pi0 , P−i ). However, by independence of irrelevant alternatives,ϕ(X\{y}, P ) = ϕ(X\{y}, Pi0 , P−i ). Thus, x ∈ ϕ(X\{y}, Pi0 , P−i ). It is acontradiction. Hence our supposition is incorrect.
Proof of Proposition 1. The only if part: By the iterated use of Lemma 2 oncandidates and Lemma 3 on preference proﬁles, independence is obtained.
c × Dv .
The if part: Let X ∈ 2C \{Ø}, x ∈ X and P ∈ DM
S

For ally ∈ ϕ(X, P )\{x}, independence implies y ∈ ϕ(X\{x}, P ). Also for all z 6∈
ϕ(X, P )\{x}, independence implies z 6∈ ϕ(X\{x}, P ). Thus ϕ(X\{x}, P ) =ϕ(X, P )\{x} and ϕ satisﬁes strong candidate stability. Hence, it satisﬁes
candidate stability.

References
Barberà, Salvador, Hugo Sonnenschein, Lin Zhou, 1991. Voting by Committees. Econometrica 59 (3), 595-609.
Berga, Dolors, Gustavo Bergantiños, Jordi Massó, Alejandro Neme, 2004.
Stability and voting by committees with exit. Social Choice and Welfare
23 (2), 229-247.
Berga, Dolors, Gustavo Bergantiños, Jordi Massó, Alejandro Neme, 2006.
On Exiting After Voting. International Journal of Game Theory 34 (1),33-54.
Dutta, Bhaskar, Matthew O. Jackson, Michel Le Breton, 2001. Strategic
Candidacy and Voting Procedures. Econometrica 69 (4), 1013-1037.
Ehlers, Lars, John A. Weymark, 2003. Candidate stability and nonbinarysocial choice. Economic Theory 22 (2), 233-243.
Eraslan, Hülya, Andrew McLennan, 2004. Strategic candidacy for multivalued voting procedures. Journal of Economic Theory 117 (1), 29-54.
Ju, Biung-Ghi, 2003. A characterization of strategy-proof voting rules forseparable weak orderings. Social Choice and Welfare 21 (3), 469-499.
Rodrı́guez-Álvarez, Carmelo, 2005. Candidate stability and probabilistic
voting procedures. Economic Theory 27 (3), 657-677.
7

Rodrı́guez-Álvarez, Carmelo, 2006. Candidate Stability and Voting Correspondences. Social Choice and Welfare 27 (3), 545-570.
Samejima, Yusuke, 2005. Strategic candidacy, monotonicity, and strategyproofness. Economics Letters 88 (2), 190-195.
Samejima, Yusuke, 2007. Strategic candidacy and single-peakedness.
Japanese Economic Review 58 (4), 423-442.

8