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
