Sync JS Code To Tally single-winner Hare IRV RCS

[Jack Waugh]

/* candidates */

let pros = ["Peterson", "Spain"];
let cons = ["Roy", "Farnam", "DeVita"];

let next = 0;
let arlingtonCandidates = [];
for (const {stance, names} of [
  {stance: 'pro', names: pros},
  {stance: 'con', names: cons}
]) {
  for (const name of names) {
    let index = next++;
    arlingtonCandidates.push({name, index, stance})
  }
};
console.log(arlingtonCandidates)
/*
  { name: "Peterson", index: 0, stance: "pro" },
  { name: "Spain",    index: 1, stance: "pro" },
  { name: "Roy",      index: 2, stance: "con" },
  { name: "Farnam",   index: 3, stance: "con" },
  { name: "DeVita",   index: 4, stance: "con" }
*/
next = undefined;

/* Model some voting factions. */

let fac0 = [
  {prop: .51 * .9, vote: [2, 3, 4], description: "Main antis"},
  {prop: .51 * .1, vote: [3, 4, 2], description: "Anti fringe"},
  {prop: .49,      vote: [0, 1],    description: "Pros"}
];

/* Model a Hare tally. */

let Round;
let Election = {
  beh: {},
  new: function () {return Object.create(this.beh)}
};
Object.assign( Election.beh, {

  reset () {
    this.factions = undefined;
    this.candidates = undefined;
    this.rounds = []
  },

  getInitialState () {
    /*
      From the parameter values of the election, derive and return a state
      object that can be fed into the first round of tallying.
    */
    let candidates, factions;
    candidates = this.candidates; /* all of them */
    factions = this.factions; /* unmodified */
    return {candidates, factions};
  },

  getStatus () {
    /*
      Respond by giving the status that should determine whether a subsequent
      round is appropriate.
    */
    let {rounds} = this;
    let {length} = rounds;
    if (length)
      return this.getStatusOngoing();
    else
      return ['keepGoing', this.getInitialState()]
  },

  getMajorStatus () {
    return this.getStatus()[0]
  },

  getStatusOngoing () {
    /* Private --
      assumes that at least one round of tallying has already happened.
    */
    let {rounds} = this;
    let {length} = rounds;
    let last = length - 1;
    return rounds[last].result
  },

  step () {
    /* Execute the next step of the tally. */
    let status = this.getStatus();
    if ('keepGoing' !== status[0]) throw Error(
      "Election over; no further step possible."
    );
    let round = Round.new(status[1]);
    this.rounds.push(round);
    return round.churn()
  }

});

Election.beh.run = function () {  /* verbosely */
  let {factions, candidates, rounds} = this;
  let ord;  /* One-based ordinal for humans. */
  console.log("Input:");
  for (const faction of factions) {
    console.log("  Faction", JSON.stringify(faction.description) + ":");
    console.log("    Proportion of the electorate:", faction.prop);
    console.log("    Vote rankings:")
    ord = 1;
    for (const dex of faction.vote)
      console.log("      %d %s", ord++, candidates[dex].name);
  };

  console.log("\nTally:");
  ord = 1;
  while ('keepGoing' === this.getMajorStatus()) {
    console.log("  Round %d:", ord++);
    this.step();
    let round = rounds[rounds.length - 1]
    for (const rc of round.candidates) {
      console.log("    ", rc.hareScore, rc.orig.name);
    }
  };
  let tied = this.getStatus()[1];
  if (1 === tied.length) console.log("\nWinner:", tied[0].name);
  else {
    console.log("\nTied for the win:");
    for (const cand of tied) console.log("  %s", cand.name);
    console.log("-|");
  }
};


Round = {
  beh: {},
  new (initState) {
    let r = Object.create(this.beh);
    r.initState = initState;
    return r
  }
};

Round.beh.cock = function () {
  /*
    Part of initialization to be called after the inputs have been supplied.
  */
  let {initState} = this;
  let candidates = this.candidates =
    initState.candidates.map(orig => ({orig, hareScore: 0}));
  let {factions} = initState;
  this.factions = factions;
  /*
    The total votes might not be 1 because:
    - users might supply factions having a different total, and
    - prior rounds might have exhausted factions and we need the total of the
      remaining factions' votes.
  */
  this.totalVotes = factions.reduce(
    (acc, cur) => acc + cur.prop
  , 0
  )
}

