Ideas for reducing computational burden in very large elections
Warren has been working on a PR election method for Canada based on range
ballots that do not make use of party affiliations.
He has pointed out that by using an idea of Toby Pereira it is possible to
convert the voted range ballots into a collection of weighted approval
ballots that give the same average scores to the respective candidates as
the original range ballots. Since, as he further pointed out, there are
only 2^k (or 2**k for those who remember Fortran) possible approval
ballots,when there are k candidates, this may well reduce the number of
ballots that you have to handle, if you are willing to make the
transformation.
I'll get around to describing Toby's transformation in context below.
But now I want to make a couple of other suggestions:
(1) Before doing the Toby transformation, for each candidate X let b_X be
the average of all of the range ballots that rate X ahead of all other
candidates. In case a ballot rates candidates X, Y, and Z top equal,
average that ballot into b_X, b_Y, and b_Z with weights that are the
respective random ballot probabilities for deciding among X, Y, and Z.
Think of each of these averages as a weighted ballot, and apply the Toby
Transformation to each of them. That will be at most k transforms, each of
which yields at most k approval ballots (with their weights). So even if
here is no duplication, the total number of Approval ballots will be at
most k^2 .
Can we do better than this? Yes if you are willing to accept another
transformation between the amalgamation step and the Toby Transforms.
Which brings us to the second idea ...
(2) We will make use of the idea of "sincere approval strategy." This
strategy takes a range ballot and briefly considers (but rejects in favor
of a better idea that becomes apparent only at that stage) the idea of
using a random number generator to assist in converting a range ballot B
into an approval ballot.
In this thought experiment suppose that you are trying to decide whether or
not to approve candidate i . If B(i) is zero or 100%, the decision if
easy, but if the score r is strictly between zero and one, we ask for a
random number between zero and one. If the number is less than the score
r, then we approve candidate i, otherwise not. This random idea has the
merit that, if many voters use it, then statistically speaking, the average
of the converted ballots will be very close to their prior average (before
they were converted). A disadvantage is that the variance of the averages
is greater.
But I remind you we are not going to implement this idea. We are only
going to use one statistic from it: the expected number of candidates that
will be approved when a ballot is subjected to this procedure. That
expectation is the sum of the range scores of the ballot in question.
At this point a light dawns; instead of deciding approval on the basis of
the random numbers experiments, just take the expected number of approvals,
and approve that many candidates, starting at the candidates highly rated
by the ballot, and working down.
If the expected number E is not a whole number, then there will be a
remainder candidate with a range value strictly between 0 and 1. So we
have falied at converting our ballot to an approval ballot. But it now has
at most two levels. When we apply the Toby transformation at this stage,
we get only two approval ballots, one of which approves a subset of the
other.
If we do this process to the ballots {b_X| X is a candidate}, then we have
at most 2k approval ballots.
I 'll finish this next time.
A method I proposed a few years ago requires order (C) passes through the vote data for C candidates and achieves Proportional Representation.
First, the single winner simple version
Instant Runoff Normalized Ratings (IRNR)
- Voters cast ratings ballots (e.g. 0..10).
- Each vote is normalized to a magnitude-1 vector (divide by the square root of sum of squares of ratings for that vote).
- Normalized votes are summed.
- The choice with the lowest sum is disabled.
- Votes are re-normalized without disabled choices present so that each voter still has a magnitude-1 vote.
- Repeat steps 3,4,5; summing, disabling , and renormalizing until are two choices left and one gets more vote and is the winner.
Instant Runoff Normalized Ratings, Proportional-mode (IRNRp)
- Voters cast ratings ballots (e.g. 0..10).
- Each vote is normalized to a magnitude-1 vector (divide by the square root of sum of squares of ratings for that vote).
- Normalized votes are summed.
3.1. Choices with a sum over the ‘quota’ (total vote / (seats to elect + 1)) get a pre-scalar so that their sum would come out the minimum measurable amount above the quota.
3.2. Pre-scale then normalize then sum all the votes.
3.3. Repeat 3.1 and 3.2 until the system ‘settles’ (squishing vote out of one choice can cause another to overflow), or some limit (10, 100, etc) of iterations to avoid infinite loops
3.4. If (seats to elect) choices have sums over the quota, those are elected, exit - The choice with the lowest sum is disabled.
- Votes are re-normalized without disabled choices present so that each voter still has a magnitude-1 vote.
- Repeat steps 3,4,5; summing, disabling, and renormalizing until are (seats to elect) choices left, those are the winners.
I have coded this up in C and Java and Go
https://bitbucket.org/bodhisnarkva/voteutil/src
The bulk of the memory footprint is just holding all the votes in memory. Doing simple numeric computations on a big block of numbers is what computers are really really good at. I could probably even GPU accelerate this algorithm. But it’s not necessary because for any size of data I’ve thrown at it, it is done in a few seconds at most.
If we were specially lucky and got 300,000,000 people to vote on a field of 10 choices, and store each rating as a 8 bit unsigned integer 0..255, that’s only 3 gigabytes of data. Pretty soon we’ll have phones that can run that. But I think being able to run a national election on a $1000 computer is good enough.
I’ve recently been writing up a new implementation of STV (in Go, to add to my betterpolls.com site) and STV is a complexity nightmare. I’m running into a huge number of fiddly corner cases to deal with to get the accounting right. STV is kinda simple to explain in principle, but the devil is in the details. IRNR winds up being much simpler in implementation.
On Dec 14, 2015, at 10:29 PM, Forest Simmons fsimmons@pcc.edu wrote:
Warren has been working on a PR election method for Canada based on range ballots that do not make use of party affiliations.
He has pointed out that by using an idea of Toby Pereira it is possible to convert the voted range ballots into a collection of weighted approval ballots that give the same average scores to the respective candidates as the original range ballots. Since, as he further pointed out, there are only 2^k (or 2**k for those who remember Fortran) possible approval ballots,when there are k candidates, this may well reduce the number of ballots that you have to handle, if you are willing to make the transformation.
I'll get around to describing Toby's transformation in context below.
But now I want to make a couple of other suggestions:
(1) Before doing the Toby transformation, for each candidate X let b_X be the average of all of the range ballots that rate X ahead of all other candidates. In case a ballot rates candidates X, Y, and Z top equal, average that ballot into b_X, b_Y, and b_Z with weights that are the respective random ballot probabilities for deciding among X, Y, and Z.
Think of each of these averages as a weighted ballot, and apply the Toby Transformation to each of them. That will be at most k transforms, each of which yields at most k approval ballots (with their weights). So even if here is no duplication, the total number of Approval ballots will be at most k^2 .
Can we do better than this? Yes if you are willing to accept another transformation between the amalgamation step and the Toby Transforms. Which brings us to the second idea ...
(2) We will make use of the idea of "sincere approval strategy." This strategy takes a range ballot and briefly considers (but rejects in favor of a better idea that becomes apparent only at that stage) the idea of using a random number generator to assist in converting a range ballot B into an approval ballot.
In this thought experiment suppose that you are trying to decide whether or not to approve candidate i . If B(i) is zero or 100%, the decision if easy, but if the score r is strictly between zero and one, we ask for a random number between zero and one. If the number is less than the score r, then we approve candidate i, otherwise not. This random idea has the merit that, if many voters use it, then statistically speaking, the average of the converted ballots will be very close to their prior average (before they were converted). A disadvantage is that the variance of the averages is greater.
But I remind you we are not going to implement this idea. We are only going to use one statistic from it: the expected number of candidates that will be approved when a ballot is subjected to this procedure. That expectation is the sum of the range scores of the ballot in question.
At this point a light dawns; instead of deciding approval on the basis of the random numbers experiments, just take the expected number of approvals, and approve that many candidates, starting at the candidates highly rated by the ballot, and working down.
If the expected number E is not a whole number, then there will be a remainder candidate with a range value strictly between 0 and 1. So we have falied at converting our ballot to an approval ballot. But it now has at most two levels. When we apply the Toby transformation at this stage, we get only two approval ballots, one of which approves a subset of the other.
If we do this process to the ballots {b_X| X is a candidate}, then we have at most 2k approval ballots.
I 'll finish this next time.
Election-Methods mailing list - see http://electorama.com/em for list info
Hey Brian,
I like it a lot.
What if you used the L_1 norm instead of the L_2 norm to normalize the
ballot vectors? In other words, divide by the sum of the absolute values
of the ratings instead of the root sum squares.
It seems to me that this might work even better since then the contribution
to the sum of ballots is the same for each voter, and therefore inherently
proportional even with one pass if the voters coordinate a little. The
other passes can then be thought of as automatic coordination adjustments.
On Thu, Dec 17, 2015 at 9:29 AM, Brian Olson bql@bolson.org wrote:
A method I proposed a few years ago requires order (C) passes through the
vote data for C candidates and achieves Proportional Representation.
First, the single winner simple version
Instant Runoff Normalized Ratings (IRNR)
- Voters cast ratings ballots (e.g. 0..10).
- Each vote is normalized to a magnitude-1 vector (divide by the square
root of sum of squares of ratings for that vote). - Normalized votes are summed.
- The choice with the lowest sum is disabled.
- Votes are re-normalized without disabled choices present so that each
voter still has a magnitude-1 vote. - Repeat steps 3,4,5; summing, disabling , and renormalizing until are
two choices left and one gets more vote and is the winner.
Instant Runoff Normalized Ratings, Proportional-mode (IRNRp)
- Voters cast ratings ballots (e.g. 0..10).
- Each vote is normalized to a magnitude-1 vector (divide by the square
root of sum of squares of ratings for that vote). - Normalized votes are summed.
3.1. Choices with a sum over the ‘quota’ (total vote / (seats to elect +
1)) get a pre-scalar so that their sum would come out the minimum
measurable amount above the quota.
3.2. Pre-scale then normalize then sum all the votes.
3.3. Repeat 3.1 and 3.2 until the system ‘settles’ (squishing vote out of
one choice can cause another to overflow), or some limit (10, 100, etc) of
iterations to avoid infinite loops
3.4. If (seats to elect) choices have sums over the quota, those are
elected, exit - The choice with the lowest sum is disabled.
- Votes are re-normalized without disabled choices present so that each
voter still has a magnitude-1 vote. - Repeat steps 3,4,5; summing, disabling, and renormalizing until are
(seats to elect) choices left, those are the winners.
I have coded this up in C and Java and Go
https://bitbucket.org/bodhisnarkva/voteutil/src
The bulk of the memory footprint is just holding all the votes in memory.
Doing simple numeric computations on a big block of numbers is what
computers are really really good at. I could probably even GPU accelerate
this algorithm. But it’s not necessary because for any size of data I’ve
thrown at it, it is done in a few seconds at most.
If we were specially lucky and got 300,000,000 people to vote on a field
of 10 choices, and store each rating as a 8 bit unsigned integer 0..255,
that’s only 3 gigabytes of data. Pretty soon we’ll have phones that can run
that. But I think being able to run a national election on a $1000 computer
is good enough.
I’ve recently been writing up a new implementation of STV (in Go, to add
to my betterpolls.com site) and STV is a complexity nightmare. I’m
running into a huge number of fiddly corner cases to deal with to get the
accounting right. STV is kinda simple to explain in principle, but the
devil is in the details. IRNR winds up being much simpler in implementation.
On Dec 14, 2015, at 10:29 PM, Forest Simmons fsimmons@pcc.edu wrote:
Warren has been working on a PR election method for Canada based on
range ballots that do not make use of party affiliations.
He has pointed out that by using an idea of Toby Pereira it is possible
to convert the voted range ballots into a collection of weighted approval
ballots that give the same average scores to the respective candidates as
the original range ballots. Since, as he further pointed out, there are
only 2^k (or 2**k for those who remember Fortran) possible approval
ballots,when there are k candidates, this may well reduce the number of
ballots that you have to handle, if you are willing to make the
transformation.
I'll get around to describing Toby's transformation in context below.
But now I want to make a couple of other suggestions:
(1) Before doing the Toby transformation, for each candidate X let b_X
be the average of all of the range ballots that rate X ahead of all other
candidates. In case a ballot rates candidates X, Y, and Z top equal,
average that ballot into b_X, b_Y, and b_Z with weights that are the
respective random ballot probabilities for deciding among X, Y, and Z.
Think of each of these averages as a weighted ballot, and apply the Toby
Transformation to each of them. That will be at most k transforms, each of
which yields at most k approval ballots (with their weights). So even if
here is no duplication, the total number of Approval ballots will be at
most k^2 .
Can we do better than this? Yes if you are willing to accept another
transformation between the amalgamation step and the Toby Transforms.
Which brings us to the second idea ...
(2) We will make use of the idea of "sincere approval strategy." This
strategy takes a range ballot and briefly considers (but rejects in favor
of a better idea that becomes apparent only at that stage) the idea of
using a random number generator to assist in converting a range ballot B
into an approval ballot.
In this thought experiment suppose that you are trying to decide whether
or not to approve candidate i . If B(i) is zero or 100%, the decision if
easy, but if the score r is strictly between zero and one, we ask for a
random number between zero and one. If the number is less than the score
r, then we approve candidate i, otherwise not. This random idea has the
merit that, if many voters use it, then statistically speaking, the average
of the converted ballots will be very close to their prior average (before
they were converted). A disadvantage is that the variance of the averages
is greater.
But I remind you we are not going to implement this idea. We are only
going to use one statistic from it: the expected number of candidates that
will be approved when a ballot is subjected to this procedure. That
expectation is the sum of the range scores of the ballot in question.
At this point a light dawns; instead of deciding approval on the basis
of the random numbers experiments, just take the expected number of
approvals, and approve that many candidates, starting at the candidates
highly rated by the ballot, and working down.
If the expected number E is not a whole number, then there will be a
remainder candidate with a range value strictly between 0 and 1. So we
have falied at converting our ballot to an approval ballot. But it now has
at most two levels. When we apply the Toby transformation at this stage,
we get only two approval ballots, one of which approves a subset of the
other.
If we do this process to the ballots {b_X| X is a candidate}, then we
have at most 2k approval ballots.
info
This might come down to how we define the “one vote” part of one-person-one-vote.
Should the sum of the vote be 1 or should the magnitude of the vote vector be 1?
Which ‘distortion’ best preserves voter intent?
I’m not 100% sure which form of normalization is better.
It might just be mathematical intuition that makes me prefer ‘magnitude’. I feel like I had a better reason for this a while ago and forgot the reason I chose vector magnitude L2 normalization.
If I haven’t already done it and forgotten where the results are, I should run my random election simulator on IRNR normalized by both modes and see which one produces better outcomes.
On Dec 17, 2015, at 4:37 PM, Forest Simmons fsimmons@pcc.edu wrote:
What if you used the L_1 norm instead of the L_2 norm to normalize the ballot vectors? In other words, divide by the sum of the absolute values of the ratings instead of the root sum squares.
Well, one thing that comes to mind is that single winner range voting with
L2 normalization tends to minimize the incentive for strategic voting, in
particular under zero information the optimum strategy for maximizing
utility is to submit a ballot that is just your L2 normalized utility
vector (with the average utility subtracted from each component).
Geometrically this follows from the fact that the L2 unit ball doesn't have
any bulges. Note that the L_k unit ball for k<2 bulges towards the
coordinate axes, which skews optimal strategy towards "plumping" or "bullet
voting." When k>2 the bulges are in the directions where all of the
coordinates have the same absolute values, which tends to give ballots
whose components all have nearly the same absolute value, but the
"approved" candidates get positive ratings and the disapproved negative..
Of course, we know that with Yes/No ballots it makes little difference
whether "no" is represented by zero or by negative one.
The the three cases are typified by L_1 (strategically equivalent to
plurality), L_2, and L_infinity (approval in disguise).
Thinking about these things has led me to a maximization method for
Proportional Representation that uses L_2 normalization, and would tend to
give a high quality score Q to a subset of the candidates chosen by Brian's
PR method that we have been talking about, namely Instant Runoff Normalized
Ratings, Proportional-mode (IRNRp).
Suppose that we are to elect a subset of 17 candidates from a total of K
candidates. Ballots are range style vectors that give non-negative ratings
to the candidates. Let B be the set of these ballot vectors. Let S be the
set of all candidate vectors (i.e. with K components) such that exactly 17
of the components are ones, and the rest are zeroes.
The winning subset is the one given by the member s of S that maximizes
Q = Sum over b in B of (dot(b,s)^2/dot(b,b)) .
Each of the summands in the Sum to be maximized is the square of the scalar
projection of the vector s onto the vector b. The closer s comes to the
direction of b, the larger this value.
At this point I am not sure which power of the scalar projections should be
used. The second power is the simplest, since that allows us to use
dot(b,b) in the denominator without the square root.
Best Wishes,
Forest
On Thu, Dec 17, 2015 at 4:03 PM, Brian Olson bql@bolson.org wrote:
This might come down to how we define the “one vote” part of
one-person-one-vote.
Should the sum of the vote be 1 or should the magnitude of the vote vector
be 1?
Which ‘distortion’ best preserves voter intent?
I’m not 100% sure which form of normalization is better.
It might just be mathematical intuition that makes me prefer ‘magnitude’.
I feel like I had a better reason for this a while ago and forgot the
reason I chose vector magnitude L2 normalization.
If I haven’t already done it and forgotten where the results are, I should
run my random election simulator on IRNR normalized by both modes and see
which one produces better outcomes.
On Dec 17, 2015, at 4:37 PM, Forest Simmons fsimmons@pcc.edu wrote:
What if you used the L_1 norm instead of the L_2 norm to normalize the
ballot vectors? In other words, divide by the sum of the absolute values
of the ratings instead of the root sum squares.