First off, a warning. The following is highly mathematical. If you don't like or understand this kind of stuff, don't read it. The purpose of this article is to provide a stronger foundation for the belief that the beat-path winner, as described by Markus, is the most probable best candidate. First, some definitions. I usually measure the strength of a pair-wise victory by the margin of majority. Others, including Markus, prefer to use only the number on the winning side. I don't intend to debate this point here. If there is a series of pair-wise victories leading from one candidate to another, for example A->B, B->C, C->D "->" means beats pair-wise then there is a path from C to D. The strength of a path is equal to the strength of its weakest victory. If the strongest path from A to B is stronger than the strongest path from B to A, then I say that A has a Schulze victory over B. Assuming there are no ties, we can create a complete ranking of the candidates by ranking a candidate over every candidate they Schulze-defeat. Next, some premises I start with the assumption that people will have a tendency towards making correct decisions. So, if presented with two options, they will be slightly more likely to pick the correct one. This means that the more people support a proposition, the more likely it is to be true. And the more who oppose, the less likely. One, although not the only, way we can use this is by saying that the probability of a statement being correct increases with the margin by which it is supported. I should point out that the kind of statement we have available to use this kind of test is the A>B kind, with every person who ranks A over B being evidence for this proposition and every person who ranks B over A being evidence against. Kemeny's method takes these pair-wise victories and assumes that they are independent. That is, that a person's favouring of A>B is independent of their favouring of C>D. In fact, this is a very poor assumption. Since decisions are being made by the same people, on the same basis, often about similar candidates, independence is unlikely. For example, if someone rates candidates A, B, and C low on their ballot because they are all conservatives, all want to decrease farm subsidies, or are all women, this should not be assumed to be an independent decision. As a result, Kemeny has some clone problems. For example, if someone submits a proposals identical to another, this could change the results, although not by causing this proposal to be elected or not elected. Kemeny's method assumes that the decisions voters are making on the two identical proposals are in fact made independently. So, if there are three groups of twins A, B and C with Ax1->Bx2->Cx3->Ax4 for all x1,x2,x3,x4 Ai denotes a twin of twin set A for all A. Then, the more twins of set C there are, the worse the alternatives of set A are perceived, since each new twin is considered to be independent information against the twins in A. So, the question is, is it possible to make a method on a probabilistic basis which does not assume independence. I suggest that Schulze is such a method, possibly the only one, at least for ranked ballots. --- If we have a majority decision A>B, this can be taken as evidence in favour of the proposition that A is better than B. So, it follows that if we have a path, A>B B>C C>D D>E that this is evidence that A is better than E. If we write [A>B] to mean the margin by which A defeats B, we could write F([A>B],[B>C],[C>D],[D>E]) to mean the increasing function which assigns a strength to this evidence. Let me now suggest a useful analogy. Consider a lottery that awards a free ticket 1/2 the time, and $1000 dollars 1/10000 of the time. What is your chance of winning both? If you assume they are independent, 1/20000. However, what if every $1000 dollar winner automatically receives a free ticket? This would mean the chance would drop to 1/1000. We know, however that it is impossible that every free ticket winner automatically wins $1000 dollars because the free ticket probability is greater. Now, we want F to be unaffected by any assumption of independence. For example, if we knew that C>D was dependent on B>C, so that these voters by deciding B>C automatically decided C>D, we would want F([A>B],[B>C],[C>D],[D>E]) = F'([A>B],[B>C],[D>E]) That is, we wouldn't want F to make use of the extraneous information that C>D. Of course if [B>C]<[C>D], we would know that it is not true that B>C->C>D, at least for some people. However, if there are two majorities, there is no way to know that the larger majority is not dependent on the lesser. Therefore, if we don't want to make any assumptions about dependence, we have to use a function F that only depends on the strength of the smallest majority in the path. This is how Schulze defines the strength of a beat path. Note that this is not exactly the same as assuming dependence. We aren't actually saying that p(A>B and B>C) = p(A>B) just that the function F will only be based on evidence we know not to be affected by level of dependency. In the same way, when we count each persons vote as equal, we aren't assuming that they are all equally likely to be right or wrong. We just aren't assuming anything about who is more likely to be right. This brings up the question of what to do if you have several paths from A to E. The argument is the similar. If you don't want to assume any independence you have to use only the maximum beat path. After all, the beat paths which provide less strong evidence could be redundant (dependant) information. It therefore makes sense to do as Schulze describes, comparing the strongest beat paths between A and B is equivalent to comparing the strength of the evidence for A>B with the strength of the evidence that B>A, without assuming any level of independence. ----- To help explain this argument, I will suggest the following situation. We have several statements made by an oracle. The oracle does not promise that she is stating the truth. Sometimes she ignores the truth and replies randomly. However, she always gives a probability that the statement was based on truth instead of chance. Imagine that you have these oracle statements about candidates A, B, C and D, and you want to know what the most likely best candidate is. 1. A>B 60% 2. B>C 70% 3. C>A 80% 4. A>D 55% 5. B>D 55% 6. C>D 55% If we use a Minimax (Simple Condorcet) procedure to resolve this, we would say that D is the most likely winner. After all, we would argue that statement #1 shows that we have a 60% certainty statement saying that B is not the winner. #2 gives 70% that C is not. #3 gives 80% that A is not. If we don't want to assume any level of independence, we have to say that there is only 55% certainty against D. But we are making the mistake of assuming that the not B, not C, and not A statements are independent. Although each when considered independently has a high chance of truth, we know that one of them is false, and that one must be false whether or not D wins. Many of the points I've made here have suffered due to my desire for brevity. If anyone has any questions, I'm happy to explain myself more thoroughly. I hope to kick off a discussion about probabilistic justifications for voting methods, particularly Schulze's method. --- Blake Cretney See the EM Resource: http://www.fortunecity.com/meltingpot/harrow/124
