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

[Jobst Heitzig]

Dear folks,

some time ago we discussed shortly whether it was possible to design a
strategy-free ratings-based method, that is, a method where voters give
ratings and never have any incentive to misrepresent their "true" ratings.

If I remember right, the methods that were discussed then were only of
academic use since they were far from being efficient and often elected
bad options unwanted by most of the voters.

Several days ago, I had a new idea how range voting could be modified to
get a method both strategy-free and efficient. A bit of research 
revealed that much of it resembles the ideas in the paper 
http://mpra.ub.uni-muenchen.de/627/, but not all of it. I will first 
describe the basic idea and then the method.

Disclaimer: All of what follows is suitable only for the case where one
can assume that voters can sincerely attribute some numerical "utility"
to all options, which is an assumption I personally don't believe to
hold generally :-)  Anyway, here's the...


Basic Idea
-----------

In order to understand the basic idea, consider a decision problem with
two options, A and B, and two voters, V1 and V2, who are able to
attribute some monetary values
   U1(A)>U1(B),
   U2(B)>U2(A)
to these options. (We will not need to assume monetary values later on,
but the idea is easier to grasp this way)

Now consider the following method: Both voters fill in a ratings ballot
for A and B, giving ratings
   R1(A)>R1(B),
   R2(B)>R2(A).
Then a coin is tossed to decide which of the two voters is the "seller"
and which is the "buyer". Let's assume throughout the following that V1
turns out to be the seller. Now the winner is determined like this: If
   R2(B)-R2(A) <= R1(A)-R1(B)
then A wins. Otherwise, that is, if
   R2(B)-R2(A) > R1(A)-R1(B),
then V2 "buys" the decision from V1: B wins but V2 pays an amount of
   ( R2(B)-R2(A) + R1(A)-R1(B) ) / 2
to V1.

If this deal happens, V2 profits from it if and only if this "price" for
getting B instead of A,
   ( R2(B)-R2(A) + R1(A)-R1(B) ) / 2,
is at most U2(B)-U2(A). Fortunately, she can ensure that the deal
happens exactly when this is fulfilled: she only needs to specify her
sincere ratings by putting R2(A)=U2(A) and R2(B)=U2(B). If she does so,
the deal happens if and only if
   U2(B)-U2(A)>R1(A)-R1(B),
which is equivalent to
   ( U2(B)-U2(A) + R1(A)-R1(B) ) / 2 < U2(B)-U2(A),
so the deal happens if and only if it is profitable for V2. Moreover, V2
can ensure this independently of V1's behaviour!

Analogously, V1 profits from the deal if the price is at least
U1(A)-U1(B), and she can also ensure that the deal happens exactly when
it is profitable for her: she specifies her sincere ratings by putting
R1(A)=U1(A) and R1(B)=U1(B), no matter what V2 does.

Of course, this is far from being a new idea so far, and it is not yet
the whole idea since it has an obvious problem: although it obviously
manages to elect the "better" option (the one with the larger total
monetary value), it encourages both the seller and the buyer to
misrepresent their ratings so that the gap between R2(B)-R2(A) and
R1(A)-R1(B) becomes as small as possible and hence their respective
profit as large as possible. In other words, this method is not at all
strategy-free.

However, there is a simple modification which makes it strategy-free!
The reason for the strategic incentives is that the ratings V1 (and
analogously V2) gives not only influence whether the deal happens but
also how much V1 profits from the deal when it happens. This is no
longer the case when we change the method so that V1's profit depends on
V2's ratings only and vice versa: If the deal happens, that is, when
   R2(B)-R2(A) > R1(A)-R1(B),
then
   B wins instead of A,
   V1 gets an amount of R2(B)-R2(A)
   but V2 only pays an amount of R1(A)-R1(B).
As before, both voters can ensure that the deal happens exactly when
they profit from it by voting sincerely. The difference is that now they
no longer have any incentive to narrow the gap between R2(B)-R2(A) and
R1(A)-R1(B) since a voter's profit is independent of her ratings!

There is just a minor problem with this: The balance of the money
transfers is positive, so where is this extra money supposed to come
from? Obviously, we cannot let V1 and V2 each pay half of the required
extra money since that would make the method identical to the original
method.


Solving the extra money problem
--------------------------------

