## Approximability of Dodgson’s Rule

JOHNC. M^{C}CABE-DANSTED

Department of Mathematics, Auckland University [email protected]

DRGEOFFREY PRITCHARD

Department of Statistics, Auckland University [email protected]

DRARKADII SLINKO

Department of Mathematics, Auckland University [email protected]

25 August 2006

**A****BSTRACT****.** It is known that Dodgson’s rule is computationally very demanding. Tideman
(1987) suggested an approximation to it but did not investigate how often his approximation se-
lects the Dodgson winner. We show that under the Impartial Culture assumption the probability
that the Tideman winner is the Dodgson winner tend to 1. However we show that the conver-
gence of this probability to 1 is slow. We suggest another approximation — we call it Dodgson
Quick — for which this convergence is exponentially fast. Also we show that Simpson and Dodg-
son rules are asymptotically different. We formulate, and heavily use in construction of examples,
the generalization of M^{c}Garvey’s theorem (1953) for weighted majority relations.

**JEL C****LASSIFICATION****:** D7

**K****EYWORDS****:** Dodgson’s rule, Simpson’s rule, M^{c}Garvey’s Theorem, weighted majority rela-
tion, Impartial Culture assumption.

The official version of this paper is published in Social Choice and Welfare.

Seehttp://dx.doi.org/10.1007/s00355-007-0282-8.

**1 Introduction**

Condorcet proposed that a winner of an election is not legitimate unless a majority of the popula- tion prefer that alternative to all other alternatives. However such a winner does not always exist.

A number of voting rules have been proposed which select the Condorcet winner if it exists, and otherwise selects an alternative that is in some sense closest to being a Condorcet Winner. A prime example of such as rule was the one proposed by Dodgson (1876).

Unfortunately, Bartholdi et al. (1989) proved that finding the Dodgson winner is an NP-hard
problem. Hemaspaandra et al. (1997) refined this result by proving that it is Θ^{p}_{2}-complete and
hence is not NP-complete unless the polynomial hierarchy collapses. As Dodgson’s rule is hard to
compute, it is important to have simple and fast approximations to it. We investigate the asymp-
totic behaviour of simple approximations to the Dodgson rule as the number of agents gets large.

Tideman (1987) suggested an approximation but did not investigate its convergence to Dodgson.

We prove that under the assumption that all votes are independent and each type of vote is equally likely (the Impartial Culture (IC) assumption), the probability that the Tideman (1987) approxima- tion picks the Dodgson winner asymptotically converge to 1, but not exponentially fast.

We propose a new social choice rule, which we call Dodgson Quick. The Dodgson Quick ap- proximation does exhibit exponential convergence to Dodgson, and we can quickly verify that it has chosen the Dodgson winner. This, together with it simplicity and other nice properties, makes our new approximation useful in computing the Dodgson winner. Despite its simplicity, our approximation picked the correct winner in all of 1,000,000 elections with 85 agents and 5 alternations, each generated randomly according to the Impartial Culture assumption. Our ap- proximation can also be used to develop an algorithm to determine the Dodgson winner with O(lnn)expected running time for a fixed number of alternatives andnagents.

A result independently obtained by Homan and Hemaspaandra (2005) has a lot in common with our result formulated in the previous paragraph, but there are important distinctions as well.

They developed a “greedy” algorithm that, given a profile, finds the Dodgson winner with certain probability. Under the Impartial Culture assumption this probability also approaches 1 as we increase the number of agents. However they do not suggest any rule with a simple mathematical definition and, unlike their algorithm, the Dodgson Quick rule requires only the information in the weighted majority relation. This makes the Dodgson Quick rule easier to study and compare to other simple rules such as the Tideman rule.

Our experimental results (M^{c}Cabe-Dansted and Slinko, 2006) showed that Simpson’s and Dodg-
son’s rules are very close. However, in the present paper we discover that under the Impartial
Culture assumption, the frequency that the Simpson rule picks the Dodgson winner does not con-
verge to one.

M^{c}Garvey (1953) proved that for any tournament, we can find a profile such that the tournament
is the majority relation on that profile. However, when we pass from a profile to the majority
relation on that profile, we lose all the information about the margins of defeat. By retaining
this information we obtained the so-called weighted majority relation on the profile. Weighted
majority relation can be represented as an ordinary tournament with advantages attached to its

edges, i.e. by a weighted tournament. For the purposes of constructing the examples in this paper we need a generalisation of McGarvey’s theorem to weighted tournaments. Fortunately it can be done, and for any weighted tournament, it is possible to find a society with that weighted tournament as its weighted majority relation, if and only if all the weights are even or all the weights are odd.

The first paper that mentions this result was probably Debord’s PhD thesis (1987) as quoted by Vidu (1999). However this source is inaccessible to the authors. We view this result as important and give an independent proof of it in this paper.

**2 Preliminaries**

LetAandN be two finite sets of cardinalitymandnrespectively. The elements ofAwill be called alternatives, the elements ofN agents. We assume that the agents have preferences over the set of alternatives represented by (strict) linear orders. ByL(A)we denote the set of all linear orders on A. The elements of the Cartesian product

L(A)^{n}=L(A)× · · · × L(A) (ntimes) (1)
are called**profiles. The profiles represent the collection of preferences of an**n-element society of
agentsN. A family of mappingsF ={F_{n}},n∈N,

F_{n}:L(A)^{n}→A, (2)

is called a**social choice function**(SCF).

LetP = (P1, P2, . . . , Pn)be a profile. If a linear orderPi ∈ L(A)represents the preferences of the
i^{th}agent, then byaPib, wherea, b∈A, we denote that this agent prefersatob. We definenxy to be
the number of linear orders inP that rankxabovey, i.e. n_{xy} = #{i|xP_{i}y}. The approximations
we consider depend upon the information contained in the matrixNP, where(NP)_{ab} = n_{ab}. A
functionW^{P}:A×A→Zgiven byW^{P}(a, b) =nab−n_{ba}for alla, b∈A, will be called the**weighted**
**majority relation**onP. It is obviously skew symmetric, i.e.W^{P}(a, b) =−W^{P}(b, a)for alla, b∈A.

Many of the rules to determine the winner use the numbers

adv(a, b) = max(0, nab−n_{ba}) = (n_{ab}−n_{ba})^{+}, (3)
which will be called**advantages. Note that adv(a, b) =** max(0, W(a, b)) = W(a, b)^{+}whereW is
the weighted majority relation onP.

