Kevin Baas idea about proportionality

[Warren D Smith]

Kevin Baas sent me an interesting suggestion about proportional representation,
which I here am re-posting to election science forum after slight editing
by me:

=========

KB:
Recently was talking with fairvote about the seat apportionment algorithm.
They use "Droop" quota. which is votes/(seats+1) instead of votes/seats.
Apparently this was designed to solve a problem with the results not being
proportional.

I looked into it a little more and the problem is that the votes are
traditionally counted with the wrong algorithm.

Baas suggests what he considers a better algorithm:
1. if no candidate has a quota of first preferences:
consider the candidate X with the fewest first choice votes, and:
temporarily ignore him; thus for any ballot which top-ranked X
its second choice becomes first choice, third becomes second, etc.
(if the first choice was already ignored on this ballot, ignore the
second choice in addition to the first, etc.)
2. repeat step 1 as necessary until some candidate has quota or there is
only one remaining
3. the candidate with the most votes now wins a seat (regardless of whether
quota is reached, or multiple candidates reached quota)
4a. if that is at or under the quota, just eliminate these ballots
4b. if that is above the quota, each ballot included in that quota should
now count as ((count - quota) / count) ballots.
5. eliminate the winning candidate from all ballots, all choice positions,
since they can only be elected once.
6. un-ignore all the choices you ignored - that was just temporary for that
round.
7. repeat from step 1 until all seats are filled

--
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking
"endorse" as 1st step)

[Ted Stern]

How is this different from Single Transferable Vote?

--
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.

[Brian Olson]

This will have a slightly different rebalancing effect than the STV that I’m used to thinking about.

If you leave the ‘elected’ choices _in_ then they can still be target of additional overvote. Someone’s current-first choice gets disqualified and their next choice is someone who is already winning. Now people who vote for that choice get their vote slightly less deweighted because there’s more overvote for the winning choice and they have more of their vote transferred to their next choices.

Hiding a winning choice from this process would change how vote-power is ultimately distributed.

[Brian Olson]

Simple-Ish made up numbers example:
2 seat election
15000 votes, quota is 5000 votes

9999 people vote their first choice vote for candidate A. A is clearly winning. All those people now get slightly less than half a vote applied to their second choice candidate. Maybe they all slate voted and choice B now has just less than a quota from the slate voters alone.

4000 votes for C.
1001 votes for D. D gets disqualified.

Some of those D voters had A as their second choice. A now has over 10000 votes and B now has a win based on the coalition of AB voters and DA voters.

If A had been removed from the process after winning, this transferal wouldn’t have happened.


> On Mar 30, 2016, at 10:12 PM, Kdog <happy...@gmail.com> wrote:
>
> I think you misunderstand - I applied to the forum by the way - when a candidate is elected _those votes are removed_. The difference is votes are _only_ removed when they're used to elect a candidate.
>
> Sent from my iPhone

[Kevin Baas]

hello all!  I just got approved to the forum.

how is this different from STV?

STV is a place where this can be used - in fact, the place that was being considered when I discovered the flaws in the current method.

The traditional way of counting STV votes is different from this.  For example, in the traditional way of counting, when the lowest ranking candidate is eliminated, it is eliminated permanently, instead of being restored for consideration in the next round.  

This is erroneous because votes should only be eliminated when those votes have been represented by an elected candidate.

This algorithm corrects that error.

[Kevin Baas]

i can't run brian's scenario because he didn't give exact vote counts for the second choices, but i ran 3 scenarios i found on the internets.

in all cases the proposed algorithm, which i am calling the "correct hare", apportions correctly,

whereas the incorrect counting methods fail due to the aforementioned error of eliminating votes that have not

bee apportioned to a candidate.

http://www.accuratedemocracy.com/e_shares.htm 

case 1:

incorrect droop: pass

incorrect hare: fail

correct hare: pass

https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas

scenario 1:

incorrect droop: pass

incorrect hare: fail

correct hare: pass

https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas

scenario 2:

incorrect droop: fail

incorrect hare: pass

correct hare: pass

i wrote a counter in java.  feel free to go ahead and test scenarios and compare with the incorrect counting algorithm.  included are the three above-mentioned scenarios:

import java.util.*;

