Dear folks! Some time ago I reported here upon the "Condorcet Lottery", a method which determines the winner by drawing from a special probability distribution (=lottery) among a special subset of the candidates (the so-called Bipartisan set). The special property of that method was that for every candidate X, the probability that the winner beats X is at least 1/2. In other words, the chosen lottery is "undefeated" by any candidate in this specific sense. I thought this a desirable property since it implied that for every majority-size coalition of voters who think about making X the winner by voting strategically X>rest, there is a probability of at least 1/2 that some member of the coalition ends up worse than with the sincere result. However, "Condorcet Lottery" had the major disadvantage of being non-monotonic.
Now I realized that one can define a notion of "candidate defeats lottery" in more that just the above way, and that perhaps a different definition is more helpful in evaluating lotteries. 1. Defeats in expected utility ------------------------------ Assume each voter i assigns a real-valued utility u(A,i) to each candidate A. Then it is straightforward to also assume that the voter assigns a utility to each lottery by averaging the candidates' utilities using the weights assigned by the lottery: u(aA+bB+cC+...,i) := a*u(A,i) + b*u(B,i) + c*u(C,i) + ... (a,b,c,... being the weights of A,B,C,... in the lottery). In short, it is natural to assume that voters evaluate lotteries by their expected utility. Hence we may naturally assume that voter i prefers candidate X to a lottery L if and only if u(X,i)>u(L,i). Then it makes sense to say that X DEFEATS L IN EXPECTED UTILITY if and only if for more than half of the voters u(X,i)>u(L,i). The interesting question is of course whether there is again always a lottery which is undefeated by all candidates in this sense. Unfortunately, this is not the case, as can be seen easily from the following example: 1 A(3)>B(2)>C(0) 1 B(3)>C(2)>A(0) 1 C(3)>A(2)>B(0) The "pure" lotteries A, B, and C are defeated by candidates C, A, and B, respectively. Each mixed lottery L has a utility of less than 3 for all voters. If L has a utility of less than 2 for some voter, it is thus defeated by at least one candidate. Hence an undefeated lottery L would need a utility of at least 2 for each voter which is impossible since the utility of any lottery L averaged over the three voters must be 5/3 < 2. 2. Defeats in median -------------------- A more promising notion of "candidate defeats lottery" uses a kind of median instead of the expected value. This has the additional advantage that we need not assume utility functions but only total (aka complete) preference orderings: Let us assume voter i evaluates the lottery L in comparison to candidate X by asking whether it is more probable that she prefers X to the winner drawn from L than that she prefers the winner drawn from L to X. Accordingly, let us say that X DEFEATS L IN MEDIAN if and only if more than half of the voters are more likely to prefer X to the L-winner than to prefer the L-winner to X. (Don't confuse this with "it is more likely that more voters prefer X to the L-winner than that more voters prefer the L-winner to X", which was used in the context of "Condorcet Lottery"!) Again the question is: Is there always a lottery which is undefeated in median? This would be nice since such a lottery is not likely to be overruled by a strategizing majority -- unlike all deterministic methods in face of a cycle at the top. In the 3-cycle example A>B>C, B>C>A, C>A>B, the uniform lottery A/3+B/3+C/3 is the only undefeated lottery: To be not defeated by C, L must assign A at most the same weight as B. By symmetry, L(A)<=L(B)<=L(C)<=L(A), hence all three weights must be 1/3. The same lottery A/3+B/3+C/3 is the only undefeated in median in the following example: 1 A>D>B>E>F>C 1 B>E>C>F>D>A 1 C>F>A>D>E>B But in 1 A>D>E>B>C>F 1 B>E>F>C>A>D 1 C>F>D>A>B>E only the lottery D/3+E/3+F/3 is undefeated in median. This is interesting since in both examples the defeats are A>B>C>A, D>E>F>D, A>D,A>E,A<F, B>E,B>F,B<D, C>F,C>D,C<E and have all the same strength of 2:1. Hence the set of lotteries undefeated in median is not a function of the defeat matrix nor a function of the summed preferences matrix alone! (In contrast, the "Condorcet Lottery" would be A/3+B/3+C/3 in both cases since the Condorcet Lottery is a function of the defeat matrix alone.) Although I was skeptical first, I was not yet able to find an example without a lottery which was undefeated in median, so I dare to... CONJECTURE: THERE IS ALWAYS A LOTTERY WHICH IS UNDEFEATED IN MEDIAN. Please prove me wrong! Jobst ---- Election-methods mailing list - see http://electorama.com/em for list info