A**Condorcet winner**is an alternativeafor which adv(b, a) = 0for all other alternatives b. A
Condorcet winner does not always exist. The rules we consider below attempt to pick an alterna-
tive that is in some sense closest to being a Condorcet winner. These rules will always pick the
Condorcet winner when it exists; such rules are called Condorcet consistant rules.

The social choice rules we consider are based on calculating the vector of**scores**and the alter-
native with the lowest score wins. Let the lowest score be s. It is possible that more than one

alternative has a score ofs. In this case we may have a set of winners with cardinality greater than one. Strictly speaking, to be a social choice function, a rule has to output a single winner. Rules are commonly modified to achieve this by splitting ties. One of the most popular methods of splitting ties is to use for this purpose the preference of the first agent. However we will usually study the set of tied winners rather than the single winner output from a tie-breaking procedure, as this will give us more information about the rules.

The **Dodgson score**(Dodgson 1876, see e.g. Black 1958; Tideman 1987), which we denote as
Sc** _{d}**(a), of an alternative a is the minimum number of neighbouring alternatives that must be
swapped to makeaa Condorcet winner. We call the alternative(s) with the lowest Dodgson score
the

**Dodgson winner(s).**

The**Simpson score**(Simpson 1969, see e.g. Laslier 1997)Sc** _{s}**(a)of an alternativeais
Sc

**(a) = max**

_{s}b6=a adv(b, a). (4)

We call the alternative(s) with the lowest Simpson score the **Simpson winner(s). That is, the**
alternative with the smallest maximum defeat is the Simpson winner. This is why the rule is often
known as the Maximin or Minimax rule.

The**Tideman score**(Tideman, 1987)Sc** _{t}**(a)of an alternativeais
Sc

**(a) =X**

_{t}b6=a

adv(b, a). (5)

We call the alternative(s) with the lowest Tideman score the**Tideman winner(s). Tideman (1987)**
suggested the rule based on this score as an approximation to Dodgson.

The**Dodgson Quick (DQ) score**Sc** _{q}**(a)of an alternativea, which we introduce in this paper, is
Sc

**(a) = X**

_{q}b6=a

F(b, a), (6)

where

F(b, a) =

adv(b, a) 2

. (7)

We call the alternative(s) with the lowest Dodgson Quick score the**Dodgson Quick winner(s) or**
**DQ-winner.**

The **Impartial Culture** assumption (IC) stipulates that all possible profiles P ∈ L(A)^{n} are
equally likely to represent the collection of preferences of ann-element society of agents N, i.e.

all agents are independent and they choose their linear orders from the uniform distribution on
L(A). This assumption is of course does not accurately reflect the voting behaviour of most vot-
ing societies. Worse, we have found that the choice of probability model for the population can
affect the similarities between approximations to the Dodgson rule (M^{c}Cabe-Dansted and Slinko,
2006). However the IC is the simplest assumption available. As noted by Berg (1985), many
voting theorists have chosen to focus their research upon the IC. Thus an in depth study of the

approximability of Dodgson’s rule under the Impartial Culture is a natural first step.

The IC leads to the followingm!-dimensional multinomial distribution. Let us enumerate all
m!linear orders in some way. LetP ∈ L(A)^{n}be a random profile. Let thenX be a vector where
eachX_{i}, fori = 1,2, . . . , m!, represents the number of occurrences of thei^{th} linear order in the
profileP. Then, under the IC, the vectorXis(n, k,p)-multinomially distributed withk=m!and
p=1_{k}/k= (^{1}_{k},_{k}^{1}, . . . ,_{k}^{1}).

**3 A M**

^{c}**Garvey Theorem for Weighted Tournaments**

The M^{c}Garvey Theorem (1953) is states that every tournament can be represented as a majority
relation for a certain society of voters. We will prove a generalization of the M^{c}Garvey Theorem
to weighted tournaments and weighted majority relations.

Like most other authors, Laslier (1997) defines weighted tournaments as matrices and tourna- ments as (complete and asymmetric) binary relations. However Laslier notes that there are many different equivalent definitions of tournaments, of which Laslier gives four examples. In this pa- per we define both tournaments and weighted tournaments as functions, for consistency.

**Definition 3.1** A**weighted tournament**on a setAis any functionW:A×A→ZsatisfyingW(a, b) =

−W(b, a)for alla, b∈A.

We callW(a, b)the**weight**of an ordered pair of distinct elements(a, b). One can view weighted
tournaments as complete directed graphs whose edges are assigned integers characterising the
intensity and the sign of the relation between the two vertices that this particular edge connects.

The only condition is that if an edge fromatobis assigned integerz, then the edge frombtoais assigned the integer−z.

Weighted majority relationW^{P}on a profilePdefined earlier in this paper is a prime example of
a weighted tournament. We say that a profileP **generates**a weighted tournamentW ifW =W^{P}.
We note that adv(a, b) = W^{P}(a, b)^{+}, where x^{+} = max(0, x). Similarly W^{P}(a, b) = adv(a, b)−
adv(b, a). Another important example is the classical tournament onA which can be identified
with a weighted tournamentW whose all weightsW(a, b)are 1 or−1.

**Definition 3.2** For a weighted tournamentW, for which all weightsW(a, b)are non-zero, we define the
**reduction**ofW to be the tournamentWS, where:

WS(a, b) =

1 if W(a, b)>0,

−1 if W(a, b)<0, 0 if a=b.

(8)

For any weighted tournamentW for which there exista6=bsuch thatW(a, b) = 0, this reduction
is not defined. We note that ifnis odd andW^{P}is the weighted majority relation on the profileP,
then the reductionW_{S}^{P}is the classical majority relation on the profileP.

We are now ready to formulate the main result of this section.

**Theorem 3.3** Let W be a weighted tournament. Then there exists a profile that generates a weighted
tournamentW if and only if all weights inW have the same parity (either all odd or all even).

The proof will be split into three lemmata.

**Lemma 3.4** LetW^{P} be a weighted majority relation on a profileP withnagents, then all weights inW^{P}
have the same parity asn. That is, for each pair of distinct alternativesaandb, the weightW^{P}(a, b)is even
if and only ifnis even.

Proof. We know that for all alternativesaandb we haveW^{P}(a, b) = n_{ab}−n_{ba} andn =
n_{ba}+n_{ab}. HenceW^{P}(a, b) +n= 2n_{ab}and soW^{P}(a, b)andnhave the same parity.

**Lemma 3.5** For a weighted tournamentW with all weights being even, we may construct a profileP that
generatesW.

Proof. We may construct such a profile as follows. We start with an empty profileP. For each ordered pair of alternatives(a, b), for which the weightW(a, b)is positive, we letk=W(a, b)/2.

