Recursive IRV

[Jack Waugh]

I'm thinking there must be a way to specify the recursion such that it will bottom out.

[rob]

@jack-waugh Yes if by "bottom out" you mean it won't change the ordering anymore, that should happen with just a few levels deep.

[spelunker]

@rob said in Recursive IRV:

Recursive IRV is a way of continuing this process of refinement by doing an inner process of elimination, in order to determine which candidate to eliminate in the outer process of elimination. So instead of using plurality to determine the "bad candidates" to eliminate, it uses plurality to determine the "good candidates" to eliminate from the determination of which are "bad candidates," and therefore to be eliminated.
To the degree that IRV improves upon plurality, this method can improve upon IRV.

I apologize, but I do not think I really understand what your method does. Especially this "it uses plurality to determine the "good candidates" to eliminate from the determination of which are "bad candidates," and therefore to be eliminated" part seems quite vague. Is there an easy fully description of the method?

[Jack Waugh]

@spelunker Maybe if I can convince myself to get off my butt and achieve things, I will get around to coding this in JS. Currently, I am rewriting part of the simulation framework, then I will return to debugging bottom-two runoff.

@rob means he wants to apply the Hare method recursively. A given specification of the recursive method might put a fixed limit on the depth of recursion. The bottom will just use Hare. If not at the bottom, conduct an IRV election among the remaining candidates to decide which one to eliminate from the list for the subsequent round of tallying.

[spelunker]

@jack-waugh said in Recursive IRV:

@rob means he wants to apply the Hare method recursively. A given incarnation of the method might put a fixed limit on the depth of recursion. The bottom will just use Hare. If not at the bottom, conduct an IRV election among the remaining candidates to decide which one to eliminate from the list for the subsequent round of tallying.

I am still not sure if I fully understand. "If not at the bottom, conduct an IRV election among the remaining candidates to decide which one to eliminate from the list for the subsequent round of tallying." This doesnt really make sense to me. Wouldnt this just eliminate a candidate with lowest plurality score?

[Jack Waugh]

@spelunker No, that is not the same thing. You might as well say that you could skip the top application of Hare and just elect the candidate with the highest plurality score and that would be the same as Hare.

[Jack Waugh]

The recursive method alternates between looking for a good candidate and looking for the worst candidate.

I have not checked @rob's assertion that just one level of recursion will make the system comply with Condorcet.

[spelunker]

@jack-waugh

Now I am fully confused. Would you be able to give a complete (and self-contained) description of the rule? (Pseudocode would also work)

[Jack Waugh]

@rob , this is kind of the key section of your code for this, right?

doEliminationLoop = (candidates, ballotsExp, isNegative) => {
  var results = {
    rounds: []    
  };
  var numCandidates = candidates.length;
  
  for(var i=0; i<numCandidates; i++) {
    var candidatesSorted = // (depth>0) ? 
        //sortedCandidatesByEliminationRounds(candidates, ballotsExp, true, 1) :
        sortedCandidatesByFirstPlaceVotes(candidates, ballotsExp);
    console.log(depth + " " + isNegative)
    console.log(JSON.stringify(candidatesSorted,0,2))
    var toBeEliminated = candidatesSorted[(isNegative)?0:candidatesSorted.length-1];
    results.rounds.push(candidatesSorted);
    //setValue('output_2', JSON.stringify(candidatesSorted,0,2))
    // maybe use Array.filter?
    candidates = []; // rebuild array without winner
    for(var j=0; j<candidatesSorted.length; j++) {
      if(candidatesSorted[j].name != toBeEliminated.name) {
        candidates.push(candidatesSorted[j].name);
      } 
    }
  }
  results.winner = results.rounds[results.rounds.length-1][0]
  return results
}

His condition on isNegative is key here. He's sorting the candidates the same way, based on top rankings, but he's picking whom to eliminate from the list from either the top or the bottom of the list.

[Jack Waugh]

@spelunker I could be vague on some details and we might need @rob to clarify, unless one of us wants to fully reverse engineer his code and see why it produced different results for the Burlington, Vt. election than what you would predict, @spelunker.

[spelunker]

This still very much seems like IRV and not Condorcet compliant though. Just imagine you have two voters and three candidates with preferences a>b>c and c>b>a. Wouldn't this method delete b in the first step which was the condorcet winner?

[Jack Waugh]

Thanks for giving an example to work.

Hare to the zeroth power is choose-one plurality.

Hare to the first power is Hare.

Hare squared does about (n - 1)(n - 1)/2 rounds, concerned with promotion of candidates rather than elimination of them.

I have three candidates and want to get down to two. Whom do I promote first? It's a tie between a and c. I have to appeal to @rob for tiebreaking rules, or make up my own.

Can you give an example that doesn't tie at any stage?

