arXiv:2105.00216v1 [cs.

MA] 1 May 2021

Lecture Notes on
Voting Theory

Davide Grossi

Bernoulli Institute for Maths, CS and AI

University of Groningen
Amsterdam Center for Law and Economics
Institute for Logic, Language and Computation
University of Amsterdam

[Link]

©Davide Grossi 2021

Contents

1 Choosing One Out of Two 2

1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Key definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Basic axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Plurality is the best . . . when m = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Axiomatic characterizations of plurality when m = 2 . . . . . . . . . . . . . . . . . 6
1.2.2 Plurality as maximum likelihood estimator when m = 2 . . . . . . . . . . . . . . . 7
1.3 Chapter notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Choosing One Out of Many 11

2.1 Beyond plurality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Plurality selects unpopular options . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 More voting rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.3 More axioms for SCFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.4 Impossibility results for SCFs: examples . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 There is no obvious social choice function when m > 2 . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Social preference functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Arrow’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Social choice by maximum likelihood & closest consensus . . . . . . . . . . . . . . . . . . 21
2.3.1 The Condorcet model when m > 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Voting rules as MLE when m > 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 Social choice as the closest consensus . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Chapter notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Eliciting Truthful Ballots 28

3.1 Preliminaries: strategic voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.1 Voting strategically . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.2 Manipulability and strategy-proofness . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3 Strategy-proofness and responsiveness axioms . . . . . . . . . . . . . . . . . . . . . 30
3.2 There is no obvious strategy-proof social choice when m > 2 . . . . . . . . . . . . . . . . . 31
3.2.1 Strategy-proofness when m = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Strategy-proofness when m > 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Coping with manipulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Strategy-proofness when individual preferences are ‘coherent’ . . . . . . . . . . . . 33
3.3.2 Making manipulation difficult . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Letting manipulation be . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Chapter notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2
3

4 Choosing Many Out of Many 40

4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.1.1 Multi-winner social choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.1.2 Where are CSFs relevant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Some multi-winner voting rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.1 Excellence-driven rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 Diversity-driven rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.3 Proportionality-driven rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.4 Choose-and-repeat rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Axiomatic results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 Condorcet consistency and monotonicity . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Proportionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Chapter notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Topics for Projects 47

Foreword
These lecture notes have been developed for the course Computational Social Choice of the Artificial
Intelligence MSc programme at the University of Groningen (academic years 2019/20 and 2020/21). They
cover mathematical and algorithmic aspects of voting theory.
The author wishes to thank the students of the above mentioned courses, and Yuzhe Zhang, for the
many corrections and suggestions provided for these notes.
Chapter 1

Choosing One Out of Two

This chapter introduces the basic ideas and definitions of standard voting theory and applies them to
the context in which a group has to choose one out of two alternatives. In this context we prove two
fundamental theorems of social choice over two alternatives.

1.1 Preliminaries
1.1.1 Key definitions
A social choice problem arises whenever a group needs to take a collective choice, among two or more
options, based on the different preferences or opinions that the members of the group may have about
those options. We can make this social choice context precise as follows:
• N is a finite set of n voters, or agents (so, |N | = n). We specifically take N to be a set of natural
numbers: N = {1, 2, . . . , n}.

• A is a finite set of alternatives, or options, of size m (so, |A| = m). We assume that m ≥ 2.
Alternatives are denoted by the initial letters of the alphabet: a, b, c, etc.
Each voter expresses a preference, or ballot i . Such ballots are taken to be linear orders1 over A:
x i y stands for “x is strictly preferred to y by i, or x = y”. The set of all linear orders over A is denoted
L(A). So, for all i ∈ N , i ∈ L(A). The asymmetric (and thus irreflexive) part of each i is denoted ≻i .2
Collecting all these ballots together defines a so-called preference (or ballot) profile P = h1 , 2 , . . . , n i.
That is, a tuple collecting all ballots of the voters in N about the alternatives in A. Such a tuple is called
a profile. The set of all profiles for the voters in N is denoted L(A)n .3
So the problem of social choice, loosely defined, is the problem of finding a suitable subset of alterna-
tives that makes as many voters as ‘happy’ as possible, given the preference information revealed by the
ballots in a profile.

Example 1.1 (A preference profile). Let N = {1, 2, 3} and A = {a, b}. A possible preference profile
is the triple h1 , 2 , 3 i where: 1 = ab, 2 = ab and 3 = ba.a This profile can be represented in

1
That is, a binary relations that are transitive, total (or complete), and antisymmetric (and therefore reflexive).
2
Note that  and ≻ are identical except for the fact that the first is reflexive and the second is irreflexive.
3
We can also conveniently think of a profile P as a matrix
 
x11 x12 x13 ... x1m
x21 x22 x23 ... x2m 
P=
 ... .. .. .. .. 

. . . .
xd1 xd2 xd3 ... xnm

where each entry xij denotes the alternative in the j th position in the linear order of voter i. Using matrix notation we can
write Pij for such an entry. Similarly Pi denotes the vector representing the linear order i of voter i.
2
3

tabular form as follows:

1 a b
2 a b
3 b a
Here each row represents a voter, and the linear order representing to the voter’s ballot is rendered
from the most preferred (left) to the least preferred (right).
a
We denote linear orders simply as sequences, or vectors, of alternatives from the most preferred (left) to the least
preferred (right).

Definition 1.1. Let hN, Ai be given. A social choice function or SCF for hN, Ai is a function

f : L(A)n → 2A \ ∅. (1.1)

That is, for any profile P, an SCF outputs a non-empty set of alternatives. These are the alternatives
constituting the ‘social choice’ made by the group N via function f , given the expressed preferences in P.
If the size of the output of an SCF is larger than 1 then the alternatives it contains can be thought of as
‘tied’ choices.
We will refer to concrete social choice functions as voting rules. The possibly best-known voting rule
selects a single alternative as the social choice based on the number of first positions that each alternative
gets in the ballots of the input voting profile:

Rule 1 (Plurality). The plurality rule is the SCF defined as follows. For any profile P ∈ L(A)n :
    
Plurality(P) = x ∈ A ∄y ∈ A, i ∈ N | max(A) = y > i ∈ N | max(A) = x
i i

We will also refer to |{i ∈ N | maxi (A) = x}| as the plurality score of alternative x in profile P and
we will sometimes denote it by Plurality(P)(x).

So according to plurality, the social choice for a profile contains all alternatives for which there is no other
alternative that occurs as top preference more often in the profile. Notice that this allows for ties in the
social choice.

Example 1.2 (Plurality). Applying the plurality rule to the profile h1 , 2 , 3 i in Example 1.1 we
obtain Plurality(h1 , 2 , 3 i) = {a}. The single winner is therefore alternative a.

A useful benchmark for the further exploration of the space of voting rules are dictatorships.

Rule 2 (Dictatorship). The dictatorship of a given i ∈ N is the SCF defined as follows. For any
profile P ∈ L(A)n :  
Dictatorshipi (P) = max(A) .
i

1.1.2 Basic axioms

Asking what is the best way to aggregate the preferences of a group in order to reach a social choice
amounts to asking whether we can identify a ‘best’ social choice function f . For each hN, Ai there are
n
many social choice functions: (2m − 1)|L(A) | . So even just for the social choice context of Example 1.1
3
there are (23 − 1)2 = 2562890625 such functions, among which plurality and dictatorships are just some
of them.
A way to get a hold of this space is by imposing axioms on the SCF f we would like to identify.
Axioms are meant to capture properties of SCFs which are considered desirable. Ultimately one would
 4

like to identify a set of such desirable properties that, all together, uniquely determine (characterize) f .
Each of the axioms reported below captures a property of SCFs that may be considered desirable, in at
least some contexts of collective decision-making. Some may be considered more intuitive than others,
but no axiom can really be considered unquestionable.
The first group of axioms concerns some basic requirements roughly inspired by an idea of ‘democratic
voting’ in which all voters and all alternatives should be treated equally.

Definition 1.2 (Equal treatment axioms). Let hN, Ai be given. An SCF f is:

Anonymous iff for every permutation π : N → N and P ∈ L(A)n ,

D E
f (h1 , 2 , . . . , n i) = f π(1) , π(2) , . . . , π(n) .
| {z }
P

Intuitively, f treats all voters equally.

Non-dictatorial iff there exists no i ∈ N s.t. ∀P ∈ L(A)n , f (P) = {maxi (A)}. Otherwise f is
said to be dictatorial with i being the dictator.
Intuitively, there exists no voter that can unilaterally determine the social choice.

Neutral if for every permutation ρ : A → A and P ∈ L(A)n ,

ρ(f (h1 , 2 , . . . , n i)) = f (hρ(1 ), ρ(2 ), . . . , ρi (n )i)

| {z }
P

where for i = x1 x2 . . . xn , ρ(i ) = ρ(x1 )ρ(x2 ) . . . ρ(xm ).

Intuitively, f treats all alternatives equally.

The next group of axioms concerns the ability of an SCF to respond appropriately to growing support
for alternatives. They rule out odd SCFs such as ’choose x whenever the number of voters supporting x is
odd’, or SCFs allowing for too many ties (e.g., ‘choose all alternatives supported by at least one third of
the voters’). Before introducing the axioms we define one extra piece of notation. Given a profile P and
xy
two distinct alternatives x and y, NP = {i ∈ N | x ≻i y} denotes the set of voters that strictly prefer x
to y in P. Throughout these notes will also write #xy xy
P instead of |NP | to denote the number of voters
that strictly prefer x to y in P.

Definition 1.3 (Responsiveness axioms). Let hN, Ai be given. An SCF f is:

Pareto iff for all P ∈ L(A)n and for all x ∈ A, if there exists y ∈ A s.t. for all i ∈ N y ≻i x, then
x 6∈ f (P).
Intuitively, the social choice cannot contain dominated alternatives, that is, alternatives for
which the unanimity of voters prefers a different alternative.

Unanimous iff for all P ∈ L(A)n and x ∈ A, if for all i ∈ N maxi (A) = x, then f (P) = {x}.
Intuitively, whenever an alternative is the top choice of all voters, that alternative is the unique
social choice.

Monotonic iff for all P ∈ L(A)n and x ∈ A, if x ∈ f (P) then x ∈ f (P′ ), where:

• P′ ∈ L(A)n
xy xy
• NP ⊆ NP′ , for all y ∈ A \ {x}
yz yz
• NP = NP′ , for all y, z ∈ A \ {x}
5

Intuitively, if an alternative is a social choice it remains so whenever a voter decides to rank it

higher in her ballot.

Positively responsive iff for all x ∈ A and P ∈ L(A)n , if x ∈ f (P) then f (P′ ) = {x} where:

• P 6= P′ ∈ L(A)n
xy xy
• NP ⊆ NP′ , for all y ∈ A \ {x}
yz yz
• NP = NP′ , for all y, z ∈ A \ {x}

Intuitively, if an alternative is selected as a social choice in a profile, it becomes the only social
choice those profiles in which some voter ranks x higher.

The axioms in this last group concern the ability of an SCF to output a single social choice, therefore
ruling out ties, and its ability to effectively consider the whole space of possible preferences in the voters’
population.

Definition 1.4 (Imposition and resoluteness axioms). Let hN, Ai be given. An SCF f is:

Non-imposed iff for all x ∈ A there exists P ∈ L(A)n s.t. f (P) = {x}. It is said to be imposed
otherwise.
Intuitively, every alternative is selected as unique social choice for at least one profile.

Resolute iff for all P ∈ L(A)n , f (P) is a singleton.

Intuitively, the social choice is unique.

An SCF is imposed whenever there exists an alternative that can never be the social choice. It is
irresolute when it admits ties.

Some immediate consequences can be drawn from the above definitions. If f is anonymous, then for
all profiles P and P′ such that, for all distinct alternatives x and y it holds that #xy xy
P = #P′ , we have that
′
f (P) = f (P ). That is, for anonymous SCFs the only information that matters in a profile is the size of
support for each alternative against each other alternative. As a direct consequence dictatorships are not
anonymous. We state here some further observations:

Fact 1.1. Let hN, Ai be given, and let f ba an SCF.

a) If f is non-imposed and monotonic, then it is unanimous;

b) If f is is Pareto, then it is unanimous.

c) If f is unanimous, then it is non-imposed.

Proof. Exercise 1.1

1.2 Plurality is the best . . . when m = 2

We discuss now the plurality rule in the context of social choice problems where m = 2. Observe
immediately that in such cases the plurality rule (Rule 1) simplifies as follows, for all P ∈ L(A)n :
    