We take the linear orderv, on the set of alternativesA, such thatavbandbvxfor allx 6=a, band
the linear orderwsuch thatawbandxwafor allx6=a, b. We addkinstances ofvandkinstances
of w to the profile P. After we have done this for every pair (a, b), it is easy to check that the
resulting profile generates weighted majority relation W^{P} such thatW^{P}(a, b) = W(a, b) for all
a, b∈A.

For the last lemma we will need the following definition.

**Definition 3.6** LetW1 andW2 be two weighted tournaments. We define their sumW1 +W2 and their
differenceW_{1}−W_{2}as functions, which for all alternativesaandbsatisfy

(W1+W2)(a, b) =W1(a, b) +W2(a, b), (W1−W2)(a, b) =W1(a, b)−W2(a, b). (9) It is easy to check that the sum and the difference of two weighted tournaments is again a weighted tournament.

**Lemma 3.7** For a weighted tournament W with all weights being odd, we may construct a profile which
generates this weighted tournament.

Proof. LetW_{1} be the weighted majority relation of a profile consisting of a single arbitrarily
chosen linear orderv. LetW2 =W −W1. Note that asW1is generated from a profile with an odd
number (i.e. one) of linear orders, all the weights inW1 must be odd. Thus all weights inW2 are
the difference between two odd numbers. Hence all weights inW_{2}are even and we can construct
a profile for which W2 is the majority relation, as shown by Lemma 3.5. Since W = W1 +W2,

joining the profile that generatesW1, which is the linear orderv, and the profile that generatesW2

we obtain a profile that generatesW.

Our generalisation to the M^{c}Garvey theorem easily follows from these lemmata.

**4 Dodgson Quick, A New Approximation**

In this section we work under the Impartial Culture assumption.

**Definition 4.1** LetP = (P_{1}, P_{2}, . . . , P_{n})be a profile. We say that thei^{th}agent ranksb**directly above**a
if and only ifaPiband there does not existcdifferent froma, bsuch thataPicandcPib. We defineD(b, a)
as the number of agents who rankbdirectly abovea.

**Lemma 4.2** The probability that D(x, a) > F(x, a) for all x converges exponentially fast to 1 as the
number of agentsntends to infinity.

Proof. Asn_{ba} andD(b, a) are binomially distributed with means ofn/2 andn/m, respec-
tively, from Chomsky’s (Dembo and Zeitouni, 1993) large deviation theorem, we know that for a
fixed number of alternativesmthere existβ1 >0andβ2>0such that

P

D(b, a) n < 1

2m

≤e^{−β}^{1}^{n}, P
n_{ba}

n −1 2 > 1

4m

≤e^{−β}^{2}^{n}.

We can rearrange the second equation to involveF(b, a), P

n_{ba}
n −1

2 > 1 4m

=P

2n_{ba}

n −1> 1 2m

(10)

= P

n_{ba}−n_{ab}
n > 1

2m

(11)

= P

adv(b, a) n > 1

2m

. (12)

Since adv(b, a)≥F(b, a), P

n_{ba}
n −1

2 > 1 4m

≥ P

F(b, a) n > 1

2m

. (13)

From this and the law of probabilityP(A∨B)≤P(A) +P(B)it follows that P

F(b, a) n > 1

2m

≤e^{−β}^{2}^{n}, P

D(b, a) n < 1

2m

≤e^{−β}^{1}^{n},

and so forβ = min(β1, β2)we obtain P

F(b, a) n > 1

2m or D(b, a) n < 1

2m

≤e^{−β}^{1}^{n}+e^{−β}^{2}^{n}≤2e^{−βn}. (14)
Hence

P

∃_{x} F(x, a)
n > 1

2m or D(x, a) n < 1

2m

≤ 2me^{−βn}. (15)
UsingP( ¯E) = 1−P(E), we find that

P

∀_{x} F(x, a)
n < 1

2m < D(x, a) n

≥ 1−2me^{−βn}. (16)

**Lemma 4.3** The DQ-scoreSc** _{q}**(a)is a lower bound for the Dodgson ScoreSc

**(a)ofa.**

_{d}Proof. LetP be a profile anda ∈ A. Suppose we are allowed to change linear orders inP,
by repeated swapping neighbouring alternatives. Then to makeaa Condorcet winner we must
reduce adv(x, a)to 0 for allxand we know that adv(x, a) = 0if and only ifF(x, a) = 0. Swapping
aover an alternativebranked directly aboveawill reducen_{ba}−n_{ab}by two, but this will not affect
nca−n_{ac}wherea6=c. Thus swappingaoverbwill reduceF(b, a)by one, but will not affectF(c, a)
whereb6=c. Therefore, makingaa Condorcet winner will require at leastΣ_{b}F(b, a)swaps. This
is the DQ-ScoreSc** _{q}**(a)ofa.

**Lemma 4.4** If D(x, a) ≥ F(x, a) for every alternativex, then the DQ-ScoreSc** _{q}**(a) ofais equal to the
Dodgson ScoreSc

**(a)and the DQ-Winner is equal to the Dodgson Winner.**

_{d}Proof. If D(b, a) ≥ F(b, a), we can find at leastF(b, a) linear orders in the profile where b
is ranked directly above a. Thus we can swapadirectly over b, F(b, a) times, reducingF(b, a)
to 0. Hence we can reduceF(x, a) to 0 for allx, makingaa Condorcet winner, usingΣ_{x}F(x, a)
swaps of neighbouring alternatives. In this case, Sc** _{q}**(a) = Σ

_{b}F(b, a) is an upper bound for the Dodgson Score Sc

**(a) of a. From Lemma 4.3 above, Sc**

_{d}**(a) is also a lower bound for Sc**

_{q}**(a).**

_{d}HenceSc** _{q}**(a) =Sc

**(a).**

_{d}**Theorem 4.5** The probability that the DQ-ScoreSc** _{q}**(a)of an arbitrary alternativeais equal to the Dodg-
son ScoreSc

**(a), converges to 1 exponentially fast.**

_{d}Proof. From Lemma 4.4, ifD(x, a) ≥F(x, a)for all alternativesxthenSc** _{q}**(a)=Sc

**(a). From Lemma 4.2, the probability of this event converges exponentially fast to 1 asn→ ∞.**

_{d}**Corollary 4.6** The probability that the DQ-Winner is the Dodgson Winner converges to 1 exponentially
fast as we increase the number of agents.

**Corollary 4.7** Suppose that the number of alternatives m is fixed. Then there exists an algorithm that
computes the Dodgson score of an alternative ataking as input the frequency of each linear order in the
profileP with expected running time logarithmic with respect to the number of agents (i.e. isO(lnn)).