public class Election {

public static void main(String[] args) {

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

int seats = 0;

int candidates = 0;

int scenario = 0;

switch(scenario) {

case 0:

//scenario 0 (from http://www.accuratedemocracy.com/e_shares.htm ) 

seats = 3;

candidates = 4;

addBallots(ballots,12,new int[]{0,1});

addBallots(ballots,7,new int[]{1,0});

addBallots(ballots,9,new int[]{2,3});

addBallots(ballots,8,new int[]{3,2});

//result matches droop quota = good

break;

case 1:

//scenario 1 (from https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas )

//0=a,1=b,2=c,3d,4j,5s

seats = 5;

candidates = 6;

addBallots(ballots,31,new int[]{0,2,1});

addBallots(ballots,30,new int[]{2,0,1});

addBallots(ballots,2,new int[]{1,0,2});

addBallots(ballots,20,new int[]{3,5,4});

addBallots(ballots,20,new int[]{5,3,4});

addBallots(ballots,17,new int[]{4,3,5});

//result: matches droop quota = good

break;

case 2:

//scenario 2 (from https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas )

//0=a,1=b,2=c,3d,4j,5s

seats = 3;

candidates = 5;

addBallots(ballots,50,new int[]{0,1,2});

addBallots(ballots,25,new int[]{3});

addBallots(ballots,24,new int[]{4});

//result: matches hare quota = good

break;

} 

System.out.println("ballots: "+ballots.size());

System.out.println("quota: "+((double)ballots.size())/(double)seats);

//compute winners

Vector<Integer> winners = getWinners(ballots,seats,candidates);

//show winners

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

System.out.print( i > 0 ? ", " : "");

System.out.print( ""+winners.get(i).intValue());

}

System.out.println();

}

static void addBallots(Vector<Ballot> ballots, int count, int[] choices) {

for( int i = 0; i < count; i++) {

Ballot b = new Ballot();

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

b.add(new Choice(choices[j]));

}

ballots.add(b);

}

}

static Vector<Integer> getWinners( Vector<Ballot> _ballots, int num_seats, int num_candidates) {

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

_ballots.get(i).weight = 1;

}

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

for( Ballot ballot : _ballots) {

ballots.add(ballot);

}

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

double quota = ((double)ballots.size()) / ((double)num_seats);

for( int i = 0; i < num_seats; i++) {

int winner = getNextWinner( ballots, quota, num_candidates);

if( winner < 0) {

break;

}

winners.add(winner);

}

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

_ballots.get(i).weight = 1;

_ballots.get(i).resetIgnores();

}

return winners;

}

static int getNextWinner( Vector<Ballot> ballots, double quota, int num_candidates) {

System.out.println("resetting ignores");

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

ballots.get(i).resetIgnores();

}

while( true) {

double[] counts = getCounts(ballots, num_candidates);

double min = -1;

int min_index = -1;

double max = -1;

int max_index = -1;

int candidates_left = 0;

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

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

if( counts[i] > 0) {

candidates_left++;

} else {

continue;

}

if( counts[i] > max || max_index < 0) {

max = counts[i];

max_index = i;

}

if( counts[i] < min || min_index < 0) {

min = counts[i];

min_index = i;

}

}

System.out.println();

if( max >= quota) {

elect(ballots,max_index,max,quota);

System.out.println("chose above quota "+max_index);

return max_index;

}

if( candidates_left == 0) {

return -1;

}

if( candidates_left == 1) {

elect(ballots,max_index,max,quota);

System.out.println("chose below quota "+max_index);

return max_index;

}

System.out.println("temporarily ignoring "+min_index);

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == min_index) {

ch.ignored = true;

}

}

}

}

static int elect(Vector<Ballot> ballots, int c, double votes, double quota) {

double new_weight = (votes-quota)/votes;

if( new_weight <= 0) {

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == c) {

b.weight = 0;

ballots.remove(i);

i--;

}

}

} else {

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == c) {

b.weight *= new_weight;

}

}

}

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

ballots.get(i).resetIgnores();

}

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

ballots.get(i).candidateElected(c);

}

return c;

}

static double[] getCounts( Vector<Ballot> ballots, int num_candidates) {

double[] counts = new double[num_candidates];

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

counts[ch.candidate] += b.weight;

}

return counts;

}

}

class Ballot extends Vector<Choice> {

double weight = 1;

Choice getFirst() {

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

Choice c = get(i);

if( !c.ignored && !c.elected) {

return c;

}

}

return null;

}

void resetIgnores() {

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

get(i).ignored = false;

}

}

void resetElecteds() {

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

get(i).ignored = false;

}

}

