Improve handling of ties

[ggordn3r]

See here for an especially thorny example of many-way ties: https://rankit.vote/results/zDvGganVwjdYGafT2mLh/1

From Louis:

1. When a tie happens, it reports the tie in that round, but it waits until the next round to actually eliminate one of the tied candidates. These two things should happen in the same round. Louis says the tabulator resolves ties in the same round, but we don't currently get that information in the response. 2 potential solutions, either expand the response we get back to include that info or "look ahead" to the next round to see who is missing from the array and say that person is about to be eliminated.

2. When it's reporting the tie, it says: "So, the choices with the fewest votes, Bell pepper, Garlic, and Pesto, will be eliminated one at a time." But that's not accurate. What actually happens is that one of those choices will be randomly selected to be eliminated, and we don't know yet what will happen to the other choices. The app actually does the right thing; it's just the explanatory text that is wrong. Instead, we should identify the exact choice to be eliminated in the round summary and clarify, i.e. "X, Y and Z are tied for last. Y is chosen at random and eliminated. Voters who chose Y will have their votes redistributed to the remaining candidates based on their next preferences."

[proggeramlug]

I'm a bit at a loss here as to what to do. I went through the algorithm today and I know the problem, it has to do with the script randomly removing options that are tied.

So what should happen instead? Mind you this process is triggered every time someone votes, because of the randomness the results might vary vote-to-vote (that is, they will anyways, but they also might just because we pick a random looser in ties).

[ggordn3r]

@proggeramlug I don't really know what to do either. "Louis", the person who raised this issue, is the developer on the tabulator that we are using: https://www.rankedchoicevoting.org/universal_rcv_tabulator

The random removal is running as it should. That's how ranked choice voting works--if two choices are tied for last, it eliminates one at random. But Louis claims that we should be able to get the response after the script has run so that we can tell the viewer who is about to be eliminated.

Take a look at the tabulator and let me know if you see that as an option. If not, let's proceed with just this fix during the priority release:

Change the explanatory text in the Round Summary for when two or more candidates are tied to this: "X, Y and Z are tied for last. One of these will be randomly picked for elimination. Voters who chose it will have their votes redistributed to their next-favorite [custom label]."

We can request more information from Louis before the larger release

[ggordn3r]

An alternative solution would be to mention the person eliminated at the beginning of the next round, like in Slide 37 of the RCV design recommendations. @proggeramlug does this make more sense to you?

We'd keep the language I just suggested, i.e. "someone is about to be eliminated at random" in Round N then in Round N+1 say "X was eliminated and their votes redistributed..."

[proggeramlug]

Okay, I implemented this now, though we need to test it and maybe change/adjust the language.

See here: https://rankit.skelpo.com/results/I4cnPOhEjpqc0mnmo0Pp/2

[ggordn3r]

Adjustments to language:

Round 2 should have no mention of the tie for last because the focus is currently on choice "2", not any of the bottom choices. https://rankit.skelpo.com/results/I4cnPOhEjpqc0mnmo0Pp/2 Round 2's summary should read: We have a winner! 2 wins with 46% of the vote. 2’s votes in excess of the threshold will be redistributed to the remaining choices based on 2’s voter’s next preferences.

Round 3 should read: 3 is leading but no remaining choice has over 25% of the votes. One of the choices tied for last place, 4 and 5, will be eliminated at random. Voters who chose that will have their votes redistributed to the remaining choices based on their next preferences.

[proggeramlug]

Hmm, I'm not sure this is correct. In round 2 you can see that 3+4+5 all are tied and that's why a choice is removed randomly. In every round the system tries to determine all winners, so it's not quite accurate to say that round 2 is only focused on "2" as the winner.

Maybe I'm missing something?

[ggordn3r]

Yes, they are tied in Round 2, but the only difference between Round 2 and Round 3 is that Choice 2's votes have been redistributed. The elimination doesn't actually happen until Round 4, so Round 2 is too early to mention that a loser will be eliminated

The tricky part is that Round 1 names 2 winners, but takes 2 rounds to reallocate their votes. Here are the transactions that should be "in focus" each round:

Round 1 - Winners 1 and 2 declared, 1's excess votes will be reallocated in next round Round 2 - 1's votes have been reallocated, Winner 2 declared (again), 2's excess votes will be reallocated in next round Round 3 - 2's votes have been reallocated, no choice meets the threshold, lowest will be eliminated--since there's a tie, one will be eliminated at random and their votes reallocated in the next round Round 4 - 4 was eliminated, Winner 3 chosen, all winners chosen, poll is over.

[proggeramlug]

This is not exactly how the algorithm does it though. I'll check again, but it's tricky.

[ggordn3r]

Ok--if you share the way the algorithm treats each round, I may be able to find an intermediate solution.

Trey Gordner Founder, Koios (803) 570-2144 Website https://www.koios.co | Twitter https://twitter.com/koioslib | Join our Newsletter https://www.koios.co/join-koios-newsletter/ Helping libraries show up online