Proof. The are at mostm!distinct linear orders in the profile. Hence for a fixed number of alternatives the number of distinct linear orders is bounded. Hence we may find the DQ-score and check whetherD(x, a)≥F(x, a)for all alternativesxusing a fixed number of additions. The largest possible number of additions needed is proportional to the number of agentsn. Additions can be performed in time linear with respect to the number of bits and logarithmic with respect to the size of the number. So we have only used an amount of time that is logarithmic with respect to the number of agents.

IfD(x, a) ≥F(x, a)for all alternativesx, we know that the DQ-score is the Dodgson score and we do not need to go further. From Lemma 4.2 we know that the probability that we need go further declines exponentially fast, and, if this happens, we can still find the Dodgson score in time polynomial with respect to the number of agents (Bartholdi et al., 1989).

**Corollary 4.8** There exists an algorithm that computes the Dodgson winner taking as input the frequency
of each linear order in the profileP with expected running time that is logarithmic with respect the number
of agents.

**5 Tideman’s Rule**

In this section we focus our attention on the Tideman rule which was defined in Section 2. We continue to assume the IC.

**Lemma 5.1** Given an even number of agents, the Tideman winner and the DQ-winner will be the same.

Proof. Since thenis even, we know from Lemma 3.4 that all weights in the majority relation
W are even. Since the adv(a, b)≡W(a, b)^{+}it is clear that all advantages will also be even. Since
adv(a, b)will always be even,dadv(a, b)/2ewill be exactly half adv(a, b)and so the DQ-score will
be exactly half the Tideman score. Hence the DQ-winner and the Tideman winner will be the
same.

**Corollary 5.2** LetP be a profile for which the Tideman winner is not the DQ-winner. Then all non-zero
advantages are odd.

Proof. As we must have an odd number of agents, from Lemma 3.4 all weights in the
majority relationW^{P} must be odd. Since the adv(a, b) =W^{P}(a, b)^{+}the advantage adv(a, b)must
be zero or equal to the weightW^{P}(a, b).

**Lemma 5.3** There is no profile with three alternatives such that the Tideman winner is not the DQ-winner.

Proof. The Tideman and Dodgson Quick rules both pick the Condorcet winner when it ex- ists, so if a Condorcet winner exists the Tideman winner and DQ-winner will be the same. It is well known that the absence of a Condorcet winner on three alternatives means that we can rename these alternatives a, b and c so that adv(a, b) > 0, adv(b, c) > 0, and adv(c, a) > 0.

These advantages must be odd from the previous corollary. Hence for somei, j, k ∈Zsuch that adv(a, b) = 2i−1, adv(b, c) = 2j−1, and adv(c, a) = 2k−1. The DQ-Scores and Tideman scores of a, b, carei, j, kand2i−1, 2j−1, 2k−1respectively. From here the result is clear, since ifi > j > k then2i−1>2j−1>2k−1.

**Lemma 5.4** For a profile with four alternatives there does not exist a pair of alternatives such thatais a
DQ-winner but not a Tideman winner, andbis a Tideman winner but not a DQ-winner.

Proof. By way of contradiction assume that such alternatives a, b exist. Thus there is no
Condorcet winner, and so for each alternative c there are one to three alternatives d such that
adv(c, d) >0. Also, since the set of Tideman winners and DQ-winners differ,nmust be odd and
hence all non-zero advantages must be odd. The relationship between the Tideman scoreSc** _{t}**(c)
and the DQ-scoreSc

**(c)is as follows:**

_{q}Sc** _{t}**(c) = X

d∈A

adv(c, d) = 2X

d∈A

adv(c, d) 2

−#{c:adv(c, d)∈/ 2Z} (17)

= 2Sc** _{q}**(c)−(1or2or3). (18)

Thus,2Sc** _{q}**(c)−3≤Sc

**(c)≤2Sc**

_{t}**(c)−1,and, in particular,**

_{q}Sc** _{t}**(a) ≤ 2Sc

**(a)−1, 2Sc**

_{q}**(b)−3≤Sc**

_{q}**(b). (19) Given thatais DQ-winner andbis not, we know thatSc**

_{t}**(a) ≤Sc**

_{q}**(b)−1.Thus by substitution, Sc**

_{q}**(a)≤2(Sc**

_{t}**(b)−1)−1 = 2Sc**

_{q}**(b)−3≤Sc**

_{q}**(b).This shows that ifbis a Tideman winner, so is a. By contradiction the result must be correct.**

_{t}**Example 5.5** There do exist profiles with four alternatives where the set of tied Tideman winners differs
from the set of tied DQ-winners. By Theorem 3.3, we know we may construct a profile whose weighted
majority relation has the following advantages:

*a*

1 1 3 1

5 5

*c*
*b*

*x*

Scores a b c x Tideman 5 3 5 3

DQ 3 2 3 3

Herex, bare tied Tideman winners, butbis the sole DQ-winner.

**Example 5.6** There do exist profiles with five alternatives where there is a unique Tideman winner that
differs from the unique DQ-winner. By Theorem 3.3, we know we may construct a profile whose weighted
majority relation has the following advantages:

1

1

1

1

5 1 1 9 9

9

*x*

*y*
*b*

*a*

*c*

Scores a b c x y

Tideman 10 10 9 4 5

DQ 6 6 5 4 3

Herexis the sole Tideman winner, butyis the sole DQ-winner.

**Theorem 5.7** For anym≥5there exists a profile withmalternatives and an odd number of agents, where
the Tideman winner is not the DQ-winner.

In Example 5.6 we gave an example of a profile withm= 5alternatives for which the Tideman winner is not the Dodgson Quick winner. To extend this example for larger numbers of alter- natives, we may add additional alternatives who lose to all of a, b, c, x, y. From Theorem 3.3 and Lemma 3.4, there exists a profile with an odd number of agents that generates that weighted majority relation.

**Theorem 5.8** If the number of agents is even, the probability that all of the advantages are 0 does not
converge to 0 faster thanO(n^{−}^{m!}^{4} ).

Proof. LetP be a random profile,V = {v_{1},v2, . . . ,vm!} be an ordered set containing allm!

possible linear orders onmalternatives, andXbe a random vector, with elementsX_{i}representing
the number of occurrences ofvi inP. Under the Impartial Culture assumption,X is distributed
according to a multinomial distribution withntrials andm!possible outcomes. Let us group the
m!outcomes intom!/2pairsS_{i} ={v_{i},v¯_{i}}. Denote the number of occurrences ofvasn(v). Let the
random variableY_{i}^{1} ben(vi)andY_{i}^{2}ben(¯vi). LetYi=Y_{i}^{1}+Y_{i}^{2}.

