[EM] A more efficient strategy-free ratings-based method than Hay voting

[Jobst Heitzig]

Dear friends,

Hay voting was supposedly the first known method under which it is 
always optimal (as judged from expected utility) to vote sincere ratings 
(i.e. ratings proportional to true utility). However, it seems that it 
is a rather inefficient method (as judged from total expected utility), 
even less efficient than Random Ballot.

Here's a different, more efficient method under which it is also always 
optimal (as judged from expected utility) to vote sincere ratings. It is 
also based on Random Ballot, but in a very different way. It is 
essentially a Random Ballot method with an added mechanism of automatic 
cooperation for compromise. The basic idea is that when there is a pair 
of ballots showing preferences A>...>C>...>B and B>...>C>...>A, those 
two voters can profit from cooperating and transferring part of "their" 
share of the winning probability from A and B to the compromise option C.

Here's the method, I call it...


RANDOM BALLOT WITH AUTOMATIC COOPERATION, Version 1 (RBAC1):
------------------------------------------------------------
Voters rate each option.
Three ballots i,j,k and two numbers x,y between 0 and 1/2 are drawn at 
random.
Assume that the top-ranked options of i,j,k are A,B,C, and that i and j 
have assigned to A,B,C the ratings ri(A),ri(B),ri(C) and 
rj(A),rj(B),rj(C), respectively.
Now check whether the inequalities
  y * (ri(C) - ri(B)) > x * (ri(A) - ri(C))
and
  x * (rj(C) - rj(A)) > y * (rj(B) - rj(C))
both hold.
If so, elect A, B, or C with probabilities  1/2 - x,  1/2 - y,  x + y,  
respectively.
Otherwise, elect A or B each with probability 1/2.


Why should it be optimal to vote sincere ratings under this method?

Consider an arbitrary voter i with favourite option A, and some 
arbitrary options B,C and numbers x,y between 0 and 1/2.
Let us designate the A,B,C-lottery with probabilities  1/2 - x,  1/2 - 
y,  x + y  by L, and the A,B-lottery with probabilities 1/2 and 1/2 by M.
The only thing i can do about the election outcome is by influencing 
whether or not "her" inequality
  y * (ri(C) - ri(B)) > x * (ri(A) - ri(C))
holds, and the only situations in which this matters at all are those in 
which i is among the first two drawn ballots, the other of the two has B 
top-ranked, and the third has C top-ranked.
As it is equally likely for i's ballot to be drawn as the first or the 
second ballot, and as i cannot influence whether or not the other inequality
  x * (rj(C) - rj(A)) > y * (rj(B) - rj(C))
holds, i would therefore want "her" inequality
  y * (ri(C) - ri(B)) > x * (ri(A) - ri(C))
to hold if and only if she prefers lottery L to lottery M.
But the latter is the case if and only if
  y * (ui(C) - ui(B)) > x * (ui(A) - ui(C))
where ui(A),ui(B),ui(C) are i's evaluations of the true utility of the 
options A,B,C.
Now x and y were arbitrary numbers, so the only way to get this 
equivalence is to put ri(A),ri(B),ri(C) proportional to 
ui(A),ui(B),ui(C), and perhaps adding some irrelevant constant. Q.E.D.


Note that it doesn't matter from which precise distribution x and y are 
drawn as long as all values from 0 to 1/2 are possible. For the sake of 
efficiency, one should therefore use a distribution that strongly 
favours values near 1/2, so that cooperation will be more likely. Also, 
the winning probabilities can safely be changed to
  1/2 - x/z,  1/2 - y/z,  (x+y)/z,
where z := 2 * max(x,y). This will increase the probability of good 
compromises further.

Finally, note the following important fact about the method: It is 
perfectly democratic since it distributes power equally in the following 
sense: Any faction of m voters can give "their" share m/n of the winning 
probability to any option they like by simply "bullet-rating" that 
option at one and all others at zero.

Please send comments!
Jobst