On Fri, May 1, 2020 at 1:43 PM Ralph Küpper notifications@github.com wrote:

This is not exactly how the algorithm does it though. I'll check again, but it's tricky.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/iambateman/RankIt/issues/100#issuecomment-622488375, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNMYBB3XBMDUADY3LWSX4LRPMC47ANCNFSM4LDEQVLQ .

[proggeramlug]

I'm trying to come up with a good way to explain the algorithm, let me just post the code and I explain what happens:

First off: The algorithm is called every time someone votes. So even after the votes have taken place, the algorithm stays the same and does the same thing, every time. It is stateless, it uses the votes in the system every time all over again.

We keep a list of the following:

  let name2totals = {}; // the names of the winners that have been cast already
  let name2ballots = {}; // the names of the ramaining candiates
  let name2weights = {}; // the current weight of the names

  // results arrays
  const rounds = [];
  const elected = [];
  const eleminated = [];

We also have:

  // THRESHOLD
  // Threshold is the number of votes that mathematically guarantees that the candidate cannot lose
  // Ex: 327 ballots / (2 winners + 1) = 109 + 1 = 110.
  // In a 2 winner race with 327 ballots, a candidate with 110 votes is guaranteed victory.
  const threshold = Math.floor(ballots.length/(winners+1))+1;

Now the next piece is the ongoing loop (rounds) that happens as long as it needs:

  // Factor
  let factor = 1; // To calculate the weight
  let elim; // the eliminated candidate
  let cans; // I think this is the remaining candidates

  // do...while the winner count is less than the "can win" count.
  do {

    // ITERATE OVER EACH BALLOT
    ballots.forEach(function(ballot, i) {
      while (ballot.length) { // do this loop for every candidate

        // grab the name of the vote and remove from the ballot array.
        let name = ballot.shift(); 

        // if it's the first round, everyone gets through.
        // otherwise, we check to see if name is in name2totals
        if (rounds.length === 0 || name in name2totals) {
          let new_weight = rounds.length === 0 || (name2weights[elim][i] * factor);
          name2ballots[name] = (name2ballots[name] || []);
          name2ballots[name].push(ballot);
          name2weights[name] = (name2weights[name] || []);
          name2weights[name].push(new_weight);
          name2totals[name] = (name2totals[name] || 0) + new_weight;
          break;
        }
      }
    });
   // at this point the round is done, so add the names to the current rount
    rounds.push({...name2totals});

  // Maxmium amount of votes for all names
    let mx = Math.max(...Object.values(name2totals));
  // we have a clear winner
    if (threshold <= mx) {
      winners--; // we have to find one winner less
      elim = Object.entries(name2totals).filter(x=>x[1]===mx)[0][0]; // who is the winner
      elected.push(elim); // push that winner in the elected array
      factor = (mx-threshold)/mx; // adjust the factor
    } else {
    // no clear winner

   // find the minimum value for all names
      let mn = Math.min(...Object.values(name2totals));
    // find the names for that value (might be more than 1)
      let mn_keys = Object.entries(name2totals).filter(x=>x[1]===mn).map(x=>x[0]);
     // pick one (!) random name out of the names
      elim = mn_keys[parseInt((Math.random())*mn_keys.length)];
// add to the eliminated array for this round
      eleminated.push({"round": (rounds.length-1), "name": elim, "from": mn_keys.length});
      factor = 1; // reset factor
    }

    ballots = name2ballots[elim]; /* Changing the Reference */
// remove the winner (or removed) candidate from the names
    delete name2totals[elim];

    //  Cans
    // counts the number of potential winners who remain
    cans = Object.keys(name2totals).length;
    // console.log(cans, name2totals);

  } while (winners < cans && winners > 0); // this is the condition for the outer loop to coninue

  if (winners !== 0) {
 // add potential winners here
    Object.keys(name2totals).forEach(x=>elected.push(x));
  }   
// this return value we save for every poll
  return {"elected": elected, "rounds": rounds, "threshold": threshold, "eleminated": eleminated};
} 

[ggordn3r]

Hmm. I haven't come up with any better ideas. Should we defer this to the next release, or have you thought of a way to implement what I commented above?

[proggeramlug]

Well, the way it currently works is how I would interpret it to be that case but it contradicts what you are saying. I feel like for a release soon (these days) this is too much of a dumpster fire to play with :D

[ggordn3r]

I agree. Can you roll back whatever you have implemented on this and I will move it to the full release?

[proggeramlug]

yes, rolled back!

[ggordn3r]

@proggeramlug I went back to the link above to confirm that the changes have been rolled back, but I think you've switched to "Do not show results" since then, since I can't see them anymore. Can you "Show results" again so I can confirm?

https://rankit.skelpo.com/results/I4cnPOhEjpqc0mnmo0Pp/2

[proggeramlug]

changed!

[ggordn3r]

Confirmed--moving this to the main release.

[proggeramlug]

@ggordn3r Need your input here, what should we change how? See our latest discussion above.

