Recursive IRV

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.

@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.

@rob Sorry for being so bothersome. The Javascript function naturally has a lot of overhead, which makes it quite hard to analyse and parse. (For instance, all the data structure overhead is not needed for a pseudocode) Maybe this is just me, though.

rob

@spelunker said in Recursive IRV:

Sorry for being so bothersome.

Not at all, I appreciate your taking an interest.

Do you know any programming language? I think the JS implementation is quite nice and clean, as is most of ChatGPTs stuff. It is cleaner than if I wrote it directly, unless I had put a huge amount of effort in. However, if you know python or whatever, I can ask chatGPT to produce a python version. It's quite good at that.

The code could be simplified if I removed the part where it passes back data so we can show a big nested json structure as output. If all you want is a winner, the code would possibly be easier to read, but not easier to follow by running a CodePen since there'd be no output of "process"

That said, the easiest way to follow it is to follow the chatgpt conversation as I prompted it to build it. Not only can you see what I asked it in plain English, it explains the code in plain English.

Do you at least get the main idea? Let me try to put my thoughts into a logical series of statements, starting with the most simple and obvious.

Plurality can be applied to ranked ballots. That is, you can count the first place votes and ignore all the rest.

Plurality voting can be used to find either a "good candidate", or a "bad candidate". The best candidate is defined as having the most first choice votes. The worst is defined as having the fewest first choice votes. (ties are possible and need to be accounted for, but for the rest of this we'll ignore them)

Plurality logic is used within IRV. In this case, it looks for bad candidates, since it needs to eliminate these candidates. So regular IRV could be said to eliminate plurality losers.

IRV can be used to find a bad candidate, just as plurality can. To do this, we eliminate good candidates (plurality winners) one by one. So both Plurality voting, and IRV voting, are able to produce an inverse result (i.e. "loser")

Given that IRV can produce an inverse result, it can be substituted for Plurality within IRV logic. So we can produce a recursive IRV, that calls inverse IRV, to determine who to eliminate. That IRV election, though, calls into Plurality to produce its result. This is one level of recursion.

And we can continue doing this to any depth. If the depth is an odd number (1 being normal IRV, 2 being the above described first level of recursion), it will always use inverse plurality. If the depth is even, it will use regular plurality. (notice that there doesn't appear to be any different results with odd vs even recursion depth. It just seems to get more accurate at greater depth)

Let me know if any of this helps, or if you want me to try to put it in another language or form.

Jack Waugh

You propose recursive application of Hare. Recursion could also be applied to other IRV variants. I don't know whether they produce "better" results or converge faster.

rob

@jack-waugh said in Recursive IRV:

Recursion could also be applied to other IRV variants.

Which IRV variants? Just curious.

The algorithm I currently have could work with various differences, such as instead of doing plurality as the last step, it does something like Score or Borda count. Or considering that the winner is the one with the least last place votes.

My hypothesis, far from proven, is that they would all converge to the same result. If that were actually proven, that would be pretty notable, I'd think.

Jack Waugh

Bottom-two Runoff and Reverse STAR.

Short of a formal proof, we could try some examples and see whether they conform to your hypothesis that the variants and recursive Hare converge to the same results.

rob

@jack-waugh I would describe bottom two runoff as a baby step toward recursive IRV. It goes just far enough to guarantee condorcet compliance, while one level of recursion ("hare squared as I used to call it) goes further, I think. Multiple levels of recursion go further, with infinite recursion being as far as it could theoretically go.

I just wouldn't consider Reverse STAR an IRV variant, really. Reverse STAR is two stage, but I can't see how you can extend that much further. Short of doing what I suggested above, use IRV recursion, but when it gets to maximum depth, using Score rather than Plurality. As I mentioned, I think that would converge to the same results as using plurality at final stage.

@rob Thanks Rob, the plain English is just what I needed. I will think about it