[rob]

@spelunker Hey sorry if my explanation wasn't clear. I actually started to develop a much better version, where you could choose any depth, and (the hard part) it had the ability to show output so it was understandable, but then I messed up and lost my code or something and dropped it for a while. (I'm sure I'll come back to it)

Look at it this way. What IRV attempts to do, prior to doing the final calculation (i.e. "determine who is preferred by more people"), is to remove irrelevant alternatives so the calculation is not affected by them. But it does the elimination rather crudely, based on "negative plurality". (least first choice votes)

This just takes it to another level, using the same logic for the elimination as it does for the final determination. As you go to further and further recursion depths, this should get more and more accurate, as the "crude part" is less and less relevant.

My general hypothesis is that Condorcet compliance is simply an easy to define step on the way to our goal of "immune to vote splitting." IRV logic is obviously closer to this goal than plurality, but since it can result in missing the Condorcet winner, it isn't very far toward the goal. Applying the logic twice appears to make it Condorcet compliant. Applying it 3 or more times moves it ever closer to the goal.

Since it is technically impossible to apply it an infinite number of times, this doesn't violate Arrow's theorem (and the like).

[Jack Waugh]

@rob This is sort of like engineered chess programs. They look ahead a certain number of moves and then resort to crude heuristics.

The ones that are not "engineered" use connectionism and/or Darwinism, but techniques like that are not relevant here. Before people tried those, they were engineering the solution, i. e. designing it top to bottom by hand.

[rob]

@spelunker said in Recursive IRV:

Just imagine you have two voters and three candidates with preferences a>b>c and c>b>a. Wouldn't this method delete b in the first step which was the condorcet winner?

It might, but I don't consider that a good example since to me it is (or should be) a three way tie.

If you have a case where there are no pairwise ties, and there is a Condorcet winner which it misses, I'd be interested in seeing it.

[Jack Waugh]

I believe it's a Copeland tie and a Dasgupta-Maskin tie.

a vs. b: no winner.

a vs. c: no winner.
c vs. b: no winner.

-|

[Jack Waugh]

I wonder whether it can be proven that adding more and more layers of recursion eventually converges on a fixed outcome, for any given set of ballots.

[rob]

@jack-waugh said in Recursive IRV:

I wonder whether it can be proven that adding more and more layers of recursion eventually converges on a fixed outcome, for any given set of ballots.

I'd love to see it proven. It seems to me that it is obviously true, but it is beyond my capabilities to actually prove it. Currently I am relying on intuition as well as just testing it on sample data.

[spelunker]

@rob said in Recursive IRV:

@jack-waugh said in Recursive IRV:

I wonder whether it can be proven that adding more and more layers of recursion eventually converges on a fixed outcome, for any given set of ballots.

I'd love to see it proven. It seems to me that it is obviously true, but it is beyond my capabilities to actually prove it. Currently I am relying on intuition as well as just testing it on sample data.

I could try to prove it, but I might need a more formal definition of the method for it. If possible not in JavaScript

[rob]

@spelunker Is there anything in particular you need explained or clarified?

While my current implementation is javascript, I didn't "write" it so much as prompted ChatGPT to write it, and since I did it very step by step, it should be easy to follow.

Here is the chatGPT conversation: https://sharegpt.com/c/fyOiNHy
It didn't make any mistakes, so it is pretty easy to follow, but I was careful in terms of prompting it to do one thing at a time.

Here is the codepen: https://codepen.io/karmatics/pen/KKxeEEJ?editors=1010

First I asked ChatGPT to parse ranked ballots and put them into a reasonable data structure. Then I had it so it could clone that data structure and remove a candidate (from the list of candidates as well as from the ballots), to allow for elimination.

Then I made a function "doPlurality" to do a plurality calculation on that, and return the winner(s) in an array (in case of tie it can be more than one). Then I had that function be able to do it inverted, to find the plurality loser.

Then I had it make a function "doIRV": to do an IRV tabulation on it, which in turn calls the "doPlurality" function multiple times, inverted so it picks the loser so that candidate can be eliminated.

Then I made sure doIRV could be inverted itself.

Finally, I made doIRV so it can recurse to a given depth, which means that, instead of calling doPlurality to find candidates to eliminate, it calls doIRV. (until it reaches the specified depth, when it will call doPlurality) Whether calling doIRV or doPlurality, it always reverses the "findLoser" flag from that sent to the containing function. (you want it to look for "bad" candidates to eliminate, but look for "good" candidates to eliminate from being eliminated, and so on)

I'm not sure what you are looking for as far as a formal definition, but if you need something else please let me know. Between my chatGPT prompts, the actual code, and the running app on CodePen it should be pretty concisely defined.

It would be awesome if you were able to do some kind of proof or at least an analysis.