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
