[Election-Methods] a strategy-free range voting variant?

[Jobst Heitzig]

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
>