Plurality(P) = x ∈ A ∄y ∈ A, i ∈ N | max(A) = y > i ∈ N | max(A) = x
i i
yx xy
= {x ∈ A | ∄y ∈ A, #P > #P }

 {x}
 if #xy n+1
P ≥⌈ 2 ⌉
yx
= {y} if #P ≥ ⌈ n+1
2 ⌉ (1.2)

 A otherwise
 6

where y is the second element of A. The rule defined by (1.2) is also known as simple majority.
In this section we will also be working with the following generalization of the simple majority rule,
under the assumption that m = 2.

Rule 3 (Quota). Let A be such that m = 2. The quota rule Quotaq , where q (the quota) is an
integer such that 1 ≤ q ≤ n + 1, is an SCF defined as follows. For any profile P ∈ L(A)n :
(
{x ∈ A | |{i ∈ N | maxi (A) = x}| ≥ q} if such set is non-empty
Quotaq (P) =
A otherwise

Clearly, simple majority (1.2) is the quota rule where q = ⌈ n+1

2 ⌉. More generally, quota rules select an
alternative as social choice whenever the support for that alternative reaches a given quota. Ties can
arise when the quota are below a majority quota, or when the quota is impossible to be met (q = n + 1).
n
Fact 1.2. Let A be such that m = 2. If 2 < q ≤ n + 1 then:
 xy
 {x} if #P ≥ q

Quotaq (P) = {y} if #yx
P ≥q (1.3)

 A otherwise

Proof. It suffices to observe that by the definition of Rule 3, for every profile P and alternatives x, y ∈ A,
if n2 < q ≤ n then x ∈ Quotaq (P) implies y 6∈ Quotaq (P).

1.2.1 Axiomatic characterizations of plurality when m = 2

The following three theorems provide an axiomatic justification for the use of simple majority voting in
social choice contexts involving only two options.

Theorem 1.1 (May’s theorem [May, 1952]). Let hN, Ai be given such that n is odd and m = 2. The
plurality rule is the only SCF that is resolute, anonymous, neutral and monotonic.

Proof. Left-to-right Assuming that f is plurality, we need to show that f is therefore resolute, anony-
mous, neutral and monotonic. See Exercise 1.2 Right-to-left Let f be resolute, anonymous, neutral and
monotonic. We need to show that f = Plurality. Observe first of all that since m = 2 there are only
two possible ballots: xy or yx. Furthermore, since f is resolute there are only two possible outcomes: {x}
or {y}. Let us proceed towards a contradiction, and assume that f 6= Plurality. Then there exists a
profile P where f returns a choice different from what Plurality returns. There are two possible cases:
either #xy yx yx
P > #P , or #P > #P .
xy

#xy yx
P > #P By assumption, f (P) = {y}. Now permute the alternatives to obtain a profile P where
′

#xy yx yx xy ′
P = #P′ (and therefore #P = #P′ ). Then, by the neutrality of f it follows that f (P ) = {x}. Notice
that P differs from P′ in having more voters preferring x to y. By permuting the agents in N we can then
xy xy
construct a new profile P′′ such that NP ′′ ⊆ NP . That is, we make sure that the same agents ranking x

above y in P also rank x above y in P. By anonymity f (P′′ ) = {x} and by monotonicity f (P) = {x}.
′′ 4

Contradiction. We thus conclude that f (P) = {x}.

#yx xy
P > #P By assumption, f (P) = {x}. An argument identical to the one for the previous case
applies to conclude f (P) = {y}. We thus obtain a contradiction in this case too.
In both cases we obtain a contradiction. Function f is therefore the plurality rule (1.2).

At a high level the proof exploits this argument. Since m = 2 and n is odd, f can choose either
the minority or the majority alternative. If it chooses the minority alternative, then by anonymity and
4
Note that this is precisely what is required by the second condition in the definition of monotonicity. Note furthermore
that as we are handling only two alternatives, the third condition of the unanimity axiom is trivially satisfied.
7

neutrality the minority alternative should be chosen in all profiles that split N in the same way size-wise
(i.e., the cell with ballot xy vs. the cell with ballot yx, or the cell with ballot yx vs. the cell with ballot
xy). However, consistently selecting the minority option goes against monotonicity. Hence f must select
the majority alternative. We now look at generalizations of Theorem 1.1.
First of all Theorem 1.1 assumes an odd number of voters. When that is not the case, it is reasonable
for the SCF to output both alternatives (a tie). The theorem can be generalized to this setting.

Theorem 1.2 (May’s theorem with ties [May, 1952]). Let hN, Ai be given such that m = 2. The
plurality rule is the only SCF that is anonymous, neutral and positively responsive.

Proof. See Exercise 1.3.

Theorem 1.3 (May’s theorem for quota rules). Let hN, Ai be given such that m = 2. Let f be
an SCF that is anonymous, neutral and monotonic. Then there exists q ∈ ( n2 , n + 1] such that
f = Quotaq .

Proof. See Exercise 1.4.

Observe that this theorem allows us to obtain Theorem 1.1 as a corollary.

1.2.2 Plurality as maximum likelihood estimator when m = 2

Theorem 1.1 above provides a justification of the use of simple majority in contexts involving two alter-
natives based on the fact that such a rule is the only one satisfying a set of desirable properties. Simple
majority can be further justified via a truth-tracking, or epistemic, route. We turn to it in this section.

Maximum likelihood estimation

Assume that there exists an objective true ranking ≻ of the two alternatives. Either ≻= xy or ≻= yx.5
Voters are uncertain about which one of the two is the true ranking, but each voter can track the correct
option with some given probability 0.5 < p ≤ 1, which is the same for all voters. Such p represents the
voters’ individual accuracy and corresponds to the conditional probability Pr(x ≻i y |≻= xy). That is,
the probability that i ranks x above y given that x is (actually) better than y.
So voters observe the state of the world imperfectly and vote accordingly to their imperfect observation.
We can then think of each voter’s ballot i as a random variable generated by the probability distribution
p, once the true state of the world ≻ has been fixed. So assuming each such vote is independent, a profile is
therefore a series of identically distributed independent random variables that can take two values (xy or
yx).6 The most likely state of the world is therefore the one that has the highest likelihood of generating
the observed profile P, that is: argmax≻∈{xy,yx} P r(P |≻).

Example 1.3. Assume N = {1, 2, 3} and A = {a, b}. Assume furthermore that p = 32 and that ab
and ba have identical priors: Pr(≻= ab) = Pr(≻= ba) = 0.5. Voters can express one of two ballots
(ab or ba), and assume that the profile we observe is P = hab, ab, bai.

Pr(P |≻= ab) = p2 · (1 − p)

while

Pr(P |≻= ba) = p · (1 − p)2

5
You can think for instance of x and y as two policies, of which only one is the truly better for the group. Or you can
thing of x and y as two candidates for a job, for which only one is the objectively better fit.
6
You can think of a profile as a sequence of n coin tosses, where each coin corresponds to a voter, and the coin used is a
biased coin with bias p towards the correct option.
 8

p
So ranking ab is 1−p = 2 times as likely as ranking ba given P.

Remark 1.1. If we assume that the alternatives are equally likely (i.e., that there is an equal prior
for xy and yx), then the above approach is essentially equal to establishing the probability of each
state of the world given the observed profile. Continuing on the previous example, by Bayes rule:

Pr(P |≻= ab) · Pr(≻= ab)

Pr(≻= ab | P) =
Pr(P |≻= ab) · Pr(≻= ab) + Pr(P |≻= ba) · Pr(≻= ba)
p2 · (1 − p) · 0.5
= 2
p · (1 − p) · 0.5 + ((1 − p)2 · p) · 0.5
p2 · (1 − p) p · (1 − p)
= 2 2
= = p.
p · (1 − p) + (1 − p) · p p(1 − p) + (1 − p)2

This is the probability that ab is the correct state of the world, given the observation of profile P,
equals p.

A jury theorem
Can the maximum likelihood estimation approach described above be implemented through a SCF?
Intuitively we would like the SCF to select, given the profile, the alternative corresponding to the most
likely correct ranking. It turns out that this is possible, and again such SCF is the plurality rule.

Theorem 1.4 (Condorcet’s jury theorem). Fix A such that m = 2. Assume furthermore that
0.5 < p ≤ 1 and that, for any N such that n is odd, each profile for hN, Ai is an i.i.d. sequence of
random variables i generated by p. Then:

pPlurality (n) ≤ pPlurality (n + 2) for every odd n (1.4)

p ≤ pPlurality (n) for every odd n (1.5)
lim pPlurality (n) = 1 (1.6)
n→∞

where pPlurality (n) denotes the accuracy of the social choice for hN, Ai determined via plurality.

Proof. First of all observe that a decision taken by plurality is correct if and only if a majority of voters
has voted
correctly (1.2). That is, whenever a number h ≥ n+1 2 of voters votes correctly. There are
Pn n
n+1
=h h
such majorities. For each of these the probability that precisely that majority of h voters
2
votes correctly is ph · (1 − p)n−h . We thus obtain that:
n
!
X n
pPlurality (n) = · ph · (1 − p)n−h (1.7)
n+1
h
2
=h

We proceed to prove the three claims of the theorem.

(1.4) The claim is a consequence of the following recursive formula:
!
n n+1
pPlurality (n + 2) = pPlurality (n) + (2p − 1) · n+1 · (p · (1 − p)) 2 . (1.8)
2
| {z }
φ

Given the assumption 0.5 < p ≤ 1, it is easy to see that φ ≥ 0 (and that φ > 0 when in addition p 6= 1),
from which we can conclude that pPlurality (n + 2) > pPlurality (n) as desired. We now proceed to derive
(1.8) by a combinatorial argument. We are focusing on profiles of length n + 2. It is now helpful to
think of pPlurality (n + 2) as the probability that more than half of the first n + 2 votes in the profile are
9

correct, and of pPlurality (n) as the probability than more than half of the first n votes are correct. Call
the corresponding events Hn+2 and Hn . So: pPlurality (n + 2) = P r(Hn+2 ) and pPlurality (n) = P r(Hn )
Consider now the two following events:

• Hn+2 \ Hn denotes the event that more than half of the first n + 2 votes, but less than half of the
first n votes, are correct;

• Hn+2 ∩ Hn denotes the event that more than half of the first n + 2 votes and more than half of the
first n votes are correct.

Using these events and the standard laws of probability we can rewrite pPlurality (n + 2) as follows:

pPlurality (n + 2) = P r(Hn+2 )
= P r(Hn+2 \ Hn ) + P r(Hn+2 ∩ Hn )
= P r(Hn+2 \ Hn ) + P r(Hn ) − P r(Hn \ Hn+2 )
= pPlurality (n) + P r(Hn+2 \ Hn ) − P r(Hn \ Hn+2 ) (1.9)
| {z } | {z }
α β

We proceed to establish α and β. α Event Hn+2 \Hn occurs if the first n votes contain a narrow incorrect
majority (the majority is decided by one voter) and the two subsequent votes are both correct. The first
n
n−1 n+1
event happens with probability n+1 · p 2 · (1 − p) 2 and the second with probability p2 . We thus
2
obtain:
!
n n−1 n+1
α= n+1 ·p 2 · (1 − p) 2 · p2
2
!
n n+1
=p· n+1 · (p · (1 − p)) 2 . (1.10)
2

β In the same fashion, event Hn \ Hn+2 ) occurs if the first n votes contain a correct majority but the
first n + 2 do not, implying the last two votes are incorrect. The first event happens with probability
n
n+1 n−1
n+1 · p 2 · (1 − p) 2 and the second with probability (1 − p)2 . We thus obtain:
2

!
n n+1 n−1
β= n+1 ·p 2 · (1 − p) 2 · (1 − p)2
2
!
n n+1
= (1 − p) · n+1 · (p · (1 − p)) 2 . (1.11)
2

We can now replace (1.10) and (1.11) in (1.9) and obtain (1.8) as desired:
! !
n n+1 n n+1
pPlurality (n + 2) = pPlurality (n) + p · n+1 · (p · (1 − p)) 2 − (1 − p) · n+1 · (p · (1 − p)) 2

2 2
!
n n+1
= pPlurality (n) + (2p − 1) · n+1 · (p · (1 − p)) 2 .
2

(1.5) The claim follows directly from (1.4) once observed that p = pPlurality (1).
(1.6) By the weak law of large numbers as n grows to infinity the average number of correct votes
converges to p. As p > 0.5 it follows that the probability of a correct majority goes to 1.

The theorem is probably the first mathematical analysis of a form of ‘wisdom of the crowds’. It states
that groups become more accurate as they grow larger (1.4), that majorities are more accurate that single
individuals (1.5), and that infinite groups achieve perfect accuracy (1.6).
 10

1.3 Chapter notes

The bulk of this chapter is based on the introductions to voting theory provided in [Brandt et al., 2016, Ch.
2], [Taylor, 2005, Ch. 1] and [Endriss, 2011]. The Pareto principle was first formulated in [Pareto, 1919].
Theorem 1.1 was first presented in [May, 1952], still a beautiful example of the application of the ax-
iomatic method to voting. Theorem 1.4 appeared first in [Condorcet, 1785] and was rediscovered sev-
eral times during the last century (e.g., [Moore and Shannon, 1956]). Even though Theorem 1.4 is a
well-known result, not many detailed and accessible proofs exists. The proof presented is based on
[Dietrich and Spiekermann, 2020].

1.4 Exercises
Exercise 1.1. Provide a proof of Fact 1.1

Exercise 1.2. Provide a proof of the Left-to-right direction of Theorem 1.1.

Exercise 1.3. Provide a proof of Theorem 1.2.

Exercise 1.4. Provide a proof of Theorem 1.3. Hint You want to show there exists a number q that
has two properties: x is the only social choice if at least q voters rank x above y; and q ∈ ( n2 , n + 1]. Now
collect in a set Q all numbers k that have the property that if k voters rank x over y then {x} is the
social choice. Q can be empty, or not. Reason from there.

Exercise 1.5 (Odd rule). Consider the following rule.

Rule 4. Let A = {a, b}. The odd rule is the SCF defined as follows. For every P:
(
{a} if #ab
P is odd
Odd(P) =
{b} otherwise

Intuitively, the rule chooses a whenever the size of the set of voters supporting it is odd, otherwise it
chooses b. Determine whether the odd rule is: anonymous, neutral, unanimous, positively responsive,
non-imposed, resolute. Explain your answers.

Exercise 1.6 (Iterated voting when m = 2). Consider a series of choice contexts

hN1 , A1 i , hN2 , A2 i , . . . , hNk , Ak i ,

with k large (e.g., k ≥ 2n ) and such that for every 1 ≤ i < k, Ni = Ni+1 , Ai = Ai+1 and such that
m = 2. For any series P1 , P2 , . . . , Pk of profiles, a social choice function f would thus determine the
series of social choices f (P1 ), f (P2 ), . . . , f (Pk ). According to your intuition, would plurality be a ‘fair’
way of determining such series of social choices? Justify your answer and if you think the answer is
negative devise a voting rule that would behave more ‘fairly’ according to your insights. Again, explain
your answer.

Exercise 1.7. Consider Theorem 1.4 and determine how its statement should be modified, for all its
parts (1.4), (1.5) and (1.6), once the assumption 0.5 < p ≤ 1 is changed to p = 0.5 (first variant), and to
0 ≤ p < 0.5 (second variant). State these two variants of the theorem.
Chapter 2

Choosing One Out of Many

2.1 Beyond plurality

The classic contributions to social choice theory sparked from the dissatisfaction of how the plurality rule
(Rule 1) behaves in social choice contexts when m > 2.

2.1.1 Plurality selects unpopular options

Example 2.1 (Roman Senate, 1 century b.C.). “ . . . the consul Africanus Dexter had been found
slain, and it was uncertain whether it had died at his own hand or at those of his freedmen. When the
matter came before the Roman Senate, Pliny wished to acquit them [alternative a], another senator
moved that they should be banished to an eiland [alternative b]; and a third that they should be put
to death [alternative c]” [Ordeshoek, 2003, p. 54]:

#102 a b c
#101 b a c
#100 c b a

The standard voting practice in the Roman Senate would have consisted of a staged procedure: first a
vote on a (are the freedmen innocent, and therefore to-be-aquitted, or are they guilty?), which would
have been lost; second a vote on b vs. c, which would have been won by b. Pliny, who was chairing
the session, favoured a, and so demanded a vote by plurality. Plurality would select a as unique social
choice which, however, is hugely unpopular: it corresponds to about 31 of the votes of all the senators;
and there is one alternative, namely b, who is preferred to both a and both c by a strong majority of
senators.

Example 2.2 (2002 US Presidential elections, stylized [Dasgupta and Maskin, 2004]). The example
assumes only four kind of voters and abstracts away from the electoral college procedure in use for
the election of the US president. It assumes there are 100000 voters (rows indicate multiple of 1000).

#2 Nader Gore Bush Buchanan

#49 Gore Bush Nader Buchanan
#48 Bush Buchanan Gore Nader
#1 Buchanan Bush Gore Nader
Again here plurality would elect Gore, who is receiving a minority of votes. At the same time Bush
appears to occupy higher positions than Gore in the voters’ rankings.
11
 12

2.1.2 More voting rules

What seems to be the root of plurality’s problems in convincingly aggregating preferences over more than
two alternatives is that it disregards all information provided by voters, except for their top choices. Each
of the rules discussed in this section puts that extra information at work, in different ways, to establish
a ‘reasonable’ social choice.

Pairwise comparison rules

One piece of information that appears to be relevant in the above examples is how often an alternative x
‘beats’ another alternative y in a pairwise contest, that is, whether there exists a larger support for x over
y than there is for y over x. We can easily tabulate such information as a pairwise comparison m × m
matrix [#xy xy yx
P ] with x, y ∈ A. Clearly, for x 6= y, #P = n − #P and, for any x ∈ A, #
xx = 0.1

Example 2.3. The pairwise comparisons matrix for the election described in Example 2.2 is:

Buchanan Bush Gore Nader

Buchanan 0 1 49 49
Bush 99 0 49 98
Gore 51 51 0 98
Nader 51 2 2 0

Based on such information we can then identify which alternatives are considered better than which
other alternatives in pairwise comparisons and thereby possibly identifying the ‘best’ alternatives.

Definition 2.1 (Net preference). Let P be a profile for context hN, Ai. For any pair of distinct
alternatives xy, the net preference for x over y in P is

Net P (xy) = #xy yx

P − #P .

Note that Net P (xy) = #xy yx xy

P − #P = 2 · #P − n.

Definition 2.2 (Pairwise DmajorityE tournament). The pairwise majority tournament (or majority
graph) of P is the graph A, ≻Net where ≻Net 2 Net y iff
P P ⊂ A is a binary relation such that x ≻P
Net P (xy)
D > 0.E The weighted pairwise majority tournament (or weighted majority graph) is the
graph A, ≻Net
P P is labeled by Net P (xy). When the profile is clear from
where each edge xy ∈≻Net
the context we will omit reference to it and write simply Net(xy) and ≻Net . The weak majority
tournament, allowing for ties, can be naturally defined as: x Net
P y iff Net P (xy) ≥ Net P (yx).

Given a majority tournament, there is therefore one natural way to identify a possible social choice:
check whether there exists an alternative that beats any other alternative in the tournament.
D E
Definition 2.3 (Condorcet winner). Let A, ≻Net be the majority graph of P. An alternative
x ∈ A is the Condorcet winner of P if for all y ∈ A \ {x}, x ≻Net
P y. It is a weak Condorcet winner of
Net
P if for all y ∈ A \ {x}, x P y.

So a Condorcet winner is an alternative that beats every other alternative in a pairwise comparison—in
graph-theoretical terms it is a ‘source’ in the majority graph. As such, it can be considered the natural
social choice, at least if we care about majorities. Notice that relation ≻Net
P is irreflexive and complete
when n is odd, for any profile P. However, it is not transitive in general. It follows that a Condorcet
winner may not exist.
1
This method of representing relevant election information was known already to R. Lull [Llull, 1275] in the 13th century.
13

Example 2.4. The majority graph of the profile in Example 2.1 is: b ≻Net a ≻Net c. Alternative b
is therefore the Condorcet winner of the profile. The majority graph of the profile in Example 2.2 is:

Gore ≻Net Bush ≻Net Nader ≻Net Buchanan

Example 2.5 (Condorcet paradox [Condorcet, 1785]). Three instantiations of the paradox for h{1, 2, 3} , {a, b, c}i
(left), h{1, . . . , 303} , {a, b, c}i (center), h{1, 2, 3} , {a, b, c, d}i (right):

1 a b c 102× a b c 1 a b c d
P1 = 2 b c a P2 = 101× b c a P3 = 2 b c a d
3 c a b 100× c a b 3 c a b d

The pairwise majority tournament all the above profiles contains a 3-cycle a ≻Net b ≻Net c ≻Net a.
These are also called majority cycles and can arise whenever m > 2.

Finally it is worth knowing that any tournament (i.e., irreflexive, complete binary relation) can be gen-
erated via Definition 2.2 by some profile, under the assumption that n is odd (McGarvey’s theorem
[McGarvey, 1953]).
We introduce now two rules based on (unweighted) majority graphs.

Rule 5 (Condorcet). The Condorcet rule is the SCF defined as follows. For every profile P ∈ L(A)n :
(
{x} if ∀y ∈ A \ {x} , x ≻Net
P y
Condorcet(P) =
A otherwise

So the Condorcet rule selects a Condorcet winner when it exists and let otherwise all alternatives tie.

Rule 6 (Copeland [Llull, 1275, Copeland, 1951]). The Copeland rule is the SCF defined as follows.
For any profile P ∈ L(A)n :

Copeland(P) = argmax CP (x)

x∈A

where n o n o
CP (x) = y ∈ A | x ≻Net
P y − y ∈ A | y ≻Net
P x .

This value is called the Copeland score of x (in P).

So the Copeland score consists of the number of times an alternative beats other alternatives, minus the
number of times it is beaten by other alternatives (in the majority graph of the corresponding profile).
The social choice is then the set of alternatives with the highest Copeland score. Notice that the rule
disregards the margins whereby an alternative beats, or is beaten by, other alternatives: the Copeland
score can be computed by just looking at the majority graph of a profile, disregarding the net preference
information. In other words, it disregards the relative positions of alternatives in the voters’ rankings.
This type of information becomes available in the next class of rules we are going to discuss.

Example 2.6. Consider again Example 2.5. We have that: Condorcet(P1 ) = Copeland(P2 ) =
{a, b, c} but Condorcet(P3 ) = {a, b, c, d} while Copeland(P3 ) = {a, b, c}.

Remark 2.1. Another voting

D rule Ebased on (unweighted) majority graphs is the Slater rule [Slater, 1961]:
given the majority graph A, ≻Net find the strict linear order ≻ that minimizes the number of edges
 14

one needs to switch in ≻Net to get ≻. The social choice is the singleton consisting of the top alternative
in ≻.

Remark 2.2. There are voting rules that need the information of the weighted majority
D graph to beE
computed. An example is the Ranked-pairs rule: given the weighted majority graph A, ≻Net , Net
order the edges of relation ≻Net by the size of their weight (largest to smallest), then construct a linear
order over A by starting from the edge with the largest weight and proceeding to add edges following
their weights unless a cycle is formed. The social choice is the top alternative in the constructed
order.

Positional scoring rules

Positional scoring rules are a class of SCFs that determine the social choice by assigning points to alterna-
tives depending on how often the alternative occupies a given position in the voters’ ballots. The social
choice is the alternative collecting the most points.

Definition 2.4 (Positional scoring rules). A positional scoring rule f is an SCF, for hN, Ai, such
that there exists a vector of weights (score vector) w = hw1 , w2 , . . . , wm i and, for all P ∈ L(A)n
X
f (P) = argmax wi(x)
x∈A i∈N

where i(x) denotes x’s position in the linear order i .

* +
Observe that plurality (Rule 1) can also be considered a scoring rule, with score vector 1, 0, . . . , 0 .
| {z }
m times
The most famous, and most widely deployed, positional scoring rule is the Borda rule.2

Rule 7 (Borda). The Borda rule Borda is the positional scoring rule with score vector

w = hm − 1, m − 2, . . . , 0i .
P
For every alternative x and profile P, i∈N wi(x) is called the Borda score of x (in P).

In the Borda method an alternative x therefore collects, for each voter, as many points as the alternatives
that that voters places under x in her ballot. Such points are then summed up across voters to obtain
the Borda score of the alternative in the given profile.

Example 2.7 (Borda vs. Condorcet). Consider again the profile in Example 2.2. We have seen that
the Condorcet winner in that profile is Gore (Example 2.4). However, the Borda rule selects Bush:
X X
wi(Bush) = 3 · 48 + 2 · 50 + 1 · 2 wi(Gore) = 3 · 49 + 2 · 2 + 49
i∈N i∈N
X X
wi(Nader) = 3 · 2 + 1 · 49 wi(Buchanan) = 2 · 48
i∈N i∈N

where the relevant score vector is h3, 2, 1, 0i.

So the Borda rule may fail to select a Condorcet winner when it exists. This can be shown to generalize
to all positional scoring rules.
Other examples of positional scoring rules follow:
2
The method carries the name of Jean-Charles de Borda, French mathematician and engineer [J.-C., 1781]. The method
already appeared in the writings of Nicholas of Cusa in the 15th century.
15

* +
Rule 8 (Veto). The veto rule Veto is the positional scoring rule with score vector w = 1, . . . , 1 , 0 .
| {z }
m−1 times

Rule 9 (k-Approval). The*k-Approval rule Approval

+ k , with 1 ≤ k ≤ m, is the positional scoring

rule with score vector w = 1, . . . , 1, 0, . . . , 0 .

| {z } | {z }
k times m−k times

So plurality is the 1-Approval rule, and veto is the m − 1-Approval rule.

An area where positional scoring rules are widely applied are sport or music competitions, such as
the F1 championship or the Eurovision Song Contest competition. For example, the winner of the F1
championship is determined via a positional scoring rule based on the ranking of each pilot in a fixed
number of races. Notice that each race here acts as a voter: it determines a linear order over the pilots.
Over the years various score vectors have been used for the computation of winners, for example: in
the 1961-1990 seasons the vector h9, 6, 4, 3, 2, 1, 0, . . . , 0i was used; in the 1991-2002 seasons, the vector
h10, 6, 4, 3, 2, 1, 0, . . . , 0i; and in the 2003-2208 seasons, the vector h10, 8, 6, 5, 4, 3, 2, 1, 0, . . . , 0i. In song
competitions, like the Eurovision Song Contest, juries (and the public) act as voters. The score vector of
the Eurovision Song Context is currently h12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0, . . . , 0i.

Multiround rules
This third class of rules is based on the idea that ballots can be revised in an iterated manner by removing,
at each round in the process, the ‘least popular’ alternatives from the ballots, until one alternative achieves
majority.
Before introducing these rules we need some auxiliary notation. Let P be a profile and X ⊆ A a set
of alternatives. Then the profile restricted to X is P|X = h1 |X , . . . , n |X i, where each i |X is the
restriction of i to the alternatives in X. Then let σP : 2A → 2A be a set-transformer defined as follows:

σP (X) = X \ {x ∈ A | x has lowest plurality score in P|X } .

That is, given a set of alternatives X, σP (X) removes from X the alternatives that are ranked highest by
the smallest number of voters. For k ∈ N we denote by σP k the k th -fold iteration of σ .
P

Rule 10 (Plurality with run-off). The plurality with run-off rule is the SCF defined as follows, for
any profile P:
(
n+1
RO {x} if |{i ∈ N | maxi (A) = x}| ≥ 2
Plurality (P) =
Plurality(P|Top2 ) otherwise

where Top2 ⊆ A is the set of the 2 alternatives in A with the two highest plurality scores in P.

Example 2.8 (Non-monotonicity). Consider the two profiles

#6 a b c
#8 a b c
#2 c a b
P = #10 c a b P′ =
#10 c a b
#7 b c a
#7 b c a

We have that PluralityRO (P) = {c} (b is eliminated in the first round, and c wins in the second
round against a by a net preference of 17 − 8) but PluralityRO (P′ ) = {b} (a is eliminated in the
 16

first round, and b wins in the second round against b by a net preference of 13 − 12) even though in
P′ 2 voters have ranked c higher than in P.

Rule 11 (Single transferable vote). The single transferable vote rule (STV) is the SCF defined as
follows, for any profile P:
k −1 ⋆
STV(P) = σP (A)
⋆
where k∗ is the step at which all alternatives are removed: σP
k (A) = ∅.

Intuitively, STV iteratively removes the alternatives with lowest plurality score until all alternatives are
removed. So STV is still based on the plurality score, but it extracts as much information as possible from
the ballot profile, thereby reducing the amount of votes ‘wasted’. By means of comparison, in a standard
plurality election normally more than half the votes would be ‘wasted’ in the sense of supporting losers of
the election. STV obviates to this problem by iteratively removing plurality losers and recomputing the
plurality score based on the preferential ballots. So the alternatives that are removed last constitute the
social choice, which therefore consists of either one alternative with a majority support, or by alternatives
with equal plurality score.3 The STV rule goes also under other names, e.g., Hare rule [Hare, 1859],4
instant run-off voting, ranked choice voting.

2.1.3 More axioms for SCFs

Definition 2.5. Let hN, Ai be given. An SCF f is:

Non-dictatorial iff there exists no i ∈ N s.t. for all P ∈ L(A)n , f (P) = Dictatorshipi (P) (cf.
Rule 2). Otherwise f is said to be dictatorial with i being the dictator.
Intuitively, there exists no voter that can unilaterally determine the social choice.

Condorcet-consistency iff for all P ∈ L(A)n , if x is the Condorcet winner of P, then f (P) = {x}.
Intuitively, the rule agrees with the Condorcet rule on all profiles that give rise to transitive
majority graphs.
xy xy
Independent iff for any two profiles P, P′ ∈ L(A)n and two alternatives x, y ∈ A, if NP = NP′
′
and x ∈ f (P) but y 6∈ f (P) then y 6∈ f (P ).
Intuitively, whether one alternative belongs to the social choice while the other does not depends
only on how voters rank the two alternatives, and not on how they rank other alternatives.
xy
Liberal iff for all i ∈ N there exists x 6= y ∈ A s.t. for every profile P ∈ L(A), i ∈ NP implies
yx
y 6∈ f (P) and i ∈ NP implies x 6∈ f (P). Each such agent i is said to be two-way decisive on x
and y.
Intuitively, each agent should be able to unilaterally veto, for at least two alternatives, whether
the alternative is part of the social choice.

Axioms can help understand the different behavior of different voting rules by looking at what rules
satisfy what axioms. See Exercise 2.3.

3
Several variants to this definition exist, mostly focusing on what to do when ties exist among the alternatives with lowest
scores.
4
In 1862 John Stuart Mill referred to it as “among the greates improvements yet made in the theory and practice of
government”. It is popular among electoral reform groups and it is widely deployed to elect representatives (among others
in Ireland, Northern Ireland, Australia).
17

2.1.4 Impossibility results for SCFs: examples

As Table 2.2 makes evident, the rules we have considered so far satisfy some of the desirable properties—
the axioms—we came up with, but none satisfies all. The question then arises of whether such ‘ideal’
social choice functions could actually be found. The upshot of the next section is that this is not the case,
and the key means to show that is through so-called impossibility results: theorems stating the inexistence
of functions with a given set of properties. Before moving to the next section and discuss one of the main
impossibility results, we illustrate here ‘style’ of such results with two simple(r) examples.
Fact 2.1. Let hN, Ai be given such that n = m = 2. There exists no SCF that is anonymous, neutral
and resolute.

Theorem 2.1. Let hN, Ai be given such that m > 2 and n ≥ 2. There exists no SCF that is Pareto
(recall Definition 1.3) and liberal.

Proof. See Exercise 2.4.

2.2 There is no obvious social choice function when m > 2

2.2.1 Social preference functions
The rules discussed in the previous section not only identify a social choice for each profile, but actually
determine a weak ‘social preference’ over the set of alternatives. That is, they can be viewed as social
preference functions5 mapping profiles of individual linear orders to total preorders (that is, linear orders
admitting ties):
F : L(A)n → T P(A). (2.1)
where T P(A) denotes the set of all total preorders6 on the set of alternatives. So, for any profile P, we
refer to F (P) =FP as the social preference determined by F in profile P, and to ≻FP as its asymmetric
(strict) part.
It is worth stressing that SCFs and SPFs are closely related:

Remark 2.3 (Correspondence between SCFs and SPFs). Let hN, Ai be given.

a) For every SPF F , maxF (·) (A) is the SCF that selects, for any profile P ∈ L(A)n , the top alterna-
tives in FP .

b) For every SCF f , the linear order

f (P) ≻ f (P|A\f (A) ) ≻ f (Pf (P|A\f (A) ) ) ≻ . . . .

defines a social preference function FP where the tied top-ranked alternatives are the alternatives
in f (P), the tied second-ranked alternatives are the alternatives in f (P|A\f (A) ) and so on. Observe
that the length of FP is clearly at most m − 1 when f is resolute.

Intuitively, the social choice corresponds to the best alternatives in such a social preference. Vice versa,
the social preference can be induced by iterated social choices on sets of alternatives from which the
winners of the previous social choice have been removed.
It is worth observing right away that May’s and Condorcet’s theorems (Theorems 1.1 and 1.4) for
the setting m = 2 can be straigthorwardly formulated for the setting of SPFs. In general, the axioms we
studied so far can all be adapted to the SPF setting. Here we present three, that will be used for the
impossibility result discussed later in this section.
5
A more common terminology is ‘social welfare function’.
6
That is, reflexive, transitive and total binary relations.
 18

Definition 2.6. Let hN, Ai be given. An SPF F is:

Non-dictatorial iff there exists no i ∈ N s.t. ∀P ∈ L(A)n , F (P) =i . Otherwise f is said to be
dictatorial with i being the dictator.
Intuitively, there exists no voter whose ballot is always identical to the social preference.
xy
Pareto iff for any profile P ∈ L(A)n whenever NP = N , x ≻FP y.
Intuitively, if everybody agrees on the relative ranking of two alternatives that ranking should
be part of the social preference.

Independent of irrelevant alternatives (IIA) iff for any two profiles P, P′ ∈ L(A) and two
xy xy F F
alternatives x, y ∈ A, if NP = NP′ then x P y iff x P′ y

Intuitively, if two profiles are identical with respect to the relative ranking of two alternatives,
then the relative ranking of the two alternatives in the the social preferences for those two
profiles is the same.

The following proposition shows how properties such as the above ones may interact in ways that may
be unexpected at first. The proposition will also be of importance in the discussion of Arrow’s theorem
in the next section.
Proposition 2.1. Let F be a SPF for a hN, Ai s.t. m > 2. If F satisfies Pareto and IIA, then F always
outputs a linear order.
Proof. Assume towards a contradiction that there exists a profile P in which x and y are tied in F (P)—
xy xz ∩ N zy and N yx = N zy ∩ N zx . That is, in
x ∼FP y. Now consider a new profile P′ such that NP = NP ′ P′ P P′ P′
P′ the voters that were ranking x over y now place an alternative z between x and y, while the voters
that were ranking y over x now place an alternative z above both y and x. By IIA we get x and y tied
in F (P′ )—x ∼FP′ y—and by Pareto we get z ≻FP′ y and therefore z ≻FP′ x.
xy xz ∩ N yz
Now consider a different profile P′′ where we choose a different placement for z: NP = NP ′′ P′′
yx yz zx ′′
and NP = NP′′ ∩ NP′′ . That is, in P the voters that were ranking x over y now place the alternative
z below both x and y, while the voters that were ranking y over x now place an alternative z between
the two. By IIA we get again x ∼FP′′ y and by Pareto we get y ≻FP′′ z and therefore x ≻FP′′ z. However
NPxz = N xz , but z ≻F x and x ≻F z, which violates IIA. Contradiction.
′ P′′ P′ P′′

The lemma tells us that SPFs that are Pareto and IIA, when there are at least three alternatives, map
profiles of linear orders to linear orders, that is, they do not allow for ties in the social preference.

2.2.2 Arrow’s theorem

Arrow’s theorem establishes that it is impossible to aggregate the preferences of a finite set of voters while
respecting Pareto, independence of irrelevant alternatives and non-dictatorship. The three axioms are
inconsistent.7

Theorem 2.2 (Arrow’s theorem [Arrow, 1950, Arrow, 1963]). Let F be a SPF for a hN, Ai s.t. m > 2.
F satisfies Pareto and IIA if and only if it is a dictatorship.

Another way to look at the theorem is that of a characterization of the dictatorship rule, exactly like
May’s theorem is a characterization of the plurality rule in the m = 2 context: dictatorships are the only
SPFs that are Pareto and IIA. In a way the theorem shows that there is no ‘obvious’ method—in the
sense of being independent of irrelevant alternatives and Pareto—to aggregate preferences on more than
2 alternatives.
7
The enormous impact that this theorem had in social choice, economics and political theory in general was well sum-
marized by Paul Samuelson (like Arrow, a winner of the Nobel Memorial Prize in Economic Science):“Arrow’s devastating
discovery is to mathematical politics what Kurt Gödel’s 1931 impossibility-of-proving-consistency theorem is to mathematical
logic”.
19

Proof strategy and decisive coalitions

The proof of the theorem presented here relies on one main definition and three lemmas. The central
definition in the proof of Arrow’s theorem is that of a decisive coalition of voters.

Definition 2.7 (Decisive coalition). Let F be a SPF (for a given hN, Ai), and x, y ∈ A. A coalition
C ⊆ N is decisive for x over y (or xy-decisive), under F , if
xy
∀P ∈ L(A)n : if C ⊆ NP then x ≻FP y.

A coalition C ⊆ N is decisive if it is decisive for every pair of alternatives. The set of xy-decisive
coalitions (under F ) is denoted DFxy (or simply D xy when F is clear from the context). The set of
decisive coalitions (under F ) is denoted D.

Intuitively, a set of voters is decisive for x over y whenever, if they all agree with ranking x over y, then
x is ranked over y in the social preference.
The proof then relies on three main lemmas. The first lemma shows that if a coalition is decisive for
a pair of alternatives, then it is decisive for all alternatives.
The second one shows that if SPFs are Pareto and IIA, then their set of decisive coalitions D takes
the form of a so-called ultrafilter. Ultrafilters are collections of sets and were originally introduced in
[Cartan, 1937] to capture a handful of properties characterizing the notion of ‘large set’, like: i) the
largest set is a large set; ii) a set is large iff its complement is not large; iii) the intersection of two large
sets is large.
The third lemma is a fact about ultrafilters constructed on finite sets (like the set of voters N ), and
it states that every finite ultrafilter contains a singleton. It follows that if D is an ultrafilter, it must be
finite since N is finite, and it must therefore contain a singleton decisive coalition, that is, a dictator. The
intuition behind the use of ultrafilters in voting theory is that a notion of ‘large set’ can naturally be used
to define SFPs responding to the rough intuition: issue x is ranked above y in the social preference if and
only if there is a ‘large set’ of individuals—a ‘large coalition’—supporting it.

