[EM] Nominations for presidential poll

[Gervase Lam]

> Date: Fri, 13 Feb 2004 08:00:00 -0500
> From: Stephane Rouillon
> Subject: Re: [EM] Nominations for presidential poll

> I nominate those three methods just to show how different they work on:
>
> Ranked Pair (relative margins),
> Ranked Pair (winning votes) with an extended graph,
> IRV with residual approval weights.

I don't expect there to be much difference between the above two Ranked 
Pair methods because I don't think there will be any significant number of 
tied or truncated rankings.  Nevertheless, recently I have been pondering 
about what the probability of there being a difference between "margins" 
and "winning votes" (or more strictly, "pairwise opposition").

What follows was at least partially if not mainly inspired from the way 
Weber worked out optimal Approval ballots.  Weber basically used something 
like a pairwise matrix in order to do this.  As a result, I will be using 
a very tiny bit of Approval terminology in this.

Most of the following is really just scene setting.  I've decided to do 
this just in case there is a flaw in this.  If so, then at least people 
have a general idea of what I was thinking of and then correct the 
mistakes or use the ideas to do other calculations.

As a starting point, I will assume that a Condorcet election is zero info. 
 In other words, the election race is "open."  Nobody can predict who is 
going to win.

Also, as I want to find out the probability of there being a difference 
between "margins" and "winning votes" for any election, I will assume that 
each element in the pairwise matrix can have any non-negative number.  In 
other words, the number in an element of a pairwise matrix can be from 0 
to infinity.

I'll concentrate on the pairwise contest between candidates A and B.  This 
involves the matrix elements that denote the number of A>B and B>A voters. 
 Given that all elements can contain a number from 0 to infinity, it can 
be seen that the probability of the A>B element being larger than the B>A 
element is 1/2.

This can be used to work out the probability of a candidate A being the 
Condorcet winner.  If there are 4 candidates, then the probability is 
(1/2)^4 (i.e. each of Candidate A's matrix elements must be higher than 
each of its corresponding pairwise opponents' element).

Since there are 4 candidates, therefore the probability of the election 
having a Condorcet winner is 4*(1/2^4).  This can be generalised to find 
the probability of a Condorcet method getting a Condorcet winner: N/2^N, 
where N is the number of candidates.  It can therefore be seen from this 
expression that the likelihood of there being a Condorcet winner gets 
small very quickly for an increasing number of candidates.

So, what about if there is no Condorcet winner?  To work this out, I will 
assume that the method being used is Min(Max(pairwise opposition)).  I'll 
imagine that there is no possibility of there being a Condorcet winner in 
this method.  One way to do this is to have an election that has an 
infinite number of candidates.

In order to determine the winner, the list of the worst pairwise 
opposition votes for each candidate is listed.  This obviously comes 
directly from the pairwise matrix, which can contain any number.

For a candidate A to win, it needs to beat the other candidates' worst 
pairwise opposition votes.  Therefore, the probability of candidate A 
winning is 1/2^(N-1).

I'll now introduce the margins aspect.  What is the probability of margins 
contradicting winning votes for a given pairwise contest?

I'll abbreviate the number of those who voted A>B to X and the number of 
those who voted B>A to Y.  To win, a candidate's worst pairwise opposition 
votes must be the least worst in comparison with the others.  Say this is 
Y.  Margins could contradict this by having X>Y.  The probability of this 
happening is 1/2.  Therefore, for a given pairwise contest, there is a 50% 
chance of margins contradicting worst pairwise opposition votes.

Initially, I left things here and assumed therefore that for 
Min(Max(pairwise opposition)), the chances of there being a difference is 
50%.  I then went on to work out what would happen if the other 
candidates' pairwise votes against were to contradict margins.  In other 
words, how many permutations were there of 2 candidates pairwise votes 
against contradicting margins, 3 candidates, 4 candidates and so on.  The 
expression for this turns out to be...

nP1 + nP2 + nP3 + ... + nPr (n = Number of candidates in election)

I then continued to work out the number of permutations where margins and 
pairwise votes against did not contradict.  To do this, I needed to work 
out how many permutations were there of 2 candidates pairwise votes 
against agreeing with margins, 3 candidates, 4 candidates and so on.  This 
obviously turns out to be...


nP1 + nP2 + nP3 + ... + nPr

In other words, the total number of permutations that contradict equals 
the total number of permutations that do not contradict.

Going into the seedy world of infinity has been useful here.  It means 
that the chances of A>B and B>A being the same number is infinitesimally 
small.

However, this does mean that this does start to break down the smaller the 
number of voters are.  For example, if there were 10 voters, there is a 
reasonable chance of a pairwise element getting a 0 or 10.  The chances of 
getting an element more than 0 or 10 is 100% or 0% respectively.  This 
means that the probabilities vary, compared with always being 50% if very 
large numbers (i.e. infinity) are used.  Also, with 10 voters, the chances 
of getting a tie in a pairwise contest is much higher.

Thanks,
Gervase.