tag:blogger.com,1999:blog-8217294657304563413.comments2018-12-06T05:50:25.072-08:00OpaVote BlogJeff O'Neillnoreply@blogger.comBlogger65125tag:blogger.com,1999:blog-8217294657304563413.post-58746306342603686392018-12-05T10:06:03.803-08:002018-12-05T10:06:03.803-08:00I thought so, but just wanted to make sure. Many t...I thought so, but just wanted to make sure. Many thanks!Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-27844579179997718932018-12-04T13:16:06.330-08:002018-12-04T13:16:06.330-08:00Yes, it "eliminate[s] this problem by adding ...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.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-29289109397277970902018-12-04T10:10:51.742-08:002018-12-04T10:10:51.742-08:00To Kevin:
Thanks again.
I have another question. W...To Kevin:<br />Thanks again.<br />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?Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-65343890423145149482018-11-03T13:54:32.642-07:002018-11-03T13:54:32.642-07:00I did check your new algorithm and it did compute ...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!<br /><br />Below 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). <br /><br />one seat; 21 voters<br />10 orderings are A,B,C<br />2 orderings are B,C,A<br />3 orderings are B,A,C<br />6 orderings are C,B,A<br />hare quota, not full elimination=A<br />not hare quota, not full elimination=A<br />hare quota, full elimination=B<br />not hare quota, full elimination=A<br /><br />change one ordering from CBA to BCA<br />hare quota, not full elimination=A<br />not hare quota, not full elimination=A<br />hare quota, full elimination=B<br />not hare quota, full elimination=B<br />Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-89149447339529519562018-11-02T23:42:39.794-07:002018-11-02T23:42:39.794-07:00You're welcome. To be clear I'm pretty su...You'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.<br /><br />IMO the greatest issue with my proposed method is that the time to compute winners is O(N!), but I think that<br />* 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.<br />* 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.<br />It remains for that algorithm to be written. But I feel I've provided a good start.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-37874625807844304152018-11-02T16:54:53.532-07:002018-11-02T16:54:53.532-07:00Thanks! When I have a minute I'll check it out...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!Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-12640365740671834042018-11-02T15:43:37.620-07:002018-11-02T15:43:37.620-07:00These are my notes from a few years ago on lemmas ...These are my notes from a few years ago on lemmas you could use to compute tge order of dropping candidates "as needed":<br /><br />where a,b represents total rank demotions caused by dropping candidates a and b<br /><br />(a,b) >= (a)<br />(a)+(b) >= (a,b)<br />3*({a}+{b}+{c}) >= {a,b,c} >= 1/3*({a}+{b}+{c})<br /><br />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.<br />happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-21784276436577504422018-11-02T14:33:08.569-07:002018-11-02T14:33:08.569-07:00I've update the counter at http://autoredistri...I've update the counter at http://autoredistrict.org/ranked_choice_counter.zip <br />* 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.<br />* When you uncheck "full elinination ordering", it won't pre-compute all possible orderings.<br /><br />40 should now be manageable, if you first un-check "full elimination ordering".<br /><br />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 )<br />And you can see the remaining advantages over standard STV by comparing "I" with "L".<br />* It still produces a more proportional result than standard STV.<br />* And protects against tactical voting better than standard STV.<br /><br />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.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-22590483340921326752018-11-02T13:43:44.072-07:002018-11-02T13:43:44.072-07:00Well this motivates me to update it to handle big ...Well 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?happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-9814698559239726052018-11-02T13:09:34.844-07:002018-11-02T13:09:34.844-07:00Yes, that is what I meant, one ordering at a time....Yes, 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. Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-18736305973146969262018-11-02T13:01:08.482-07:002018-11-02T13:01:08.482-07:00Thank you for this response. I suspected as much. ...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.Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-62652153665798408662018-10-31T16:25:11.888-07:002018-10-31T16:25:11.888-07:00Thinking this through more carefully, in other ATV...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.<br /><br />Since my method _does_ reintroduce dropped candidates each round, my method _completely eliminates_ this problem.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-78845406449476246762018-10-31T14:54:12.685-07:002018-10-31T14:54:12.685-07:00Thinking through it analytically, I'm pretty s...Thinking 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 ).<br /><br />If any one can find a scenario that fails the test, please post. But I don't think there is one.<br /><br />"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.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-91086097277903694212018-10-31T14:48:20.848-07:002018-10-31T14:48:20.848-07:00Yes, the calculator sets the Hare quota at 21 in t...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.happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-14172868311115430412018-10-31T14:43:37.258-07:002018-10-31T14:43:37.258-07:00by "one vote at a time" i presume you me...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. happyjack27https://www.blogger.com/profile/06322415607461417789noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-65702323149090055582018-10-31T13:30:51.344-07:002018-10-31T13:30:51.344-07:00Suppose there are 3 candidates A, B, and C, for on...Suppose there are 3 candidates A, B, and C, for one position. 21 votes total.<br />10 votes are A B C<br />2 votes are B C A<br />3 votes are B A C<br />6 votes are C B A<br />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.]Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-50766259917840868482018-10-05T11:50:53.577-07:002018-10-05T11:50:53.577-07:00Jeff, we don't have any plans to implement thi...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.Jeff O'Neillhttps://www.blogger.com/profile/11828614939910702199noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-10872902018430914982018-10-05T10:25:15.869-07:002018-10-05T10:25:15.869-07:00to Kevin Baas,
Is there a way to speed up the proc...to Kevin Baas,<br />Is 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. Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-90329606674319240272018-10-05T10:23:24.478-07:002018-10-05T10:23:24.478-07:00To Jeff O'Neill,
Are you going to adopt this a...To Jeff O'Neill,<br />Are you going to adopt this as one of the options on your site?<br /><br />Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-29780766310046193612018-09-27T10:40:14.664-07:002018-09-27T10:40:14.664-07:00I have read that it is possible, when an STV syste...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?Jeff Stakehttps://www.blogger.com/profile/08560473952197625800noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-4695184732689686242018-08-03T12:12:49.297-07:002018-08-03T12:12:49.297-07:00Sorry for the late reply. This can't be autom...Sorry for the late reply. This can't be automated so the election manager would need to handle it.Jeff O'Neillhttps://www.blogger.com/profile/11828614939910702199noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-9061694996850563812018-07-05T03:47:52.093-07:002018-07-05T03:47:52.093-07:00Keith and All - the Scots did not invent the Wei...Keith and All - the Scots did not invent the Weighted Inclusive Gregory Method (WIGM) of transferring surpluses. It was a development from the defective Inclusive Gregory Method (IGM) used for federal STV-PR elections in Australia - see Farrell and McAllister (2003) Australian Journal of Political Science 38: 479 - 91. As Jeff said, the WIGM version of STV is not intended for manual counting (though it can be done). WIGM STV-PR was introduced in Scotland only after it was decided that we should use electronic counting (scanning conventional STV ballot papers) - the first implementation of WIGM STV for public elections anywhere in the world.<br /><br />The "inclusive" versions of the Gregory Method of fractional transfers were introduced because the 'last parcel' provision of the Gregory Method was considered by some to be "unfair" to significant numbers of voters. Consider the following election (only relevant candidates reported): Quota 100. Stage 1 first preference votes: Candidate A 101; Candidate B 99; Candidate C 5. All of these ballot papers are transferable as they have several 'next available preferences' marked.<br /><br />At Stage 1, Candidate A is elected. At Stage 2 Candidate A's surplus of one vote is transferred using all 101 ballot papers - none of those votes go to B or C and no other candidate achieves a quota. [Transfer value: 1 / 101 = 0.0099.] At Stage 3, Candidate C is excluded (eliminated) when two of her votes transfer to B, who is thereby elected (99 + 2 = 101). Stage 4 is the transfer of B's surplus. Under the 'last parcel' provision of the Gregory Method, only the two ballot papers received from C (the 'last parcel') will be used to transfer the surplus. [Transfer value: 1 / 2 = 0.5.] Giving the 99 voters who gave first preferences to B no say in the Stage 4 transfer has been considered "unfair" compared to the involvement of all of the 101 voters (comparable number) who gave their first preferences to Candidate A.<br /><br />To overcome this "unfairness" the Australians invented the "Inclusive Gregory Method" in which all of the relevant candidate's ballot papers are used whenever a surplus is transferred and the 'transfer value' is calculated as an average over all the ballot papers, no matter what value the ballot papers had when the now-elected candidate received them. Some simple arithmetic will show that this method is defective because it has the effect of increasing the value of some ballot papers above one vote, with compensatory reductions in the value of other ballot papers. Thus the Inclusive Gregory Method does not meet the fundamental requirement of "one person, one vote" and so should never be used for any kind of election anywhere. Despite the repeated demands of the Proportional Representation Society of Australia and others, the Australian authorities will not listen and they continue to use this defect procedure for federal STV-PR elections.<br /><br />The defect in the Inclusive Gregory Method was removed in the Weighted Inclusive Gregory Method by weighting each ballot paper by its current value when a new transfer value had to be calculated for the transfer of a surplus, as described by David Farrell and Ian McAllister. In this way all ballot papers retain their "one vote" value at all stages of the count.<br /><br />For a Detailed Description of a count in accordance with the current Election Rules for STV elections in Scotland see:<br /> http://www.gov.scot/Resource/0038/00389095.pdf<br />James Gilmourhttps://www.blogger.com/profile/17374325929212547383noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-24403475159233806762018-06-18T11:44:59.350-07:002018-06-18T11:44:59.350-07:00Am involved in a confederation in which regional e...Am involved in a confederation in which regional entities are represented. These entities have weighted votes based on the number of employees. TO win an election at the confederation level, you need to win the vote (based on weighted voting which i understand how to do and have played around with a trial election on your very impressive site) but you also need to get the support of 25% of the entities (to ensure that a couple of bigger entities cannot railroad the others. So its not a supermajority, but a minimum threshold (not of votes but of entities). Can this be automated or does the election manager just count the number of voting entities at the end of the election before certifying the vote? THanks Patrick Francishttps://www.blogger.com/profile/01104613036900274143noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-34763409812030414992018-05-03T05:51:57.051-07:002018-05-03T05:51:57.051-07:00Ok, thanks Jeff.
Ok, thanks Jeff.<br />Rob Wallishttps://www.blogger.com/profile/05207067067856913521noreply@blogger.comtag:blogger.com,1999:blog-8217294657304563413.post-72300969337289259732018-05-03T05:16:18.910-07:002018-05-03T05:16:18.910-07:00Hi Rob, you can't do that with weighted votes....Hi Rob, you can't do that with weighted votes. If you want to do that, you'd need to use 4 voting codes (for code voters) or 4 email addresses (for email voters) for Alice.Jeff O'Neillhttps://www.blogger.com/profile/11828614939910702199noreply@blogger.com