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
