sample code for allocation-based voting with transferrable votes

[Kevin Baas]

sample code for allocation-based voting with transferrable votes.

below.  in java.

i ran one random election for testing/debugging.

surplus transfer is a little more subtle to get right, but ignore logic is much simpler, being at worst O(N) - just sort the raw counts, then add one at a time from least to greatest.  (because if the second lowest can't win, then neither can the lowest, etc.)  so, this is a worst-case polynomial time algorithm.

------------------

import java.util.*;

public class AllocationElection {

public static void main(String[] args) {

Vector<AllocationBallot> _ballots = new Vector<AllocationBallot>();

int candiates = 5;

int seats = 2;

_ballots.add(new AllocationBallot(10,new double[]{1,2,3,4,5}));

_ballots.add(new AllocationBallot(10,new double[]{6,2,3,4,0}));

_ballots.add(new AllocationBallot(10,new double[]{0,3,3,4,5}));

_ballots.add(new AllocationBallot(10,new double[]{0,7,4,4,0}));

int[] winners = getWinners( _ballots, candiates, seats);

System.out.print(" winners:");

for( int i = 0; i < winners.length; i++) {

System.out.print(""+winners[i]+", ");

}

System.out.println();

}

public static int[] getWinners(Vector<AllocationBallot> _ballots, int num_candidates, int seats) {

int[] winners = new int[seats];

Vector<AllocationBallot> ballots = new Vector<AllocationBallot>();

for( int i = 0; i < _ballots.size(); i++) {

ballots.add(_ballots.get(i).clone());

}

for( int i = 0 ; i < winners.length; i++) {

for( int j = 0; j < ballots.size(); j++) {

System.out.print("[");

for( int k = 0; k < ballots.get(j).allocs.length; k++) {

System.out.print(ballots.get(j).allocs[k]+", ");

}

System.out.println("]");

}

int[] ignore_order = getIgnoreOrder(ballots,num_candidates);

Vector<Integer> ignores = new Vector<Integer>();

Triplet<Integer,Double,Double>  winner = getWinner(ballots,ignores,num_candidates,seats-i);

int ignore = 0;

while( winner.a < 0 && ignore < ignore_order.length) {

ignores.add(ignore_order[ignore++]);

System.out.print(" ignoring: ");

for( int j = 0; j < ignores.size(); j++) {

System.out.print(""+ignores.get(j)+", ");

}

System.out.println();

winner = getWinner(ballots,ignores,num_candidates,seats-i);

}

System.out.println("   elected: "+winner.a+" "+winner.b+" "+winner.c);

System.out.println();

winners[i] = winner.a;

if( winner.a > -1) {

for( int j = 0; j < ballots.size(); j++) {

ballots.get(j).elected(winner.a, winner.b, winner.c, ignores);  //is this right? (the surplus vote count / reallocation)

}

}

}

return winners;

}

public static Triplet<Integer,Double,Double> getWinner(Vector<AllocationBallot> ballots, Vector<Integer> ignores, int num_candidates, int seats_left) {

double[] ws = getTotals( ballots, ignores, num_candidates);

System.out.print(" totals: ");

for( int j = 0; j < ws.length; j++) {

System.out.print(""+ws[j]+", ");

}

System.out.println();

double quota = 0;

for( int j = 0; j < ws.length; j++) {

quota += ws[j];

}

quota /= (double)seats_left;

System.out.println(" quota: "+quota);

int max_index = 0;

double max = ws[0];

for( int j = 0; j < ws.length; j++) {

if( ws[j] > max) {

max = ws[j];

max_index = j;

}

}

if( max >= quota) {

return new Triplet<Integer,Double,Double>(max_index,max,quota);

} else {

return new Triplet<Integer,Double,Double>(-1,0.0,0.0);

}

}

public static double[] getTotals(Vector<AllocationBallot> ballots, Vector<Integer> ignores, int num_candidates) {

double[] sum = new double[num_candidates];

for( int i = 0; i < ballots.size(); i++) {

double[] dd = ballots.get(i).getWeightsIgnored(ignores);

for( int j = 0; j < dd.length; j++) {

sum[j] += dd[j];

}

}

return sum;

}

public static int[] getIgnoreOrder(Vector<AllocationBallot> ballots, int num_candidates) {

double[] tots = getTotals(ballots,new Vector<Integer>(),num_candidates);

Vector<Pair<Double,Integer>> s = new Vector<Pair<Double,Integer>>();

for( int i = 0; i < tots.length; i++) {

s.add(new Pair<Double,Integer>(tots[i],i));

}

Collections.sort(s);

int[] order = new int[num_candidates];

for( int i = 0; i < s.size(); i++) {

order[i] = s.get(i).b;

}

return order;

}

}

import java.util.Vector;

public class AllocationBallot {

public static double total_avail_points;

public double weight = 0;

public double[] allocs = new double[]{};

public double total_points_used = 0;

public AllocationBallot(double w, double[] a) {

weight = w;

allocs = a.clone();

calcTotalPointsUsed();

}

public void calcTotalPointsUsed() {

total_points_used = 0;

for( int i = 0; i < allocs.length; i++) {

total_points_used += allocs[i];

}

}

public AllocationBallot clone() {

return new AllocationBallot(weight,allocs);

}

public double[] getWeightsIgnored(Vector<Integer> ignores) {

double[] w = allocs.clone();

double redistrib = 0;

for( int i = 0; i < ignores.size(); i++) {

int ig = ignores.get(i);

redistrib += w[ig];

w[ig] = 0;

}

double sum = 0;

for( int i = 0; i < w.length; i++) {

sum += w[i];

}

double mult = (sum+redistrib)/sum;

for( int i = 0; i < w.length; i++) {

w[i] *= mult*weight;

}

return w;

}

public void elected(int e, double used, double quota, Vector<Integer> ignores) {

double[] weights_ignored = getWeightsIgnored(ignores);

double votes_used = weights_ignored[e]*quota/used;

calcTotalPointsUsed();

if( votes_used == 0 || total_points_used == 0) {

return;

}

double target_points = total_points_used - votes_used/weight;

if( target_points < 0) {

target_points = 0;

}

allocs[e] = 0;

calcTotalPointsUsed();

double mult = target_points/total_points_used;

for( int i = 0; i < allocs.length; i++) {

allocs[i] *= mult;

}

calcTotalPointsUsed();

}

}

public class Triplet<A extends Comparable<A>,B,C> implements Comparable<Triplet<A,B,C>> {

A a;

B b;

C c;

public Triplet(A a, B b, C c) {

this.a = a;

this.b = b;

this.c = c;

}

@Override

public int compareTo(Triplet<A, B, C> o) {

return a.compareTo(o.a);

}

}

[Kevin Baas]

...opps, divide by zero bug in getWeightsIgnored.getWeightsIgnored.  fix:

public double[] getWeightsIgnored(Vector<Integer> ignores) {

double[] w = allocs.clone();

double redistrib = 0;

for( int i = 0; i < ignores.size(); i++) {

int ig = ignores.get(i);

redistrib += w[ig];

w[ig] = 0;

}

double sum = 0;

for( int i = 0; i < w.length; i++) {

sum += w[i];

}

//fix divide by 0 bug

if( sum == 0) {

return w;

}

double mult = (sum+redistrib)/sum;

for( int i = 0; i < w.length; i++) {

w[i] *= mult*weight;

}

return w;

}

[Kevin Baas]

...and i got the ignores wrong, you have to recalc the ignores after each one you add.  and i forgot sorting already makes it nlogn.  so it's something like n^2logn.  whatever, still easily polynominal time.

[Kevin Baas]

source code & compiled executable for allocation vote system counting,  now available here:  http://autoredistrict.org/allocation_counter.zip

On Friday, May 13, 2016 at 2:48:23 PM UTC-5, Kevin Baas wrote:

[Brian Olson]

A little like my "Instant Runoff Normalized Ratings Proportional" method.

I still think the single-winner base method is pretty awesome. https://bolson.org/voting/IRNR_explaination.pdf

The Proportional method got messy figuring out how to determine voter satisfaction and distribute voting power. And I never settled on a satisfying measure of how good a PR result is for some simulated population. As many people as possible should get at least one representative to call their own, right? But if one person gets 8 people they like elected that's good but with rapidly diminishing returns compared to getting 7 other people electing someone they like. I never found a simple measure of means and medians and standard deviations that codified the desired qualities of a PR outcome. Single winner is a lot easier.

https://bitbucket.org/bodhisnarkva/voteutil/src/185ebbd922685d9fffe221df4a0ded6d6bdaea83/java/org/bolson/vote/IRNR.java

https://bitbucket.org/bodhisnarkva/voteutil/src/185ebbd922685d9fffe221df4a0ded6d6bdaea83/java/org/bolson/vote/IRNRP.java

[Toby Pereira]

I just had a look at that. What do you mean by "normalized to have the same magnitude"? In your example, one of the ballots has a max of 0.62 and a min of -0.62, for another it's 0.66 and -0.66, for two others it's 0.59 and -0.59 and for the other it's 0.44 and -0.21.

[Brian Olson]

Equal magnitude could either be "the sum of absolute values" of the vote parts adds up to 1.0; or "the sum of the squares" of the vote parts adds up to 1.0. I go back and forth about which is more fair to voters.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Toby Pereira]

