[Election-Methods] Representative Range Voting with Compensation - a new attempt

[Jobst Heitzig]

Dear folks,

I must admit the last versions of RRVC (Representative Range Voting with 
Compensation) all had a flaw which I saw only yesterday night. Although 
they did achieve efficiency and strategy-freeness, they did not achieve 
my other goal: that voters who like the winner more than the random 
ballot lottery compensate voters who liked the random ballot lottery 
more than the winner. In short, the flaw was to use the three randomly 
drawn voter groups for only one task each, either for the benchmark, or 
the compensation, or the decision.

I spare you the details and just give a new version which I think may 
finally achieve all three goals: efficiency, strategy-freeness, and 
voter compensation.

The basic idea is still the same: Partition the voters randomly into 
three groups, let one group decide via Range Voting, and use each group 
to benchmark another group and to compensate still another group.

To make an analysis more easy, I write it down more formally this time 
and assume the number of voters is a multiple of 3. 

DEFINITION OF METHOD RRVC (Version 3)
=====================================

Notation:
---------

  X,Y,Z are variables for options
  i,j,k are variables for voters
  f,g,h are variables for groups of voters

Input:
------

All voters give ratings and mark a "favourit". Put...

  R(X,i) := the rating voter i gave option X
  F(i) := the option marked "favourite" on ballot of voter i
  A(i) := balance on voter i's "voting account" before the decision

Tally:
------

Randomly partition the N voters into three groups of equal size. 
The winner is the range voting winner of group 1. 
The voting accounts are adjusted as follows. Put...

  S := N/3

  Q := (S-1)/S

  G(i) := group in which voter i landed

  T(X,f) := total rating group f gave option X
          = sum { R(X,i) : i in group f }

  W(g) := range voting winner of group g
        = that W with T(W,g)>T(X,g) for all X other than W

  P(X,h) := proportion of group h favouring X
          = probability of X in group h's random ballot lottery 
          = # { i in group h : F(i)=X } / S

  D(f,g,i) := rating difference on voter i's ballot 
              between the range voting winner of group f 
              and the random ballot lottery of group g
            = R(W(f),i) - sum { P(X,g)*R(X,i) : X }

  E(f,g,h) := total rating difference in group h 
              between the range voting winner of group f 
              and the random ballot lottery of group g
            = sum { D(f,g,i) : i in group g }

For each voter i, add the following amount to her voting account C(i):

If i is in group 1:  
  deltaC(i) := E(1,2,1)-D(1,2,i) - E(2,2,2)  -  Q*E(3,3,2) + E(3,3,3)

If i is in group 2:  
  deltaC(i) := E(3,3,2)-D(3,3,i) - E(3,3,3)  -  Q*E(1,1,3) + E(1,1,1)

If i is in group 3:  
  deltaC(i) := E(1,1,3)-D(1,1,i) - E(1,1,1)  -  Q*E(1,2,1) + E(2,2,2)

(Remark: E(1,2,1) and D(1,2,1) are not typos!)

(END OF METHOD RRVC)


Analysis:
---------

1. 
The sum of all C(i) remains constant, so "voting money" retains its 
value. To see this, note that

  sum { E(1,2,1)-D(1,2,i) - E(2,2,2) : i in group 1 }
  = S*E(1,2,1) - E(1,2,1) - S*E(2,2,2) )
  = S*( Q*E(1,2,1) - E(2,2,2) )
  = sum { Q*E(1,2,1) - E(2,2,2) : i in group 3 }

and analogous for the other terms in the above sums.

2. 
Note that the terms E(1,2,1)-D(1,2,i), E(3,3,2)-D(3,3,i), and 
E(1,1,3)-D(1,1,i) in the above sums do not depend on voter i's ratings! 

Hence the only way in which the ballot of voter i can affect her own 
voting account is trough the dependency of W(1) on her ratings, and 
this is only the case for voters in group 1, the "deciding group". 

So, as only voters in group 1 can influence their outcome, an analysis 
of individual voting strategy is only required these voters. For such a 
voter i the net outcome, up to some constant which is independent of 
i's behaviour, is this:

  O(i) := sum { R(W(1),j) : j other than i } + U(W(1),i)