It is easy to show that, givenY_{i} = y_{i} for alli, eachY_{i}^{1}is independently binomially distributed
withp = ^{1}/2 andy_{i} trials. It is also easy to show that for an arbitrary integern > 0, a(2n,0.5)-
binomial random variableXhas a probability of at least ^{√}^{1}

2nof equalingn; thus ifyiis even then
the probability thatY_{i}^{1} =Y_{i}^{2}is at least _{2}^{√}^{1}_{y}

i. Combining these results we get
P(∀_{i}Y_{i}^{1} =Y_{i}^{2} | ∀_{i}Y_{i} =y_{i} ∈2Z) ≥ Y

i

1 2√

y_{i} ≥Y

i

1 2√

n = 2^{−}^{m!}^{2} n^{−}^{m!}^{4} . (20)
It is easy to show that for anyk-dimensional multinomially distributed random vector, the prob-
ability that allkelements are even is at least2^{−k+1}; hence the probability that allX_{i}are even is at
least2^{−k+1}wherek=m!/2. Hence

P(∀_{i}Xi,1 =Xi,2) ≥

2^{−}^{m!}^{2} ^{+1} 2^{−}^{m!}^{2} n^{−}^{m!}^{4}

= 2^{1−m!}n^{−}^{m!}^{4} . (21)

If for alli,Xi,1 =Xi,2 then for alli,n(vi) =n(¯vi), i.e. the number of each type of vote is the same as its complement. Thus

n_{ba} = X

v∈{v:bva}

n(v) = X

¯v∈{¯v:a¯vb}

n(¯v) = X

v∈{v:avb}

n(v) =n_{ab}, (22)

so adv(b, a) = 0for all alternativesbanda.

**Lemma 5.9** The probability that the Tideman winner is not the DQ-winner does not converge to 0 faster
thanO(n^{−}^{m!}^{4} )as the number of agentsntends to infinity.

LetP be a random profile fromL(A)^{n}for some odd numbern. Let|C|be the size of the profile
from Theorem 5.7. Let us place the first |C|agents from profile P into sub-profiles C and the
remainder of the agents into sub-profileD. There is a small but constant probability thatCforms
the example from Theorem 5.7, resulting in the Tideman winner ofCdiffering from its DQ-winner.

Asn, |C|are odd,|D|is even. Thus from Theorem 5.8 the probability that the advantages inDare
zero does not converge to 0 faster thanO(n^{−}^{m!}^{4} ). If all the advantages inDare zero then addingD
toC will not affect the Tideman or DQ-winners. Hence the probability that the Tideman winner
is not the DQ-winner does not converge to 0 faster thanO(n^{−}^{m!}^{4} ).

**Theorem 5.10** The probability that the Tideman winner is not the Dodgson winner does not converge to 0
faster thanO(n^{−}^{m!}^{4} )as the number of agentsntends to infinity.

Proof. From Corollary 4.6 the DQ-winner converges to the Dodgson winner exponentially
fast. However, the Tideman winner does not converge faster thanO(n^{−}^{m!}^{4} )to the DQ-winner, and
hence also does not converge faster thanO(n^{−}^{m!}^{4} )to the Dodgson winner.

Our next goal is to prove that under the IC the probability that the Tideman winner and Dodg- son winner coincide converges asymptotically to1.

**Definition 5.11** We define the adjacency matrixM, of a linear orderv, as follows:

Mij =

1 if ivj

−1 if jvi 0 if i=j

. (23)

**Lemma 5.12** Suppose that v is a random linear order chosen from the uniform distribution on L(A).

Then its adjacency matrixM is anm^{2}-dimensional random variable satisfying the following equations for

alli, j, r, s∈A.

E[M] = 0 (24)

cov(Mij, M_{rs}) = E[M_{ij}M_{rs}] (25)

=

1 if i=r6=j=s,

1/3 if i=r, buti, j, sdistinct ∨ j =s, others distinct,

−1/3 if i=s, others distinct ∨ j=r, others distinct, 0 if i, j, r, sdistinct ∨ i=j=r=s,

−1 if i=s6=j =r.

(26)

Proof. Clearly,E[Mij] = ^{(1)+(−1)}_{2} = 0. As cov(X, Y) =E[XY]−E[X]E[Y](see e.g. Walpole
and Myers 1993; p97), cov(Mij, M_{rs}) =E[M_{ij}M_{rs}]−(0)(0) =E[M_{ij}M_{rs}]. Note that for alli 6=j
we know thatMiiMii = 0,MijMij = 1, andMijMji = −1. Ifi= randi, j, sare all distinct then
the sign ofMijMisfor each permutation ofi, jandsis as shown below.

i i j j s s

j s i s i j

s j s i j i

M_{ij} + + − − + −

Mis + + + − − −
M_{ij}M_{is} + + − + − +

(27)

Thus,E[M_{ij}M_{rs}] = +1+1−1+1−1+1
6 = ^{1}_{3}.

Ifi, j, r, sare all distinct then there are six linear ordersvwhereivjandrvs, six linear ordersv whereivjandsvr, six linear ordersvwherejviandrvs, and six linear ordersvwherejviand svr. Hence,

E[MijMrs] = 6(1)(1)+6(1)(−1)+6(−1)(1)+6(−1)(−1)

24 = 0 . (28)

We may prove the other cases for cov(Mij, M_{rs})in much the same way.

We note that as var(X) =cov(X, X)we also have, var(Mij) = 1ifi6=jand var(Mij) = 0i=j.

**Example 1** For example, form= 4the covariances withM12are shown in the matrix

L =

0 1 ^{1}/3 1/3

−1 0 ^{−1}/3 −1/3

−1/3 1/3 0 0

−1/3 1/3 0 0

, (29)

whereL_{ij} =cov(Mij, M12).

DefineY to be a collection of random normal variables indexed byi, jfor1≤ i < j ≤meach with mean of 0, and covariance matrixΩ, where

Ωij,rs = cov(Yij, Yrs) =cov(Mij, Mrs), (30)

We may use the fact thati < j, r < simpliesi6=j,r 6=s,(s=i⇒r 6=j)and(r =j ⇒s6=i) to simplify the definition ofΩas shown below:

Ωij,rs =

1 if (r, s) = (i, j),

1/3 if r=i, s6=jors=j, r6=i,

−1/3 if s=iorr=j, 0 if i, j, r, sare all distinct,

(31)

i.e. ifi, j, r, sare all distinct then