I can't really say I like either of them. Surely this system would respond horribly to clones for one thing. If you've only got a certain amount of "magnitude" then surely it's a matter of picking the two candidates leading the polls and maximising the distance between them, so it would be very much plurality/First Past the Post strategy. If it's absolute magnitude, it probably doesn't matter as much how you do it. Give one positive and one negative and it will be normalised to make a difference of 1 (i.e. 0.5, -0.5; 0.9, -0.1 etc.) But if it's the sum of squares, I think you'd have to give them equal amounts positive and negative to maximise the difference of root 2 (with them ending up on about 0.7, -0.7).

I think Kevin Baas also suggested something similar the other day.

[Brian Olson]

If it comes down to the two front-runners in the polls, your vote will be re-normalized to maximize how you voted on them. If you like them both, that might come out (0.4 0.6), but you like them both, you're getting one, you're fine. If you like one and hate the other, it might be (-0.5 0.5), and that's a properly maximized vote!

I don't think clones are a problem. Given a large number of voters, someone will have slightly less, get runoff-removed earlier, and then your vote of (0.5 0.5) for your two favorite clones will become a vote of (1.0 nil) for the one that survives and your vote is properly cast for someone that you like.

[Kevin Baas]

Actually if you transfer votes right it responds perfectly to clones.  That is, it's IIC.

Basically it comes down to this:

* anyone who makes quota without vote transfers in the presence of clones would have also made quota in their absence.

* after removing all the ones who make quota without vote transfer, you're down to the clones.

* you transfer votes from the lesser clone to the greater one until one makes quota.  so it's as if there was no clone.

Feel free to test some scenarios to try to "break" it, if you don't believe me:  http://autoredistrict.org/allocation_counter.zip