The three lemmas

Lemma 2.1 (Contagion lemma). Let F be a SPF (for a given hN, Ai) which is Pareto and IIA. If
C ∈ D xy for some x, y ∈ A, then C ∈ D.

Proof. We want to show that if C ∈ D xy for some x, y ∈ A then C ∈ D wz for all w, z ∈ A. So consider
any profile P where each voter i in C holds preferences satisfying w ≻i x ≻i y ≻i z and any other voters
j holds preferences satisfying w ≻j x and y ≻j z:

C ... w ... x ... y ... z ...

P= C ... w ... x ...
... y ... z ...

Notice that this specification of P leaves it open to how voters in C rank w w.r.t. z and x w.r.t y. Now
C ⊆ NP wz and, since C is xy decisive, we therefore have that x ≻F y and, by Pareto, we have that w ≻F x
P P
and y ≻FP z. By transitivity we thus have that w ≻FP z. Now consider any profile P′ such that C ⊆ NP wz .
′
wz wz F
By the specification we gave for P, there exists a profile P such that NP = NP′ . By IIA, w ≻P′ z. We
can then conclude that C ∈ D wz , as desired.

Lemma 2.2 (Ultrafilter lemma). Let F be a SPF (for a given hN, Ai), that satisfies Pareto and IIA.
The set D of decisive coalitions (for F ) is an ultrafilter over N , that is:

i) N ∈ D, i.e., the set of all individuals is a decisive coalition;

 20

ii) C ∈ D iff C 6∈ D, i.e., a coalition is decisive if and only if its complement is not;

iii) D is closed under finite intersections: if C, D ∈ D then C ∩ D ∈ D, i.e., if two coalitions are
winning then the individuals they have in common form a winning coalition.

Proof. i) The claim is a direct consequence of the assumption that F satisfies Pareto.

ii) Left-to-right Suppose, towards a contradiction, that C, C ∈ D. Consider now a profile P where
xy yx
C = NP and C = NP . This profile must exist as SPFs admit any profile in L(A)n as input, and be
such that xy, yx ∈ F (P). But F (P) must be a linear order by Proposition 2.1. Contradiction.
Right-to-left Assume C 6∈ D. Then there exists a pair of (distinct) alternatives yx such that C 6∈ D yx .
So assume, for x 6= y ∈ A, that C 6∈ D yx . Then, by Definition 2.7, there exists a profile P such that
yx
C ⊆ NP and x ≻FP y. Such profile can be depicted as follows:

C′ . . . x . . . y . . .
P = C ′′ . . . y . . . x . . .
C ... y ... x ...