**Lemma 5.13** LetP = (P_{1}, P_{2}, . . . , P_{n})be a profile chosen from the uniform distribution on L(A)^{n}. Let
M_{i} be the adjacency matrix ofP_{i}. Then, asnapproaches infinity,P_{n}

i=1M_{i}/√

nconverges in distribution to

0 Y12 Y13 · · · Y1m

−Y_{12} 0 Y_{23} · · · Y_{2m}

−Y_{13} −Y_{23} 0 · · · Y3m

... ... ... . .. ...

−Y_{1m} −Y_{2m} −Y_{3m} · · · 0

, (32)

whereY is a collection of random normal variables indexed byi, jfor1≤i < j ≤meach with mean of 0, and covariance matrixΩ, where

Ωij,rs = cov(Yij, Yrs) =cov(Mij, Mrs). (33)

Proof. AsM_{1}, M_{2}, . . . , M_{n}are independent identically-distributed (i.i.d.) random variables,
we know from the multivariate central limit theorem (see e.g. Anderson, 1984; p81) thatPn

i=1Mi/√
n
converges in distribution to the multivariate normal distribution with the same mean and covari-
ance as the random matrixM from Lemma 5.12. AsM^{T} =−M andM_{ii} = 0, we have the result.

**Lemma 5.14** Ωis non-singular.

Proof. ConsiderΩ^{2} with elements

(Ω^{2})_{ij,kl} = X

1≤r<s≤m

Γ_{ij,kl}(r, s), (34)

whereΓ_{ij,kl}(r, s) = Ωij,rsΩ_{rs,kl}.

Ifi, j, r, sdistinct, then

Γ_{ij,ij}(i, j) = Ω_{ij,ij}Ω_{ij,ij} = (1)(1) = 1, (35)

Γ_{ij,ij}(r, j) = Ω_{ij,rj}Ω_{rj,ij} = (^{1}/3)(^{1}/3) =^{1}/9, (36)
Γij,ij(i, s) = Ωij,isΩis,ij = (^{1}/3)(^{1}/3) =^{1}/9, (37)
Γij,ij(r, i) = Ωij,riΩri,ij = (^{−1}/3)(^{−1}/3) =^{1}/9, (38)
Γij,ij(j, s) = Ωij,jsΩjs,ij = (^{−1}/3)(^{−1}/3) =^{1}/9, (39)

Γij,ij(r, s) = Ωij,rsΩij,rs = 0. (40)

Let us consider the case(i, j) = (k, l). If(i, j) = (k, l)then

Γ_{ij,ij}(r, s) = Ω_{ij,rs}Ω_{rs,ij} =

(1)^{2} if (r, s) = (i, j),
(^{1}/3)^{2} if r=i, s6=jors=j, r6=i,
(−^{1}/3)^{2} if s=i,(r6=j)orr=j,(s6=i),

0 if i, j, r, sare all distinct.

(41)

Recall thatr < s,i < jandr, s ∈[1, m]. Let us consider for how many values of(r, s)each of the above cases occur:

• (r, s) = (i, j): This occurs for exactly one value of(r, s).

• r =i, s6= j: Combining the fact thatr < sandr = iwe geti < s. Thuss∈ (i, j)∪(j, m], and there are(j−i−1) + (m−j) = (m−i−1)possible values ofs. As there is only one possible value ofrthis means that there are also(m−i−1)possible values of(r, s).

• s=j, r 6=i: Combining the fact thatr < sands=jwe getr < j. Thusr∈[1, i)∪(i, j), and there are(i−1) + (j−i−1) = (j−2)possible values of(r, s).

• s=i: Here we wantr 6=j, howeverr < s=i < j, so explicitly statingr 6=jis redundant.

Combining the fact thatr < sands = iwe getr < i. Hencer ∈ [1, i]and there arei−1 possible values for(r, s).

• r = j: Here we want s 6= i, however i < j = r < s, so explicitly stating that r 6= j is redundant. From here on we will not state redundant inequalities. Combining the fact that r < sandr =jwe getj < s. Hences∈(j, m]and there arem−jpossible values for(r, s).

Hence, X

1≤r<s≤m

Γ_{ij,ij}(r, s) = (1)(1) + ((m−i−1) + (j−2))
1

3 2

+ ((i−1) + (m−j)) −1

3 2

(42)

= 1 + (m+j−i−3) 1

9

+ (m+i−j−1) 1

9

(43)

= (9 + (m+j−i−3) + (m+i−j−1))/9 (44)

= 2m+ 5

9 . (45)

Let us consider now the casei=k, j 6=l. Then

Γij,il(r, s) = Ωij,rsΩrs,il=

1Ωrs,il if (r, s) = (i, j),

1/3Ω_{rs,il} if r=i, s6=jors=j, r6=i,

−1/3Ω_{rs,il} if s=iorr =j,
0 if i, j, r, sare all distinct.

(46)

more precisely,

Γ_{ij,il}(r, s) =

(1)(^{1}/3) = ^{1}/3 if (i, j) = (r, s),
(^{1}/3)(1) = ^{1}/3 if r =i, s=l6=j,
(^{1}/3)(^{1}/3) = ^{1}/9 if r =i, s6=j, s=6=l,

(^{1}/3)(0) = 0 if s=j6=l, r6=i,
(^{−1}/3)(^{−1}/3) = ^{1}/9 if s=i,

(^{−1}/3)(^{1}/3) = ^{−1}/9 if r=j, s=l,
(^{−1}/3)(0) = 0 if r=j, s6=l,

0 = 0 if i, j, r, sare all distinct,

(47)

hence,

X

1≤r<s≤m

Γ_{ij,il}(r, s) = 1
3 +1

3+ X

1≤r<s≤m,r=i,s6=j,s=6=l

1

9+ X

1≤r<s≤m,s=i

1 9 −1

9 (48)

= 1 3 +1

3+ X

i<s≤m

1 9−2

9 + X

1≤r<i

1 9 −1

9 (49)

= 1

3 + (m−i)1

9+ (i−1)1

9 (50)

= m+ 2

9 . (51)

Similarly fori6=k, j=l, we may show(Ω^{2})_{ij,kj} = ^{m+2}_{9} . Ifj=kthen
(Ω^{2})_{ij,kl} = −1

3− 1 3+1

9 − X

1≤r<i,r6=i

1

9 − X

j<s≤m,s6=l

1

9, (52)

= −m+ 2

9 , (53)

similarly forl=i. Ifi, j, k, lare all distinct,(Ω^{2})_{ij,kl}equals 0. Consequently
Ω^{2} =

m+ 2 3

Ω−

m+ 1 9

I. (54)

Since the matrix ΩsatisfiesΩ^{2} = αΩ +βI withβ 6= 0 it has an inverse, henceΩis not singular.

