Reply #2: [EM] FWD: Borda Count by Paul Dumais

[Blake Cretney]

Paul Dumais wrote:

> I think you're onto something. I will try to find out what is happening.
> Any ideas? It appears the assymetry appear when we drop candidates. If
> borda was used alone, then the result would be sysmetrical. So it
> appears that we should not drop candidates. Perhaps there's a feature of
> path voting that can help here?
Path Voting does not have this asymmetry.
> 
> Does path voting always yield a winner? 

This procedure, of deciding between two candidate by determining
which has the "greater" path to the other, never results in a circular
tie.  A tie is possible, with likelihood similar to that for
plurality, etc.

For a simple example of the method in use:

Given pair-wise majorities with margins
A>B 30
B>C 20
C>A 15
A>D 2
B>D 3
C>D 4

Obviously, these are circular preferences.  There is no Condorcet
winner because
A>B>C>A

However, remembering that paths are measured by their weakest victory

A>B 30  B>C>A 15  So, A is ranked over B
A>B>C 20 C>A 15   So, A is ranked over C
A>D 2   D has no path to A    So, A is ranked over D
If we want a full ranking.
B>C 20 C>A>B 15   So, B is ranked above C
C>D 4  D has no path to A.  So, C is ranked above D.
The full ranking is A,B,C,D

So, even though pair-wise majorities are circular, the comparison of
strongest paths is not.  To create a tie you need some well-positioned
equal margins of victory.

I suspect at this point you're wondering:
Why is a path's strength defined as its smallest majority?
Why use the strongest paths to decide between two candidates?

You've shown some desire to evaluate voting methods based on a
probabilistic view.  This is appropriate for understanding Path
Voting.

It stands to reason, for example, that if you have a majority
A>B
that this provides some evidence that A is in fact superior to B, and
that the strength of this evidence increases with the margin of
victory.

So, a path
A>B B>C
must provide evidence that A is superior to C.

One possible way we could judge the level of evidence of a path would
be to assume that all majorities are independent.  Then, we would
likely employ a procedure involving assigning every level of majority
a probability.  Then, we would likely multiply all these probabilities
together to get path strength.  If we had multiple paths from A to C
and C to A, we would use some procedure involving multiplying together
one minus the probability assigned to each path.

The reason we don't do this is that we aren't prepared to assume any
level of independence for these majority decisions.  For one thing, a
high degree of dependence is likely to exist.  For another, any
assumption of independence seems to result in a method that violates
GITC.  It could be argued that some middle ground, of assuming some
level of independence would be most accurate.  Unfortunately, it would
be very hard to determine what that level was, it would vary from
election to election, and it would likely change as people start to
use the strategic opportunities this would create.

Borda provides a good example.  It assumes independence, and as a
result, running multiple candidates (what I call teaming) becomes a
good strategy.  As a result, the actual decisions of voters will be
even less independent, since there will be so many very similar groups
of candidates.

So, we take the lowest victory, and use it to measure path strength,
because to use any other victories as well, in a probabilistic model,
we would have to assume some level of independence between the two. 
Likewise, we use the strongest path, because to add in weaker paths as
if they were additional information would require us to assume some
level of independence for them.

---
Blake Cretney
See the EM Resource:  http://www.fortunecity.com/meltingpot/harrow/124