# [EM] Nominations for presidential poll

Gervase Lam gervase.lam at group.force9.co.uk
Mon Feb 16 16:30:01 PST 2004

```> 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

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%

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
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.

```