[EM] Lotteries undefeated "in median"

[Jobst Heitzig]

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