Re: [Election-Methods] a strategy-free range voting variant?
Range Voting selects the option with the highest average rating. Jobst has found a method that selects the option with the highest average rating by a random subset of the voters, while (totally?) discouraging the exageration of preferences that tends to happen in ordinary Range Voting. It seems to me that it should be even easier to find a similar strategy free method that selects the option with the highest median rating; when a vote is above or below the median it makes no difference on the value of the median how far above or below (at least in the case of an odd number of voters). The simplest idea is just to charge one voter grickle against the account of each voter that voted above the median of the winner, and redistribute these evenly to the accounts of the voters that voted below median. Of course, lots of technical details would have to be worked out, e.g. to take care of the case where several options have the same median, and the case where nobody voted above median. This version would end up being similar to some version of Bucklin with a tax for winning and a compensation for losing. More analogous to Jobst's idea would be a method where a random ballot benchmark lottery is used, but instead of using the expected ratings of that lottery on the various ballots, use the rating R for which it is equally likely that the lottery winner would be rated above or below R (on ballot i). If (on ballot i) the winner X is rated above R, then the probability P of the lottery winner being between R and X is the tax paid (by the compensating voters) on behalf of i into the accounts of the other voters. Instead of voters with higher accounts having greater range possibilities, they would have greater weight in determining medians. Also, the Random Ballot Lottery would take into account these weights. Essentially, if your virtual bank account is 30, it is like having thirty votes, whether in the Bucklin aspect, or in the RB Lottery aspect. I know that social scientists addicted to utility will prefer the mean approach over the median approach, but this makes more sense to me, because the money has a more direct relation to probability. What do you think? Can something along these lines be worked out? Forest Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] a strategy-free range voting variant?
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,
Re: [Election-Methods] a strategy-free range voting variant?
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
Re: [Election-Methods] a strategy-free range voting variant?
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.) This is the part I understand the least. Let's imagine the following votes from the deciding voters: 10 million: Nader: 10 Gore: 5 Bush: 0 41 million: Gore: 10 Nader: 5 Bush: 0 49 million: Bush: 10 Gore: 5 Nader: 0 Let's say that the lottery winner was Bush. The real winner is going to be Gore, with 705 million voting money units, while Bush has only 490 million. The total rating difference is 215 million. Do you want to modify each deciding voter's account with that big amount? You can try to diminish this modification by the fixed fee but I guess the modification will still be very high, because you are not able to precisely predict the votes not to mention who the lottery winner is going to be. And I guess if you try to eliminate this huge voting money transfer by some averaging operation, you will bite your other finger by ruining the strategy-freeness. Even if these worries are valid, this random partitioning of the electorate looks a witty idea, worth some other trials. I also like the idea of voting money, but with some reservations; if the value of the voting money is not bound exactly to some real value, then good-bye, strategy-freeness, I guess. Otherways, voting money can be used even with the classical Clarke-tax. Yes, Clarke-tax goes to one direction, but every voter on every day can get one voting money unit. If my voting money does not grows (except by votings), I will use the most amount of it when I'm afraid to die soon - why keep them if I can't use them?. So there seems to be some extra voting power on the part of the deadly ill. Peter Barath Tavaszig, most minden féláron! ADSL Internet már 1 745 Ft/hó -tól. Keresse ajánlatunkat a http://www.freestart.hu oldalon! Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] a strategy-free range voting variant?
Dear Warren,
you wrote:
But I do not fully understand it yet and I think you need to
develop+clarify+optimize it further... plus I'd like you to unconfuse me!
I'll try...
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.
--QUESTION:
if they make the gap small, then the buyer pays little to the seller.
Yes, that is better for the buyer.
But doesn't the seller have the opposite incentive?
It is not clear to me the incentive you say exists here, really does exist.
If it doesn't, then you do not need to fix this problem
because there is no problem. It'd help to clarify this point.
Isn't that the usual situation when bargaining? Given that the buyer
would be willing to pay more than the seller would minimally accept as a
price, the seller tries to maximize the price as long as he thinks the
buyer is willing to pay it, and the buyer tries to minimize her offer as
long as she thinks the seller is willing to accept it. So, both work to
minimize the gap between the demanded and the offered payment.
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
among the *other* deciding voters, minus some fixed fee F, say
10*N^(1/2). (Note that the resulting adjustment may be positive or
negative.)
QUESTION:
I'm confused about this whole benchmarking thing.
You said the benchmark voters were being benchmarked, but now you
say the deciding
voters are being benchmarked. ???
That might be a language problem for my part. What I mean is this: In my
thinking, democracy demands equal decision power for every voter. Random
Ballot accomplishes this in a way, but is not efficient. But the Random
Ballot lottery can still serve as a benchmark for other, more
efficient choices. In my suggested method, the benchmark voters are
needed only to estimate what the Random Ballot lottery amoung all voters
would be. The individual ratings for the actual winner of the election,
who is only determined by the deciding voters, is then compared to the
individual ratings for this benchmark (i.e. of the estimated Random
Ballot lottery) in order to the individual transfers of voting money.
The higher a deciding voter rated the benchmark and the lower she rated
the winner, the more voting money is transferred to her account (or,
rarely, the less is transferred *from* her account).
In mathematical terms: Let p(X) be the probability of X being the
highest rated option when we draw one of the benchmark voter's ballots
uniformly at random. (So the p's define our benchmark lottery)
Let r(i,X) be the rating deciding voter i specified for X. Put
r0(i) := sum { p(X)*r(X,i) : X }
(over all options X), i.e., the expected rating deciding voter i
specified for the lottery outcome. Then put
t(X) := sum { r(X,i) : i }
(over all deciding voters i) and
t0 := sum { p(X)*t(X) : X }.
Assume W is the range voting winner of the deciding ballots, i.e.,
t(W) t(X) for all X other than W
Now the voting account of deciding voter i is changed by this amount:
sum { r(W,j)-r0(j) : j different from i }
(over all deciding voters j different from i),
which is equal to
(t(W)-t0) - (r(X,i)-r0(i))
The higher you rated the winner (i.e., the higher your r(X,i)) and the
lower you rated the average favourite of the benchmark voters (i.e., the
lower your r0(i)), the less voting money you get.
What does total rating difference between the winner and the
benchmark lottery among the *other* deciding voters MEAN precisely???
This is not clear english... the winner's rating is a number but
the benchmark lottery is not a number. You need two numbers.
It means
sum { r(W,j)-r0(j) : j different from i }
(see above).
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)
--this seems to hurt poor voters. I.e. if there are rich voters who
vote +-100
and poor voters who vote +-1 then the poor voters will need to pay the same fee
in 5b as the rich voters. They may therefore have incentive to avoid
being in the electorate at all, in which case the electorate will
become biased (rich-dominated).
Yes, that might be a problem. So, being in the electorate (meaning
amoung the whole number of N voters) should not be something one can
choose. In other words, we put N to be the number of all eligible
voters, no matter whether they choose
Re: [Election-Methods] a strategy-free range voting variant?
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
Re: [Election-Methods] a strategy-free range voting variant?
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. --But it influences how much other people get paid or pay. If I hate Republicans, I might try to influence things to force Republicans to pay more and/or get paid less. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] a strategy-free range voting variant?
I haven't completely digested this yet, but it looks great. Very ingenious! Election-Methods mailing list - see http://electorama.com/em for list info
[Election-Methods] a strategy-free range voting variant?
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