where C = C ′ ∪ C ′′ and C ′′ may be empty. Now consider the following variant of P constructed by
placing a third alternative x in different positions in the individual ballots:

C′ . . . x . . . y . . . z . . .
′
P = C ′′ . . . y . . . z . . . x . . .
C ... y ... z ... x ...

The social preference F (P′ ) for this profile is such that: x ≻FP′ y by IIA; y ≻FP′ z by Pareto; x ≻FP′ z
by the definition of SPF (2.1). By IIA, in any profile P′′ such that NP xz = N xz we have that x ≻F z.
′ P′′ P′′
′ xz ′ xz
It follows that C ∈ D . Since, by construction, C ⊆ C we also obtain C ∈ D . Finally, by Lemma
2.1, we conclude C ∈ D as desired.

iii) Assume towards a contradiction that C, D ∈ D and C ∩ D 6∈ D. By the previous item, C ∩ D ∈ D.

Construct a profile P with the following features:8

C ∩D ... x ... y ... z ...

D\C ... y ... z ... x ...
C \D ... z ... x ... y ...
C ∪D ... z ... y ... x ...

We have that:

• (C ∩ D) ∪ (C \ D) = C, which is decisive by assumption. So, as for all i ∈ C x ≻i y, it follows

that x ≻FP y;
• (C ∩ D) ∪ (D \ C) = D, which is decisive by assumption. So, as for all i ∈ D y ≻i z, it follows
that y ≻FP z;
• C ∪ D ∪ (C \ D) ∪ (D \ C) = C ∩ D, which is also decisive by claim ii). So, as for all i ∈ C ∩ D
z ≻i x, it follows that z ≻FP x.

The above forces the social preference FP to be cyclical, which is impossible by the definition of SPFs
(2.1). Contradiction.
All claims have been proven and the proof is therefore complete.

The second lemma concerns a general well-known fact about finite ultrafilters. Worth noticing is that
the fact and its proof do not involve any reference to SPFs.
8
Note the resemblance with the Condorcet paradox (Example 2.5).
21

Lemma 2.3 (Existence of a dictator). Let D be an ultrafilter on N . Then D is principal, i.e.:

∃i ∈ N s.t. {i} ∈ D.

Proof. Recall the definition of ultrafilter given in Lemma 2.2. Since the set of voters N is finite by
T
assumption, the closure D of D under finite intersections belongs to D by property iii). We therefore
T
have that D 6= ∅. For suppose not, then N 6∈ D by property ii), against property i). So, w.l.o.g., assume
T
i ∈ D for i ∈ N . We want to show that {i} ∈ D. Suppose towards a contradiction that {i} 6∈ D. By
T
property ii) we have that {i} ∈ D, from which follows that i 6∈ D. Contradiction. Hence {i} ∈ D.

Completing the proof

We can now pull the above lemmas together and prove the result we are after:

Proof of Theorem 2.2. Right-to-left Assume F is a dictatorship. For each profile where N xy = N , the
dictator ranks x over y. Hence xy ∈ F (P), proving Pareto. For any two profiles agreeing on the set of
voters ranking x over y either the dictator belongs to that set, and therefore xy belongs to both social
preferences, or it does not and therefore yx belongs to both social preferences. This proves IIA.
Left-to-right By Lemma 2.2 the set of decisive coalitions under F is an ultrafilter. By Lemma 2.3
such ultrafilter is principal and therefore it contains a singleton. Such singleton is a decisive coalition and
therefore, by Definition 2.7, the voter in the singleton is a dictator.

2.3 Social choice by maximum likelihood & closest consensus

In this section we look at two other perspectives on social choice, and some of the voting rules they inspire:
the maximum likelihood estimator (MLE) approach, which we already saw at work in the two alternatives
case with the Condorcet jury theorem (Theorem 1.4); and the consensus-based approach.
According to the MLE perspective a ‘true’ (correct, objective) ranking of the alternatives in A exists,
and individual ballots are noisy estimates of such ranking. The voting rule should then identify the most
likely ranking that has generated the observed profile, that is, it should be a maximum likelihood estimator.
According to the consensus-based approach, the social preference is a form of ‘consensus’ intended as a
preference that is ‘as close as possible’ to the observed profile. So the voting rule should identify the
closest consensus.

2.3.1 The Condorcet model when m > 2

The model Condorcet developed in [Condorcet, 1785] for the case in which m > 2 is based on the following
assumptions (cf. Section 1.2.2):

C0 All rankings are equally likely a priory.

C1 In each pairwise comparison each voter chooses the objectively better alternative with probability
p ∈ (0.5, 1].

C2 Each voter’s opinion on a pairwise comparison is independent of her opinion on any other pairwise
comparison.

C3 Each voter’s opinions are independent of any other voter’s opinions.

C4 Each voter’s judgment defines a linear order.

The four assumptions are clearly incompatible (specifically, C2 and C4). Here, following [Young, 1988],
we drop C4 and explore to what kind of voting rules assumptions C0-C3 lead. It is worth stressing that
even though there are intuitive reasons against dropping condition C4 (after all it feels odd to allow for
intransitive opinions), there are also natural reasons in favor of such a choice: if we take individual votes as
 22

the voter’s best approximation at trying to identify the correct ranking, such votes may well be intransitive
since best approximations of linear orders may well fail to be transitive (cf. [Truchnon, 2008]).9

2.3.2 Voting rules as MLE when m > 2

First, under the above assumptions C0-C3 we are interested in finding a voting rule that identifies the
most likely social preference. Two adjustments to the notion of SPF are needed. First, individual ballots
may now not be linear orders as their strict part may contain cycles. They are, instead, tournaments (cf.
Definition 2.2), that is, asymmetric, complete but not necessarily transitive binary relations over A. We
denote the class of tournaments over A by T (A). Second, there might be more than one most likely social
preference. We therefore generalize the notion of SPF as follows. A generalized social preference function
(GSPF) is a function:
G : T (A)n → 2L(A) (2.2)
That is, it takes a vector of tournaments as input and outputs a set of linear orders. Notice that an SPF
(2.1), when its output is a linear order (cf. Lemma 2.1), can therefore be viewed as a GSPF that always
outputs a singleton set of linear orders.
The MLE of the correct ranking is therefore a GSPF G such that, for every profile P ∈ T (A)n , G(P)
is the set of linear orders  that maximize the probability of the observed profile P given . That is:
G(P) = argmax (Pr(P |)). (2.3)
∈L(A)

We discuss a concrete application of this approach, and a slight variant of it.

The Kemeny rule

We first introduce one more piece of notation. The distance between two linear orders  and ′ , called
swap distance, is defined as:10
n o
dswap (, ′ ) = xy ∈ A2 | x ≻ y and y ≻′ x (2.4)

That is, the swap distance between two linear orders is given by the number of pairs of alternatives with
respect to which the two orders disagree. Equivalently dswap (, ′ ) is the minimum number of swaps (i.e.,
inversions) of adjacent alternatives whereby one can obtain ′ from .

