Instant-Runoff Voting in JavaScript with Additional Votes

I was trying to implement IRV in JavaScript, but I only get 10 pairs of votes per 5 seconds (for development testing only), so it was impractical to add to an array each time that a new pair of votes arrive to a client. So I was wondering if there is any way of handle the data when it was received and keep consistency with the new data that will be received.

const candidates = ['candidate1', 'candidate2', 'candidate3'];

// I Will Receive more votes after 5 secs (or any in prod) that will replace this
let votes = [['candidate1', 'candidate3', 'candidate2'],
            ['candidate2', 'candidate1', 'candidate3'] /* etc*/];

// I Want to calculate the winner at the time
// But after 5 secs the array won't have the previous votes

I'am asking if there is any algorithm for calculate IRV Winner at the time, knowing that after some seconds later the previous values are gone, making it impossible to calculate in a normal way.

Is there any way that we can give points based on their position, that could be incremented and still get the winner?

This is what I came up with, but it doesn’t work as it should. But it should give you an idea of what I need.

// The Base Votes (only one for the demo)
let votes = [['candidate1', 'candidate3', 'candidate2']];

// Stores the Ranks Per Candidate
let ranked = [0, 0, 0];

// Calculates the IRV
function irv() {
    votes.forEach(vote => {
        let points = vote.length;

        vote.forEach((candidate, i) => {
            ranked[i] += points;
            points--;
        });
    });
}

// Calculate the Winner at the time
irv();

// Add new Votes
votes = [['candidate2', 'candidate1', 'candidate3']];

// ReCalculate the Winner
irv();

// Show the Winner
console.log(ranked);

Following IRV it shoud give a tie between candidate 1 and candidate 2, this method gives us candidate 1 as the winner. Can you help me figgure this out or give me a better algorithm that can solve this problem?

Solution

Here's a (probably too simplistic) IRV implementation:

const irv = (ballots) => {
  const candidates = [... new Set (ballots .flat())]
  const votes = Object .entries (ballots .reduce (
    (votes, [v]) => {votes [v] += 1; return votes},
    Object .assign (... candidates .map (c => ({[c]: 0})))
  ))
  const [topCand, topCount] = 
    votes .reduce (([n, m], [v, c]) => c > m ? [v, c] : [n, m], ['?', -Infinity])
  const [bottomCand, bottomCount] = 
    votes .reduce (([n, m], [v, c]) => c < m ? [v, c] : [n, m], ['?', Infinity])

  return topCount > ballots .length / 2 
    ? topCand
    : irv (ballots .map (ballot => ballot .filter (c => c != bottomCand)) .filter (b => b.length > 0))
}

const ballots = [
  ['A', 'C', 'B', 'E', 'D'],
  ['B', 'D', 'A', 'F', 'G'],
  ['C', 'B', 'D'],
  ['B', 'D', 'E', 'A', 'H'],
  ['A', 'B', 'G', 'H', 'F'],
  ['G', 'E', 'B', 'H', 'D'],
  ['E', 'C', 'D', 'B', 'G'],
  ['A', 'B'],
  ['D', 'G'],
  ['F', 'E', 'C'],
  ['F', 'C', 'G', 'A', 'E'],
  ['B', 'C', 'G', 'A', 'E'],
  ['A', 'B', 'F', 'G'],
]

console .log (irv (ballots))

(Note that, as per my comment, I don't try to maintain any particular state between calls. If you need to accumulate ballots, I would suggest doing that separately, and then run this function when those ballots arrive. If that's too expensive, then it could be run on a fixed schedule based on the ballots received so far.)

Our ballots are simply an ordered list of candidate choices. In the end we choose candidate B by sequentially eliminating those with the fewest first-place votes and moving the remaining candidates on those ballots up one place higher.

The code first collects the candidates by flattening the list of ballots and choosing all unique members of collection. Then we count the first place votes for each candidate. This will be in the format [["A", 4], ["C", 1],["B", 3], ["E", 1], ["D", 1], ["F", 2], ["G", 1], ["H", 0]], which makes it easiest in the next two steps to find the top and bottom candidates, using reduce-based min- and max-choosers.

Here the algorithm is naïve, breaking ties by simply choosing the first one with that value, which is dependent upon ballot order. A full IRV system would have a better mechanism than this.

Then, finally, if the count for the top candidate is more than half the total count, we return that candidate. If not, we remove the bottom candidate from all ballots and rerun the function with the remaining candidates.

This version is recursive, as that leads to cleaner code. But note that recursion depths are not likely to be an issue, unless you have a race with thousands of candidates, as each recursive step reduces the number of candidates.

Walkthrough

in the first round we have these ballots:

ACBED, BDAFG, CBD, BDEAH, ABGHF, GEBHD, ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG

with these first-place vote counts:

{A: 4, B: 3, C: 1, D: 1, E: 1, F: 2, G: 1, H: 0}

We have no majority vote yet. Since H has the lowest count, we remove it from every ballot:


ACBED, BDAFG, CBD, BDEAH, ABGHF, GEBHD, ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG
ACBED, BDAFG, CBD, BDEA,  ABGF,  GEBD,  ECDBG, AB, DG, FEC, FCGAE, BCGAE, ABFG

With these first-place vote count:

{A: 4, B: 3, C: 1, D: 1, E: 1, F: 2, G: 1}

We randomly choose one of those with the lowest first-place counts, C, and remove it:

ABED, BDAFG, BD, BDEA, ABGF, GEBD, EDBG, AB, DG, FE, FGAE, BGAE, ABFG

{A: 4, B: 4, D: 1, E: 1, F: 2, G: 1}

Then we remove E:

ABD, BDAFG, BD, BDA, ABGF, GBD, DBG, AB, DG, F, FGA, BGA, ABFG

{A: 4, B: 4, D: 2, F: 2, G: 1}

Then G:

ABD, BDAF, BD, BDA, ABF, BD, DB, AB, D, F, FA, BA, ABF

{A: 4, B: 5, D: 2, F: 2}

And D:

AB, BAF, B, BA, ABF, B, B, AB, F, FA, BA, ABF

{A: 4, B: 6, F: 2}

And then F:

AB, BA, B, BA, AB, B, B, AB, A, BA, AB

{A: 5, B: 6}

And here we finally have a majority, and return B.