void candidateElected(int c) {

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

if( get(i).candidate == c) {

get(i).elected = true;

}

}

}

}

class Choice {

int candidate = -1;

boolean ignored = false;

boolean elected = false;

public Choice(int i) { candidate = i; }

}

[Warren D Smith]

Kevin Baas had experienced trouble trying to join CES forum,
but I guess he now has succeeded.

[Kevin Baas]

Minor adjustment to the algorithm:

ballots that run-out of non-ignored choices but have not been eliminated serve to _temporarily_ reduce the quota as if those ballots were never cast.  

this is mathematically equivalent to saying that they put "any" as their final choice. (since 1/num_candidates from the quota is equivalent to adding a 1/num_candidates fractional vote to each candidate)

this makes scenario 5 and 6 below produce identical results (except for ordering).  this way a party or candidate or voter isn't punished or rewarded for ranking more or fewer candidates - not ranking is now equivalent to indifference.

NEW CODE (including adjustment for exhausted choices):

---------

import java.util.*;

public class Election {

public static void main(String[] args) {

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

int seats = 0;

int candidates = 0;

int scenario = 6;

switch(scenario) {

case 0:

//scenario 0 (from http://www.accuratedemocracy.com/e_shares.htm ) 

seats = 3;

candidates = 4;

ballots.add(new Ballot(12,new int[]{0,1}));

ballots.add(new Ballot(7,new int[]{1,0}));

ballots.add(new Ballot(9,new int[]{2,3}));

ballots.add(new Ballot(8,new int[]{3,2}));

//result matches droop quota = goodf

break;

case 1:

//scenario 1 (from https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas )

//0=a,1=b,2=c,3d,4j,5s

seats = 5;

candidates = 6;

ballots.add(new Ballot(31,new int[]{0,2,1}));

ballots.add(new Ballot(30,new int[]{2,0,1}));

ballots.add(new Ballot(2,new int[]{1,0,2}));

ballots.add(new Ballot(20,new int[]{3,5,4}));

ballots.add(new Ballot(20,new int[]{5,3,4}));

ballots.add(new Ballot(17,new int[]{4,3,5}));

//result: matches droop quota = good

break;

case 2:

//scenario 2 (from https://en.wikipedia.org/wiki/Comparison_of_the_Hare_and_Droop_quotas )

//0=a,1=b,2=c,3d,4j,5s

seats = 3;

candidates = 5;

ballots.add(new Ballot(50,new int[]{0,1,2}));

ballots.add(new Ballot(25,new int[]{3}));

ballots.add(new Ballot(24,new int[]{4}));

//result: matches hare quota = good

break;

case 3:

//scenario  (from https://en.wikipedia.org/wiki/CPO-STV )

//0=a,1=b,2=c,3d,4j,5s

seats = 3;

candidates = 5;

ballots.add(new Ballot(25,new int[]{0}));

ballots.add(new Ballot(34,new int[]{2,1,3}));

ballots.add(new Ballot(7,new int[]{1,3}));

ballots.add(new Ballot(8,new int[]{3,1}));

ballots.add(new Ballot(5,new int[]{3,4}));

ballots.add(new Ballot(21,new int[]{4,3}));

//result: good

break;

case 4:

//scenario  (from https://en.wikipedia.org/wiki/CPO-STV )

//0=a,1=b,2=c,3d,4j,5s

seats = 2;

candidates = 4;

ballots.add(new Ballot(16,new int[]{0,1,2,3}));

ballots.add(new Ballot(24,new int[]{0,2,1,3})); 

ballots.add(new Ballot(17,new int[]{3,0,1,2}));

//result: good

break;

case 5:

//scenario  (from https://en.wikipedia.org/wiki/CPO-STV )

//0=a,1=b,2=c,3d,4j,5s

seats = 3;

candidates = 5;

ballots.add(new Ballot(12,new int[]{0,1}));

ballots.add(new Ballot(7,new int[]{1,0}));

ballots.add(new Ballot(9,new int[]{2,3}));

ballots.add(new Ballot(8,new int[]{3,2}));

ballots.add(new Ballot(3,new int[]{4,1}));

ballots.add(new Ballot(2,new int[]{4,3}));

break;

case 6:

//scenario  (from https://en.wikipedia.org/wiki/CPO-STV )

//0=a,1=b,2=c,3d,4j,5s

seats = 3;

candidates = 5;

ballots.add(new Ballot(12,new int[]{0,1}));

ballots.add(new Ballot(7,new int[]{1,0}));

ballots.add(new Ballot(9,new int[]{2}));

ballots.add(new Ballot(8,new int[]{3}));

ballots.add(new Ballot(3,new int[]{4,1}));

ballots.add(new Ballot(2,new int[]{4,3}));

break;

} 

//compute winners

Vector<Integer> winners = getWinners(ballots,seats,candidates);

//show winners

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

System.out.print( i > 0 ? ", " : "");

System.out.print( ""+winners.get(i).intValue());

}

System.out.println();

}

