I am still unsure if I personally agree with Kevin's conclusions, but his approach is very novel and worth sharing with others. Kevin's post is

**very**technical so put on your thinking caps and get ready to dive in.

## Rethinking STV Fundamentals

Three errors have plagued the counting of ranked choice ballots for over a century, and here’s how to fix them.While learning about how ranked choice ballots are traditionally counted, I discovered three critical flaws in the way everyone does it -- indeed, the way everyone has been doing it for over a century. I would like to share with you how I discovered these flaws and how to fix them. In the end I will outline a new and complete method for counting ranked choice ballots that contains none of these flaws, and consequently produces fairer results than any other system. (With the possible exception of CPO-STV, which it might be tied with.) In addition to explaining the reasoning for these changes, I will provide evidence to support my (admittedly bold) claim that the results are more fair.

Firstly let me outline two of the flaws by walking through two hypothetical scenarios.

### On passing two tests.

#### Failing Test 1

Consider the scenario (from http://www.accuratedemocracy.com/e_shares.htm ):A ranked-choice election to fill 3 seats. The candidates are A, B, R, and S and 36 ballots are cast.

Numbers of voters 12 7 9 8

Their preferences AB BA RS SR

Thus 19 voters, a majority, prefer A and B while 17 prefer R and S.

Now the most immediately apparent way to determine the winners, is that, since each candidate represents 1/3 of the voters, or 36/3 voters, then that's how many votes they need to get elected. Any surplus votes should transfer to the next choices. And the final seat will be determined by who has the most votes.

Okay, so 36/3=12... So only A has quota. A is elected, leaving:

Numbers of voters 7 9 8

Their preferences B RS SR

Well now no one has quota, so what do we do now? Well the standard thing to do in counting ranked choice ballots is to eliminate the candidate with the fewest votes, and transfer the votes to the next choice. Well, that would be B. That leaves only R and S. There are only 2 candidates left, and 2 seats, so we give them to them. So the final winners are: A,R,S.

But wait.... A and B was preferred by the majority, so shouldn't it have gone to A,B,R? Yes, it should have. We have failed this test.

#### Passing Test 1

The standard way to "solve" this problem is by using votes/(seats+1) as the quota instead. This is called the "Droop quota” and is used almost universally in ranked choice elections. If we instead used votes/(seats+1) = 9 as the quota, B would have received 3 surplus votes, making it 10 B - 9 RS - 8 SR. B & R make quota, filling the two remaining seats. Thus, the majority wins the majority. We now pass the test.#### ...but Failing Test 2

But the "Droop" quota introduces its own problem. Consider this scenario:5 seats, 2 parties (a,b,c,d,e - vs - v,w,x,y,z)

ballots are:

690 ballots: a,b,c,d,e, v,w,x,y,z

310 ballots: v,w,x,y,z, a,b,c,d,e,

Using votes/(seats+1) as the quota, quota is 1000/(5+1) = 166.666 Majority party meets quota 4 times, minority party 1 time. No seats remain Thus majority party wins 4 seats, and minority wins 1. Using, instead, votes/seats as the quota, quota is 1000/5 = 200

Majority party meets quota 3 times, minority party 1 time. There's 1 seat left. The final seat is determined by plurality vote. After subtracting used votes, the remaining votes are:

690 - 3*200 = 90

310 - 1*200 = 110

The minority party has plurality, and thus gets the final seat, making it 3 to 2. So which one is right? Well the ratio of majority voters to minority voters is closer to 3:2 than it is to 4:1, so the proper quota is more fair; represents the voters more proportionally. Using votes/(seats+1) as the quota systematically over-favors the majority at the expense of minority parties. Test failed.

#### Passing both Test 1 and Test 2

So how can you solve both problems at once? Well, by realizing that the problem in the first scenario, was never with the quota - it was that after B was eliminated in the first round, he was never re-introduced. Simply re-introducing candidate B -- and more generally re-introducing dropped candidates each round -- allows them to win in a later round. Thus solving the first problem. And does so without having to skew the quota, thus never creating the second problem.So let's go back to the step where we eliminated B and this time only _temporarily_ eliminate B.

Numbers of voters 7 9 8

Their preferences B RS SR

We see that, as before, it leaves only R and S. Only 2 candidates left, and 2 seats... but remember B can be re-introduced in the next round - so we still have 3 candidates that could win a seat! So we can't just give 'em to R and S. We have to check for quota, which is votes/seats, which is 12. No one has it, so temporarily eliminate the lowest, which is now S. The votes all transfer to R, giving R 17, which meets quota.

Numbers of voters 7 9 8

Their preferences (B) R(S) (S)R

So now remember we only _temporarily_ eliminated S, so any surplus votes can still transfer. Well there are 17-12 = 5 surplus votes, and they all transfer to S. So now we elect R, and S now has 5, leaving us with:

Numbers of voters 7 5

Their preferences B S

No one has quota, so we eliminate the lowest, leaving just B, which thus fills our final seat. And the winners are: A,R,B. The majority wins the majority! And without having to create the second problem discussed above, where the minority can get under-represented! By solving our initial problem correctly we avoided creating a second problem.

### You look skeptical...

At this point, a reader knowledgeable in voting system theory will probably be skeptical, particularly on the subject of using the “Hare quota” (votes/seats) instead of the unbalanced “Droop quota” (votes/(seats+1)). They’d say “The Droop quota has been preferred for over a hundred years. You’d have to make a very strong case, if you presume to claim the Hare quota should be used in any scenario.” Well the critical thinker in me would be inclined to respond “That’s the ad populum fallacy! A claim is true or false based on its merits, not its popularity or lack thereof!” But the rhetorician in me would say “Why yes, yes I would have to make a very strong case. Bear with me, and I shall do precisely that!”Let me begin by backing this up a bit. I came to discover the errors with the current methods when working on an entirely different (though related) problem...

### How I discovered a new method of counting ranked choice ballots

While in the process of generating multi-member redistricting maps for FairVote.org, we were discussing how the winners are calculated. This is when I first learned of the “Droop quota” (votes/(seats+1)), and how basically all STV vote counting methods use it. My first impression was "that's wrong". Where “seats” is the number of seats available, each candidate represents votes/seats voters. So quota should obviously be votes/seats.Let me explain this in pictures… A “seats-votes curve” graphs the relationship between the fraction of votes a party gets, and the fraction of seats that gives them. When you use votes/(seats+1), then the further the vote is from a 50/50 split, the more distant the resulting winners are from what people want. You can clearly see this in the resulting “seats-votes curve”. Theoretically it should be a straight diagonal line, but when you use a quota of votes/(seats+1), it’s inevitably steeper than it should be. Below are the seats-votes curve for hypothetical multi-member districts (5 seats per district) for Texas, Ohio, and Pennsylvania, when using votes/(seats+1) as the quota.

*Votes-seats curves for multi-member districts (5 seats per district), using a quota of votes/(seats+1). (Namely, Texas, Ohio, and Pennsylvania) (x = % dem votes, y = % dem seat) The +1 in the denominator skews the seats-votes curve in favor of whichever party has the majority, resulting in representation that is not proportional. The darker red/blue shading shows excess seats for that party, beyond what would be proportional to the votes. (The extra-dark shading highlights asymmetries in the curve.) The curve has a slope of (5+1)/5.*

Now there is only one way to solve this problem: Take the +1 out of the denominator. With the +1 in the denominator, you’re essential graphing the function y = x * (seats+1)/seats, which looks, well, like you see above. But to be proportional, the curve should look like y = x, by definition. To get that, you need to change that y = x *(seats+1)/seats to a y = x * (seats+0)/seats. Which means you need to use votes/(seats+0) for the quota instead of votes/(seats+1).

The inescapable conclusion is that in order to get proportional representation, you

**must**use votes/seats as the quota. There’s no two ways about it. So why does everyone use votes/(seats+1) as the quota, if it’s doomed to bias? Well when I asked, I was given that first example I explained above in “On passing two tests”.

Then I found there was another thing wrong with the way ranked choice was traditionally counted. When no one meets quota, they eliminate the candidate that got the fewest votes and look at the next highest choice for those ballots. Okay, that's fine -- that makes sense -- but then after a candidate meets quota, they never reintroduce those candidates! That elimination should have only been temporary -- only for determining the winner for that seat.

**You should only eliminate a ballot permanently when it's used to meet quota**. Otherwise those voters just aren't being represented at all. They might as well not show up to the polls because you just threw away their ballot.

But now I was starting to see why they were using an unbalanced quota of votes/(seats+1) (called the "Droop" quota): because the premature elimination of the ballots was screwing things up, especially for minority candidates. So instead of realizing what was causing this (the premature elimination of ballots), they artificially lowered the bar, and that seemed to work, so they went with it. They added a second error to try to treat a symptom of the first, thereby compounding the error. I'm reminded of the nursery rhyme "There was an old lady who swallowed a fly..." Now it made sense. They were using the wrong quota because they were prematurely eliminating ballots. The correct solution was of course to not prematurely eliminate ballots, and to use the correct quota of votes/seats. Somehow this had gone unnoticed for centuries. The old lady had gone on swallowing things and the fly was still wiggling and jiggling inside her.

### The first iteration

So, equipped now with a proper solution, I did as all good programmers do: I wrote a program. This accomplishes three things:- It helps me make sure I've got every nuance and corner case and all that taken care of; make sure I really have every part in the machine figured out. (And if I do, it demonstrates that.)
- It allows me to quickly and accurately run tests to verify and confirm the method.
- It gives me a working automated counter to demonstrate the method's superiority. (Or discover its inferiority, be that the case.)

So there was my 3rd change:

- Re-calculate the quota just before testing for it, instead of just once at the beginning. This compensates for ballots that have run out of choices.

### The second iteration

Well turns out I didn't have every nuance figured out. It occurred to me that if I tried (temporarily!) eliminating candidate A, then tried eliminating candidate A and B, well wouldn't it be better to try eliminating just candidate B, before trying both A and B together? The standard method was just to add one more candidate to what you’re eliminating, each time, thus skipping eliminating just B alone. That didn’t seem right. More precisely I knew it was wrong (because I had a counterexample) – I just didn’t know what the right way was.So, I just went with the traditional way for now, see where that gets me. I figured I could revisit the problem later, and be better equipped when I did. All the results of my tests looked pretty good, except for one. And I knew almost right away what the problem was. Because the elimination order was wrong. It was going from A to A,B -- skipping B. it was time to revisit the elimination order.

Thanks to some conversation on google election science forum, I decided to go all the way with this - to order every single possible combination of candidates. The key was switching the sort criteria from how many ballots were affected, to what I called (for lack of a better term) how many "choice demotions" were produced. Going from 1st choice to 2nd was 1 “choice demotion”, whereas going from 1st to 3rd was 2. Now I had a way to score every possible combination of candidates, and thus a way to sort them. Notwithstanding ties (which are unavoidable), I now had a complete ordering.

So I tried that, worked beautifully. And now I have my final algorithm. The 4 major changes from traditional STV are:

- Uses the correct quota of votes/seats (don’t swallow the spider)
- Only permanently eliminate ballots if they are used to make quota (don’t swallow the fly)
- Recalculate quota right before checking (‘cause ballots could have run out of choices)
- Temporarily eliminate sets of candidates in order of fewest "rank demotions" to most, ordering all possible combinations.

### Validation

So now I have 3 major changes from the traditional way of counting ranked choice votes:- Restore ballots that haven’t been used to meet a quota. (as opposed to not restoring)
- Use votes/seats as the quota. (commonly known as “Hare quota”). (as opposed to using an unbalanced quota of votes/(seats+1))
- Temporarily ignore combinations of candidates based on the number of choice demotions it results in. (sorted from least to most) (as opposed to fewest votes)

But the more curious would ask a few further questions: “What if you implement just some of these changes? E.g. just the first and the second, or just the third? Maybe one of those rules doesn’t really make that big of a difference. Maybe one of those rules makes a huge difference. Maybe two of those rules only make a difference when they’re both applied… etc.”

Well I’ll give you one guess which type of person I am -- that’s right, the more curious type. And I have a very valuable skill that gives me a unique ability to satisfy my curiosity with relative ease: I know how to code. So you can guess what comes next: I wrote a computer program to automatically calculate the results for all 8 different combinations of the rules, then I gathered no less than 42 different scenarios from across the internet, and made my program test all 42 of them, for all 8 different combinations. Then I put the results in a spreadsheet and prettied it up.

A few things stand out in the results:

- Firstly, and most glaringly,
**using all 3 changes passes ALL BUT ONE of the tests, and it is the ONLY combination that does**. - Secondly,
**if you don’t apply change #2 (Hare quota), neither of the other changes make much of a difference**, except for a few cases. - Thirdly,
**the only way to pass the proportionality test is by using change #2 (Hare quota)**. This also is the only way to make it tactical voting immune, at least for the cases tested. - Fourthly, if you pick ANY of the changes and choose not to apply it, there are tests that that will ALWAYS fail, regardless of whether or not you apply the other 2 changes. This tells you that
**each original rule is definitely wrong**. - And finally, change #1 (Restore ballots) only makes a difference (save a few cases) when change #2 (Hare quota) is applied. So
**there is no value in combining the restore ballots rule with the Droop quota. You need to do both Hare & restore or neither**.

**ALWAYS results in a better result than any other combination**.

But you say: “This isn’t every possible test case. There may be some scenarios you haven’t tried in which some other combination performs better.” To this I say: “Find one, show it to me, and I’ll concede it. That is the true test of science.” What did Albert Einstein say?: “No amount of experimentation can ever prove me right; a single experiment can prove me wrong.” I welcome such a test -- nay, I invite it! I wrote a user-friendly interface for my vote-counting program, and published it and its source code online, here. Test, test, test away! For with each successful test, my case grows stronger, and with each failure our knowledge increases!

### The method

For the sake of precision, let me lay it all out:STEP 0: Make a copy of the ballots - these will be referred to as the "original" copy, even though they'll be altered (reweighted) due to surplus vote transfers.

Determining the next winner:

STEP 1: Determine quota 1: Count how many ballots are left (using the weighted value of the ballot), divide by number of seats left to fill. This is the quota.

STEP 2: order all combinations of candidates

- Compute all combinations of candidates (e.g. {a},{b},{c},{a,b},{b,c},{a,c},{a,b,c})
- For each such combination, count how many "choice demotions" would happen if those candidates are removed, in order for every voter to have a 1st choice candidate, or run out of choices. For instance, if a person's choices are {a,b,c,d}, and a,b & d are removed, then the result is {c}, and it counts as 2 demotions. (Since what is now the 1st choice used to be the 3rd). Remember to use the weighted value of the ballot in counting demotions.
- Sort all combinations by how many choice demotions they produce, least to most.
- Ties are broken by fewest ballots affected.
- Ties on that, in turn, are broken by most candidates eliminated this way.
- Add the "empty set" (no candidates) to the beginning.

- Make a local copy of the ballots. For the remainder we will be operating on this local copy.
- Take the next set of candidates in the sorted demotion list (if this is the first time, this will be an empty set).
- Remove those candidates from the ballot, and promote all the choices so it doesn't skip any ranks. if a ballot is out of choices, disregard it.

- Check if any candidate has reached or exceeded quota (using their weighted value -- always use the weighted value).
- If one has, the one with the most votes is elected.
- If none have reached quota, revert to the local copy you made in step 3, and repeat, using the next candidate combination in the sorted list.

- The candidate with the most first place votes is elected.
- Re-weight the ballots that were used to make quota - that have that person listed as first in the local copy. Their new weight is whatever their previous weight was, times 1-(quota/(the sum of their current weights)). This re-weighting applies to the _original_ ballots, not our local copy.
- Remove the elected candidate from all ballots, and shift the ranks up to make them sequential. If any ballot runs out of choices, remove it.

So the choice demotions makes this multi-winner borda count?

ReplyDeleteIn single-winner this reduces to Borda count.

DeleteHowever, it is different than "multi-winner Borda count". "Multi-winner Borda count" is a first-past-the-post system (aka non-transferable votes), and thus greatly over-represents the majority. (By giving the majority more than one vote.) This system uses transferable votes, and thus remains proportional in the multi-winner case.

So no, it's different because it uses transferrable votes - because used votes are subtracted, thus making sure everyone gets the same number of votes. This makes it far superior to multi-winner Borda count - far more fair and proportional.

I have read that it is possible, when an STV system is used, that ranking a candidate higher can result in elimination of that candidate. Does this Baas system do anything to reduce that problem? If it is still a problem, could someone post 2 lists of votes (that can be plugged into the java program I downloaded from above) that shows how an increase in rank by a voter can result in a candidate losing in a multi-winner election? Is there any way to know how often this problem might actually occur?

ReplyDeleteThinking through it analytically, I'm pretty sure that with my system, ranking a candidate higher CANNOT result in elimination of that candidate. And testing it empirically, I didn't encounter that failure in any of my tests: ( https://docs.google.com/spreadsheets/d/18AN5xli49l39Fh5bRQerLPF0iT5AJpEjY6dvUzk-TUI/edit#gid=0 ).

DeleteIf any one can find a scenario that fails the test, please post. But I don't think there is one.

"Is there any way to know how often this problem might actually occur?" Two ways: 1) figure out the mathematical rules under which it occurs, and then compute from there, analytically. 2) simulate millions of elections and find the rate of occurence there. The second method would take less thought, and could be re-used for other problems.