where 

  U(X,i) := true value of X for i.

If voter i is honest and puts R(X,i)=U(X,i), this simply adds up to
 
  O(i) = T(W(1),1)  (if i is honest).

Now assume this honest voter i thinks about changing the winner from 
W(1) to some other option Y by voting dishonestly. The net outcome for 
i after this manipulation would be

  O'(i) = sum { R(Y,j) : j other than i } + U(Y,i)
        = T(Y,1)-R(Y,i) + U(Y,i)
        = T(Y,1)
        < T(W(1),1) = O(i).

So after all, i has no incentive to manipulate the outcome because she 
would have to pay more than she gains from this.

3. 
Now consider a large electorate of honest voters, and think about what a 
voter can expect, before the random process of drawing the three groups 
is applied, of how much her voting account will be adjusted. If I got 
it right this time, this expected value of deltaC(i) should be, up to 
some constant term which is equal for all voters, just

  the rating difference on voter i's ballot 
  between the random ballot lottery 
  and the winner of the decision, i.e.

  sum { P(X)*R(X,i) : X } - R(W,i).

This means that in this version I finally managed that voters who like 
the winner more than the random ballot lottery compensate voters who 
liked the random ballot lottery more than the winner.

Let's see why this is probably true: For a large electorate, it is 
probable that all three randomly drawn groups are quite representative 
of the whole electorate and will all give approximately the same total 
ratings, hence the same range voting winner, and approximately the same 
random ballot lottery. In other words, one can expect that

  approx. T(X,1)=T(X,2)=T(X,3) and P(X,1)=P(X,2)=P(X,3) for all X,
  and W(1)=W(2)=W(3)=:W.

But then also all terms E(*,*,*) share a common approximate value E, and 
deltaC(i) becomes

  E - D(1,2,i) - E - Q*E + E
  = E/S - R(W,i) + sum { P(X)*R(X,i) : X }  approximately.

The constant term E/S makes the whole thing sum up to zero so that no 
voting money is produced or destroyed, only redistributed. Q.E.D.

The thing most astonishing to me is that although the actual value of 
deltaC(i) is independent of i's ratings (as long as the winner is not 
changed), the expected value of this adjustment does more or less 
depend *only* on these ratings.

4.
And how much does the actual adjustment vary for different choices of 
the three groups? More precisely, what is the approximate variance of 
deltaC(i) for a large, honest electorate? Let us unrealistically assume 
all ratings R(X,i) were identically and independently distributed. As 
deltaC(i) is a sum of individual rating differences whose variance is 
some constant value V, we essentially have to count them. Each E(*,*,*) 
consists of S such differences, so we have approximately

  Var(deltaC(i)) = V*(S + 1 + S + Q*S + S)*V = V*4S 
                 = V * 4/3 * N.

In other words, the variance of an individual adjustment is of order N, 
so the standard deviation is of order sqrt(N).

This still seems a bit large to me, so perhaps after some of you have 
verified the above claim, we can further improve the method by using an 
averaging procedure as in the (flawed) version 2. Because of the large 
number of possible partitions of the voters into three goups, such an 
averaging of the adjustments should hopefully reduce the variance by a 
factor of order at least 1/N, making it shrink instead of grow with 
growing N...

5.
A final remark as to strategy-freeness: As with Clarke taxes, the 
strategy-freeness is for individual voters not voter groups. That is, 
each individual voter can maximize her expected net outcome by voting 
honestly no matter what the others do. This does not exclude the 
possibility of some voter group manipulating the decision to their 
mutual advantage. In fact, with both Clarke taxes and with RRVC, such 
group strategies definitely do exist. 

However, I don't think that group strategies are much of a problem when 
the individually optimal strategy is honesty, because when the decision 
process assures anonymity, the group can never enforce cooperation, so 
for each individual it will be optimal to cheat the group by voting 
honestly, no matter what the contract was. This is even more so as 
cheating the group only means being honest, while sticking to the 
group's strategy means being dishonest, doing a suboptimal thing from 
the individual's perspective, and risking that other group members 
cheat.
 
Yours, Jobst