Remark 2.4. Many alternative notions of distance can be defined. The simplest one is possibly the
so-called discrete distance:
(
′ 1 if 6=′
ddiscr (,  ) = (2.5)
0 otherwise

That is, the distance is 1 for all and only the ballots that differ from . Another way to interpret it
is to say that, if the cost of any operation on a linear order (e.g., swapping alternatives in arbitrary
positions) is 1, then in order to turn  into ′ one incurs a cost of 0 (if they are the same order) or
of 1 (otherwise).
In general, a distance is a function d satisfying the following properties, for any , ′ , ′′ :

Non-negativity, d(, ′ ) ≥ 0;

Identity of indiscernibles, d(, ′ ) = 0 iff =′ ;

Symmetry, d(, ′ ) = d(′ , );

9
The alternative choice consisting of retaining C4 while dropping C2 requires different noise models for the random
generation of linear orders. One such widely deployed model is the so-called Mallows noise model [Mallows, 1957].
10
The distance is also known as, among others, Kendall tau or bubble-sort distance.
23

Triangle inequality, d(, ′ ) ≤ d(, ′′ ) + d(′′ , ′ ).

Theorem 2.3. Let P = h1 , . . . , n i ∈ T (A)n be randomly generated according to assumptions

C0-C3 above. Then X
argmin dswap (i , )
∈L(A) i∈N

is the MLE of the correct ranking.

Proof. For ease of presentation we work with the asymmetric (strict) part of linear orders. Let ≻∈ L(A)
be the correct ranking. Let now ≻′ ∈ T (A) be a tournament that agrees with ≻ on k pairs of alternatives.
′ m

Observe that by (2.4) we have dswap (≻ , ≻) = 2 − k. So, by assumptions C1 and C2 the probability
that a voter expresses ballot ≻′ is
 −dswap (≻′ ,≻)
m m m p i
pk · (1 − p)( 2 )−k = p( 2 )−dswap (≻ ,≻) · (1 − p)dswap (≻ ,≻) = p( 2 ) ·
′ ′
.
1−p
Then by assumption C3 we have that the probability of a profile h≻′1 , . . . , ≻′n i, given that ≻ is the correct
ranking, is proportional to
Y −dswap (≻′ ,≻)  − P dswap (≻′i ,≻)
p i p i∈N
= .
i∈N
1−p 1−p

By C0 the rankings that are most likely to be the correct one are the ones that maximize the probability
p
of the observed profile. In our case, by C2 (since p ∈ (0.5, 1], 1−p > 0.5), those are the rankings that
P ′
minimize i∈N dswap (≻i , ≻), thus proving the claim.

The theorem provides an MLE justification of the following voting rule, which is known as the Kemeny
rule [Kemeny, 1959].

Rule 12 (Kemeny). The Kemeny rule is the SCF defined as follows. For all profiles P:
( !)
X
Kemeny(P) = max(A) ∈ argmin dswap (i , ′ )
 ′ ∈L(A) i∈N
P
Fixing a linear order , i∈N dswap (i , ) is called the Kemeny distance of  to P.

Intuitively, the Kemeny rule first identifies the linear orders which minimize the Kemeny distance of the
order from the profile, then selects the top ranked alternatives in such linear orders.

Example 2.9 ([Young, 1995]). Let n = 60 and m = 3. Consider the following profile:

#23 a b c
#17 b c a
P = #2 b a c
#10 c a b
#8 c b a

Notice that the profile has no Condorcet winner. There are 3! possible linear orders. For each of
them we can calculate their Kemeny distance from the above profile. For example, let us consider
the order bca. We have:

23 · dswap (abc, bca) + 17 · dswap (bca, bca) + 2 · dswap (bac, bca) + 10 · dswap (cab, bca) + 8 · dswap (cba, bca)
= 46 + 0 + 2 + 20 + 8
= 76
 24

The Kemeny distance for the other rankings is computed in like fashion (left to the reader). The
ranking bca is in fact the one that minimizes the Kemeny distance. So Kemeny(P) = {b}.

Fact 2.2. Assume m = 2. Then, for any profile P ∈ L(A)n : Plurality(P) = Kemeny(P)

Proof. See Exercise 2.8.

As a corollary of the above fact and Theorem 2.3 we have that, on two alternatives, the plurality rule
(Rule 1) is the MLE (cf. Theorem 1.4) under the Condorcet’s assumptions.

The Borda rule as MLE

We have shown that the Kemeny rule, a natural generalization of plurality, is the MLE under the as-
sumptions C0-C3. By varying such assumptions it is possible to obtain similar MLE characterizations
for different rules (cf. [Conitzer and Sandholm, 2005]). Here we show how this can be done for the Borda
rule (Rule 7) by modifying in a specific way the error model (condition C2) in order to require a specific
probability for a voter to rank an alternative at position k under the condition that such alternative is the
top alternative in the correct ranking. In the case of Borda we are not interested in estimating the most
likely true ranking, but the most likely true winner (i.e., the most likely top alternative in the correct
ranking).11

Theorem 2.4 (Borda as MLE [Conitzer and Sandholm, 2005]). Let P = h1 , . . . , n i ∈ L(A)n be
randomly generated according to assumptions C0, C1, C3, C4 and assuming that

Pr( i(x) = k | max(A) = x ) ∼ 2m−k .



where i(x) denotes the rank of x in i’s ballot in P. Then the Borda rule is the MLE of the correct
winner.

Proof. By the constraint on Pr(i(x) = k | max (A) = x), the probability of observing profile P, given
the true preference ranks x as first, is therefore proportional to
n
Y Pn
2m−i(x) = 2( i=1
m−i(x))
.
i=1
P P
Notice that ni=1 m − i(x) = i∈N m − i(x) is precisely the Borda score (Rule 7). It follows that the
alternative with the highest Borda score is also the alternative that is most likely the correct winner given
the observed profile P.

2.3.3 Social choice as the closest consensus

As briefly mentioned above the consensus-based approach to social choice is based on the following idea:
we should first identify a compromise profile—a consensus—which is as close as possible to the observed
profile, and than use that compromise profile to determine the social choice. Depending on how the
notions of ‘consensus’ and ‘closeness’ are made precise, different voting rules may be characterized. In
this section we will discuss four prominent examples of characterizations of voting rules in terms of types
of consensus and distance.
As a first example we mention again the Kemeny rule (Rule 12). We can think of the Kemeny rule
as follows. First we identify a preference that is as close as possible—by swap distance—to the observed
profile. That preference is then taken up by every agent creating a strongly unanimous profile where
11
Technically this involves an MLE that is an SCF rather than a GSPF.
25

everybody agrees on the relative position of all alternatives. We can then take the top-ranked alternative
in that unanimous preference to determine the social choice. So the rule can be reformulated as follows:
  
 X 
Kemeny(P) = max
′
(A) i ∈ N and P′ ∈ argmin  dswap (Pj , P′′j ) (2.6)
 Pi P′′ ∈S 
j∈N

where S is the class of profiles P ∈ L(A)n such that ∀i, j ∈ N i =j (strong unanimity profiles). So
we can justify the Kemeny rule both from an MLE and a consensus-based perspective. Recall that Pi
denotes the i’th projection of P, i.e., the linear order i of i in P.
As a second simple example, we show that the plurality rule (Rule 1) is the SCF that minimizes the
discrete distance from a consensual profile where every voter ranks the same alternative first:

Theorem 2.5. For all P ∈ L(A)n

  
 X 
Plurality(P) = max
′
(A) i ∈ N and P′ ∈ argmin  ddiscr (Pj , P′′j )
 Pi P′′ ∈U 
j∈N

where U is the class of profiles P ∈ L(A)n such that ∀i, j ∈ N maxi (A) = maxj (A) (unanimity
profiles).

Proof. See Exercise 2.9.

Notice furthermore that since P′ ∈ U, the top-ranked alternative of each voter is the same. That is
why the social choice is determined by the top-ranked alternative of any agent i. So the plurality rule is
the rule that selects the alternatives that are unanimously top-ranked in profiles that minimize the total
distance—measured by ddiscr —from the input profile.
A similar characterization exists also for the Borda rule (Rule 7).

Theorem 2.6. For all P ∈ L(A)n

  
 X 
Borda(P) = max
′
(A) i ∈ N and P′ ∈ argmin  dswap (Pj , P′′j )
 Pi P′′ ∈U 
j∈N

where U is the class of unanimity profiles.

Proof. See Exercise 2.9.

Intuitively, under this characterization the Borda rule is the rule that selects the alternatives that are
unanimously top-ranked in profiles that minimize the total distance—measured this time by dswap —from
the input profile.
Finally, we introduce the last rule of this chapter, which was explicitly defined in terms of closest
consensus, the Dodgson rule [Dodgson, 1876].

Rule 13 (Dodgson). The Dodgson rule Dodgson is the SCF defined as follows. For all profiles P:
  
 X 
Dodgson(P) = Condorcet(P′ ) P′ ∈ argmin  dswap (P′′j , Pj )
 P′′ ∈C j∈N


where C is the class of profiles P ∈ L(A)n for which there exists a Condorcet winner (Condorcet
profiles) and Condorcet is the Condorcet rule (Rule 5).
 26

Rules Consensus class Distance

Plurality Unanimous Discrete
Borda Unanimous Swap
Kemeny Strongly unanimous Swap
Dodgson Condorcet Swap

Table 2.1: Types of consensus classes and distances for the characterizations of Plurality, Borda, Kemeny
and Dodgson.

Resoluteness Unanimity Condorcet-cons. Independence Monotonicity Liberalism

Dictatorship X X X X
Plurality
Condorcet X X X X
Copeland
Borda
STV

Table 2.2: Table stating which rules satisfy which axioms (only cases for Dictatorship and the Condorcet
rule are provided).

Intuitively the rule outputs the alternatives that are Condorcet winners in the Condorcet profiles that are
closest—according to dswap —to the input profile. Clearly such rule is Condorcet-consistent by definition.
Table 2.3.3 recapitulates the characterizations of the rules dealt with in this section in terms of type
of consensus and type of distance.

2.4 Chapter notes

The bulk of this chapter is again based on the introductions to voting theory provided in [Brandt et al., 2016,
Ch. 2], [Taylor, 2005, Ch. 1], [Endriss, 2011] and, in addition, [Taylor and Pacelli, 2008].
The proof of Arrow’s theorem presented above is based on [Hansson, 1976]. The first proof of Arrow’s
theorem based on the ultrafilter argument is due to [Fishburn, 1970] and [Kirman and Sondermann, 1972].
The theorem has been proved with a wealth of different arguments. See for instance [Barberá, 1980,
Reny, 2001, Geanakoplos, 2005].
Various generalizations and variants of Theorem 2.4 are studied in [Conitzer and Sandholm, 2005]. For
an overview of results about the MLE and consensus-based approaches to voting rules see [Elkind and Slinko, 2016].

2.5 Exercises
Exercise 2.1. Consider the following rule:

Rule 14 (Symmetric Borda). The symmetric Borda voting rule is the SCF defined as follows. For
all P ∈ L(A)n : X
Bordas (P) = argmax Net xy
P
x∈A y∈A

That is, the rule selects the alternatives that beat all other alternatives (in the corresponding majority
graph) by the largest margin. Prove that for any profile P: Borda(P) = Bordas (P).

Exercise 2.2. Come up with a ballot profile that has the property that all rules mentioned in Table 2.2
output a different social choice. You may ignore the Copeland rule (Rule 6).
27

Exercise 2.3. Consider Table 2.2. Rows correspond to voting rules, and columns to axioms we introduced
in this and the previous chapter. Choose two out of the four rules of Plurality, Copeland, Borda, STV.
Determine whether the rules you chose satisfy (X) or do not satisfy (no mark) the axioms given in the
columns of the table. Provide a proof for each such statement. By doing so you are completing Table 2.2.

Exercise 2.4. Provide a proof of Theorem 2.1. Hint argue towards a contradiction and construct a
profile in which liberalism and Pareto together would force an empty social choice, which we know is
impossible by the definition of SCF.

Exercise 2.5. Prove that every ultrafilter U on a an arbitrary set X (see the definition of ultrafilter
provided in Lemma 2.2) is closed under supersets. That is: if Y ∈ U and Y ⊆ Z ⊆ X then Z ∈ U.

Exercise 2.6. Let A = {a, b}, n odd and let Plurality⋆ denote the SPF corresponding to the plurality
rule we introduced as SCF (Rule 1). Consider the set of decisive coalitions DPlurality ⋆ under Plurality⋆ .
For each of the three properties of ultrafilters (cf. Lemma 2.2) prove that DPlurality⋆ satisfies that property
or provide a counter-example if it does not.

Exercise 2.7 (Properties of the Kemeny rule). Determine whether the Kemeny rule satisfies the proper-
ties in Table 2.2. Justify your answers.

Exercise 2.8. Prove Fact 2.2.

Exercise 2.9. Prove Theorem 2.5.

Exercise 2.10. Prove Theorem 2.6.

Exercise 2.11. Determine whether the Kemeny and Dodgson rules satisfy neutrality (Definition 1.2).
Justify your answer.
Chapter 3

Eliciting Truthful Ballots

The previous chapters tacitly assumed that the ballots provided by the voters report their genuine individ-
ual preferences: the voting rule can access truthful information and thus establish an appropriate social
choice, according to the specific logic driving the rule. However, voting rules may create incentives for
voters to misrepresent their true preferences by submitting a manipulated ballot to the rule, and thereby
steer the rule’s outcome towards better—for them—alternatives.

3.1 Preliminaries: strategic voting

3.1.1 Voting strategically
We start with three examples illustrating how voters could manipulate the social choice in their favour
by misrepresenting their true preferences to the voting rule.

Example 3.1 (Roman senate, continued). Consider again the profile discussed in Example 2.1

#102 a b c
#101 b a c
#100 c b a

Pliny demanded a vote by plurality that would lead to the choice of {a}. For 100 voters (bottom
row) this amounts to the worst possible alternative being selected as social choice. They have an
incentive to misrepresent their ballots by submitting b as their top-ranked alternative rather than c.
The plurality rule would then be applied to the profile

#102 a b c
#101 b a c
#100 b c a

leading to the choice of {b}.a

a
This is what in fact happened in the Roman senate, as documented in, e.g., [Szpiro, 2010].

Example 3.2 ([Zwicker, 2016]). Consider the following profile for N = {1, . . . 7} and A = {a, b, c, d, e}:

#2 a b c d e
P = #3 d e b c a
#2 e c a d b

The Borda rule selects {e} with a score of 17. For 2 voters—those with ballot abcde—this is the worst

28
29

possible alternative. It suffices for one of them, let it be voter 1, to modify his ballot to dabce in order
to have d instead selected as Borda winner. The new profile

#1 a b c d e
#1 d a b c e
P• =
#3 d e b c a
#2 e c a d b

is such that Borda(P• ) ≻1 Borda(P).

Example 3.3 ([Conitzer and Walsh, 2016]). Let now N = {1, 2, 3} and A = {a, b, c}, and suppose
the social choice is carried out using plurality with an alphabetic tie-breaking rule (a > b > c).
Consider now the following ballot profile:

1 a b c
P= 2 b a c
3 c b a

In this case the social choice would be {a}, making agent 3 the least happy with the choice since a
is ranked at the bottom of her preference. However, were 3 to misrepresent her ballot by reporting
b ≻3 c ≻3 a instead, b would become the social choice, granting her a better outcome.

3.1.2 Manipulability and strategy-proofness

The examples above show: that the Borda rule (Rule 7), in profiles where a single winner is selected, is
manipulable by a single voter;1 that the plurality rule (Rule 1) can be manipulated by a coalition of voters,
or by a single voter when it is supplemented by a deterministic tie-breaker (that enforces resoluteness).
We can make all the above forms of manipulation of a social choice process mathematically precise.
In this chapter, however, we will focus on single-voter manipulability of resolute rules as illustrated in
Example 3.3.

Definition 3.1. A resolute SCF f (for a given hN, Ai) is (single-voter) manipulable if there exist two
profiles

P = h1 , . . . , i , . . . n i and P• = h1 , . . . , i−1 , •i , i+1 , . . . , n i

such that f (P• ) ≻i f (P). We say then that i is a manipulator, that i is i’s truthful ballot and •i
is i’s untruthful (or manipulated, or strategic) ballot.a
a
Notice that by writing f (P• ) ≻i f (P) we slightly abuse notation as the output of f is, technically, a singleton.

Intuitively, an SCF is said to be manipulable whenever there exist situations (profiles) in which some
voter has an incentive to submit an untruthful ballot to the SCF, that is, by manipulating his balllot
the social choice is an alternative he prefers over the alternative that would be selected were he to vote
truthfully.
It is worth noticing that the definition makes a full information assumption on the manipulator: the
manipulator needs to know the ballots of all other agents in order to be able to select the right manipulated
ballot. This is in general unrealistic, but it is a reasonable assumption when n is small (e.g., deliberative
committees) or when accurate enough information is available in the form of opinion pools (e.g., political
elections). The assumption can also be interpreted as a worst-case assumption: as we cannot anticipate
the level of information of a potential manipulator, we should conservatively assume full information.
1
The French Academy of Sciences, of which Borda was a member, did experiment with the Borda rule but did not pursue
its use further exactly because of this susceptibility to manipulation. Borda famously responded to this criticism by stating
“My scheme is intended for only honest men" [Black, 1958].
 30

Remark 3.1 (Manipulability for irresolute SCFs). We defined manipulability only for resolute rules.
This is a simplifying—and arguably unrealistic—assumption, although we saw that resoluteness is a
by-product of natural requirements such as IIA and Pareto (Proposition 2.1). It is however possible
to define manipulability also in the context of irresolute SCFs. In such a case we need to specify how
voters may rank sets of alternatives. Two natural definitions have been explored (cf. [Taylor, 2005]):

• For an optimistic manipulator i, f (P) ≻i f (P′ ) whenever maxi (f (P)) ≻i maxi (f (P′ ));

• For a pessimistic manipulator i, f (P) ≻i f (P′ ) whenever mini (f (P)) ≻i mini (f (P′ )).

The problem with manipulability is that it creates the possibility for the process of social choice to be
mislead as profiles may no longer represent the true preferences of the voters. In addition, manipulability
creates indirect incentives for voters to invest energy and time into anticipating each others’ manipulative
behavior, rather than investing them on the substance of the decision at issue: if i knows that j has
an incentive to manipulate, she will try to adapt her ballot accordingly, at which point j may need to
reconsider her ballot again, and so on. This motivates the following axiom.

Definition 3.2. Let hN, Ai be given. A resolute SCF F is strategy-proof iff it is not manipulable.

That is, no voter ever has an incentive to misrepresent her ballot.2

3.1.3 Strategy-proofness and responsiveness axioms

Strategy-proofness in resolute SCFs is directly linked to the responsiveness properties introduced in Defi-
nition 1.3. In particular:

Lemma 3.1. Let hN, Ai be given. Let f be a resolute and strategy-proof SCF. Then:

(a) f is monotonic;

(b) f is independent;

(c) if f is non-imposed, it is Pareto.

Proof. (a) We prove the claim by contraposition. So assume f is not monotonic (Definition 1.3). Then
there exist two distinct alternatives x 6= y ∈ A and two profiles P, P′ ∈ L(A)n such that:
xy xy
• NP ⊆ NP′ , for all y ∈ A \ {x};
yz yz
• NP = NP′ , for all y, z ∈ A \ {x};

• f (P) = {x} and x 6∈ f (P′ ).

That is, in P′ some more voters rank x over y while keeping the rankings of all other alternatives
as in P, and shifting the winner to a different alternative from x. Let then f (P′ ) = {z} with
z 6= x. Notice there may be many such voters so there exists a sequence of intermediate profiles
P = P̂1 , . . . , P̂k = P′ differing only in the ballot of one voter and such that at some point 1 < ℓ ≤ k
we have that f (P̂ℓ−1 ) = {x} and f (P̂ℓ ) = {z}. So w.l.o.g. let us assume that P and P′ are such
profiles differing only in the ballot of one voter i who has raised the ranking of x w.r.t. y in her ballot.
yx xy ′ ′ ′
Observe that i ∈ NP ∩ NP ′ . There are two cases. x ≻i z Then in P (where still x ≻i z by how P is

constructed) i can manipulate by submitting i . z ≻i x Then in P i can manipulate by submitting

′i . In both cases f is therefore manipulable, which proves the claim.

(b) We prove the claim by contraposition. So assume f is not independent (Definition 2.5). Then there
xy xy
exist two profiles P, P′ ∈ L(A)n and two alternatives x, y ∈ A, such that NP = NP ′ , x ∈ f (P)

2
In game-theoretic terms we say that reporting a truthful ballot is a dominant strategy in the voting game hN, L(A)i , f, i i.
31

(therefore y 6∈ f (P) by resoluteness) and y ∈ f (P′ ) (therefore f (P′ ) = {y} by resoluteness). It follows
that: there exists i ∈ N such that i 6=′i . By an argument analogous to the one provided in (a) we
can focus w.l.o.g. to profiles P and P′ that differ only in the ballot of i. There are two cases. x ≻i y
Then in P′ (where still x ≻′i y by how the profile is constructed) i can manipulate by submitting
i . y ≻i x Then in P i can manipulate by submitting ′i . In both cases f is therefore manipulable,
which proves the claim.

(c) See Exercise 3.1.

All items have been proven and the proof is complete.

Any failure of monotonicity or independence in resolute SCFs generates a chance for manipulating behavior.
In addition, monotonicity guarantees Pareto in the presence of non-imposition.

3.2 There is no obvious strategy-proof social choice when m > 2

The question we are after in this section then is: are there ‘nice’ SCFs that are strategy-proof? Two
immediate SCFs come to mind. First, dictatorships are trivially strategy proof as all ballots, except the
dicator’s, are irrelevant to determine the social choice. Second, simple majority—that is, plurality when
m = 2—is also strategy-proof: reporting a manipulated ballot inevitably lowers the plurality score of the
top alternative.

3.2.1 Strategy-proofness when m = 2

For social choice contexts with two alternatives we can prove this simple consequence of May’s theorem:

Theorem 3.1. Let hN, Ai be given such that m = 2 and n is odd. A resolute SCF is anonymous,
neutral and strategy-proof if and only if it is plurality.

Proof. Right-to-left Straightforward. Left-to-right It follows from Theorem 1.1 and Lemma 3.1 (mono-
tonicity).

3.2.2 Strategy-proofness when m > 2

We prove a fundamental theorem—akin to Arrow’s (Theorem 2.2)—showing that there exists no resolute
SCF that is at the same time non-imposed, strategy-proof and non-dictatorial.

Theorem 3.2 (Gibbard-Satterthwaite theorem [Gibbard, 1973, Satterthwaite, 1975]). Let f be a

resolute SCF for a hN, Ai s.t. m > 2. f is non-imposed and strategy-proof if and only if it is a
dictatorship.

Proof strategy and blocking coalitions

The proof we present relies on a concept related to the concept of decisive coalitions in the proof of
Arrow’s theorem: blocking coalitions.

Definition 3.3 (Blocking coalition). Let f be a resolute SCF (for a given hN, Ai), and x, y ∈ A. A
coalition C ⊆ N is blocking for y by x, under f , if
xy
∀P ∈ L(A)n : if C ⊆ NP then y 6∈ f (P).

A coalition C ⊆ N is blocking if it is blocking w.r.t. every pair of alternatives. The set of all blocking
coalitions is denoted B. The set of blocking coalitions for yx (under f ) is denoted Bfyx (or simply B yx
when f is clear from the context).
 32

Observe that if B contains a singleton then there exists a voter i who is blocking for every pair of
alternatives. Therefore, for any profile P ∈ L(A)n , f (P) = {maxi (A)}, that is, i is a dictator (Definition
1.2).
The proof then relies on Lemma 3.1 and two further lemmas. The first one is an ultrafilter lemma for
the set of blocking coalitions: any resolute SCF that is strategy-proof and non-imposed induces a set of
blocking coalitions that takes the form of an ultrafilter. The second lemma is Lemma 2.3, which we used
also in the proof of Arrow’s theorem in the previous chapter.

The ultrafilter lemma for resolute, non-imposed, strategy-proof SCFs

Lemma 3.2 (Ultrafilter lemma). Let f be a resolute SCF (for a given hN, Ai), that satisfies non-
imposition and strategy-proofness. The set B of blocking coalitions (for f ) is an ultrafilter over N ,
that is:

i) N ∈ B, i.e., the set of all individuals is a decisive coalition;

ii) C ∈ B iff C 6∈ B, i.e., a coalition is decisive if and only if its complement is not;

iii) D is closed under finite intersections: if C, C ′ ∈ B then C ∩ C ′ ∈ B, i.e., if two coalitions are
winning then the individuals they have in common form a winning coalition.

Proof. i) By non-imposition, for any alternative x there exists a profile P such that f (P) = {x}. Now
xy
take such profile P and construct a profile P′ such that NP ′ = N for all y 6= x. By strategy-proofness
′
and Proposition 3.1 (monotonicity), f (P ) = {x}. Again by Proposition 3.1 (independence), it follows
that for any unanimous profile P′′ on x, y 6∈ f (P′′ ) for any alternative y 6= x. That is, N ∈ B.

ii) Left-to-right Suppose, towards a contradiction, that C, C ∈ B. Consider now a profile P where: for
xy yx
all i ∈ N the top two alternatives in each i are either x or y; and C = NP and C = NP . This
n
profile must exist as SCFs admit any profile in L(A) as input, and be such that x 6∈ F (P) and
y 6∈ F (P ). Hence there exists z ∈ A \ {x, y} such that f (P) = {z}, against Pareto (Lemma 3.1).
Right-to-left Assume C 6∈ B. Then there exists a profile P and alternatives x and y such that
xy xy xy
C ⊆ NP and f (P) = y. By Lemma 3.1 (independence) for every profile P′ such that NP = NP′,
′ yx yx
x 6∈ f (P ). That is, NP is a blocking coalition for x by y. Observe that NP ⊆ C. Then by Lemma
3.1 (monotonicity) C is also blocking for x by y. By adapting the argument provided earlier for
Lemma 2.1 (contagion lemma) we can conclude that C ∈ B (see Exercise 3.3).

iii) We proceed towards a contradiction and assume that C, D ∈ B and C ∩ D 6∈ B. By the previous
item, C ∩ D ∈ B. Construct a profile P with the following two features. One, all ballots are such
that the top 3 alternatives are either x, y or z. Second, the relative rankings of the alternatives in
{x, y, z} are as follows:3
C ∩D x y z
D\C y z x
C \D z x y
C ∪D z y x
We have that:

• (C ∩ D) ∪ (C \ D) = C, which is blocking by assumption. So, as for all i ∈ C x i y, it follows

that y 6∈ f (P);
• (C ∩ D) ∪ (D \ C) = D, which is decisive by assumption. So, as for all i ∈ D y i z, it follows
that z 6∈ f (P);
3
Cf. the same item in Lemma 2.2
33

• C ∪ D ∪ (C \ D) ∪ (D \ C) = C ∩ D, which is also blocking by claim ii). So, as for all i ∈ C ∩ D

z i x, it follows that x 6∈ f (P).

Therefore f (P) ∩ {x, y, z} = ∅. However, for all w 6∈ {x, y, z} there exists w′ ∈ {x, y, z} such that
w′ i w. By Proposition 3.1 (Pareto) then w 6∈ f (P). It follows that f (P) = ∅, which is impossible
by the definition of SCF (1.1). Contradiction.
All claims have been proven.

The proof
Proof of Theorem 3.2. Right-to-left It is straightforward to prove that a dictatorship is non-imposed and
strategy-proof. Left-to-right By Lemma 2.2 the set of blocking coalitions under f is an ultrafilter. By
Lemma 2.3 such ultrafilter is principal and therefore it contains a singleton. Such singleton is a blocking
coalition and therefore, by Definition 3.3 and the resoluteness of f , for any profile the social choice must
consist of the top-ranked alternative of the voter in the singleton. Therefore f is a dictatorship.

3.3 Coping with manipulability

So strategy-proofness is unattainable in general. Yet there are many ways to deal with this inherent
limitation of social choice functions. We overview some of them in this section.

3.3.1 Strategy-proofness when individual preferences are ‘coherent’

Example 3.4 (after [Zwicker, 2016]). Three friends want to go on a hike together. There are three
types of hikes: short s, medium m and long l. So the social choice context is h{1, 2, 3} , {s, m, l}i.
They hold the following true preferences:

1 l m s
P= 2 s m l
3 m s l

Observe that these preferences are aligned with the natural ordering of the alternatives based on
distance, from longest to shortest lms: an individual either prefers longer hikes over shorter ones; or
vice versa; or she prefers medium distance hikes. Let us denote this linear order by l ≫ m ≫ s. No
individual ranks the extremes (l and s) above the middle alternative (m). Diagrammatically, with
the line corresponding to 1, the dashed line to 2 and the dotted line to 3:

rank in ballot

1st

2nd

3rd

exogenous rank
s m l

There is a Condorcet winner in this profile: m.a This guarantees the top-ranked alternative for
3 and the second-best for 1 and 2. Furthermore, neither 1 nor 2 could obtain a better result by
 34