static Vector<Integer> getWinners( Vector<Ballot> ballots, int num_seats, int num_candidates) {

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

double num_votes_cast = 0;

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

num_votes_cast += ballots.get(i).weight;

}

for( int i = 0; i < num_seats; i++) {

int winner = getNextWinner( ballots, num_candidates, num_votes_cast, num_seats);

if( winner < 0) {

break;

}

winners.add(winner);

}

return winners;

}

static int getNextWinner( Vector<Ballot> ballots, int num_candidates, double num_votes_cast, int num_seats) {

double quota = num_votes_cast/(double)num_seats;

System.out.println("ballots: "+num_votes_cast);

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

System.out.println("resetting ignores");

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

ballots.get(i).resetIgnores();

}

while( true) {

double temp_quota = quota;

System.out.println("resetting temp quota to "+temp_quota);

double[] counts = new double[num_candidates];

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

//if a ballot is out of choices, adjust the temporary quota as if the ballot was never cast

temp_quota -= b.weight/num_candidates;

System.out.println(b.weight+" ballots out of choices, adjusting temp quota to "+temp_quota);

continue;

}

counts[ch.candidate] += b.weight;

}

double min = -1;

int min_index = -1;

double max = -1;

int max_index = -1;

int candidates_left = 0;

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

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

if( counts[i] > 0) {

candidates_left++;

} else {

continue;

}

if( counts[i] > max || max_index < 0) {

max = counts[i];

max_index = i;

}

if( counts[i] < min || min_index < 0) {

min = counts[i];

min_index = i;

}

}

System.out.println();

if( max >= temp_quota) {

System.out.println("chose above quota "+max_index);

elect(ballots,max_index,max,quota);

return max_index;

}

if( candidates_left == 0) {

return -1;

}

if( candidates_left == 1) {

System.out.println("chose below quota "+max_index);

elect(ballots,max_index,max,quota);

return max_index;

}

System.out.println("temporarily ignoring "+min_index);

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == min_index) {

ch.ignored = true;

}

}

}

}

static int elect(Vector<Ballot> ballots, int c, double votes, double quota) {

double new_weight = (votes-quota)/votes;

if( new_weight <= 0) {

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == c) {

b.weight = 0;

//ballots.remove(i--);

}

}

} else {

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

Ballot b = ballots.get(i);

Choice ch = b.getFirst();

if( ch == null) {

continue;

}

if( ch.candidate == c) {

b.weight *= new_weight;

}

}

}

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

ballots.get(i).resetIgnores();

}

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

ballots.get(i).candidateElected(c);

}

return c;

}

}

class Ballot {

Choice[] choices;

double weight = 1;

public Ballot(double count, int[] choices) {

super();

weight = count;

this.choices = new Choice[choices.length];

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

this.choices[j] = new Choice(choices[j]);

}

}

Choice getFirst() {

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

Choice c = choices[i];

if( !c.ignored && !c.elected) {

return c;

}

}

return null;

}

void resetIgnores() {

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

choices[i].ignored = false;

}

}

void resetElecteds() {

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

choices[i].elected = false;

}

}