Thinking this through more carefully, in other ATV systems, ranking a candidate higher can result in elimination of that candidate because and _only_ because dropped candidates aren't re-introduces each round.

DeleteSince my method _does_ reintroduce dropped candidates each round, my method _completely eliminates_ this problem.

Thank you for this response. I suspected as much. I mistakenly posted my ballot example a couple of paragraphs below, instead of here. I think that example shows one benefit of your approach over STV. If Scottish STV is used, it is my understanding that the result in my election is that A wins. However, if just one voter switches from CBA to BCA, then B wins. That means a person opposed to A has to be careful not to rank C above B if C has less chance of winning. Using the Baas approach, however, B wins either way, freeing that voter to express her preference for C over B without worry that the effect is to elect A.

DeleteTo Jeff O'Neill,

ReplyDeleteAre you going to adopt this as one of the options on your site?

Jeff, we don't have any plans to implement this method. Because there are so many methods out there, we limit OpaVote to methods that are in use by a government or otherwise used extensively.

DeleteSuppose there are 3 candidates A, B, and C, for one position. 21 votes total.

Delete10 votes are A B C

2 votes are B C A

3 votes are B A C

6 votes are C B A

The Baas calculator gives B the win with Hare quota and A the win without Hare quota. The calculator sets the Hare quota at 21; is that right? Who wins under Scottish STV? [I would use OPAvote to count, but I used up my 3 free counts.]