submitting a different ballot unless such ballot is not aligned any more with the natural ordering of
the alternatives l ≫ m ≫ s.
a
So Condorcet(P) = Copeland(P) = {m}.

Single-peakedness as a form of preference coherence

The example illustrates that when individual preferences are ‘similar enough’, then manipulability ceases
to be an issue. There are many ways in which this notion of ‘similarity’ or ‘coherence’ across individual
preferences can be made precise. Here we present one among the most well-known, and the one that was
first studied in the literature.

Definition 3.4 (Single-peakedness [Black, 1948]). A ballot i ∈ L(A) is single-peaked if there exists
a ≫∈ L(A) s.t., for all x, y ∈ A:

if ti ≫ x ≫ y or y ≫ x ≫ ti then x ≻i y

where ti = maxi (A) is called the peak of i (in i ). We say then that i is single-peaked with respect
to ≫. The set of single-peaked linear orders over A is denoted SPL(A).
A profile of linear orders is single-peaked if there exists a ≫∈ L(A) s.t for all i ∈ N , i is single-
peaked with respect to ≫. For a given profile P ∈ SPL(A)n we denote by tP the vector of peaks of
the ballots in P ordered by ≫.
Intuitively, a ballot is single-peaked whenever there exists an exogenous ranking on the alternatives such
that whenever an alternative x lies between the maximal of the ballot (the peak) and another alternatieve
y, then the ballot ranks x over y. A profile is single-peaked if all its ballots are single-peaked w.r.t. the
same exogenous ranking. The exogenous ranking ≫ represents a property (e.g., being left in the political
spectrum) that the alternatives enjoy to an increasing or decreasing degree. The reader should check that
profiles illustrating Condorcet’s paradox (Example 2.5) are not single-peaked. Finally, observe that when
m = 2 all profiles are trivially single-peaked.
Single-peaked profiles, or profiles that are single-peaked with high probability (cf. [Regenwetter et al., 2006]),
are natural in many settings (e.g., political elections, facility locations, committee decision-making). Em-
pirical studies have shown that single-peakedness is also sometimes the result of deliberative processes
changing agents’ preferences (cf. [List et al., 2013]).

Social choice on single-peaked preferences

We want to see whether single-peakedness can give us strategy-proofness. First of all observe that an SCF
defined on single-peaked profiles is a function
f : SPL(A)n → 2A \ ∅. (3.1)

Rule 15. The median rule is the SCF defined as follows. For all P ∈ SPL(A)n

Median(P) = {x ∈ A | x is median in tP }

Observe that with the profile P of Example 3.4 Median(P) = Condorcet(P) = {m}. The Condorcet
winner is the top-ranked alternative of the median voter.

Theorem 3.3 (Black’s theorem [Black, 1948]). Let P ∈ SPL(A)n . Then:

(a) If n is even, the weak majority tournament Net

P (Definition 2.2) is transitive and if n is odd, the
Net
majority tournament ≻P is transitive.

(b) If n is odd then Median(P) is the singleton containing the Condorcet winner in P. If n is even
35

then Median(P) is the set of weak Condorcet winners in P.

(c) For n odd, Median is strategy-proof.

Proof. (a) We have to consider two cases: n even and n odd. n odd We want to prove that, for all
distinct x, y, z ∈ A, x ≻Net y and y ≻Net z implies x ≻Net z. There are two cases to consider.

B(xyz) By assumption x ≻Net y we have that N xy > n2 . Since y is between x and z in ≫, by

single-peakedness it follows that for every i ∈ N xy , y ≻i z. From this, by the transitivity of
individual preferences we obtain N xz > n2 and therefore x ≻Net z as desired.
B(yxz) By assumption x ≻Net y we have that N xy > n2 . Now suppose towards a contradiction that
z Net x. By single-peakedness, all agents i ∈ N zx would prefer z over y by transitivity, against
the assumption that y ≻Net z. We thus conclude that x ≻Net z as desired.
B(xzy) By assumption x ≻Net y and y ≻Net z. By the above assumptions there exists an agent i
such that x ≻i y ≻i z. However, this preference is not single-peaked under the assumption that
z lies between x and y. As we assumed that P ∈ SPL(A)n this case is therefore impossible.

In all (possible) cases we conclude x ≻Net z as desired, proving the claim. n even The argument is
similar and needs to consider the possibility of split majorities in pairwise comparisons.

(b) There are two cases. n odd Then Median(P ) is a singleton {ti }. We need to show that for all x ∈ A,
N ti ,x > 0. Now let: * +
tP = . . . , ti , |{z}
|{z} ...
L R

For all voters j whose peaks appear in L we have that ti is preferred over any alternative x to the
right of ti in ≫ (and therefore to any peak in R). Vice versa, for all voters j whose peaks appear in
R we have that ti is preferred over any alternative y to the left of ti in ≫ (and therefore to any peak
in L). It follows that ti beats any other alternative in a pairwise comparison, i.e., it is a Condorcet
winner.
n odd Then Median(P) contains two elements {ti , tj }. Assume w.l.o.g. that ti ≫ tj . Now let:
* +
tP = . . . , ti , tj |{z}
|{z} ...
L R

We reason in a similar fashion as in the case for n odd to conclude that ti and tj are weak Condorcet
winners.

(c) Let P be given, and let i be the manipulator. Assume w.l.o.g. that i’s peak lies to the right (w.r.t.
≫) of Median(P). She has two ways to manipulate her ballot by submitting an untruthful peak t′i .
ti ≫ t′i Submit a ballot with peak t′i further to the right of ti . In such a case Median(P) would not
change. t′i ≫ ti Submit a ballot with peak t′i to the left of ti . In such a case, if Median(P) changes,
it changes to an alternative further away (w.r.t. ≫) to i’s truthful peak. So no manipulation for i
exists.
The proof is complete.

In this section we showed how the issue of manipulability can be sidestepped when it is possible to
make certain assumptions about the coherence of the voters’ true preferences. If restricting the domain
of SCFs in such a way is not possible, there are a number of other avenues that have been explored in
order to manage the issue of manipulability. We turn to them now, just sketching the key ideas behind
each approach.
 36

3.3.2 Making manipulation difficult

We sketch three ways in which manipulations, even though possible, may be considered difficult or unlikely:
by making them computationally intractable, by making their informational requirements matter, and by
introducing randomness in the SCFs. We sketch them in turn.

Using computational complexity

The key intuition of this approach is the following: even if an SCF is manipulable, finding the manipulating
strategy may be an intractable computational problem. The task of finding a suitable manipulation can
be approximated by considering the following decision problem:

Given A partial profile P−i without the vote of the manipulator i; and i’s preferred alternative x

Question Is there a ballot i that i can submit so that f (P−i , i ) = {x}?

It has been shown (e.g., [Bartholdi et al., 1989]) that the above decision problem is solvable in time
polynomial (in n + m) for many of the rules we discussed (Plurality, Borda) by using a simple greedy
algorithm that works as follows:

Initialization: Rank x at the top;

Repeat: Check whether another alternative can be ranked immediately below the previous one without
making x lose; if that is the case, do so; if that is not possible, manipulation is impossible.

However, the problem has been shown to be intractable (NP-hard) for some other common rules like,
in particular, STV (Rule 11) [Bartholdi and Orlin, 1991].

Using uncertainty
Definition 3.1 can be modified in order to make it sensitive to the knowledge that is actually available to
the manipulator.

Definition 3.5 (Dominating manipulations [Conitzer et al., 2011]). Fix a true profile P (for a given
n
hN, Ai). Let IS : N → 2L(A) assign to each voter a set of profiles (information set) such that
P ∈ IS(i) for all i ∈ N , and all profiles in IS(i) agree on i . A resolute SCF f is vulnerable to
dominating manipulations (in P) if there exist a voter i and ballot •i s.t

(a) f (P′−i , •i ) i f (P′ ) for all P′ ∈ IS(i),

(b) f (P′−i , •i ) ≻i f (P′ ) for some P′ ∈ IS(i)

where P′−i denotes the partial profile obtained from P′ by removing i’s ballot. Ballot •i is called a
dominating manipulation by i. An SCF is said to be immune to dominating manipulations iff it is
not vulnerable to dominating manipulations in any P.

Observe that dominating manipulations reduce to simple manipulations (Definition 3.1) whenever a ma-
nipulator has full information, that is, his information set is {P}. The definition allows then to break the
negative result of Gibbard-Satterthwaite theorem by exploiting the fact that the larger the information
set, the harder it becomes to find a dominating manipulation.

Fact 3.1. The Borda rule with a deterministic tie-breaking rule is immune to dominating manipulation
when the manipulator’s information set is ⊆-maximal (i.e., the manipulator has no information).

Proof. See Exercise 3.8.

37

By randomization
One way to rule out (deterministic) manipulations altogether is by introducing randomization in the
workings of SCFs. A randomized SCF (RSCF) is a function

r : L(A)n → ∆(A) (3.2)

P
where ∆(A) = {x ∈ Rm | ∀i ∈ A, xi ≥ 0 and i∈A xi = 1} is the set of all lotteries (distributions) over
A.
An elegant theorem by Gibbard [Gibbard, 1977] shows that the random draw of one agent (the so-
called randomized dictatorship) from N is the only RSCF that is ‘lottery’ strategy-proof (in the specific
sense of stochastic dominance4 ) and ‘lottery’ efficient (in the sense of never assigning positive probability
to alternatives that are Pareto dominated).

3.3.3 Letting manipulation be

What happens if every voter is allowed to act as a manipulator? In particular, can we quantify exactly
how bad the social choice on the fully manipulated profile would be when compared with the social choice
supported by a truthful profile? To answer this question requires a game-theoretic perspective on voting.5
Any (resolute) SCF f for a given context hN, Ai induces an ordinal game G = hN, A, L(A)n , P, f i
where:

• N is the set of players;

• A is the set of outcomes;

• L(A) is the strategy space of each agent (this could be coarsened to A, e.g., for plurality);

• P are the (true) preferences of the players;

• f is the outcome function mapping strategy profiles to outcomes.

A (pure-strategy) Nash Equilibrium of G is a profile P = h1 , . . . , n i such that there exists no player
i ∈ N such that for some ′i
f (P−i , ′i ) ≻i f (P)
That is, no player can profit by unilaterally misrepresenting her preference with a different ballot. In
other words, no agent has a so-called profitable deviation in P. Another way to think of Nash Equilibria is
via graphs over the set of profiles. The set N E(G) of Nash equilibria of G are also the sinks in the graph
hL(A)n , →i where → links two profiles whenever the second can be obtained from the first by letting one
agent execute a profitable deviation.

Example 3.5. Recall Example 3.3 with N = {1, 2, 3} and A = {a, b, c}, and f be plurality with an
alphabetic tie-breaking rule (a > b > c). Assume the following profile of true preferences

1 a c b
P= 2 b c a
3 c b a

From this profile agent 3 has a best response consisting of ballot bca, leading to a NE where {b} is
the social choice. Similarly, agent 2 has also a best response consisting of ballot cba, which leads to

4
P P
A lottery p stochastically dominates a lottery q for i iff x∈A:xPi y
p(x) ≥ x∈A:xPi y
q(y), for any y ∈ A. A sortition
rule is strategy-proof, w.r.t. stochastic dominance if for all i ∈ N , it never selects a lottery which is stochastically dominated
by another lottery for i.
5
For an introduction to game theory see [Osborne and Rubinstein, 1994].
 38

a NE where, instead, {c} is the social choice.

The question that has been asked in the iterative voting literature [Brânzei et al., 2013, Meir, 2018a]
is how far a NE is from the truthful profile, once such NE is obtained through a sequence of best responses
starting at the truthful profile. A way to make this question precise for the class of scoring rules (Definition
2.4) is by using the so-called (dynamic) price of anarchy:

sf (f (P), P)
P oA(f ) = min ′min (3.3)
P P ∈N EP sf (f (P′ ), P′ )

where sf (x, P) denotes the score of x given P according to f , and N EP is the set of NE reachable from
P via best-response dynamics. That is, PoA denotes the worst case ratio between the true score of an
alternative and the score it would receive in equilibrium.
It has been shown [Brânzei et al., 2013] that P oA(Plurality), with a deterministic tie-breaker, is
close to 1. In other words, full-blown manipulation does not have much impact on the quality of the
outcome. A much more negative result has been proven for the Borda rule (cf. [Brânzei et al., 2013]).

3.4 Chapter notes

The bulk of this chapter is again based on the introductions to voting theory provided in [Brandt et al., 2016,
Ch. 2], [Taylor, 2005, Ch. 1], [Endriss, 2011] and [Taylor and Pacelli, 2008].
The proof of Theorem 3.2 is based on [Batteau et al., 1981]. Since the original articles [Gibbard, 1973,
Satterthwaite, 1975] many alternative proofs of the theorem have been presented, e.g.: [Barberá, 1983,
Benoît, 2000].
Section 3.3 is based on several sources: [Conitzer and Walsh, 2016] (complexity of manipulation),
[Brandt, 2018] (randomization), [Meir, 2018a] (voting games), [Conitzer et al., 2011] (information).

3.5 Exercises
Exercise 3.1. Prove item iii) of Lemma 3.1.
Exercise 3.2. Define a variant of manipulability for irresolute SCFs as follows: an SCF f (for a given
hN, Ai) is manipulable if there exist two profiles

P = h1 , . . . , i , . . . n i and P• = h1 , . . . , i−1 , •i , i+1 , . . . , n i

such that f (P• ) and f (P) are singletons and f (P• ) ≻i f (P).
Prove that the Plurality rule (Rule 1) is not manipulable according to the above definition.
Exercise 3.3. Let F be a resolute SPF (for a given hN, Ai) which is non-imposed and strategy-proof.
Prove that if C ∈ B xy for some x, y ∈ A, then C ∈ B. This is the equivalent of the contagion lemma
(Lemma 2.1) for the Gibbard-Sattertwhaite theorem (Theorem 3.2).
Exercise 3.4. In no more than three sentences discuss the differences between Arrow’s theorem (Theorem
2.2) and the Gibbard-Sattertwhaite theorem (Theorem 3.2).
Exercise 3.5. For |A| = m, |L(A)n | = (m!)n . Now fix an order ≫. How many single-peaked profiles
exist for ≫? Justify your answer.
Exercise 3.6. Determine whether the median voter rule (Rule 15) satisfies: unanimity, independence,
monotonicity. Justify your answers.
Exercise 3.7. Use the variant of May’s theorem with ties (Theorem 1.2) to prove that, when m = 2, the
median rule (Rule 15) is anonymous, neutral and positively responsive.
Exercise 3.8. Prove Fact 3.1.
39

Exercise 3.9. Does the Gibbard-Satterthwaite theorem (Theorem 3.2) still hold if we drop the assumption
of non-imposition? Justify your answer. If the theorem still holds explain how the proof can go through
without that assumption. If the theorem does not hold any more, and therefore there exist SCFs which
is strategy-proof and non-dictatorial, provide one of such functions.
Chapter 4

Choosing Many Out of Many

The social choice problem we considered so far concerns how to select one ‘best’ alternative given a profile
of individual rankings, or more generally a set of tied ‘best’ alternatives. In this chapter we present some
results on the related problem of selecting one ‘best’ set of alternatives—a so-called committee—or, more
generally, one tied set of sets of ‘best’ alternatives. Voting for committee selection is a much more recent,
and therefore less consolidated, area of research in social choice and many directions of research in this
area are still open.

4.1 Preliminaries
We follow the same approach used to introduce and discuss social choice functions: we provide the general
definition of functions for committee selection; we then provide concrete examples of such functions; and
we finally show how also these functions can be studied from an axiomatic point of view.

4.1.1 Multi-winner social choice

We are interested in situations where a subset of alternatives of a given size k ≤ m, the committee, is to
be selected based on the preferences over A of n individuals. Given a context hN, Ai a multi-winner SCF
or committee-selection function (CSF), for a given committee size 1 ≤ k ≤ n, is a function

fk : L(A)n → 2{X⊆A | |X|=k}

\∅ (4.1)

Given a profile of linear orders, the function outputs a set of sets of alternatives (i.e., a set of committees),
all of size k. Obviously a CSF f1 is equivalent to an SCF, as it selects a committee of size 1. When we
leave k unspecified, we talk about a family of CSFs mapping every integer k in {1, . . . n} to the CSF fk .
In this chapter, we refer to families of CSFs as committee selection or multi-winner rules.

Remark 4.1. Notice that there is a natural way in the problem of committee selection can be casted
as a social choice problem where committees of size k are the D alternatives
n relevantoEfor the social
A
choice. In other words the social choice context would be N, X ⊆ 2 | |X| = k , and voters


would need to submit ballots ranking all elements in such a set, which would therefore m k long.
Given a profile of such ballot an SCF could be applied to select a tied set of committees. The type in
(4.1) takes a different—and for obvious reasons more practical—approach selecting committees using
only information consisting of rankings of alternatives.

4.1.2 Where are CSFs relevant

Three application domains are normally mentioned for CSFs:

Excellence-driven Here the issue is to select the best k alternatives from A. A typical example of this
type of committee selection problem are shortlisting processes.
40
41

Diversity-driven Here the issue is to select k alternatives that can cover all possible views on A. Typical
examples of this type are: facility location problems (e.g., where to place k new schools), movie
selection for an airline entertainment system, product selection for the homepage of an internet
store.

Proportionality-driven Here the issue is to select k alternatives that represent the views of N propor-
tionally. The typical example are parliamentary elections.

All the above domains come intuitively with different requirements on how the CSF should ideally behave
in order to select suitable committees. Such intuitive requirements underpin the axiomatic perspective
on CSFs we present in Section 4.3 below.

4.2 Some multi-winner voting rules

For each of the application domains mentioned above we provide examples of common multi-winner rules.
Finally we also provide examples of staged rules for committee selection which are commonly used in
practice.

4.2.1 Excellence-driven rules

