[EM] The Copeland/Borda wv hybrid

[Elisabeth Varin/Stephane Rouillon]

Could you summarize the method?

Steph.

Forest Simmons a écrit :

> 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