**Theorem 5.15** The probability that the Tideman winner and Dodgson winner coincide converges asymp-

totically to1asn→ ∞.

Proof. We will prove that the Tideman winner asymptotically coincides with the Dodgson Quick winner. The Tideman winner is the alternativea∈Awith the minimal value of

G(a) = X

b∈A

adv(b, a), (55)

while the DQ-winner has minimal value of F(a) = X

b∈A

adv(b, a) 2

. (56)

Leta_{T} be the Tideman winner anda_{Q}be the DQ-winner. Note thatG(c)−m≤2F(c)≤G(c)for
every alternativec. If for somebwe haveG(b)−m > G(aT), then2F(b) ≥G(b)−m > G(aT) ≥
2F(a_{T})and sobis not a DQ-winner. Hence, ifG(b)−m > G(a_{T})for all alternativesbdistinct from
a_{T}, thena_{T} is also the DQ-winnera_{Q}. Thus,

P(aT 6=aQ) ≤ P(∃_{a6=b}|G(a)−G(b)| ≤m) (57)

= P

∃_{a6=b}

G(a)−G(b)

√n

≤ m

√n

, (58)

thus for any >0and sufficiently largen, we have P(aT 6=aQ) ≤ P

∃_{a6=b}

G(a)−G(b)

√n

≤

. (59)

We will show that the right-hand side of the inequality above converges to 0 asntends to∞. All
probabilities are non-negative so0≤P(a_{T} 6=a_{Q}). From these facts and the sandwich theorem it
will follow thatlimn→∞P(a_{T} 6=a_{Q}) = 0.

Let

G_{j} = X

i<j

(Y_{ij})^{+}+X

k>j

(−Y_{jk})^{+}, (60)

where variablesYij come from the matrix (32) to whichPn

i=1Mi/√

nconverges by Lemma 5.13 . Thus,

n→∞lim P

∃_{a6=b}

G(a)−G(b)

√n

≤

= P(∃_{i6=j}|G_{i}−G_{j}| ≤) (61)
Since >0is arbitrary,

n→∞lim P(aT 6=aQ) ≤ P(∃_{i6=j}Gi =Gj). (62)

For fixedi < jwe have

G_{i}−G_{j} = −Y_{ij}+X

k<i

(−Y_{ki})^{+}+ X

k>i,k6=i

(Y_{ik})^{+}− X

k<j,k6=i

(Y_{kj})^{+}−X

k>j

(−Y_{jk})^{+}. (63)

Definevso thatGi−Gj = −Y_{ij} +v. ThenP(Gi = Gj) = P(Yij = v) = E[P(Yij = v|v)]. Since
Y has a multivariate normal distribution with a non-singular covariance matrixΩ, it follows that
P(Y_{ij} = v|v) = 0. That is,P(G_{i} = G_{j}) = 0for anyi, j wherei 6= j. HenceP(∃_{i6=j}G_{i} = G_{j}) =
0. As discussed previously in this proof, we may now use the sandwich theorem to prove that
limn→∞P(aT 6=aQ) = 0.

**6 Numerical Results**

In this section we present tables demonstrating the rate of convergence to Dodgson of the Dodgson Quick rule introduced in this paper in comparison to the Tideman rule. These tables show that the convergence of the Tideman winner to the Dodgson Winner occurs much slower than the exponential convergence of the DQ-Winner. We also study the asymptotic limit of the probability that the Simpson winner is the Dodgson winner as we increase the number of agents.

Table 1: Number of occurrences per 10,000 Elections with 5 alternatives that the Dodgson Winner was not chosen

Voters 3 5 7 9 15 17 25 85 257 1025

DQ 1.5 1.9 1.35 0.55 0.05 0.1 0 0 0 0

Tideman 1.5 2.3 2.7 3.95 6.05 6.85 7.95 8.2 5.9 2.95 Simpson 57.6 65.7 62.2 57.8 48.3 46.6 41.9 30.2 23.4 21.6

In these 10,000 simulations we were breaking ties according to the preferences of the first agent.

In Table 2 we present the results of another 10,000 simulations in which we consider the rules as social choice correspondences and do not break ties.

Table 2: Number of Occurrences per 10,000 Elections with 5 Alternatives that the Set of Dodgson Winners is Not Chosen

Voters 3 5 7 9 15 17 25 33 85 257 1025

DQ 4.31 4.41 3.21 1.94 0.27 0.08 0.04 0 0 0 0

Tideman 4.31 5.57 7.31 8.43 12.73 13.15 15.46 16.35 15.18 10.2 5.4

Another question is how well does Dodgson Quick approximate the Dodgson rule when the number of alternatives is different from 5 or when the number of agents is not large in comparison to the number of agents. From Table 3, it appears that the DQ-approximation is still reasonably

accurate under these conditions. This table was generated by averaging 10,000 simulations, and splitting ties according to the preferences of the first agent.

Table 3: Frequency that the DQ-Winner is the Dodgson Winner

# Agents

#Alternativesx 3 5 7 9 15 25 85

3 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 5 0.9984 0.9976 0.9980 0.9992 0.9999 1.0000 1.0000 7 0.9902 0.9875 0.9879 0.9933 0.9980 0.9995 1.0000 9 0.9792 0.9742 0.9778 0.9837 0.9924 0.9978 0.9999 15 0.9468 0.9327 0.9338 0.9412 0.9571 0.9743 0.9988 25 0.8997 0.8718 0.8661 0.8731 0.8971 0.9265 0.9840

To give meaning to these figures, let us compare them with the figures in Tables 4 and 5. We see that even where the number of agents is not very large, the Dodgson Quick rule seems to do a slightly better job of approximating the Dodgson rule than Tideman’s approximation. We also see that Simpson’s rule does a particularly poor job of approximating the Dodgson winner when the number of alternatives is large.

Table 4: Frequency that the Tideman winner is the Dodgson winner

# Agents

#Alternativesx 3 5 7 9 15 25 85

3 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 5 0.9984 0.9974 0.9961 0.9972 0.9936 0.9917 0.9930 7 0.9902 0.9864 0.9852 0.9868 0.9845 0.9805 0.9847 9 0.9792 0.9730 0.9724 0.9731 0.9718 0.9760 0.9815 15 0.9468 0.9292 0.9263 0.9273 0.9379 0.9485 0.9649 25 0.8997 0.8691 0.8620 0.8625 0.8833 0.9113 0.9534

Table 5: Frequency that the Simpson Winner is the Dodgson Winner

# Agents

#Alternativesx 3 5 7 9 15 25 85