void candidateElected(int c) {

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

if( choices[i].candidate == c) {

choices[i].elected = true;

[Kevin Baas]

I've improved the ignore logic a bit to better deal with some edge cases. (check "tier 2 ignore logic" to try):  http://autoredistrict.org/ranked_choice_counter.zip

a sample edge case, in this scenario: http://www.nytimes.com/2016/05/01/opinion/sunday/how-majority-rule-might-have-stopped-donald-trump.html?_r=0  it picks the condoret winner, whereas the old ignore logic wouldn't.

a bit hard to explain the logic so i'll just post the key code.

short of it is it keeps track of what it's tried ignoring, and only adds another if it'd be adding one that it's already tried.  otherwise it just replaces.  then once it adds another it forgots all the one's it's tried.

so for instance if it'd ignore a, then a,b; instead it ignores a, then b. in this scenario it then finds c as the next ignore and then since that's new it tries c alone instead of b,c.  still no candidate meets quota so it finds as it's next ignore, a, which it's already tried.  so this time it adds it, so it no tries ignoring c & a.  that gives B quota.

                        boolean tried = false;

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

                                if( tried_ignores.get(i).intValue() == min_index) {

                                        tried = true;

                                        break;

                                }

                        }

                        if( !tried) {

                                tried_ignores.add(min_index);

                                if( ignores.size() > 0) {

                                        ignores.remove(ignores.size()-1);

                                }

                        } else {

                                tried_ignores.clear();

                        }

                        ignores.add(min_index);

[Nevin Brackett-Rozinsky]

If I understand correctly, your approach with this modification is essentially “Find the smallest set of candidates which, if ignored, cause another candidate to achieve a quota. Then, among such sets of that size, choose the one which has the minimum number of votes according to the current count.”

I propose modifying it to simply, “Find the set of candidates with the minimum number of votes which, if ignored, cause another candidate to achieve a quota.”

In other words, change from breadth-first search (looking for the smallest set of candidates) to best-first search (looking for the set with the fewest votes).

This means that in each round, the lowest possible number of votes are ignored.

I have not analyzed the consequences of doing so, but it appeals to my intuitive sense of fairness: ignore as few votes as possible.

Nevin

[Kevin Baas]

it's a little more complicated than that.

sometimes you have to ignore more than one candidate to get a candidate to achieve quota.

so i'm trying to do that in the fairest way possible.

the traditional way is first ignore the candidate with the fewest votes, say candidate a, and then if that's not enough, add the next candidate who - after ignoring the first candidates votes - has the fewest votes.  say candidate b.

but this doesn't always produce the best results.  for example, if all second-choices for candidate b were a, then a might have met quota, but since it's already ignored, it can't.

so roughly speaking, my modification is, to firstly ignore the fewest _candidates_, and then secondly the fewest votes.

still not perfect, but an improvement over traditional.  it's a bit of a complicated problem something more like CPO-STV might be better - but not sure how you'd assign the surplus in CPO_STV, haven't exactly seen the algorithm for that.  anycase this makes it a little closer to CPO-STV, with a clear way of assigning the surplus (since you know which ballots were used).

[Nevin Brackett-Rozinsky]

I wrote:

> If I understand correctly, your approach with this modification is essentially “Find the smallest set of candidates which, if ignored, cause another candidate to achieve a quota. Then, among such sets of that size, choose the one which has the minimum number of votes according to the current count.”

You replied:

> it's a little more complicated than that.

> …

> my modification is, to firstly ignore the fewest _candidates_, and then secondly the fewest votes.

I think we might be talking past each other.

I repeat my suggestion:

> “Find the set of candidates with the minimum number of votes which, if ignored, cause another candidate to achieve a quota.”

Do you have a reason to believe that your approach of “ignore as few candidates as possible” should be more appropriate than the alternative of “ignore the set of candidate with as few votes as possible”?

Notably, your approach could end up ignoring one single candidate who has a *lot* of votes. I haven’t tried to construct any scenarios, but it is entirely imaginable that your strategy would ignore one of the top-3 vote-getting candidates, or possibly even the current leader, to elect someone else.

I contend that it is far more desirable to ignore candidates with as few votes as possible.

To put it in algorithmic terms, my proposal amounts to:

• Consider all possible sets of candidates.

• For each set of candidates, add up the total number of votes currently allocated to candidates in that set.

• Sort the sets-of-candidates in order from fewest total votes to most total votes.

• Test whether each set-of-candidates, if ignored, causes another candidate to achieve a quota.

• Select the first set-of-candidate which passes that test from the sorted list.

Does this make sense?

We are still selecting a set of candidates-to-ignore in order to achieve a quota, and among all such sets we choose the one which minimizes the number of votes that are ignored.

(If multiple sets-of-candidates are tied for fewest votes and would make different candidates obtain a quota, then some tie-break is required. Perhaps “lexicographical” sorting on the number of votes each candidate in the set has.)

On the other hand, it may turn out that my idea is flawed as well—maybe ignoring just the current leader turns out to be the vote-minimizing choice in some scenarios. There is certainly something intuitively appealing about the standard “instant-runoff” choice of candidates to ignore: as many as necessary from the bottom of the pack.

Nevin

[Kevin Baas]

>Do you have a reason to believe that your approach of “ignore as few candidates as possible” should be more appropriate than the alternative of “ignore the set of candidate with as few votes as possible”?

I think i like that approach better.  though i would revise it to "ignore the set of candidates which causes the fewest total choice demotions"  a choice demotion being going from first to second choice, or second to third, etc.

and then of all set combinations you start with the fewest choice demotions (regardless of # of candidates or # of ballots affected), and then go on up until a candidate reaches quota.

i think that might be better.

[Nevin Brackett-Rozinsky]

Just to clarify, if ignoring a certain set of candidates causes a ballot to go from its 1st choice to its 3rd choice, does that count as 2 “choice demotions”?

And if a ballot is currently being weighted with strength w, then having it go from its m’th choice to its n’th choice would count as w(n-m) “choice demotions”?

Nevin

[Kevin Baas]

yes and yes. 

except candidates that are already elected are skipped, and not counted as choice demotions.  e.g. of 1st choice isn't elected yet, 2nd choice is already elected, 3rd choice isn't, then going from 1st to 3rd count as one demotion.  essentially once a candidate is elected, the ballot is "compressed" as if that candidate never ran. that is, all ranks after where they were ranked are moved up a rank.

after all elected candidates are eliminated from the ballot and all ranks are adjusted accordingly, then...

going from choice m to choice n counts as n-m demotions.

a ballot with weighted strength x counts as x ballots.  N identical ballots with weighted strength x count as N*x ballots.  so having it go from its m’th choice to its n’th choice would count as w(n-m) “choice demotions”.

[Kevin Baas]

modified the ballot counter, and tested 13 scenarios.  The results are even better than before.  new counter (both source code and executable) available: http://autoredistrict.org/ranked_choice_counter.zip  (make sure "use new method" is checked.)

the changes are:

* dynamic quota is now: number of remaining ballots / number of remaining seats to be filled (ballots are eliminated when used to elect a candidate or they run out of choices)

* ignore logic is: ignore the set of candidates that produce the fewest "choice demotions" needed to make a candidate achieve quota.  (a choice demotion is e.g. going from 2nd choice to 3rd choice. not counting choices where the candidates is already elected.)  (due to the dynamic quota and the ignore logic, the winning candidate will always be at or above quota)

[Nevin Brackett-Rozinsky]

My one concern at this point is computational feasibility. It is not obvious to me that there is a good way to traverse the space of sets-of-candidates in order of “fewest choice demotions”.

If there are no more than 20 or so candidates then it can be brute-forced rapidly, but once you get up to 40 or 50 candidates (which could easily be exceeded in a competitive multi-winner race) then the exponential growth in the number of subsets to check may cause problems.

Conversely, the simple instant-runoff approach is computationally trivial.

Nevin

[Kevin Baas]

i'm not concerned about cpu time.

40 or 50 candidates is just not going to happen.

and like you said, even as many as 20 candidates can be brute-forced rapidly.

the advantage of getting a better answer is worth the few seconds in the worst case.

the best way to traverse "fewest choice demotions" is taking advantage of the fact that {a,b} is never greater than {a}+{b}. so, start with the smallest sets and work up.  would be fairly trivial to implement, but for any practical scenario, simply computing all combinations and sorting suffices.  

[Kevin Baas]

sorry was incomplete.  also {a,b}>={a} & {a,b}>={b}.  these rules can be used to efficiently iterate through all combinations from fewest to most demotions.

[Kevin Baas]

...and actually {a,b} <= 2*({a}+{b}).   but you get the picture -- you can iterate from small sets to larger sets while guaranteeing going in order from least demotions to most.

[Nevin Brackett-Rozinsky]

First, I claim that 50+ candidates is entirely plausible and expected in, for example, an 8–party proportional race for 24 seats.

Second, I am not clear on what you are trying to say, because you have not explained the notation you are using.

Let us define a function cd(Q) to be the (weighted) number of choice demotions caused by ignoring all candidates in subset Q.

Suppose there are 5 candidates in Q, and no voters rank any of them in 1st place, so cd(Q) = 0.

Let R contain one candidate, who is not in Q, and suppose exactly one voter ranks that candidate in 1st place, so cd(R) = 1.

Furthermore, suppose this same voter ranks the candidates in Q as choices 2–6.

Now cd(Q ⋃ R) = 6 by the definition of the cd() function.

Does this comport with your calculations?

I contend that for discrete sets A and B, the tightest “obvious” bound is:

cd(A ⋃ B) ≤ (|A| + |B|) × (cd(A) + cd(B)), where “|X|” is the cardinality of the set X.

Actually, if we define bd(X) to be the (weighted) number of ballots which have non-zero choice demotions when ignoring X, then:

cd(A ⋃ B) ≤ (|A| + |B|) × (bd(A) + bd(B))

In any case, even if the graph of subsets can be traversed rapidly via a reasonable heuristic estimate of cd(), that still presents a massive barrier to both conducting, and perhaps even more importantly *verifying* an election. It is not possible to determine whether the correct sets of candidates were ignored without retraversing the graph and recalculating the choice demotions for every single step in the process.

This tallying method is, for all practical purposes, relegated to use by microchips, and that introduces a whole new level of unverifiability to the process.

The idea is certainly interesting, however the much simpler “ignore successively more candidates from the bottom of the pack (redistributing their ballots at each step) until a quota is reached” instant-runoff approach is tremendously easier to work with, especially for hand-counted (and thus verifiable!) elections.

Nevin

[Kevin Baas]

{a} represents the number of demotions when ignoring candidate a.  {a,b} the number when ignoring both candidate a and b.

 2*({a}+{b}) >= {a,b} >= {a} 

40 or 50 is not plausible

microchip is how you need to count it for accuracy, reproducability, and transparency

“ignore successively more candidates from the bottom of the pack" does not determine the ordering among sets of equal cardinality.

[Kevin Baas]

this rule here:

 2*({a}+{b}) >= {a,b}

is more generalizable.  for instance,

3*({a}+{b}+{c}) >= {a,b,c}

i'm sure there are more ways it can be generalized.  but probably not important in this context.

i also wanted to know that, since either {a} or {b} is always at least as big as the average ({a}+{b})/2, the triple-inequality can be rewritten:

 2*({a}+{b}) >= {a,b} >= 1/2*({a}+{b})

that is, the number of demotions from a set of ignored candidates is always between twice and half the sum of any pair of disjoint subsets.

by the generalization above, you can extend this arbitrarily like so:

3*({a}+{b}+{c}) >= {a,b,c} >= 1/3*({a}+{b}+{c})

[Nevin Brackett-Rozinsky]

Kevin Baas wrote

> the number of demotions from a set of ignored candidates is always between twice and half the sum of any pair of disjoint subsets.

You are using words that have precise mathematical meanings, and those meanings do not support your claim as written.

To wit, see my previous example where Q and R are disjoint subsets (of Q⋃R, which they also cover completely) with respectively 0 and 1 choice demotions, but Q⋃R has six times as many choice demotions as that pair of disjoint subsets.

I restate: the tightest “obvious” upper bound is the number of candidates in the set times the total weight of ballots with one of those candidates top-ranked.

Kevin Baas wrote

> “ignore successively more candidates from the bottom of the pack" does not determine the ordering among sets of equal cardinality.

Neither do the more complicated procedures we have been discussing.

In the event of a tie when using the instant-runoff approach, I recommend adding all candidates-tied-at-the-bottom to the ignored set simultaneously, rather than employing any tiebreaking procedure. The degenerate case of course is when all remaining non-ignored candidates are tied, which may not have a natural resolution method.

However, the situation is at least equally dire when using “choice-demotion-minimizing-subset” or any similar approach, as the tied subsets may or may not overlap, and it is not clear how to proceed in a tie either way.

Kevin Baas wrote

> 40 or 50 is not plausible

You state this as if it were fact, but it is not fact. The entire purpose of STV-like procedures is to allow voters to rank all candidates from all parties who are running for proportional representation in a multiwinner race. Even modest numbers of parties and seats can produce large fields.

Nevin

[Kevin Baas]

>> the number of demotions from a set of ignored candidates is always between twice and half the sum of any pair of disjoint subsets.

> You are using words that have precise mathematical meanings, and those meanings do not support your claim as written.

No.

the number of demotions from a set of ignored candidates is always between twice and half the sum of any pair of disjoint subsets.

 2*({a}+{b}) >= {a,b} >= 1/2*({a}+{b})

>> “ignore successively more candidates from the bottom of the pack" does not determine the ordering among sets of equal cardinality.

> Neither do the more complicated procedures we have been discussing.

No.

The procedure we discussed gives an exact ordering for all combinations.

>> 40 or 50 is not plausible

> You state this as if it were fact, but it is not fact

the word "plausible" is by definition subjective.   it means " (of an argument or statement) seeming reasonable or probable."

you give an example of 8 parties, 24 seats, 50 choices

neither 8 parties nor 24 seats "seams reasonable nor plausible", nor does a ballot with 50 choices.

[Nevin Brackett-Rozinsky]

Kevin Baas wrote

> The procedure we discussed gives an exact ordering for all combinations.

This is factually incorrect. If there are two or more subsets of candidates which, if ignored, would result in an equal number of choice demotions, then the criterion we have been discussing does not provide an ordering among them.

For the minimal counterexample, consider a 2-candidate race for 1 seat, with 2 voters who rank the candidates oppositely.

Furthermore, the temerity with which you reject my correct assessment of upper bounds on cd(), as well as your obstinacy regarding the possibility that a large number of candidates could run in a multi-winner race, have left me with negligible interest in continuing this conversation at present.

Therefore I will add just one more observation:

Under any voting system of this general type, regardless of the specific procedure involved, suppose that a set of candidates-to-ignore has been chosen, which results in candidate Z just barely achieving a quota.

As it happens, I had ranked Z in 1st place and you had ranked Z in 6th place. Additionally, all the candidates you ranked ahead of Z were in the ignored set, so both your ballot and mine ended up “counting for” Z in this round.

Now Z is elected, and both our ballots are reweighted to a much lower value. It makes sense that *I* should have little input going forward, since my favorite candidate just won!

But why should *your* ballot be devalued as heavily as mine, when you only got your sixth choice?

Nevin

[Kevin Baas]

>> The procedure we discussed gives an exact ordering for all combinations.

> This is factually incorrect. If there are two or more subsets of candidates which, if ignored, would result in an equal number of choice demotions, then the criterion we have been discussing does not provide an ordering among them.

No it is factually correct.  the sort order between those two is then equal, rather than undefined.  a tie does not diminish the fact that all combinations are sorted.

as you can see by the code that i have posted publicaly, all combinations are generated, evaluated, and sorted.

[Kevin Baas]

conversely, sorting only on cardinality, does not determine an order for iterating through sets of equal cardinality.

[Brian Olson]

The California special election for Governor a few years ago had over 100 candidates on the ballot. Single seat, so not a PR problem specifically, but a real ballot that actually happened in the US in the last few years.

[Kevin Baas]

Even though that's single-seat, I accept it as a qualified counterexample.

N=100 is well outside what's practical for an NP-time algorithm.  Using the aforementioned constraints one might be able to construct an algorithm with an average case that's P-time.  One could also use a heuristic algorithm such as GA to find an almost best answer in P-time.  One could also run a pre-counting step of eliminating those candidates that definitely cannot get elected, to effectively reduce N.

100 candidates just seems like a horrible idea though - 100 candidates on a ballot for the same role (single winner or multi-winner).  Way to confuse the hell out of the voters and make the election essentially a coin toss, err... roulette wheel.

There's no ballot counting method that will make that problem go away.

[Kevin Baas]

I just found a fail case for my method: https://en.wikipedia.org/wiki/Independence_of_clones_criterion#Borda_count

i'll have to rethink the elimination ordering.

sort criteria to choose from:

 * a - borda count (minimal)

 * b - rank demotions from first (similiar to borda) (same as # of first place votes affected) (minimal)

 * c - affected ballots (minimal)

 * d - candidates eliminated (maximal, n/a if eliminates are cumulative)

so, at most 4! combinations of sort criteria (first criteria, second criteria...) 

i'll have to write up some code to do some automated testing.

[Kevin Baas]

okay, well i ran 'em all (that was faster than i thought) and got:

* d can't be first (duh!)

* b > c > a

so there's three that are tied for first, but i wanna put d last, so sort criteria are, in order:

1) b - rank demotions from first (similiar to borda) (same as # of first place votes affected) (minimal)

2) c - affected ballots (minimal)

3) a - borda count of eliminated candidates (minimal)

4) d - number of candidates eliminated (maximal, n/a if eliminates are cumulative)

this fails test #9, though (participation criteria).  i wonder if the only reason i passed it before was due to getting lucky on an unbroken tie.

full results are at https://docs.google.com/spreadsheets/d/18AN5xli49l39Fh5bRQerLPF0iT5AJpEjY6dvUzk-TUI/edit#gid=1842449340

(note  3=b, 2=c, 1=a, 4=d.  sorry for the shifting around)