To introduce some of the rules in this class we need some auxiliary terminology. Best-k multiwinner rules
are based on the notion of social preference function (SPF) we encountered in Chapter 2. Recall that these
functions map profiles of linear orders (the individual preference) to a total preorder, that is, a ranking
that may contain ties. Notice, however, that each total preorder  can be represented by a set of linear
orders, that is, all the possible linear orders that one obtains by resolving the ties in . The intuition
behind best-k multiwinner rules is to form a committee by simply selecting the top k alternatives in some
of those linear orders representing possible social preferences.
One more piece of notation: to the note the top k element of a linear order ∈ A2 we write maxk (A).
We move now to the formal definition.

Definition 4.1 (Best-k rules). Given an SPF G a best-k rule BestG (for G) is the family of CSFs
defined as follows. For any profile P ∈ L(A)n and integer 1 ≤ k ≤ n
 
k
BestG
k (P) = X ⊆ A | exists ∈ G(P), s.t. X = max (A) .


A family of CSFs f is said to be a best-k rule whenever there exists a G such that, for every 1 ≤ k ≤ n,
fk = BestGk (P).

Depending on the choice of G in Definition 16 we obtain different multi-winner rules. In particular, if

we take G to be the GSPF associating to any profile the set of linear orders refining a weak order induced
by an SPF F (like a scoring function) we obtain, for example:

Rule 16. The following are best-k (1 ≤ k ≤ n) multiwinner rules:

Plurality
k-Plurality , i.e., Bestk (P), also known as single non-transferable vote
Approvalk
k-Approval , i.e., Bestk (P), also known as bloc voting

k-Borda , i.e., BestBorda

k (P)

where Plurality, Approval and Borda refer to the SPFs ranking alternatives by their plurality,
approval and, respectively, Borda scores.
 42

One can in the same fashion use the Copeland (Rule 6), Kemeny (Rule 12) or Dodgson (Rule 13) scores to
obtain the corresponding rankings and then cut them to the top k alternatives to obtain the committee.
These are sometimes referred to also as ‘score-and-cut’ and ‘rank-and-cut’ rules.

4.2.2 Diversity-driven rules

Several diversity-driven multiwinner rules can be formulated as follows:

Definition 4.2 (Chamberlin-Courant [Chamberlin and Courant, 1985]). For an integer 1 ≤ k ≤ n

and scoring vector w (Definition 2.4) a Chamberlin-Courant rule for size k is defined as follows. For
any profile P ∈ L(A)n : X X
CCwk (P) = argmax wi(x)
C,|C|=k x∈C i∈N Cx
P

where NP Cx = {i ∈ N | x = max (C)} is the set of voters i that rank x as top among the alternatives
i
in C (x is then said to be the representative of i in C); and i(x) as usual denotes the position of x in
P P
i . Quantity x∈C i∈N Cx wi(x) is called the representativeness value of a given committee C.
P

By varying the scoring vector w we thus obtain different families of CSFs. For example:

Rule 17. The Borda-based k-Chamberlin-Courant multiwinner rule is the rule CCw
k where w is the
Borda scoring vector.

The intuition behind this rule is simple. It forms the committee that contains as many representatives as
possible, and with the highest possible Borda score. So, if an alternative is to be added to the committee,
alternatives with higher ranks from agents not already represented by the committee will be preferred
over alternatives with lower ranks from agents already represented by the committee.

4.2.3 Proportionality-driven rules

A simple proportionality-driven rule based on approval voting is the following one:

Rule 18. The proportional k-approval voting rule is defined as follows (1 ≤ k ≤ n):
 
X 1 1
PAVk (P) = argmax 1 + + . . . + 
C,|C|=k i∈N 2 k
maxi ∩ C

That is, the rule looks at the top k candidates in each individual preference (cf. Rule 9) and tries to
find the committee that maximizes a score that is computed by giving to each agent i as many points as
1 + 21 + . . . + 1ℓ , where ℓ is the number of alternatives in the committee that are approved by i. So, notice
that the rule will always give priority to committees that contain a few alternatives from more agents
rather than committees that contain many alternatives from fewer agents, like in the Chamberlin-Courant
rules. At the same time, alternatives that are more often approved of will be more likely to be included
in the committee, reflecting a form of proportionality.

Remark 4.2. The way we defined PAVk is more restrictive than the way in which proportional
approval voting is normally defined in the literature, where it is based on simple approval voting rather
than k-approval. Cf. [Faliszewski et al., 2017]. Proportional approval voting was first proposed by
the Danish matematician Thorvald Thiele at the end of the 19th century in [Thiele, 1895], at the
dawn of electoral suffrage in the Nordic countries. It is for this reason also known as Thiele method.
The rule was used in practice at the beginning of the 20th century in Sweden.

4.2.4 Choose-and-repeat rules

43

Rule 19 (Sequential plurality). The sequential plurality rule is the CSF defined as follows, for any
profile P ∈ L(A)n and integer k ≥ 1:
n n oo
SPluralityk (P) = X | exist x1 , . . . , xk s.t. X = x1 , . . . , xk

where each xi is inductively defined as follows, with 1 ≤ ℓ < k:

• x1 = Plurality(P) with some tie-breaking;

• xℓ+1 = Plurality(P|A\{x1 ,...,xℓ } ) with some tie-breaking.

It is worth observing that sequential plurality and k-plurality are different rules as they elect different
committees (see Exercise 4.1).

Rule 20 (Single transferable vote for committees). The single transferable vote rule for committee
selection (CSTV) is the CSF defined as follows, for any profile P and k ≤ 1:
n D E o
CSTVk (P) = X | ∃S ℓ = X ℓ , Pℓ s.t. X ℓ = k

where stages S ℓ are recursively defined as follows:

D E
S 0 = X 0 , P0 where X 0 = ∅, P0 = P
    
 X ℓ ∪ {x} , Pℓ |A\{x}

if Plurality(Pℓ )(x) ≥ q
S ℓ+1 = D E −C
 X ℓ , Pℓ |A\{y}

otherwise

where: Plurality(Pℓ ) denotes the plurality score; y ∈ argminz∈A (Plurality(Pℓ )(z)), i.e., y has
lowest plurality score; C ⊆ N is a set of size q consisting of voters who rank x as top in their
n
preferences in profile Pℓ ; and q = ⌊ k+1 ⌋ + 1.

Intuitively at each stage the following happens: an alternative is added to the committee if the plurality
score of such alternative meets the threshold q (there may be many such sets), and if that is the case
the alternative is discarded as well as a set of voters of size q (there may be many such sets); otherwise
no alternative is added to the committee and a plurality loser (there may be many such alternatives) is
discared. The above is repeated until a committee of size k is constructed.
Observe that the rule is non-deterministic, involving several tie-breaking decisions at each step. Intu-
itively all different committees resulting from different tie-breaking decisions are recorded in the output
of the rule.1

Example 4.1 ([Faliszewski et al., 2017]). Consider the following profile for {1, . . . , 6} and {a, b, c, d, e}:

1 a b c d e
2 e a b d c
3 d a b c e
P=
4 c b d e a
5 c b e a d
6 b c d e a

1
This is sometimes referred to as the parallel-universe tie-breaking model.
 44

We have:

CSTV2 (P) = {{b, c} , . . . left to the reader . . .}

Plurality
Best2 (P) = {{c, a} , {c, b} , {c, d} , {c, e}}
hm−1,m−2,...,0i
CC2 (P) = {{a, c}}
PAV2 (P) = {{a, b}}

hm−1,m−2,...,0i
In the CC2 rule a represents voters in {1, 2, 3} and c represents voters in {4, 5, 6}. In the
PAV2 the winning committee {a, b} obtains 6.5 points.

n
Remark 4.3 (Droop quota). The quota q = ⌊ k+1 ⌋+1 in the committee STV Rule 20 above is known
as the Droop quota, from Richmond Droop, English lawyer and mathematician who introduced it
(see [Droop, 1881]). It is the most commonly used quota for STV committee elections, for instance
in the Republic of Ireland. The quota is the smallest integer that guarantees that no candidate who
would reach the quota would then have no place available in the committee. So it is a generalization
of the idea of simple majority when electing committees of size k = 1. It can be derived as follows.
The quota q should satisfy two constraints: k · q ≤ n, i.e., the number of candidates meeting the
quota cannot exceed the number of voters; and n ≤ k · q + (q − 1), i.e., there cannot be a k + 1th
candidate who meets the quota. From this we obtain:
   
n+1 n n
= +1≤q ≤ .
k+1 k+1 k
Taking the smallest q satisfying the above inequalities thus gives us the Droop quota.

4.3 Axiomatic results

In this section we showcase the application of the axiomatic method to the case of multi-winner rules.
We focus on the generalization of the notion of Condorcet-consistency (recall Definition 2.5) to the case
of committee selection.

4.3.1 Condorcet consistency and monotonicity

Definition 4.3 (Condorcet committees [Gehrlein, 1985]). Let a profile P (for hN, Ai) be given. A
set C ⊆ A is a weak Condorcet committee if, for all x ∈ C and y 6∈ C, #xy yx
P ≥ #P . For a given profile
P, we denote its set of Condorcet commitees of size k by CCk (P).

Intuitively, a committee is Condorcet consistent whenever it does not elect any alternative for which a
different alternative is preferred by a majority of voters. Notice that the set of Condorcet committees for
a given size k may be empty.

Example 4.2 ([Barberá and Coelho, 2008]).

1 a b c d e
2 a b e c d
3 a b d e c
P=
4 c d e a b
5 e c d a b
6 d e c a b
45

We have that CC1 (P) = {{a}}, CC2 (P) = {{a, b}} and CC3 (P) = {{c, d, e}}.

Definition 4.4. A family of CSFs f (for a given hN, Ai) is:

Condorcet consistent (or) stable iff for all P ∈ L(A)n , and 1 ≤ k ≤ n, fk (P) ⊆ CCk (P) whenever
CCk (P) 6= ∅.
Intuitively, the rule always selects a weak Condorcet committee when one exists.

Committee monotonic iff for all P ∈ L(A)n and 1 ≤ k < n,

• if there exists C ∈ fk (P) then there exists C ′ ∈ fk+1 (P) s.t. C ⊂ C ′ ;

• if there exists C ′ ∈ fk+1 (P) then there exists C ∈ fk (P) s.t. C ⊂ C ′ .

Intuitively, an alternative selected for a small committee should be selected also in larger com-
mittees.

Observe that the first condition of committee monotonicity would suffice to express the axiom if f is a
family of resolute CSFs.

Theorem 4.1 ([Barberá and Coelho, 2008]). There exists no family of CSFs f such that f is Con-
dorcet consistent and committee monotonic.

Proof. Assume towards a contradiction that this is not the case: there exists fk such that, for any k,
fk is Condorcet consistent and committee monotonic. Let P be the profile of Example 4.2. Since f2
is Condorcet consistent by assumption, {a, b} ∈ f2 (P). Similarly, {c, d, e} ∈ f3 (P). This is a failure of
committee monotonicity. Contradiction.

Theorem 4.2 ([Elkind et al., 2017]). A family of CSFs f is committee-monotonic if and only if it is
a best-k rule.

Sketch of proof. Right-to-left Best-k rules are committee monotonic by construction (Definition 4.1).
Left-to-right The proof is by construction. Given a committee monotonic multiwinner rule f we can
define a SPF Gf which, for every profile P, chooses a social preference (total pre-order)  such that the
alternatives in  with rank k are precisely the elements in fk (P)\fk−1 (P). Given G Definition 4.1 gives
us a best-k rule as desired.

4.3.2 Proportionality
In recent years, the application of the axiomatic method to CSFs has focused especially on trying to tease
out the many ways in which the notion of proportionality can actually be interpreted. A wealth of axioms—
as well as rules inspired by them—have been studied which capture different notions of proportionality, and
highlight the richness of the concept. For example: extended justified representation [Aziz et al., 2017];
laminar proportionality [Peters and Skowron, 2020]; priceability [Peters and Skowron, 2020].

4.4 Chapter notes

Multiwinner rules are a very recent, and rapidly developing, area of research within computational social
choice. The chapter is based on [Barberá and Coelho, 2008, Elkind et al., 2017, Faliszewski et al., 2017].
 46

4.5 Exercises
Plurality
Exercise 4.1. Construct a profile, and fix a k, such that SPluralityk (P) (Rule 19) and Bestk (P)
(one of the rules in Rule 16) output different committees of size k for P. Try to make such profile as small
as possible. Based on your example explain the difference between the two rules.
Approval
Exercise 4.2. Construct a profile, and fix a k, such that Bestk k
(one of the rules in Rule 16) and
PAVk (Rule 18) output different committees of size k for P. Try to make such profile as small as possible.
Based on your example explain the difference between the two rules.

Exercise 4.3. Every committee selection function fk defines a social choice function when k = 1. What
are the social choice functions defined by:

i) CCw
1 , where w is the Borda scoring vector (Definition 17);

ii) CCw
1 , where w is the ℓ-approval vector, where 1 ≤ ℓ ≤ m (recall Definition 9);

iii) PAV1 (Definition 18).

Explain your answers.

Chapter 5

Topics for Projects

This is a list of topics, in no specific order and with relevant blibliography, to be chosen from for the final
papers.

Liquid democracy Liquid democracy is a form of voting where voting rights can be delegated tran-
sitively. It has been advocated in [Behrens et al., 2014] and used by, among others, the Pirate Party
in Germany and France. A series of recent papers have focused on various aspects of the system:
[Kling et al., 2015, Blum and Zuber, 2016, Christoff and Grossi, 2017, Bloembergen et al., 2019, Kahng et al., 2018,
Caragiannis and Micha, 2019, Zhang and Grossi, 2021]. See also [Behrens, 2017] for a history of the con-
cept.

Participatory budgeting The participatory budgeting problem consists in selecting a set of projects
within a given budget, based on the preferences of citizens in a given area (e.g., municipality)1 . A
number of papers have recently proposed and studied different voting rules for participatory budgeting
and studied their properties: [Benade et al., 2017, Aziz et al., 2018, Goel et al., 2019, Jain et al., 2020].
Again the aim is to identify ‘optimal’ rules. See [Aziz and Shah, 2020] for a recent overview.

Voting with preference intensity The type of voting covered in these lecture notes adhered to
the ‘one-voter-one-vote’ principle. This makes it impossible for voters to signal the ‘intensity’ of their
preferences (how much I like x over y). Voting rules have been suggested that make the signaling of
preference intensities possible. Here are some examples: cumulative voting [Glasser, 1959], storable voting
[Casella, 2005, Casella et al., 2006], quadratic voting [Lalley and Weyl, 2018].

Evaluative voting We are accustomed to an idea of voting in which we are asked to express our pref-
erences, rather than judging on the quality of a candidate or a policy proposal. A number of new
voting methods have been proposed which more clearly frame the social choice problem as a prob-
lem of evaluation: approval & disapproval voting [Alcantud and Laruelle, 2013], majority judgments
[Balinski and Laraki, 2014].

Randomized voting In the early days of democracy randomization played an important role and was
considered a quintessentially fair mechanism (e.g., in the Athenian democracy public officials were selected
by lottery). Growing research is currently focusing on the use of randomization to improve on standard
deterministic voting-based social choice. A good recent overview article is [Brandt, 2018].

Sybil-resilient voting A key problem of voting mechanisms over the internet is the possibility of
Sybil attacks (that is, voters can generate arbitrarily many identities thereby manipulating the outcome).
Considerable research has been dedicated to the development of voting mechanisms that can be, to a
1
Maybe good to know that a participatory budgeting pilot has been run in autumn 2019 Oosterparkwijk, Groningen. One
more is currently being run in Helpman, Groningen
47
 48

smaller or larger extent, resistant to this form of attack [Conitzer and Yokoo, 2010, Todo et al., 2011,
Waggoner et al., 2012, Wagman and Conitzer, 2008, Wagman and Conitzer, 2014, Shahaf et al., 2019].

Epistemic social choice Epistemic social choice develops the insights of jury theorems such as Con-
dorcet’s by making more realistic assumptions over voters competence and independence. A good recent
overview article is [Pivato, 2019].

Judgment aggregation We have studied the social choice problem as a problem of aggregation of
preferences, but more generally it can be framed as a problem of aggregation of logical formulas. This is
the perspective taken in so-called judgment aggregation [Endriss, 2016, Grossi and Pigozzi, 2014].

Strategic voting In Chapter 3 we discussed the issue of strategic or tactical voting, and touched on
some basic game-theoretic aspects. Extensive literature exists on strategic voting and a comprehensive
overview of the topic is [Meir, 2018b].

Doodle pool voting Doodle pools work with a form of approval voting (cf. Rule 9) giving rise to inter-
esting forms of manipulative behavior. A few recent papers have looked into this issue [James et al., 2015,
Obraztsova et al., 2017, Anthony and Chung, 2018] and modeled Doodle pools as a special type of voting
games.

Agenda manipulation SCFs are executed by central authorities (government, businesses, etc.). Such
central authorities running the voting mechanisms may have the power to decide the agenda (the alterna-
tives) of a social choice context. Can they, by changing such set, obtain better outcomes for themselves?
This is the issue of agenda setting or agenda manipulation. An introduction to the topic, with further
relevant references, is [Taylor, 2005, Section 2.4].

Incomplete preferences and elicitation In this course we assumed profiles consisted of complete
descriptions of the preferences of all agents. However, in many settings, eliciting the full linear order
from each agent may be unfeasible (e.g., because of the sheer size of the set of alternatives). Re-
cent work has extended some of the notions we studied to the setting with incomplete preferences:
[Terzopoulou and Endriss, 2019, Kruger and Terzopoulou, 2020]. A related line of research has looked
at the problem of how to best elicit voter’s preferences in order to determine winners, depending on the
different voting rules: how many queries, and how complex, does a voting rule need in order to compute
a social choice? A good starting point for this line of work is [Brandt et al., 2016, Ch. 10]. The problem
is also directly relevant to applications in participatory democracy (see, e.g. [Lee et al., 2014]).

Participation axioms An SCF suffers of the no show paradox whenever there exist profiles in which
an agent would do better by not casting their ballot under the rule. An SCF is then said to satisfy the
participation axiom if it does not suffer of the no show paradox. A good introduction to this axiom, how
it relates to monotonicity and strategy-proofness axioms, as well as relevant related literature, can be
found in [Brandt et al., 2016, Ch. 2].