A solution to this "extra money" problem becomes clear when we now
increase the number of voters and assume 3 instead of 2 voters. Consider
this method next: Each voter fills in a ratings ballot for the options
A,B. We draw at random one "default" option, say A, and one
"compensating" voter, say V3. The other voters (here V1,V2) are the
"deciding" voters. That option whose total ratings from the deciding
voters is maximal wins. If this is not the default option (so if it's
B), the following money transfers happen:
- Each deciding voter gets an amount equal to the total rating
difference between the winner and the default, minus her own rating
difference between the winner and the default.
- The compensating voter pays the needed excess money.
In our example, this means that if B wins then
- V1 gets R2(B)-R2(A) as above
- V2 gets R1(B)-R1(A) as above (that is, she pays R1(A)-R1(B))
- V3 pays R2(B)-R2(A)+R1(B)-R1(A).

To see that it is still optimal for everyone to specify sincere ratings,
one only needs to analyse in what situations a changing of a voter's
ratings makes a difference to her outcome. If she is amoung the deciding
voters, the case is the same as above. And if she is the compensating
voter, everything is completely independent from her ratings anyway.

By the way, note that this method is neutral, anonymous, and monotonic.

Now we are ready for the real thing...


The method RRVC
(Representative Range Voting with Compensations)
--------------------------------------------------

In order to get rid of the requirement to transfer real money, we need
to assume that not only one decision is made but that a fixed number of 
N voter need to make decisions with possibly varying numbers of options 
on a regular basis.

Every voter has a "voting account" whose balance at the beginning is set 
to a constant value, say 100.

A single decision is made like this:

1. Everybody fills in a ratings ballot in which she can use ratings 
between 0 and the current balance of her voting account. If the latter 
happens to be negative, she can use the rating 0 only. In addition, each 
  voter also marks her favourite option amoung those she assigned the 
largest rating to (if these are more than one).

2. Then, for each voter a die is tossed to decide to which group it 
belongs: In case of 1 or 2, the voter is a "benchmark" voter, in case of 
3 or 4 a "deciding" voter, and in case of 5 or 6 a "compensating" voter.

3. The ballots of all "deciding" voters decide the election via range 
voting, that is, that option wins whose total rating on these ballots is 
largest.

4. For each option, determine the probability P(Y) of being a randomly 
chosen "benchmark" voter's favourite. These probabilities build the 
"benchmark lottery".

5. Finally, the voting accounts are adjusted like this:

a) Each deciding voter's account is increased by an amount equal to the 
total rating difference between the winner and the benchmark lottery 
amoung the *other* deciding voters, minus some fixed fee F, say 
10*N^(1/2). (Note that the resulting adjustment may be positive or 
negative.)

b) The compensating voter's accounts are decreased by the same total 
amount as the deciding voter's accounts are increased, but in equal 
parts. (This may also be positive or negative)


With large N, both the benchmark and the deciding group are likely to be 
a representative sample, so the range decision of the deciding group 
will tend to equal the range decision amoung all voters, and the 
benchmark lottery will tend to equal the ordinary random ballot lottery 
with all voters. In particular, the method is quite efficient. 
Obviously, it is also neutral, monotonic, cloneproof, and anonymous 
(when the whole sequence of decisions is considered).

If the fee F is set so that the expected (in a reasonable model) 
adjustments of the individual accounts are all zero, then the method is 
also quite just in the sense that voters who would favour a random 
ballot lottery over the actual winner get a compensation with which they 
can increase their influence in subsequent decisions. Since the deciding 
and compensating groups are of roughly equal size, the variance of the 
individual account adjustments then also tends to be equal for the 
deciding and compensating voters.

The reason why we need compensating voters although no real money is 
used is that the "voting accounts" can be treated as virtual money of 
constant value only when their total amoung all voters remains constant. 
Otherwise, there would be "voting money inflation" or "deflation".

Finally, if I'm not mistaken, the method is still strategy-free for 
these reasons: i) A benchmark voter's "favourite" mark does neither 
influence the winner nor the voter's own account, so there is no 
incentive to misstate the favourite. ii) A deciding voter's ratings do 
influence the voter's account only by influencing the winner; the same 
arguments as above show that it is optimal for a deciding voter to 
sincerely state her true ratings. iii) A compensating voter's ratings to 
not affect anything. Since you don't know in which group you end up, 
your optimal vote is the true ratings!


I would be very interested in your opinion on this!
Jobst