Approximability of Dodgson’s Rule
JOHNC. MCCABE-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
ABSTRACT. 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 McGarvey’s theorem (1953) for weighted majority relations.
JEL CLASSIFICATION: D7
KEYWORDS: Dodgson’s rule, Simpson’s rule, McGarvey’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 Θp2-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 (McCabe-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.
McGarvey (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 calledprofiles. The profiles represent the collection of preferences of ann-element society of agentsN. A family of mappingsF ={Fn},n∈N,
Fn:L(A)n→A, (2)
is called asocial choice function(SCF).
LetP = (P1, P2, . . . , Pn)be a profile. If a linear orderPi ∈ L(A)represents the preferences of the ithagent, 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. nxy = #{i|xPiy}. The approximations we consider depend upon the information contained in the matrixNP, where(NP)ab = nab. A functionWP:A×A→Zgiven byWP(a, b) =nab−nbafor alla, b∈A, will be called theweighted majority relationonP. It is obviously skew symmetric, i.e.WP(a, b) =−WP(b, a)for alla, b∈A.
Many of the rules to determine the winner use the numbers
adv(a, b) = max(0, nab−nba) = (nab−nba)+, (3) which will be calledadvantages. Note that adv(a, b) = max(0, W(a, b)) = W(a, b)+whereW is the weighted majority relation onP.
ACondorcet winneris 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 ofscoresand 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 Scd(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 theDodgson winner(s).
TheSimpson score(Simpson 1969, see e.g. Laslier 1997)Scs(a)of an alternativeais Scs(a) = max
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.
TheTideman score(Tideman, 1987)Sct(a)of an alternativeais Sct(a) =X
b6=a
adv(b, a). (5)
We call the alternative(s) with the lowest Tideman score theTideman winner(s). Tideman (1987) suggested the rule based on this score as an approximation to Dodgson.
TheDodgson Quick (DQ) scoreScq(a)of an alternativea, which we introduce in this paper, is Scq(a) = X
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 theDodgson 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 (McCabe-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)nbe a random profile. Let thenX be a vector where eachXi, fori = 1,2, . . . , m!, represents the number of occurrences of theith linear order in the profileP. Then, under the IC, the vectorXis(n, k,p)-multinomially distributed withk=m!and p=1k/k= (1k,k1, . . . ,k1).
3 A M
cGarvey Theorem for Weighted Tournaments
The McGarvey 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 McGarvey 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 Aweighted tournamenton a setAis any functionW:A×A→ZsatisfyingW(a, b) =
−W(b, a)for alla, b∈A.
We callW(a, b)theweightof 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 relationWPon a profilePdefined earlier in this paper is a prime example of a weighted tournament. We say that a profileP generatesa weighted tournamentW ifW =WP. We note that adv(a, b) = WP(a, b)+, where x+ = max(0, x). Similarly WP(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 reductionofW 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 andWPis the weighted majority relation on the profileP, then the reductionWSPis 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 LetWP be a weighted majority relation on a profileP withnagents, then all weights inWP have the same parity asn. That is, for each pair of distinct alternativesaandb, the weightWP(a, b)is even if and only ifnis even.
Proof. We know that for all alternativesaandb we haveWP(a, b) = nab−nba andn = nba+nab. HenceWP(a, b) +n= 2naband soWP(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 WP such thatWP(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 differenceW1−W2as 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. LetW1 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 inW2are 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 McGarvey 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 = (P1, P2, . . . , Pn)be a profile. We say that theithagent ranksbdirectly abovea 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. Asnba 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−β1n, P nba
n −1 2 > 1
4m
≤e−β2n.
We can rearrange the second equation to involveF(b, a), P
nba n −1
2 > 1 4m
=P
2nba
n −1> 1 2m
(10)
= P
nba−nab n > 1
2m
(11)
= P
adv(b, a) n > 1
2m
. (12)
Since adv(b, a)≥F(b, a), P
nba 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−β2n, P
D(b, a) n < 1
2m
≤e−β1n,
and so forβ = min(β1, β2)we obtain P
F(b, a) n > 1
2m or D(b, a) n < 1
2m
≤e−β1n+e−β2n≤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-scoreScq(a)is a lower bound for the Dodgson ScoreScd(a)ofa.
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 reducenba−nabby two, but this will not affect nca−nacwherea6=c. Thus swappingaoverbwill reduceF(b, a)by one, but will not affectF(c, a) whereb6=c. Therefore, makingaa Condorcet winner will require at leastΣbF(b, a)swaps. This is the DQ-ScoreScq(a)ofa.
Lemma 4.4 If D(x, a) ≥ F(x, a) for every alternativex, then the DQ-ScoreScq(a) ofais equal to the Dodgson ScoreScd(a)and the DQ-Winner is equal to the Dodgson Winner.
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ΣxF(x, a) swaps of neighbouring alternatives. In this case, Scq(a) = ΣbF(b, a) is an upper bound for the Dodgson Score Scd(a) of a. From Lemma 4.3 above, Scq(a) is also a lower bound for Scd(a).
HenceScq(a) =Scd(a).
Theorem 4.5 The probability that the DQ-ScoreScq(a)of an arbitrary alternativeais equal to the Dodg- son ScoreScd(a), converges to 1 exponentially fast.
Proof. From Lemma 4.4, ifD(x, a) ≥F(x, a)for all alternativesxthenScq(a)=Scd(a). From Lemma 4.2, the probability of this event converges exponentially fast to 1 asn→ ∞.
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 relationWP must be odd. Since the adv(a, b) =WP(a, b)+the advantage adv(a, b)must be zero or equal to the weightWP(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 scoreSct(c) and the DQ-scoreScq(c)is as follows:
Sct(c) = X
d∈A
adv(c, d) = 2X
d∈A
adv(c, d) 2
−#{c:adv(c, d)∈/ 2Z} (17)
= 2Scq(c)−(1or2or3). (18)
Thus,2Scq(c)−3≤Sct(c)≤2Scq(c)−1,and, in particular,
Sct(a) ≤ 2Scq(a)−1, 2Scq(b)−3≤Sct(b). (19) Given thatais DQ-winner andbis not, we know thatScq(a) ≤Scq(b)−1.Thus by substitution, Sct(a)≤2(Scq(b)−1)−1 = 2Scq(b)−3≤Sct(b).This shows that ifbis a Tideman winner, so is a. By contradiction the result must be correct.
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 = {v1,v2, . . . ,vm!} be an ordered set containing allm!
possible linear orders onmalternatives, andXbe a random vector, with elementsXirepresenting 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!/2pairsSi ={vi,v¯i}. Denote the number of occurrences ofvasn(v). Let the random variableYi1 ben(vi)andYi2ben(¯vi). LetYi=Yi1+Yi2.
It is easy to show that, givenYi = yi for alli, eachYi1is independently binomially distributed withp = 1/2 andyi 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 thatYi1 =Yi2is at least 2√1y
i. Combining these results we get P(∀iYi1 =Yi2 | ∀iYi =yi ∈2Z) ≥ Y
i
1 2√
yi ≥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 allXiare even is at least2−k+1wherek=m!/2. Hence
P(∀iXi,1 =Xi,2) ≥
2−m!2 +1 2−m!2 n−m!4
= 21−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
nba = X
v∈{v:bva}
n(v) = X
¯v∈{¯v:a¯vb}
n(¯v) = X
v∈{v:avb}
n(v) =nab, (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)nfor 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 anm2-dimensional random variable satisfying the following equations for
alli, j, r, s∈A.
E[M] = 0 (24)
cov(Mij, Mrs) = E[MijMrs] (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, Mrs) =E[MijMrs]−(0)(0) =E[MijMrs]. 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
Mij + + − − + −
Mis + + + − − − MijMis + + − + − +
(27)
Thus,E[MijMrs] = +1+1−1+1−1+1 6 = 13.
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, Mrs)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)
whereLij =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 = (P1, P2, . . . , Pn)be a profile chosen from the uniform distribution on L(A)n. Let Mi be the adjacency matrix ofPi. Then, asnapproaches infinity,Pn
i=1Mi/√
nconverges in distribution to
0 Y12 Y13 · · · Y1m
−Y12 0 Y23 · · · Y2m
−Y13 −Y23 0 · · · Y3m
... ... ... . .. ...
−Y1m −Y2m −Y3m · · · 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. AsM1, M2, . . . , Mnare 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. AsMT =−M andMii = 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+29 . 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,klequals 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)
LetaT be the Tideman winner andaQbe 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(aT)and sobis not a DQ-winner. Hence, ifG(b)−m > G(aT)for all alternativesbdistinct from aT, thenaT is also the DQ-winneraQ. 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(aT 6=aQ). From these facts and the sandwich theorem it will follow thatlimn→∞P(aT 6=aQ) = 0.
Let
Gj = X
i<j
(Yij)++X
k>j
(−Yjk)+, (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|Gi−Gj| ≤) (61) Since >0is arbitrary,
n→∞lim P(aT 6=aQ) ≤ P(∃i6=jGi =Gj). (62)
For fixedi < jwe have
Gi−Gj = −Yij+X
k<i
(−Yki)++ X
k>i,k6=i
(Yik)+− X
k<j,k6=i
(Ykj)+−X
k>j
(−Yjk)+. (63)
Definevso thatGi−Gj = −Yij +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(Yij = v|v) = 0. That is,P(Gi = Gj) = 0for anyi, j wherei 6= j. HenceP(∃i6=jGi = Gj) = 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 = (v1, v2, . . . , vm!/2)be the set of all linear orders fromL(A)whereais ranked aboveb. Note that{v1,v¯1, v2,v¯2, . . . , vm!/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 = (X1, X2, . . . , Xm!/2) so that
Xi =
1 ifv=vi
−1 ifv= ¯vi
0 otherwise
(64)
Let P = (P1, P2, . . . , Pn) ∈ L(A)n be a profile with m alternatives and n agents. Let Xi be the random vector corresponding toPi. These random vectors are independently identically dis- tributed (i.i.d.) with means of 0, and covariance matrix Ω = rIm where r is some real number greater than0andIm is the identitym×mmatrix. By the multivariate central limit theorem, we know thatY = Pn
i=1Xi/√
nconverges to anN(0, rIm)multivariate normal distribution. Hence we may modelY1, Y2, . . . , Ynas 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.
McCabe-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.
McGarvey, 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.
