[Election-Methods] a strategy-free range voting variant?
Jobst Heitzig
heitzig-j at web.de
Mon Jul 21 07:12:03 PDT 2008
I performed a quick little simulation for version 2:
With K options and N voters, I drew the all K*N ratings independently
from a standard normal distribution and then applied the method with
D=sqrt(N)/2.
However, instead of using all partitions as suggested, I only used N/2D
partitions. More precisely, I ordered the ballots in a random way in
groups of size D, and then first used groups 1 and 2 as the benchmark
and deciding group, afterwards used groups 3 and 4 for this, then used
groups 5 and 6, and so on. In other words, the account adjustments were
averaged not over all possible partitions but only over these sqrt(N)
many groups.
I did this 100 times for each of a number of different pairs (K,N) and
evaluated the standard deviation of the individual account adjustments.
It turned out that for K=2 this standard deviation was approximately
0.2 / sqrt(sqrt(N))
and only slightly larger for K=16 or K=128.
Since this is quite small when compared to the standard deviation of the
original ratings, which is 1 of course, this averaging in version 2
indeed looks promising! (Without it, the standard deviation of the
individual account adjustments would grow not shrink with growing N.)
Jobst
Jobst Heitzig schrieb:
> Dear folks,
>
> this night I had two additional ideas for RRVC, so here's two new
> versions of it.
>
>
> In the first version, the fee F is determined from the benchmark ballots
> so that the expected "price" a deciding voter has to "pay" from her
> voting account is just that voter's rating difference between the winner
> and the random ballot lottery:
>
>
> RRVC - New Version 1
> --------------------
>
> 0. Each voter i is assumed to have a "voting account" whose balance is
> denoted C(i).
>
> 1. All N voters fill in a range ballot and additionally mark their
> favourite in case of a top-rating tie. Voter i can use ratings
> 0...C(i) only. If C(i) is negative, she can use the rating 0 only
> (but still mark her favourite). Let R(X,i) be the rating voter i
> gave to option X.
>
> 2. Put D = sqrt(N) (rounded up), and draw D "deciding" ballots. For
> each option X, determine the total rating T(X) these deciding
> ballots gave to X. The winner W of the decision is that option whose
> total rating is maximal, i.e. that option W for which T(W)>T(X) for
> all X other than W.
>
> 3. From the remaining ballots, draw D "benchmark" ballots. For each
> option X, determine the total rating B(X) these benchmark ballots
> gave to X, and determine the probability P(X) that X is the
> favourite on a ballot drawn randomly from these benchmark ballots.
> (I.e., P(X) is the fraction of benchmark ballots favouring X).
> Let Z be that option whose total rating is maximal in this group, i.e.
> that option Z for which B(Z)>B(X) for all X other than Z.
>
> 4. For each voter i whose ballot is amoung the deciding ballots, add
> the following amount to her voting account C(i):
>
> deltaC(i) := sum { P(X)*( B(X)-T(X,i) ) : X } + T(W,i)-B(Z),
>
> where the sum is over all options X, and where
> T(X,i) = T(X)-R(X,i)
> is the total rating of X amoung all deciding ballots of voters other
> than i.
>
> 5. The remaining N-2D voters are the "compensating" voters. For each
> compensating voter j, add the following to her voting accout C(j):
>
> deltaC(j) := - sum { deltaC(i) : i } / (N-2D),
>
> where the sum is over all deciding voters i.
>
>
> Remarks for version 1:
>
> Since the deciding and benchmark groups are of equal size, the expected
> values of T(X) and R(X) are the same, and it is also likely that
> Z=W. This implies that the expected value of deltaC(i) given that i
> is a deciding voter and all voters report sincere ratings, is just
>
> sum { P(X)*R(X,i) : X } - R(W,i).
>
> In other words, when ratings are sincere a deciding voter can expect to
> "pay" exactly her rating difference between the winner and the Random
> Ballot lottery. (This is a major difference to the Clarke tax where this
> "take Random Ballot as a benchmark" philosophy is not incorporated).
> Also note that the standard deviation of deltaC(i) under these
> assumptions is of an order somewhere between O(sqrt(D)) and O(D),
> depending on how correlated the individual voters' ratings are.
>
> Still, the actual price payed by voter i is independent of her ratings
> as long as she does not manage to change the winner. Hence there is
> still no incentive to bargain for a lower price by misrepresenting my
> ratings.
>
> Assuming the true value of W for voter i is U(A,i)=R(W,i), the net
> outcome for i is
>
> U(W,i) + deltaC(i)
> = sum { P(X)*( B(X)-T(X,i) ) : X } + T(W)-B(Z).
>
> Now assume voter i thinks about changing the winner to A, originally
> having a total of T(A)<T(W). Since this manipulation does not change
> the values T(X,i), the net outcome for i after this manipulation
> would be
>
> U(A,i) + sum { P(X)*( B(X)-T(X,i) ) : X } + T(A,i)-B(Z)
> = sum { P(X)*( B(X)-T(X,i) ) : X } + T(A)-B(Z).
>
> Since this differs from the first outcome only in that it has T(A)
> instead of T(W), it is obviously smaller since T(A)<T(W). So after
> all, i has no incentive to manipulate the outcome because she would
> have to pay more than she gains from this.
>
> Actually, since voter i cannot know who are the deciding, benchmark,
> or compensating voters, she cannot base her strategic considerations on
> the actual value of W and deltaC(i), but only on their expected
> values in the random process of drawing the three voter groups.
>
> The latter observation motivates a second version of the method. In this
> version, the winner is determined as before, but the account adjustments
> deltaC(i) are averaged over all possible configurations of the three
> voter groups. This has the advantage that because of this averaging, the
> standard deviation of deltaC(i) will become much smaller than in the
> previous versions, and hence the actual value of deltaC(i) will be
> quite close to the "fair" price sum { P(X)*R(X,i) : X } - R(W,i).
>
> Unfortunately, the precise method is a bit technical:
>
>
> RRVC - New Version 2
> --------------------
>
> 0.-2. as above.
>
> 3. For each possible partition S of the N voters into disjoint sets
> SD,SB,SC of sizes D,D,N-2D, and for each option X, do the following:
>
> a) Determine the total rating T(X,S) the ballots in SD gave to X.
> b) Determine the total rating B(X,S) the ballots in SB gave to X.
> c) Determine the probability P(X,S) that X is the favourite on a
> ballot drawn randomly from SB.
>
> 4. For each such partition S, let...
>
> a) W(S) be that W with T(W,S)>T(X,S) for all X other than W.
> b) Z(S) be that Z with B(Z,S)>B(X,S) for all X other than Z.
>
> 5. For each such partition S and each voter i, put...
>
> a) alphaC(i,S) := 0 if i is not in SD, otherwise
> alphaC(i,S) :=
> sum { P(X,S)*( B(X,S)-T(X,i,S) ) : X } + T(W,i,S)-B(Z,S),
> where T(X,i,S) = T(X,S)-R(X,i).
>
> b) gammaC(i,S) := 0 if i is not in SC, otherwise
> gammaC(i,S) := - sum { alphaC(i,S) : i } / (N-2D),
> where the sum is over all voters i in SD.
>
> 6. Finally, for each voter i, add the following amount to her voting
> account C(i):
>
> deltaC(i) := sum { alphaC(i,S)+gammaC(i,S) : S } / sum { 1 : S }
>
> where the sums are over all partitions S.
>
>
> I have not yet calculated by what factor the variance of deltaC(i) will
> shrink because of the averaging. That might be a bit difficult since the
> values of alphaC(i,S) are not independent for different S. My guess,
> however, is that the averaging will lead to the standard deviation
> having an order of at most O(1) instead of O(sqrt(D)) or even O(D).
>
> Perhaps someone can analyse this averaging in more detail and come up
> with am estimation of that standard deviation?
>
>
> Yours, Jobst
>
>
> Jobst Heitzig schrieb:
>> Another small remark:
>>
>> With N voters total and B benchmark voters, the size D of the deciding
>> group should probably be O(sqrt(N-B)).
>>
>> This is because the amount transferred to an individual deciding
>> voter's account is roughly proportional to D times a typical
>> individual rating difference, hence the total amount transferred to
>> the deciding group is proportional to D² times a typical individual
>> rating difference. The same total amount is payed by the group of at
>> most N-B-D compensating voters. Each of them should not be required to
>> pay more than a constant multiple of a typical individual rating
>> difference, hence D²/(N-B-D) should be O(1).
>>
>> Jobst
>>
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list
>> info
>>
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
More information about the Election-Methods
mailing list