[EM] The Copeland/Borda wv hybrid

[Forest Simmons]

A natural variation on this method would be to form W' by putting the
candidates' respective approval scores along the main diagonal instead of
the row sums from W.  Then the disapproval scores would go along the
diagonal of D'.

This method requires approval information, so Demorep style ballots, grade
ballots with a passing cutoff, or a None of the Below candidate option
would be needed.

Lacking approval information, one could use the number of ballots that
rank the candidate, and the number that truncate the candidate,
respectively, in place of the approval and disapproval scores.

Note that in graph G1, the edges go "uphill" that is from loser to winner,
and that in graph G2 the arrows go downhill.  So high equilibrium values
are good in the first case, and low are good in the second case.  That's
why high values are good for the entries of the vector  z =  x - y .

[The eigenvectors are the equilibrium vectors.]

The main reason to have something along the main diagonal is to assure
convergence.  If the diagonal entries are all zero, then it might turn out
that normalization of the columns puts a one in each column, and that the
matrix W'' becomes a permutation matrix.

In that case, for any power of W'', the average of its column vectors is a
vector whose entries are all equal to each other.  The method would be
indecisive.  This would be the case in a three candidate cycle, for
example, if we didn't put something along the main diagonal.

By the way, in my recipe for finding x, to be accurate in these degenerate
cases, I should have said, "Raise W'' to a high power, and take the
average of the column vectors for x."

In other words, substitute the phrase "average of the column vectors" for
the phrase "common column vector" in the text below.

In other words, start with a vector x_0 all of whose entries are ones.
Recursively let x_n = W''x_(n-1) . Find the limit of x_n as n approaches
infinity.  Then normalize to get x.

My preference is the version based on approval/disapproval scores down the
main diagonals of W' and D', respectively.

It seems like a more seamless method than Demorep's ACMA for combining
approval scores into a method satisfying the Condorcet Criterion.

Forest

On Tue, 26 Nov 2002, Forest Simmons wrote:

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

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