3 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 5 0.9433 0.9307 0.9339 0.9398 0.9493 0.9575 0.9714 7 0.8734 0.8627 0.8689 0.8786 0.9018 0.9153 0.9404 9 0.8256 0.8153 0.8167 0.8251 0.8562 0.8808 0.9124 25 0.5895 0.5772 0.6147 0.6322 0.7114 0.7529 0.7957

It appears that Simpson’s rule is not a very accurate approximation of Dodgson’s Rule. The probability that the Simpson winner does not equal the Dodgson winner is much greater than for

Tideman or DQ. We may ask, does the Simpson rule eventually converge to the Dodgson rule as we increase the number of voters, and, if not, how close does it get?

From Lemma 4.2 and Theorem 5.15 we know that the Dodgson winner, Dodgson Quick winner, and Tideman winner all asymptotically converge as we increase the number of agents. Hence we may compute the asymptotic probability that the Simpson winner is equal to the Dodgson winner, by computing the asymptotic probability that the Simpson winner equals the Tideman winner.

From Lemma 5.13 we know that the matrix of advantages converges to a multivariate normal distribution as we increase the number of agents. If we had a multivariate normal random vector generator, we could use this model to perform simulations and count in how many simulations the Simpson winner is equal to the Tideman winner. We decided to use a slightly different model so that we could use a univariate normal random number generator.

Letvbe a linear order onA. As usual, byv¯we denote the linear order onAwhere all preferences
are reversed. Leta, b ∈ Abe two distinct alternatives. LetV = (v_{1}, v_{2}, . . . , v_{m!/2})be the set of all
linear orders fromL(A)whereais ranked aboveb. Note that{v_{1},v¯_{1}, v_{2},v¯_{2}, . . . , v_{m!/2},v¯_{m!/2}}is the
setL(A)of all possible linear orders ofA. Given a random linear ordervchosen from the uniform
distribution on L(A), we define an(m!/2)-dimensional random vector X = (X_{1}, X_{2}, . . . , X_{m!/2})
so that

Xi =

1 ifv=v_{i}

−1 ifv= ¯vi

0 otherwise

(64)

Let P = (P_{1}, P_{2}, . . . , P_{n}) ∈ L(A)^{n} be a profile with m alternatives and n agents. Let X^{i} be
the random vector corresponding toPi. These random vectors are independently identically dis-
tributed (i.i.d.) with means of 0, and covariance matrix Ω = rI_{m} where r is some real number
greater than0andI_{m} is the identitym×mmatrix. By the multivariate central limit theorem, we
know thatY = Pn

i=1X^{i}/√

nconverges to anN(0, rIm)multivariate normal distribution. Hence
we may modelY_{1}, Y_{2}, . . . , Y_{n}as i.i.d. univariate normally distributed variables.

Using this model we performed 100,000 simulations and generate Table 6.

Table 6: Number of Occurrences per 1000 Elections that the Simpson Winner is Not the Dodgson Winner. (Limit asn→ ∞)

#Alternatives 3 4 5 6 7 8

#(DO6=SI)per 1000 0 6.81 17.18 27 39.33 50.18

Note that as the number of agents approaches infinity, the probability of a tie approaches0, and so tie breaking is irrelevant in this table. In Table 6, we see that even with an infinite number of voters, the Simpson rule is not especially close to the Dodgson rule.

**7 Conclusion**

In this paper we showed that under the Impartial Culture assumption the Tideman rule approxi- mates Dodgson’s rule and converges to it, when the number of agents tends to infinity. However we discovered that a new rule, which we call Dodgson Quick, approximates Dodgson’s rule much better and converges to it much faster. We also show that Simpson’s rule does not converge to Dodgson’s rule asymptotically despite often selecting the same winner. The Dodgson Quick rule is computationally very simple however in our simulations it picked the Dodgson winner in all of 1,000,000 elections with 85 agents and 5 alternations. We give numerical results illustrating the rate of convergence of Dodgson Quick to Dodgson.

We proved a generalisation of McGarvey’s theorem from ordinary tournaments to weighted tournaments and used it as a tool for constructing examples where the aforementioned rules select different winners.

The most interesting question for further research that this paper rises is whether or not the Dodgson Quick rule approximates Dodgson’s rule under the Impartial Anonimous Culture as- sumption and other models for the population.

**References**

Anderson, T. W.An Introduction to Multivariate Statistical Analysis. John Wileys and Sons, Brisbane, 2nd edition, 1984.

Bartholdi, III., Tovey, C. A., and Trick, M. A. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare: Springer-Verlag, 6:157–165, 1989. Industrial and Systems Engineering, Georgia Institute of Technology.

Berg, S. Paradox of voting under an urn model: The effect of homogeneity. Public Choice, 47:377–

387, 1985.

Black, D. Theory of commitees and elections. Cambridge University Press, Cambridge, 1958.

Debord, B. Axiomatisation de procédures d’agrégation de préférences. Ph.D. thesis, Université Scien- tifique, Technologique et Médicale de Grenoble, 1987.

Dembo, A. and Zeitouni, O. Large deviations techniques. Johns and Barlett, 1993.

Dodgson, C. L. A method for taking votes on more than two issues. Clarendon Press, Oxford, 1876.

Reprinted in (Black, 1958) with discussion.

Hemaspaandra, E., Hemaspaandra, L., and Rothe, J. Exact analysis of dodgson elections: Lewis carroll’s 1876 voting system is complete for parallel access to np. Journal of the ACM, 44(6):806–

825, 1997.

Homan, C. M. and Hemaspaandra, L. A. Guarantees for the success frequency of an algorithm for finding dodgson-election winners. 2005.

Laslier, J.-F. Tournament solutions and majority voting. Springer, Berlin - New York, 1997.

M^{c}Cabe-Dansted, J. C. and Slinko, A. Exploratory analysis of similarities between social choice
rules. Group Decision and Negotiation, 15:1–31, 2006. http://dx.doi.org/10.1007/

s00355-005-0052-4.

M^{c}Garvey, D. C. A theorem on the construction of voting paradoxes. Econometrica, 21:608–610,
1953.

Simpson, P. B. On defining areas of voter choice: Professor tullock on stable voting. The Quarterly Journal of Economics, 83(3):478–90, 1969.

Tideman, T. N. Social Choice and Welfare, 4:185–206, 1987.

Vidu, L. An extension of a theorem on the aggregation of separable preferences. Social Choice and Welfare, 16(1):159–67, 1999.

Walpole, R. E. and Myers, R. H. Probability and Statistics for Engineers and Scientists. Maxwell Macmillian International, Sydney, 1993.