[EM] The Copeland/Borda wv hybrid

[Forest Simmons]

Rob, remember that method that you proposed that turned out to be a kind
of Borda/Copeland hybrid that usually picked the CW, but not always?

I have a way to fix it.

Remember, you started by deleting all of the losing votes from the
pairwise matrix to get the winning votes matrix W.  Then you subtracted
each candidate's column sum from her row sum.  The candidate with the
highest total won the election.

Here's how to fix it:

First modify the winning votes matrix W to W' by putting its respective
row sums in place of the zeros along the main diagonal.

Next, modify W' to W'' by normalizing each column by dividing it by its
sum.

The resulting matrix W'' is a non-negative matrix with column sums of one.

[So its transpose is an example of a "stochastic matrix" representing a
Markov process, a fact that we will use later.]

The number one is necessarily an eigenvalue for such a matrix.

Let x be an eigenvector of W'' such that  W''x = x, and such that x is
normalized so that its elements sum to one.  [If there is more than one
such x, i.e. if the eigenspace for the number one is more than one
dimensional, then we want the principle eigenvector for x.]

The desired x can be obtained by squaring W'' over and over until all of
the columns become identical to as many decimal places as your machine
will handle.  This common column vector is x.


Now go back to the matrix W and take its transpose to get D the matrix of
defeating votes.

Convert D to D' and D'' by the same process used in converting W to W'
and W''.

Let y be the eigenvector that is the common column obtained by raising D''
to a sufficiently high power.

[In the vernacular of non-standard analysis, raise D'' to the N_th power,
where N is any non-standard whole number. Then let y be the standard part
of any column vector of the resulting matrix.]

Form the difference  z =  x - y  of the two vectors.

The numerical order of the entries of z induces an order on the set of
candidates, if entry z_i is numerically greater than z_j, then candidate i
is ranked ahead of candidate j.

Notice that the method automatically satisfies reverse symmetry, since
reversing all of the ballot preferences corresponds to interchanging W''
and D'' which results in reversing the signs of all the entries in the
vector z.

How do we know that this method satisfies the Condorcet Criterion?

Think in terms of Markov processes.  In fact, think of directed graphs G1
and G2, whose vertices are the candidates and the edges are given weights
by the corresponding entries in matrices W'' and D'', respectively.

Specifically, if the element in the i_th row and j_th column of W'' is
denoted by Pij, then Pij is the probability that if the current state is
candidate j, then the next state will be candidate i.

[In the Markov process context, the vertices of the graph are considered
to be "states"  in a discrete dynamical system.  Here I am going against
the convention for the order of i and j since we used right hand
eigenvectors for W'' and D'', whereas the Markov Process people generally
use the left hand eigenvectors that go with so called "stochastic
matrices" which have row sums of one, rather than column sums of one. The
transposes of W'' and D'' are examples of stochastic matrices.]

To make a long story short, eventually all of the probability fluid drains
into the Smith set, since there are drainage paths into it from all of the
other vertices, but no outlet drainage.

The previous paragraph refers to the Markov process associated with
(the transpose of) W''.

In the case of the Markov process associated with (the transpose of) D'',
all of the probability fluid drains into the reverse Smith set, or to the
Condorcet Loser, if there is one.

So non-zero entries of x correspond to members of the Smith set, and
non-zero entries of y correspond to members of the reverse Smith set.

Therefore the positive entries of z = x - y have to be members of the
Smith set, and the negative entries have to be members of the reverse
Smith set.

[It is possible for both Smith and reverse Smith to be the same set, so a
negative value does not imply that the candidate is not a member of the
Smith set.]

This method was inspired by your suggestion, so if you like it, let's call
it the LeGrand/Simmons method.

I think that folks like physicists, probabilists, graph theorists, and
others who deal with eigenvectors will appreciate the merits of such a
method.

Forest

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em