search

LivingInSyn / rcir

Ranked Choice Instant Runoff library written in Rust
MIT License
12 stars 2 forks source link

Candidates with no first choice votes can win #5

Open timotree3 opened 5 years ago

timotree3 commented 5 years ago

Consider this set of ballots:

I would expect that in the first round, the candidate with zero votes (Joe) would get eliminated, then Chris, Sam, and Bob (with one vote), would get eliminated, then either Alice would win or in CompleteMajority mode nobody would win.

The current behavior is different, Sam, Bob, and Chris get eliminated, and then Joe goes on to win.

This issue is present in both modes.

LivingInSyn commented 5 years ago

In the first round, Sam, Bob, Chris are eliminated leaving:

Alice Alice Joe Joe Joe

Joe should win

timotree3 commented 5 years ago

I would expect

then

then

then either Err(VotersNoVotes) or Winner("Alice")

LivingInSyn commented 5 years ago

This isn't how ranked choice voting works, though

1) count each persons top votes and see if you have a majority 2) remove the lowest vote getters from that round (from the set [alice, alice, sam, bob, chris]) 2a) see https://en.wikipedia.org/wiki/Instant-runoff_voting#/media/File:IRV_counting_flowchart.svg 3) re-run the election

You can't consider peoples second choice at all, until their first choice has been discarded

timotree3 commented 5 years ago

I've been using that flowchart as my baseline too :smile:. I just don't interpret "Eliminate last place candidate" the same way that you do.

I think it means "In the set of all candidates that ran for the election, find which ones have the lowest amount of votes in this round, and eliminate them"

So in my understanding, (from a theoretical level, this is not necessarily how an efficient implementation would do it), it would go

Candidate Votes this round
Alice 2
Bob 1
Chris 1
Joe 0
Sam 1

then Joe would get eliminated

Candidate Votes this round
Alice 2
Bob 1
Chris 1
Sam 1

then Sam, Chris, Bob get eliminated

Candidate Votes this round
Alice 2

(Note that usually these vote counts would be changing each round if my example had ballots that ranked more preferences in them)

You can't consider peoples second choice at all, until their first choice has been discarded

Sure, I'm not actually saying that we look ahead in the ballot and eliminate those votes, in a real implementation, we would simply remember which candidates were in the first round and skip ballot preferences that point to a candidate that didn't receive any first choice votes.

LivingInSyn commented 5 years ago

The problem is this: in round 1, you have Joe == 0. Truth is that Joe doesn't exist yet, as far as the rounds go

timotree3 commented 5 years ago

When I said "In a real implementation, Joe would be marked eliminated", that doesn't make sense because a real implementation hasn't seen Joe yet. I edited my comment.

timotree3 commented 5 years ago

Hi Jeremy, it seems to me like this solving this disagreement a matter of interpreting a reference document to decide how IRV is defined to behave. I apologize in advance if this post is too formal, I am just trying to talk precisely to avoid being misunderstood.

Given that you and I have both cited it, let's use https://en.wikipedia.org/wiki/Instant-runoff_voting#Process as our reference for what RCIRV is defined to do.

In instant-runoff voting, as with other ranked election methods, each voter ranks the list of candidates in order of preference. Under a common ballot layout, the voter marks a '1' beside the most preferred candidate, a '2' beside the second-most preferred, and so forth, in ascending order. This is shown in the example Australian ballot above.

The mechanics of the process are the same regardless of how many candidates the voter ranks, and how many are left unranked. In some implementations, the voter ranks as many or as few choices as they wish, while in other implementations the voter is required to rank either all candidates, or a prescribed number of them.

In the initial count, the first preference of each voter is counted and used to order the candidates. Each first preference counts as one vote for the appropriate candidate. Once all the first preferences are counted, if one candidate holds a majority, that candidate wins. Otherwise the candidate who holds the fewest first preferences is eliminated. If there is an exact tie for last place in numbers of votes, various tie-breaking rules determine which candidate to eliminate. Some jurisdictions eliminate all low-ranking candidates simultaneously whose combined number of votes is fewer than the number of votes received by the lowest remaining candidates.

Ballots assigned to eliminated candidates are added to the totals of one of the remaining candidates based on the next preference ranked on each ballot. The process repeats until one candidate achieves a majority of votes cast for continuing candidates. Ballots that 'exhaust' all their preferences (all its ranked candidates are eliminated) are set aside.

Specifically, the most relevant part to this disagreement is

In the initial count, the first preference of each voter is counted and used to order the candidates. Each first preference counts as one vote for the appropriate candidate. Once all the first preferences are counted, if one candidate holds a majority, that candidate wins. Otherwise the candidate who holds the fewest first preferences is eliminated. If there is an exact tie for last place in numbers of votes, various tie-breaking rules determine which candidate to eliminate. Some jurisdictions eliminate all low-ranking candidates simultaneously whose combined number of votes is fewer than the number of votes received by the lowest remaining candidates.

I think that this implies that a candidate who has run in the election and received no first preference votes would be eliminated first.

The interpretation you've presented is that this implies that out of the candidates that got > 0 first preferences, the candidate with the fewest preferences would be eliminated.

The key difference is our interpretation of the word "candidate" in this context. I think it means "a candidate who has run in the election," and you think it means "a candidate who has received first preference votes". (Specifically you said "vote getters from that round")

I understand why you would think this way, as you are someone who has probably thought a lot about the code in this crate, you are used to thinking about the problem in the way the code thinks about the problem.

However, if you take a step back from thinking about how it can be implemented and how our iterator based API works, and just interpret the word "candidate" in a Wikipedia article about a voting system that is designed to be worded clearly and is designed to be understandable to people who don't know about the topic, I think that "a candidate who has run in the election" makes much more sense than "a candidate who has received some first preference votes".

This post couldn't be complete without addressing your other point, which is "We can't 'eliminate' a candidate who we haven't seen in the iterators yet." This is true, in reality, I would recommend some variant of this option:

timotree3 commented 5 years ago

Further evidence of my argument is seen in

Ballots assigned to eliminated candidates are added to the totals of one of the remaining candidates based on the next preference ranked on each ballot. The process repeats until one candidate achieves a majority of votes cast for continuing candidates. Ballots that 'exhaust' all their preferences (all its ranked candidates are eliminated) are set aside.

Notice that this phrasing implies that any new vote that gets uncovered as a result of elimination will be assigned to a remaining candidate, implying that this Wikipedia article is written with the assumption that the algorithm never uncovers new candidates, implying that the complete set of candidates is known before beginning to do eliminations.

timotree3 commented 5 years ago

Looking back on this, I'm sorry that I used such a condescending tone in my last two posts. I figure you probably just created this small open source project without intending to put much time into maintaining it or arguing with strangers about it.

I still think there are some valuable points that I failed to communicate but I accept that it doesn't matter very much if this crate gets changed.

For the sake of my own completion here, I'm gonna make a fork of this project with the changes I'm picturing and then open some PRs here. I don't mind if you close them though. Sorry again and I hope you're doing well. -Timo