[Election-Methods] final attempt for a strategy-free range voting variant, and another proportionally democratic method
Jobst Heitzig
heitzig-j at web.de
Sun Jul 27 14:31:36 PDT 2008
Hello again.
As promised, here is my final attempt to contribute a strategy-free
range voting variant which uses a conserved amount of virtual "voting
money". Second, I will describe how this can be used to improve the
"proportionally democratic" methods Forest and I discussed some weeks ago.
I.
DEFINITION OF METHOD
Jackknife Range Voting with Zero-Sum Virtual Clarke taxes (JRV0VC)
==================================================================
Prerequisites:
--------------
N voters are to perform a sequence of decisions with a possibly varying
number of options. Each of them has a "voting account" that starts with
an equal number of "voting cents", say 100.
The method describes how to perform each single decision in the
sequence. It finds a winner and may adjust some of the "voting
accounts" by transferring some of this virtual money.
Input:
------
Each voters assigns a numeric rating to each option. She can use ratings
between 0 and her current voting account's balance. If the latter is
negative, all ratings must be 0. Put...
R(X,i) := the rating voter i gave option X
C(i) := balance on voter i's "voting account" before the decision
Because of the restrictions, we have
0 <= R(X,i) <= max { 0, C(i) }.
Tally:
------
1. Determine the ordinary range voting winner W, the runner-up Y and the
winning margin, i.e. the difference between their total ratings.
2. If this difference is larger than the maximum difference between the
ratings of any two options on any individual voter's ballot, then W is
the winner of the election.
3. Otherwise, a randomly drawn ballot is removed, the winner is the
range voting winner W' as determined from the other N-1 ballots, and the
voting accounts are adjusted as follows. Using all N ballots again, put...
T(X,i) := total rating of option X on the ballots different from i
= sum { R(X,j) : j different from i }
W(i) := range voting winner when ballot i was removed
= that W with T(W,i)>T(X,i) for all X other than W
For each voter i, add the following amount to her voting account C(i):
sum { (2-N)*R(W(i),j)
+ sum { R(W(k),j) : k different from i and j }
: j different from i }
/ N
(END OF METHOD JRV0VC)
Note that step 2 is only a short-cut. Removing it would change nothing
since the winner and adjustments would be the same.
Note also that this is quite similar to Clarke taxes. When those were
used, not W' but W would be elected and the amount added to C(i) would be
sum { R(W,j) - R(W(i),j) : j different from i }
= sum { - N*R(W(i),j)
+ N/(N-2) * sum { R(W,j) : k different from i and j }
: j different from i }
/ N
The main advantage is that while Clarke taxes do not sum up to zero, the
above JRV0VC-adjustments do, so no "voting money" needs to be destroyed
or generated, and hence no "inflation" or "deflation" can happen which
would have influences on the strategic implications.
But this can only be achieved by randomizing Range Voting slightly by
removing a randomly drawn ballot. Otherwise, there would be incentives
to misrepresent the true ratings. However, this slight randomization and
the related transfers of virtual money only happen in the rare case
where the election is so close that a single ballot can make a difference.
The idea of "virtual voting money" is not new (I learned about it in the
Pivato paper I cited last week) but the combination with removing a
single ballot to make it zero-sum is.
We need to study these things:
a) What group strategies might exist, in particular how strategic
behaviour of one voter influences the outcome of a second voter. In this
context, the method might be improved further by increasing the number
of removed ballots if that reduces group strategies.
b) Can "voting money" really be considered a form of money, and can we
expect it to be linear in individual utilities? My hope is that this is
so because the virtual money is only used to "buy" immediate voting
power and pay with potential later voting power. I think it would not be
necessary that utilities be comparable between different persons. Just
the utilities some fixed person assigns to options in the decision at
hand need be comparable to utilities the same person assigns to options
in a later decision.
c) How would the "exchange rate" of this virtual money be established?
II.
Now comes the "proportionally democratic" method which utilizes the
above method. This was my real goal in all of this, as you might have
guessed already:
DEFINITION OF METHOD
Favourite or Utilitarian Random Ballot (FURB)
=============================================
Phase I:
--------
Perform a JRV0VC election to find the "compromise option" for phase II.
The question on the ballot reads "How much value does it have for you if
option ... was the compromise option for phase II?".
Designate the winner of this phase by W.
Phase II:
---------
1. On a new ballot, everyone
(i) specifies her favourite option and
(ii) answers the question "Would you cooperate to elect W?"
2. A die is tossed. If it shows six then 15 of these ballots are
drawn at random, otherwise only 3 are drawn.
3. If all drawn ballots answered "yes", W is elected.
Otherwise the favourite on the first drawn ballot is elected.
(END OF DEFINITION)
Note that phase II is exactly the same as in Two-Phase-FAWRB.
Summary of properties:
----------------------
a) Monotonic, neutral, anonymous in the long run, clone-proof.
b) The method is "proportionally democratic" in the sense that when p
percent of the electorate mark some favourite X and say "no" to the
compromise W, then X will have at least p percent winning probability.
This is true regardless of the voting accounts since they are used only
in phase I.
c) Phase I is strategy-free and thus is likely to choose that compromise
option which will make the final result of phase II have the largest
total utility.
d) In phase II, it is optimal to mark the true favourite.
e) In phase II, optimal strategy is monotonic in the following sense:
Assume it is optimal for some voter i to say "yes" in phase II, and
assume some other voter j has the same true ratings as voter i except
that j rates the compromise option higher than i does. Then it is also
optimal for voter j to say "yes" in phase II.
f) If every voter i prefers the compromise option W to a lottery in
which i's favourite is elected with 20% probability and the Random
Ballot lottery is applied with 80% probability, and all voters know that
this is the case, then it is likely that all voters will say "yes" in
phase II and W will be the sure winner.
g) If more than one such option W as in f) exists, then the one will be
chosen in phase I which maximizes total utility. This means the method
will elect the utilitarian winner amoung the unanimously acceptable
compromise options, if such options exist.
Now, it would be nice if someone invested a bit of time to double-check
all of these claims :-)
Yours,
Jobst
Jobst Heitzig schrieb:
> 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
>
More information about the Election-Methods
mailing list