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
