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

[Jobst Heitzig]

A first typo: It must read  C(i)  instead of  A(i)  under "Input"...

--
> 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
>  
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>