Yes, the calculator sets the Hare quota at 21 in that scenario. For Hare quota, the calculator just uses number of ballots divided by number of seats. So that's 21/1 = 21. By the way my argument is that Hare quota should be the quota used. You just need to make sure that you add back in dropped (but unused) ballots each round, and order all N! permutations, instead of just doing successive elimination.

Deleteto Kevin Baas,

ReplyDeleteIs there a way to speed up the process, such as entering a matrix rather than one vote at a time, or a "calculate now" button. 21 candidates is taking a long time just to enter because the program is recalculating between each entry.

by "one vote at a time" i presume you mean one _ordering_ at a time. you can add as many ballots at a time as you want, for a given ordering. because it does full ordering, the time it takes to calculate winners grows with how many possible orderings there are, which is the roughly the number of candidates, factorial. that's why it's taking so long: because there are 21 candidates. Intuitively there are some clever mathematical tricks to speed it this up, but I haven't implemented them. It comes with the full source code, so if you know Java and have an IDE, you can edit the code yourself to e.g. add a "recalculate" button, and not have it recalculate until you press that. in retrospect, that's the way i should have built the interface. it was built for the purpose of testing and demonstration; as a proof-of-concept. for now i'd say just use fewer candidates. or modify the source code. i might update the version available for download, later, esp. if i find a really clever mathematical shortcut.