Round.beh.tallyHare = function () {
  /* Tally the round by calculating each candidate's Hare score.*/

  /*
    Assure that the votes, which use the original indices of the candidates, can
    be used to refer to our special models of the candidates, which are not
    necessarily in the original order.
  */
  let inverse = new Map();
  for (const cand of this.candidates) inverse.set(cand.orig.index, cand);

  let {candidates, factions} = this;
  for (const {vote, prop} of factions) {
    let top = vote[0];
    let topSrsly = inverse.get(top);
    topSrsly.hareScore += prop
  }
};

Round.beh.sortCandidates = function () {
  this.candidates.sort((a, b) => b.hareScore - a.hareScore);
};

Round.beh.placeFences = function () {
  /*
    Ties in large elections are rare, no doubt. However, an algorithm that does
    not take the possibility into account cannot signal virtue. Here, we look
    near both ends of the sorted list of candidates and fence off any tied
    groups touching the ends.
  */
  let {candidates} = this;
  let {length} = candidates;

  let bottomFence = length - 1;
  while (
    bottomFence > 0 &&
    candidates[bottomFence].hareScore == candidates[bottomFence - 1].hareScore
  ) --bottomFence;

  let topFence = 1;
  while (
    topFence < length &&
    candidates[topFence].hareScore == candidates[topFence - 1].hareScore
  ) topFence++;

  this.topFence    = topFence;
  this.bottomFence = bottomFence;
};

Round.beh.decide = function () {
  /*
    Determine the major outcome of the round: either someone wins, or we
    advise a subsequent round.
  */
  let {candidates} = this;
  this.majorDecision =
      this.topFence >= candidates.length
    ||
      candidates[0].hareScore > .5 * this.totalVotes
  ? 'winner' : 'keepGoing';
};

Object.assign( Round.beh, {

  infer () {
    /* Given our major decision, infer the consequences. */
    return this[this.majorDecision]()
  },

  winner () {
    /* Given that we know there is a winner, set up my result so to indicate. */
    let {candidates, topFence} = this;
    let tied = candidates.slice(0, topFence);
    this.result = ['tiedForTheWin', tied.map(({orig}) => orig)];
    return this.result
  },

  keepGoing () {
    /*
      Given that there is no winner yet, recommend a next round of tallying and
      supply the initial state for such.
    */
    let {candidates, factions, bottomFence} = this;
    let newCandidates, newFactions;

    let eliminate = candidates.slice(bottomFence);
    newCandidates = candidates.slice(0, bottomFence);
    let elimX = eliminate.map(({orig}) => orig.index);

    let trimmedFactions = factions.map( orig => {
      let vote = orig.vote.filter(x => ! elimX.includes(x));
      return {...orig, vote}
    });
    newFactions = [];
    for (const fac of trimmedFactions) if (fac.vote.length)
      newFactions.push(fac);
    else
      console.log("Exhausted", fac.description);

    return this.result = [ 'keepGoing', {
      candidates: newCandidates.map(c => c.orig), factions: newFactions
    }];
  },

  churn () {
    this.cock();
    this.tallyHare();
    this.sortCandidates();
    this.placeFences();
    this.decide();
    this.infer();
    return this.result
  }

});


/* We laid down a lot of code above. It's about time to try it out. */

let election = Election.new();
election.reset();
election.candidates = arlingtonCandidates;
election.factions = fac0;
election.run()

/*
  Roy wins, which is reasonable as the pro-MM crowd has the
  majority
*/

/* Let's stress-test the algo. */

let stress0cand = [
  {name: "A", index: 0, stance: "pro"},
  {name: "B", index: 1, stance: "pro"},
  {name: "C", index: 2, stance: "con"},
  {name: "D", index: 3, stance: "con"},
];
let stress0fac = [
  {prop: .25, vote: [0, 1], description: "Thetan Big-endians"},
  {prop: .25, vote: [3, 2], description: "Thetan Little-endians"},
  {prop: .25, vote: [1, 0], description: "Normal Big-endians"},
  {prop: .25, vote: [2, 3], description: "Normal Little-endians"}
];

election = Election.new();
election.reset();
election.candidates = stress0cand;
election.factions = stress0fac;
election.step()

[Lime]

If you're writing JS code on voting methods, you may want to talk to choco-pi on r/EndFPTP and his simulations.

[Jack Waugh]

Thanks for the cross-reference.