[EM] The Ultimate Method? Paul's Borda Count - #2

Wed Apr 28 18:59:15 PDT 1999

Paul Dumais wrote:

> Hi all,
> 
> 	I've been doing some more thinking and it appears that I have come up
> with an improved method. Here's how it works:
> 
> 1. Do a standard Borda count.
> 2. Define the borda number (BN) as the total number of candidates still
> being considered minus 1 times the number of voters: BN = (C-1)*V -where
> C is the number of candidates in consideration and V is the number of
> voters. Divide the candidates into two groups: one group with a borda
> count (BC) above BN/2 and one with a BC < BN/2.
> 3. Remove the lower group with BC < BN/2 from consideration. Change the
> BN accordingly.
> 4. Repeat steps 1-3 on as many groups as required. All candidates can be
> ranked in this way by repeating steps 1-3 on as many groups as required.
> 
> I think this method is immune to the advantage of running more
> candidates. I also think it is reverse consistant. We can ask: "who is
> the worst candidate?" and we shouldn't get a contradiction with "who is
> the best candidate?". It should also be monotonic, that is, a drop in
> support for a candidate should not result in the candidate getting
> ranked higher than otherwise.
> 
> I'm sorry, I havn't tried this method against all the criterions yet. I
> do feel however that we may have a winner(!) ;-) - or at least a soon to
> be very popular compromise!
> 
> -- 
> Paul Dumais
> 

Usually I don't comment on new methods because too many are proposed,
analyzing them is difficult, and their authors tend not to make any
serious attempts to do this themselves.

However, because you are new, and show some interest in rigorous
analysis, I'll make some comments.  I hope this will help you when it
comes to analyzing your own methods.

First, let me point out that if we have a pair-wise table, 
    A    B    C   Borda
A   X   30   60   90
B   70   X   20   90 
C   40  80    X   120

Each row gives the number of people who prefer that candidate against
the candidate for each collumn.  Equal rankings are scored as 1/2
each.  If we have a table like this, the total of each row is the
Borda Count for that row.  If we want to eliminate candidates (as in
Nanson or Paul) we can just cross out their row and column, and
retotal the rows for the new Borda counts.

Looking at the chart again, notice that we could subtract V/2 from
each cell, without altering the row scores relative to each other. 
This would reduce each row total by (C-1)*V/2, or BN.  So, for this
new chart, we would use a cut-off of BN-BN=0.  Each cell would show
either the margin of victory, or negative margin of defeat.  If we
wanted, we could redefine the eliminate rule as, eliminate all
candidates if the total of their pair-wise margins of victory is less
that the total of their pair-wise margins of defeat.

Obviously, if a candidate wins every contest, his margins of victory
will exceed his margins of defeat.  Since the Condorcet Winner wins
all contests, it must score above the cut-off on the first round, and
is not eliminated.  No matter which other candidates are eliminated,
the CW remains the CW, and must therefore stay above the cut-off. 
Therefore, the CW cannot be eliminated and must therefore win.

So, your method meets the Condorcet Criterion.  This means that if
fails the Consistency Criterion, since they are mutually exclusive.
----------------
Now consider the Smith set.  Each member of the Smith set defeats everyone
outside the Smith set, but loses to some other Smith set member.  Now,
obviously, the total internal margins of victory and negative margins of
defeat must total 0 for the Smith set, or any other set.  Since it is not
possible for everyone to be below average, at least some members of the Smith
set must total 0 or greater against the other members.  Since these members
defeat all non-Smith set candidates, they must have greater than 0 over all. 
It is not, therefore, possible that all members of the Smith set are below the
cut-off.
Notice that if candidates are eliminated from the Smith set, or outside the
Smith set, some of the remaining Smith set members form a Smith set for the
remaining candidates.  So, unless all Smith set members can be eliminated at
once, there is no way to prevent them from winning.  So, since I proved above
that they cannot all be eliminated at once, one of the Smith set members must
win.

So, your method meets the Smith Criterion.  Condorcet Loser and Condorcet
Winner are implied by this.
--------------
Now, notice that if all ballots are reversed, that using my modified table,
every value that is negative would become positive and vice versa.  So, if a
candidate not eliminated on the first round (because the row score is greater
than 0), then he would be eliminated on the first round for the reversed
ballots (because the row score is less than 0).  So, obviously a candidate
cannot win both for the normal and reversed ballots.

So, your method meets Reverse-consistency
-----------
35 A B C
33 B C A
32 C A B

A 102
B 101
C 97
BN=100, C eliminated

67 A B
33 B A

A wins

Using clones A1, A2 in place of A

35 A1 A2 B C
33 B C A1 A2
32 C A1 A2 B

A1 202
A2 102
B 134
C 162

So, since BN=150, A2, B are eliminated

35 A1 C
65 C A1

C wins.

So, your method suffers from vote-splitting.  Fails GITC.
-------------
   3 2 1 0
35 A E B C
33 B C A E
29 C A E B
3  C A B E

A 202
B 137
C 162
E 99
So, B and E are eliminated
35 A C
65 C A
C wins

Now adding a candidate D who is the last choice of everyone.

   4 3 2 1 0
35 A E B C D
33 B C A E D
29 C A E B D
3  C A B E D

A 302
B 237
E 199
C 262
D 0

D and E are eliminated

35 A B C
33 B C A
32 C A B

A wins.

Since D is not in the Smith set, this is a violation of LIIAC.  It's a
particularly bad one.

Fails LIIAC
----------

35 A E B C D
33 B C A E D
29 C A E B D
3  C A B E D

We know that A wins.  Consider if two people lower C as follows:
   4 3 2 1 0
35 A E B C D
33 B C A E D
27 C A E B D
2  A E C B D
3  C A B E D

A 304
B 237
E 201
C 258
D 0

BN=200
So, D is eliminated.

   3 2 1 0
35 A E B C
33 B C A E
27 C A E B
2  A E C B
3  C A B E

A 204
B 137
C 158
E 101
BN=150
So, B and E are eliminated

37 A C
63 C A

C wins.

So, your method fails monotonicity

----------
I hope I got all the arithmetic right.

Since you will probably want to test your own methods in the future, let me
mention a few notes that may help you.  These examples were mostly found using
the process of starting with examples that I thought might work, based partly
on the method's similarity to Nanson, and adjusting them until they did work.

Also, if you're trying to find an example where a method fails a criterion,
use examples where the method behaves differently from methods that pass it. 
So, for example, if you are trying to find an example of a method failing
monotonicity, it makes no sense to try examples of it picking the Condorcet
winner, because there are methods that always pick the Condorcet winner and
still pass monotonicty.

Recognize what is likely to cause a problem for the method.  Here is a list
of some of what I was keeping in mind while trying to find examples.

Monotonicity-  It is generally advantageous to have competitors that you
pair-wise beat, and bad to have ones that beat you.  In methods with
elimination, a major danger is that the people who you do well against will be
eliminated, but the people who beat you will remain.  Since methods try to
drop candidates who do poorly over-all, it becomes advantageous to beat a
candidate, but not so badly that you cause it to be eliminated.

GITC- in Nanson and this method, the problem occurs because the more
candidates who beat you, the worse off you are, even if these candidates are
clones.  Since, as we know from above, you are actually helping the candidates
who beat you, if there are so many of them that they cause you to be
eliminated, they can indirectly hurt themselves.

LIIAC- usually these are found by adding a candidate who is beaten much more
badly by other members of the Smith set than by the original winner.  The
violation shown above is a peculiar case.

---
Blake Cretney