ReplyDeleteYes, that is what I meant, one ordering at a time. If your calculator would work for our 40 candidates, I'd propose it to our faculty for our committee election. But since 21 candidates takes days on my computer (and even that is too long), 40 would take forever. Bummer for me. But cool process that you've invented.

DeleteWell this motivates me to update it to handle big elections better. I'll shoot for 40 in an hour on a typical desktop. I think i can benefit from there being much fewer seats than candidates. how many seats?

DeleteI've update the counter at http://autoredistrict.org/ranked_choice_counter.zip

Delete* I added a "find winners" button. It won't calculate until you press that. So now you can enter all the orderings without having to have it recalculate all the time.

* When you uncheck "full elinination ordering", it won't pre-compute all possible orderings.

40 should now be manageable, if you first un-check "full elimination ordering".

You can see the drawback of that by comparing column "I" on the spreadsheet with column "E". ( https://docs.google.com/spreadsheets/d/18AN5xli49l39Fh5bRQerLPF0iT5AJpEjY6dvUzk-TUI/edit#gid=0 )

And you can see the remaining advantages over standard STV by comparing "I" with "L".

* It still produces a more proportional result than standard STV.

* And protects against tactical voting better than standard STV.

But yeah, having to pre-compute 40! orderings... that's a no-go. To make 40 practical, using full ordering, I'd have to change it so the orderings are computed as-needed. This would be much closer to 40 operations than 40! operations.

These are my notes from a few years ago on lemmas you could use to compute tge order of dropping candidates "as needed":

Deletewhere a,b represents total rank demotions caused by dropping candidates a and b

(a,b) >= (a)

(a)+(b) >= (a,b)

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

Also it has recently occurred to me that if one can prove that the candidate who would win a borda count is always a winner, no matter how many seats are chosen, then there exists an algorithm that finds all winners in o(n) time. (where n is number of candidates) but is suspect one can't prove that.

Thanks! When I have a minute I'll check it out. In my case, 4 seats should be enough (although maybe we will have 50 candidates at some point). Thanks again!

DeleteYou're welcome. To be clear I'm pretty sure you have to do the "full elimination ordering" to completely prevent the issue that you described: voting a candidate higher can result in them not getting elected. The chance is reduced by adding dropped candidates back in, but it is not zero.

DeleteIMO the greatest issue with my proposed method is that the time to compute winners is O(N!), but I think that

* even if you don't use full elimination ordering, the result is still better. Using only the other two changes still is an objectively better process than using none of the changes.

* using lemmas such as I described, it's possible to construct an algorithm that has all three rules, while still being computationally practical, even for elections with 50+ candidates.

It remains for that algorithm to be written. But I feel I've provided a good start.

I did check your new algorithm and it did compute way faster. So, thanks for doing that. You have provided a good start; I hope someone can finish it!

ReplyDeleteBelow is one example which shows that using the Hare quota can matter. With it, there is no change in result from a tactical change by one voter. Without it, the voter needs to be aware that voting her preference might lead to her least favorite candidate winning (under a full elimination system).

one seat; 21 voters

10 orderings are A,B,C

2 orderings are B,C,A

3 orderings are B,A,C

6 orderings are C,B,A

hare quota, not full elimination=A

not hare quota, not full elimination=A

hare quota, full elimination=B

not hare quota, full elimination=A

change one ordering from CBA to BCA

hare quota, not full elimination=A

not hare quota, not full elimination=A

hare quota, full elimination=B

not hare quota, full elimination=B

To Kevin:

ReplyDeleteThanks again.

I have another question. With other STV systems, there is a potential problem if there are too many candidates and not enough voters. A person who many would like second best might be eliminated (this is described elsewhere on this website). Does your Baas system, especially the shortcut version you created, reduce or eliminate this problem by adding back eliminated candidates each round?

Yes, it "eliminate[s] this problem by adding back eliminated candidates each round". This is true for the "shortcut" (not full elimination ordering) version, too. The drawback of the "shortcut" version is that in some situations (like what you show above), it doesn't pick the number one best choice. The full elimination ordering does a comprehensive search, the shortcut version does not - which is precisely why it's so much faster. But yeah, in either case, temporarily dropped candidates are re-introduced each round. That's the big flaw in other STV systems that I realized needed fixing. The other changes were just icing on the cake.

DeleteI thought so, but just wanted to make sure. Many thanks!

DeleteRereading parts of your post, I noticed that you used votes/(seats+1) for the Droop quota. I thought that (votes/(seats+1))+1 was generally used for Droop. Does that reduce the Droop problems that you describe?

ReplyDeleteNo. The +1 is unimportant. All it means is that ties don't result in two winners, but must be broken somehow. It's the same as how in majority systems you need 50% plus one vote. So for instance if in the U.S. Senate, a vote is split exactly 50-50, the bill doesn't pass. But since the Hare quota uses up every vote exactly, you can't apply a [quota]+1 rule, since for the last seat you will have exactly [quota] ballots left. TLDR; the extra +1 on the quota really doesn't matter. We're talking on the order of 100,000 votes vs. 100,001 votes.

DeleteSpeaking of ties, I tried a sample election and noticed that your algorithm eliminates tied candidates in the order they are listed, leaving the last of the tied candidates to be winners. I suppose that there is not much that can be done with ties, but it would seem that it would be better to eliminate randomly than to eliminate in ballot order (although your method does provide better information as to what is happening). Maybe a checkbox that says "eliminate ties randomly" would be helpful.

DeleteThe "full elimination ordering" has something like 5 levels of tie-breaking. I ran a bunch of simulations to optimize the tie-breaking order. (Though really the first tie-breaking criteria is exponentially more important than the others.) The best first criteria I found was "fewest rank demotions". But yeah, failing an efficient way to do that, or some other deterministic criteria, random tie breaking would be the next best. Random tie breaking can be implemented without adding a checkbox, simply by randomly sorting the candidates _before_ tallying and determining winners. i.e. randomly assigning each candidate to "A,B,C,...", instead of a deterministic method such as alphabetical.

DeleteThis comment has been removed by the author.

ReplyDeleteIn the system I invented, which uses four averages or representative counts, the first average is of the Hare quota and the Droop quota, which I worked-out to be a Harmonic Mean quota (because these quotas are harmonic series): HMQ = votes/(seats + 1/2).

ReplyDeleteThe FAB STV system does not eliminate candidates, permanently or temporarily, before the full schedule of the count is complete.

FAB STV extends the Meek STV use of keep values. But discards its quota reduction (also employed here). The FAB STV way is that all preferences are counted (maximum use of preference information) including abstentions, which makes quota reduction irrelevant.

Mr. Baas, I've been very impressed with this revision of the STV counting process and I'm hoping to get the shortcut version known and implemented in my local community. I don't see the full elimination ordering being sufficiently practical, unfortunately, especially if ballots are counted by hand. But I wonder if one could get any closer to the FEO result by eliminating the candidate who appears, at all rankings, on the fewest ballots, instead of the one with the fewest votes.

ReplyDeleteI'm curious what you mean by "my local community". Elections for a municipality? The ballots can be entered into a computer by hand and then computer tallied. This would be more accurate and reliable than a hand tally. If people are concerned about transparency, one could provide the source code and the data (anonymized, of course), so that any one can reproduce the tally. I'm sure there are ways to have a faster elimination ordering that comes close to the accuracy of the FEO. I'm not sure your suggestion is the best approach, though. I'll have to give it some thought.

DeleteOne could use the traditional STV elimination (eliminate lowest total until someone meets quota), and then look at each dropped candidate and see if they would have won if they weren't dropped but all the others that were dropped were still dropped. e.g. if lowercase means dropped, when someone meets quota at A B C d e f, try A B C D e f, A B C d E f, and A B C d e F. then if D, E, or F win, that's the real winner. So it's basic STV elimination, with an added rollback test on each dropped candidate.

Here's an idea:

ReplyDelete1) for each candidate, find out what other candidates would have to be eliminated for that candidate to make quota, with the fewest overall rank demotions. this could be about O(N^2) per candidate, so O(N^3) total for this step.

2) find the candidate(s) with the lowest number of such rank demotions to make quota. O(N)

3) if there is only one such candidate, that's the winner. if there is a tie, take the one with the most votes in their respective scenarios.

If I'm thinkiing that through right it would be O(N^3) time, which is much better than O(N!), and would have similiar results to FEO. Someone would have to code it and test on the 43 scenarios i collected.

Eureka!

DeleteSo I decided to try the traditional elimination algorithm, but instead of elimination the fewest first choices each round, eliminating the candidate with the lowest Borda Count (adjusting the max borda value for elected and dropped candidates, and using the re-weighted ballots). I've added the results to my spreadsheet, column E. ( https://docs.google.com/spreadsheets/d/18AN5xli49l39Fh5bRQerLPF0iT5AJpEjY6dvUzk-TUI/edit?usp=sharing ) It is very close to FEO, and completes in polynominal time (something like O(N^2), I think.)!

So there's the solution to the issue of computing time when there are a lot of candidates.