[ggordn3r]

Okay, based on our conversation today, here's what needs to change: https://github.com/iambateman/RankIt/blob/master/src/app/results/components/explanation/explanation.component.ts

eleminationStatement Delete lines 91-93, which are handled by noWinnerSummaryStatement Replace return "Last round we move "+el.name+" from the choices by random selection."; with return ""+el.name+" has been eliminated and their votes redistributed to the remaining ${this.label}s.";

noWinnerSummaryStatement I can't find a good way to rewrite this while preserving all of the abstraction, so I'm breaking it into two cases:

IF losers.count > 1 (in other words, if there is a tie for last): return ${leaders.string} ${isLeading} but no ${remaining}${this.label} has over ${this.percentToString(this.winning_percentage)} of the votes. Because there is a tie for last place, one of the losing ${losingCandidate} will be randomly eliminated. Their votes will be redistributed to the voters' next-favorite ${this.label}.;

ELSE keep it the same: return ${leaders.string} ${isLeading} but no ${remaining}${this.label} has over ${this.percentToString(this.winning_percentage)} of the votes. So, the ${losingCandidate} with the fewest votes, ${losers.string}, will be eliminated${oneAtaTime}. Voters who chose ${losers.string} will have their votes redistributed to the remaining ${this.label}s based on their next preferences.;

Let's test this after you implement #137 to make sure all the explanations still line up. I'll also check for conflicts in the message handling. As discussed above in the "focus" comment, the algorithm prioritizes resolving winners before resolving losers, so the statements should not rush ahead.

[proggeramlug]

Implemented, check it out!

[ggordn3r]

Whoops, I broke this.label in the eleminationStatement and noWinnerSummaryStatement by keeping the "s" too close. Can you fix? See screenshot.

Also, there's an issue with timing for the eleminationStatement. The text is right, but it's showing up 1 round too early. Right now it is appearing as its own paragraph at the bottom of Round N, "before" the relevant elimination happens in the graph. It should appear at the top of Round N+1, "after" the choice it references has been visibly eliminated in the graph. Does that make sense?

[proggeramlug]

Should be fixed!

[ggordn3r]

this.label is definitely fixed. However, I'm still seeing the other issue so let me be more explicit with an example:

In Round 1, this is the current Round Summary:

DuPont Circle, Adams Morgan, and Columbia Heights are leading but no remaining neighborhood has over 17% of the votes. Because there is a tie for last place, one of the losing neighborhoods will be randomly eliminated. Their votes will be redistributed to the voters' next-favorite neighborhood.

Navy Yard has been eliminated and their votes redistributed to the remaining neighborhoods.

Notice that the past tense is misleading because Navy Yard isn't visibly eliminated until Round 2.

We need to make the Round Summary match what's happening on the left side. Either of these solutions will work:

A) Comment out eleminationStatement and consolidate it into the noWinnerSummaryStatement so that IF losers.count > 1 (in other words, if there is a tie for last):

return ${leaders.string} ${isLeading} but no ${remaining}${this.label} has over ${this.percentToString(this.winning_percentage)} of the votes. Because there is a tie for last place, one of the losing ${losingCandidate} will be randomly eliminated: "+el.name+". Their votes will be redistributed to the voters' next-favorite ${this.label}.;

Note: check this code after pasting it in--I'm not positive it works.

B) Alter the handling so that eleminationStatement appears at the top of the next round.

With this solution, the Round 1 Summary would read:

DuPont Circle, Columbia Heights, and Adams Morgan are leading but no remaining neighborhood has over 17% of the votes. Because there is a tie for last place, one of the losing neighborhoods will be randomly eliminated. Their votes will be redistributed to the voters' next-favorite neighborhood.

And the Round 2 Summary would read:

Navy Yard has been eliminated and their votes redistributed to the remaining neighborhoods.

DuPont Circle, Adams Morgan, and Columbia Heights are leading but no remaining neighborhood has over 17% of the votes. Because there is a tie for last place, one of the losing neighborhoods will be randomly eliminated. Their votes will be redistributed to the voters' next-favorite neighborhood.

[proggeramlug]

Alright, I altered it and I think this is correct now.

[ggordn3r]

So close. I think you just used the wrong variable.

Current Round 2 Summary:

Physics is leading but no choice has over 50% of the votes. Because there is a tie for last place, one of the losing choices will be randomly eliminated: Kinesiology, Theater, and Pre-law. Their votes will be redistributed to the voters' next-favorite choice.

This is wrong because it lists all of the choices tied for last instead of the one choice eliminated this round.

Expected Round 2 Summary:

Physics is leading but no choice has over 50% of the votes. Because there is a tie for last place, one of the losing choices will be randomly eliminated: Theater. Their votes will be redistributed to the voters' next-favorite choice.

Theater is the specific choice eliminated (see Round 3) so it is the only one listed. The variable that was doing that before was +el.name+

[proggeramlug]

True, fixed it!

[ggordn3r]

Great! This reads so much better.