[EM] Another interesting method: Lin's Eigenvector Method

[Rob Speer]

I've just come across a dissertation by M. J. Lin about an election
method that also gives a set of weights to candidates as the
result, but unlike UWA, is monotonic. It's called the Eigenvector
Method.

He gives a terse mathematical description of the method, but I believe
it works equivalently to this:

For each pair of candidates, call them A and B, define the "strength"
of A over B as the number of ballots on which A is ranked above B,
_divided by_ the number of ballots on which B is ranked above A. So the
strength of a victory is greater than 1 and the strength of a defeat is
less than 1.

Each candidate has a score between 0 and 1, and these scores are scaled
after each step so that they add up to 1. The scores can start in any
state; perhaps give 1 to one candidate and 0 to the rest. The starting
state doesn't affect the result.

At each step, take the score belonging to each candidate, and
redistribute it among all the candidates, proportional to the strengths of
those candidates over the original candidate.

Repeat as many times as necessary. Eventually, the scores will stabilize
at certain values, and these are the final weights.

These weights shouldn't be used to choose a candidate randomly; even
candidates outside the Smith Set will have a weight. Instead, just
choose the candidate with the highest weight as the winner.

The terse mathematical description: Take the matrix in which the ith
entry in the jth row is the strength of candidate j over candidate i.
Find the largest real eigenvalue of that matrix, take the eigenvector
corresponding to that eigenvalue, and scale that vector down so that its
sum is 1. This vector gives the weight for each candidate.

An example:
  A   B   C
A 1   1/2 3/2
B 2   1   3/4
C 2/3 4/3 1

Start with the scores [1, 0, 0].
These scores get redistributed and become:
[0.27, 0.55, 0.18]
[0.26, 0.39, 0.35]
[0.30, 0.37, 0.33]
[0.30, 0.38, 0.32]
[0.30, 0.38, 0.32]
... and here they have stabilized. B is the winner.

I haven't yet implemented this on the computer, so I haven't done much
testing with it.
-- 
Rob Speer