Voting theory and ensemble classifiers An established approach in Machine Learning to improve
the performance in classification tasks is by ‘combining’ the decisions of various individual classifiers. One
way to combine classifiers is to use voting and some papers have explored how different voting rule affect
performance in classification tasks by ensembles [Mu et al., 2009, Cornelio et al., 2019].
Bibliography

[Alcantud and Laruelle, 2013] Alcantud, J. C. and Laruelle, A. (2013). Dis&approval voting: A charac-
terization. Social Choice and Welfare, 43(1):1–10.

[Anthony and Chung, 2018] Anthony, B. and Chung, C. (2018). How bad is selfish doodle voting? In
Proceedings of AAAI’18, pages 1856–1858.

[Arrow, 1950] Arrow, K. (1950). A difficulty in the concept of social welfare. Journal of Political Economy,
58(4):328–346.

[Arrow, 1963] Arrow, K. (1963). Social Choice and Individual Values. John Wiley, New York, 2nd edition.

[Aziz et al., 2017] Aziz, H., Brill, M., Elkind, E., Freeman, R., and Walsh, T. (2017). Justified represen-
tation in approval-based committee voting. Social Choice and Welfare, 48(2):461–485.

[Aziz et al., 2018] Aziz, H., Lee, B. E., and Talmon, N. (2018). Proportionally representative participatory
budgeting: Axioms and algorithms. In Proceedings of the 17th International Conference on Autonomous
Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 23–31.

[Aziz and Shah, 2020] Aziz, H. and Shah, N. (2020). Participatory budgeting: Models and approaches.

[Balinski and Laraki, 2014] Balinski, M. and Laraki, R. (2014). Judge: Don’t vote! Operations Research,
62(3):483–511.

[Barberá, 1980] Barberá, S. (1980). Pivotal voters: A new proof of arrow’s theorem. Economic Letters,
6(1):13–16.

[Barberá, 1983] Barberá, S. (1983). Strategy-proofness and pivotal voters: A direct proof of the gibbard-
satterthwaite theorem. International Economic Review, 24(2):413–417.

[Barberá and Coelho, 2008] Barberá, S. and Coelho, P. (2008). How to choose a non-controversial list
with k names. Social Choice and Welfare, 31:79–96.

[Bartholdi and Orlin, 1991] Bartholdi, J. and Orlin, J. (1991). Single transferable vote resists strategic
voting. Social Choice and Welfare, 8(4):341–354.

[Bartholdi et al., 1989] Bartholdi, J., Tovey, C., and Trick, M. (1989). The computational difficulty of
manipulating an election. Social Choice and Welfare, 6(3):227–241.

[Batteau et al., 1981] Batteau, P., Blin, J., and Monjardet, B. (1981). Stability of aggregation procedures,
ultrafilters, and simple games. Econometrica, 49(2):527–534.

[Behrens, 2017] Behrens, J. (2017). The origins of liquid democracy on electronic participation, collective
moderation, and voting systems. The Liquid Democracy Journal, 5.

[Behrens et al., 2014] Behrens, J., Kistner, A., Nitsche, A., and Swierczek, B. (2014). Principles of Liquid
Feedback. Interaktieve Demokratie.
49
 50

[Benade et al., 2017] Benade, G., Nath, S., Procaccia, A., and Shah, N. (2017). Preference elicitation for
participatory budgeting. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence,
February 4-9, 2017, San Francisco, California, USA, pages 376–382.

[Benoît, 2000] Benoît, J.-P. (2000). The Gibbard-Satterthwaite theorem: A simple proof. Economic
Letters, 69(3):319–322.

[Black, 1948] Black, D. (1948). On the rationale of group decision making. The Journal of Political
Economy, 56:23–34.

[Black, 1958] Black, D. (1958). The Theory of Committees and Elections. Cambridge University Press.

[Bloembergen et al., 2019] Bloembergen, D., Grossi, D., and Lackner, M. (2019). On rational delegations
in liquid democracy. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI’19).

[Blum and Zuber, 2016] Blum, C. and Zuber, C. I. (2016). Liquid democracy: Potentials, problems, and
perspectives. Journal of Political Philosophy, 24(2):162–182.

[Brandt, 2018] Brandt, F. (2018). Rolling the dice: Recent results in probabilistic social choice. In
Endriss, U., editor, Trends in Computational Social Choice. COST.

[Brandt et al., 2016] Brandt, F., Conitzer, V., Endriss, U., Lang, J., and Procaccia, A., editors (2016).
Handbook of Computational Social Choice. Cambridge University Press.

[Brânzei et al., 2013] Brânzei, S., Caragiannis, I., Morgenstern, J., and Procaccia, A. (2013). How bad is
selfish voting? In Proc. of the 27th Conference on Artificial Intelligence (AAAI-13).

[Caragiannis and Micha, 2019] Caragiannis, I. and Micha, E. (2019). A contribution to the critique of
liquid democracy. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial
Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 116–122.

[Cartan, 1937] Cartan, H. (1937). Filtres et ultrafiltres. Comptes Rendus de l’Académie des Sciences,
pages 777–779.

[Casella, 2005] Casella, A. (2005). Storable votes. Games and Economic Behavior, 51(2):391–419.

[Casella et al., 2006] Casella, A., Gelman, A., and Palfrey, T. (2006). An experimental study of storable
votes. Games and Economic Behavior, 57(1):123–154.

[Chamberlin and Courant, 1985] Chamberlin, J. R. and Courant, P. N. (1985). Representative deliber-
ations and representative decisions: Proportional representation and the borda rule. The American
Political Science Review, 77(3).

[Christoff and Grossi, 2017] Christoff, Z. and Grossi, D. (2017). Binary voting with delegable proxy: An
analysis of liquid democracy. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality
and Knowledge (TARK’17), volume 251, pages 134–150. EPTCS.

[Condorcet, 1785] Condorcet, M.J.A.N. de C., M. d. (1785). Essai sur l’Application de l’Analyse à la
Probabilité des Décisions Rendues à la Pluralité des Voix. Imprimerie Royale, Paris.

[Conitzer and Sandholm, 2005] Conitzer, V. and Sandholm, T. (2005). Common voting rules as maxi-
mum likelihood estimators. In Proceedings of the 21st Annual Conference on Uncertainty in Artificial
Intelligence (UAI-05).

[Conitzer and Walsh, 2016] Conitzer, V. and Walsh, T. (2016). Barriers to manipulation in voting. In
Handbook of Computational Social Choice, chapter 6, pages 127–145. Cambridge University Press.

[Conitzer et al., 2011] Conitzer, V., Walsh, T., and Xia, L. (2011). Dominating manipulations in voting
with partial information. In Proceedings of AAAI’11.
51

[Conitzer and Yokoo, 2010] Conitzer, V. and Yokoo, M. (2010). Using mechanism design to prevent
false-name manipulations. AI Magazine, 31(4):65–77.

[Copeland, 1951] Copeland, A. H. (1951). A ‘reasonable’ social welfare function. Seminar on mathematics
in social sciences, University of Michigan.

[Cornelio et al., 2019] Cornelio, C., Donini, M., Loreggia, A., Pini, M. S., and Rossi, F. (2019). Voting
with random classifiers (VORACE). CoRR.

[Dasgupta and Maskin, 2004] Dasgupta, P. and Maskin, E. (2004). The fairest vote of all. Scientific
American, pages 92–97.

[Dietrich and Spiekermann, 2020] Dietrich, F. and Spiekermann, K. (2020). Jury theorems. In The
Routledge Handbook of Social Epistemology. Routledge.

[Dodgson, 1876] Dodgson, C. L. (1876). A method of taking votes on more than two issues. Oxford:
Clarendon Press.

[Droop, 1881] Droop, H. R. (1881). On methods of electing representatives. Journal of the Statistical
Society of London, 44(2):141–196.

[Elkind et al., 2017] Elkind, E., Faliszewski, P., Skowron, P., and Slinko, A. (2017). Properties of multi-
winner voting rules. Social Choice and Welfare, 48:599–632.

[Elkind and Slinko, 2016] Elkind, E. and Slinko, A. (2016). Rationalizations of voting rules. In Handbook
of Computational Social Choice, chapter 8, pages 169–196. Cambridge University Press.

[Endriss, 2011] Endriss, U. (2011). Logic and social choice. In Logic and Philosophy Today. College
Publications.

[Endriss, 2016] Endriss, U. (2016). Judgment aggregation. In Brandt, F., Conitzer, V., Endriss, U., Lang,
J., and Procaccia, A. D., editors, Handbook of Computational Social Choice, chapter 17. Cambridge
University Press.

[Faliszewski et al., 2017] Faliszewski, P., Skowron, P., Slinko, A., and Talmon, N. (2017). Multiwinner
Voting: A New Challenge for Social Choice Theory, chapter 2. AI Access.

[Fishburn, 1970] Fishburn, P. C. (1970). Arrow’s impossibility theorem: Concise proof and infinite voters.
Journal of Economic Theory, 2(1):103–106.

[Geanakoplos, 2005] Geanakoplos, J. (2005). Three brief proofs of arrow’s theorem. Economic Theory,
26(1):211–215.

[Gehrlein, 1985] Gehrlein, W. V. (1985). The condorcet criterion and committee selection. Mathematical
Social Sciences, 10(3):199–209.

[Gibbard, 1973] Gibbard, A. (1973). Manipulation of voting schemes: A general result. Econometrica,
41(4):587–601.

[Gibbard, 1977] Gibbard, A. (1977). Manipulation of schemes that mix voting with chance. Econometrica,
45(3).

[Glasser, 1959] Glasser, G. J. (1959). Game theory and cumulative voting for corporate directors. Man-
agement Science, 5:151–156.

[Goel et al., 2019] Goel, A., Krishnaswamy, A., Sakshuwong, S., and Aitamurto, T. (2019). Knapsack
voting for participatory budgeting. ACM Trans. Economics and Comput., 7(2):8:1–8:27.
 52

[Grossi and Pigozzi, 2014] Grossi, D. and Pigozzi, G. (2014). Judgment aggregation: A primer. Synthesis
Lectures on Artificial Intelligence and Machine Learning, 8(2):1–151.

[Hansson, 1976] Hansson, B. (1976). The existence of group preference functions. Public Choice, 28:89–98.

[Hare, 1859] Hare, T. (1859). Treatise on the Election of Representatives, Parliamentary and Municipal.
Longman, Brown, Green, Longmans, and Roberts.

[J.-C., 1781] J.-C., B. (1781). Mémoire sur les Élections au Scrutin. Histoire de l’Académie Royeal des
Sciences.

[Jain et al., 2020] Jain, P., Sornat, K., and Talmon, N. (2020). Participatory budgeting with project in-
teractions. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,
IJCAI 2020, pages 386–392.

[James et al., 2015] James, Z., Meir, R., and Parkes, D. (2015). Strategic voting behavior in doodle
polls. In Proceedings of 18th ACM conference on Computer-Supported Cooperative Work and Social
Computing, pages 464–472. ACM.

[Kahng et al., 2018] Kahng, A., Mackenzie, S., and Procaccia, A. (2018). Liquid democracy: An algorith-
mic perspective. In Proc. 32nd AAAI Conference on Artificial Intelligence (AAAI’18).

[Kemeny, 1959] Kemeny, J. (1959). Mathematics without numbers. Daedalus, 88:577–591.

[Kirman and Sondermann, 1972] Kirman, A. P. and Sondermann, D. (1972). Arrow’s theorem, many
agents, and invisible dictators. Journal of Economic Theory, 5(2):267–277.

[Kling et al., 2015] Kling, C., Kunegis, J., Hartmann, H., Strohmaier, M., and Staab, S. (2015). Voting
behaviour and power in online democracy: A study of LiquidFeedback in Germany’s Pirate Party. In
Proceedings of the International Conference on Weblogs and Social Media.

[Kruger and Terzopoulou, 2020] Kruger, J. and Terzopoulou, Z. (2020). Strategic manipulation with
incomplete preferences: Possibilities and impossibilities for positional scoring rules. In Proceedings
of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20,
Auckland, New Zealand, May 9-13, 2020, pages 645–653.

[Lalley and Weyl, 2018] Lalley, S. and Weyl, E. G. (2018). Quadratic voting: How mechanism design can
radicalize democracy. [Link]

[Lee et al., 2014] Lee, D. T., Goel, A., Aitamurto, T., and Landemore, H. (2014). Crowdsourcing for
participatory democracies: Efficient elicitation of social choice functions. In Proceedings of the Second
AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014, November 2-4, 2014,
Pittsburgh, Pennsylvania, USA.

[List et al., 2013] List, C., Luskin, R., Fishkin, J., and I., M. (2013). Deliberation, single-peakedness,
and the possibility of meaningful democracy: Evidence from deliberative polls. The Journal of Politics,
75(1):80–95.

[Llull, 1275] Llull, R. (1275). Artifitium electionis personarum.

[Link]

[Mallows, 1957] Mallows, C. L. (1957). Non-null ranking models. Biometrika, 44:114–130.

[May, 1952] May, K. (1952). A set of independent necessary and sufficient conditions for simple majority
decision. Econometrica, 20:680–684.

[McGarvey, 1953] McGarvey, D. (1953). A theorem on the construction of voting paradoxes. Economet-
rica, 21(4):608–610.
53

[Meir, 2018a] Meir, R. (2018a). Iterative voting. In Trends in Computational Social Choice, pages 69–86.
COST.

[Meir, 2018b] Meir, R. (2018b). Strategic Voting. Synthesis Lectures on Artificial Intelligence and Machine
Learning. Morgan & Claypool Publishers.

[Moore and Shannon, 1956] Moore, E. and Shannon, C. (1956). Reliable circuits using less reliable relays.
Journal of the Franklin Institute, 262(3):191–208.

[Mu et al., 2009] Mu, X., Watta, P., and Hassoun, M. H. (2009). Analysis of a plurality voting-based
combination of classifiers. Neural Process. Lett., 29(2):89–107.

[Obraztsova et al., 2017] Obraztsova, S., Polukarov, M., Rabinovich, Z., and Elkind, E. (2017). Doodle
poll games. In Proceedings of AAMAS’17, pages 876–884.

[Ordeshoek, 2003] Ordeshoek, P. (2003). Game Theory and Political Theory. An Introduction. Cambridge
University Press.

[Osborne and Rubinstein, 1994] Osborne, M. J. and Rubinstein, A. (1994). A Course in Game Theory.
MIT Press.

[Pareto, 1919] Pareto, V. (1919). Manuale di Economia Politica con una Introduzione alla Scienza Sociale.
Societá Editrice Libraria.

[Peters and Skowron, 2020] Peters, D. and Skowron, P. (2020). Proportionality and the limits of welfarism.
In EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July
13-17, 2020, pages 793–794.

[Pivato, 2019] Pivato, M. (2019). Realizing epistemic democracy. In Laslier, J.-F., Moulin, H., Sanver,
M. R., and Zwicker, W. S., editors, The Future of Economic Design, pages 103–112. Springer.

[Regenwetter et al., 2006] Regenwetter, M., Grofman, B., Marley, A., and Tsetin, I. (2006). Behavioral
Social Choice. Cambridge University Press.

[Reny, 2001] Reny, P. (2001). Arrow’s theorem and the gibbard-satterthwaite theorem: A unified ap-
proach. Economic Letters, 70:99–105.

[Satterthwaite, 1975] Satterthwaite, M. A. (1975). Strategy-proofness and Arrow’s conditions: Existence

and correspondence theorems for voting procedures and social welfare functions. Journal of Economic
Theory, 10(2):187–217.

[Shahaf et al., 2019] Shahaf, G., Shapiro, E., and Talmon, N. (2019). Sybil-resilient reality-aware social
choice. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence,
IJCAI 2019, Macao, China, August 10-16, 2019, pages 572–579.

[Slater, 1961] Slater, P. (1961). Inconsistencies in a schedule of paired comparisons. Biometrika, 48(3–
4):303–312.

[Szpiro, 2010] Szpiro, G. (2010). Numbers Rule: The Vexing Mathematics of Democracy, from Plato to
the Present. Princeton University Press.

[Taylor and Pacelli, 2008] Taylor, A. and Pacelli, A. (2008). Mathematics and Politics. Springer.

[Taylor, 2005] Taylor, A. D. (2005). Social Choice and the Mathematics of Manipulation. Cambridge
University Press.

[Terzopoulou and Endriss, 2019] Terzopoulou, Z. and Endriss, U. (2019). Aggregating incomplete pair-
wise preferences by weight. In Proceedings of the Twenty-Eighth International Joint Conference on
Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 595–601.
 54

[Thiele, 1895] Thiele, T. N. (1895). Om flerfoldsvalg.

[Todo et al., 2011] Todo, T., Iwasaki, A., and Yokoo, M. (2011). False-name-proof mechanism design
without money. In Proceedings of AAMAS’11, pages 651–658. IFAAMAS.

[Truchnon, 2008] Truchnon, M. (2008). Borda and the maximum likelihood approach to vote aggregation.
Mathematical Social Sciences, 55(1):96–102.

[Waggoner et al., 2012] Waggoner, B., Xia, L., and Conitzer, V. (2012). Evaluating resistance to false-
name manipulations in elections. In Proceedings of AAAI’12, pages 1485–1491.

[Wagman and Conitzer, 2008] Wagman, L. and Conitzer, V. (2008). Optimal false-name proof voting
rules with costly voting. In AAAI’08, pages 190–195.

[Wagman and Conitzer, 2014] Wagman, L. and Conitzer, V. (2014). False-name-proof voting with costs
over two alternatives. International Journal of Game Theory, 43(3):599–618.

[Young, 1988] Young, H. P. (1988). Condorcet’s theory of voting. American Political Science Review,
82(4):1231–1244.

[Young, 1995] Young, H. P. (1995). Optimal voting rules. Journal of Economic Perspectives, pages 51–64.

[Zhang and Grossi, 2021] Zhang, Y. and Grossi, D. (2021). Power in liquid democracy. In Proceedings of
AAAI’21.

[Zwicker, 2016] Zwicker, W. (2016). Introduction to voting theory. In Handbook of Computational Social
Choice, chapter 1, pages 23–56. Cambridge University Press.