Talk:IRV Prime

This is the discussion page (the "Talk:" page) for the page named "IRV Prime". Please use this page to discuss the topic described in the corresponding page in the main namespace (i.e. the "IRV Prime" page here on electowiki), or visit Help:Talk to learn more about talk pages.

LNH and Condorcet incompatibility

Hello, Condorcet and Later-no-harm are incompatible - see proof in Woodall. Could you run your method through the example provided there and update the article? Kristomun (talk) 09:12, 31 July 2021 (UTC)

So if you look at Woodall's full paper, he does not say they're incompatible:

 In general, CONDORCET is incompatible with LATER-NO-HELP, LATER-NO-HARM,
 MONO-RAISE-DELETE, MONO-SUB-PLUMP and, in the presence of PLURALITY, MONO-ADD-TOP. 

"in general" --Marcosb (talk) 22:39, 3 August 2021 (UTC)

That's just a figure of speech. Let me quote from the reference I provided:

Theorem 2 says that if an election rule satisfies Condorcet's principle, then it cannot possess any of the seven properties that are crossed in the column headed 2 in Table 1.

(emphasis mine.) The crossed properties are participation, four different monotonicity properties, later-no-help, and later-no-harm. Woodall then proceeds to prove this impossibility; if it were indeed only true some of the time, then one would imagine these proofs would contain the necessary qualifications, but they do not claim any such qualification beyond that the method must pass Condorcet. Kristomun (talk) 09:17, 4 August 2021 (UTC)

There is a problem with the proof, though; it starts with:

 Without loss of generality, suppose a is elected in P. But c becomes the Condorcet winner, and so must be elected by CONDORCET

The theorem begins with the premise that both of those are possible, i.e. that a wins & c can become the Condorcet winner simply by modifying later preferences. But I believe those premise may be unsatisfiable.

The question is: how does a win? And if a wins, is it possible to make c the condorcet winner without putting c above a? (in IRV-prime, it's impossible to fulfill both premises; either a doesn't win, or c cannot be made a condorcet winner)

It's like starting with "suppose the tree exists and the tree doesn't exist" - you can make a lot of faulty theorems by starting with premises that cannot all be satisfied.

By the way, thank you so much Kristomun for the discussion & for your time, very much appreciated!

--Marcosb (talk) 16:41, 4 August 2021 (UTC)

Was looking a little deeper at the theorem:

 there must be a profile P arbitrarily close to this (in the proportions of ballots of each type) that does not yield a tie

The problem is, such a profile P may make it impossible for c to become the Condorcet winner; looking at all the profiles P where a wins (we must increment by 2 otherwise we continue to have a tie):

(updating to use N to hopefully become clearer --Marcosb (talk) 21:52, 4 August 2021 (UTC))

P1:

abc: 3N + 2
acb: 2N
bca: 3N
bac: 2N
cab: 3N
cba: 2N

P2:

abc: 3N
acb: 2N + 2
bca: 3N
bac: 2N
cab: 3N
cba: 2N

P3:

abc: 3N + 1
acb: 2N + 1
bca: 3N
bac: 2N
cab: 3N
cba: 2N

It becomes clear that Profile P results in some unavoidable truths:

• If we add only a single abc or acb vote, a loses to or ties with c (a=7N + 1, c = 8N); so we must add 2
• For N=1, a is the Condorcet winner (& the premise "c is the Condorcet winner" does not hold); for any N>1, a loses to c (& thus the premise "a wins in P" does not hold)
• If we add 2N instead of 2 (to meet the premise "a wins for all N"), then a becomes the Condorcet winner for all N

--Marcosb (talk) 17:20, 4 August 2021 (UTC)

There's also P4 (realized from offline discussion with Marcus):

abc: 3N + 2
acb: 2N
bca: 3N
bac: 2N + 1
cab: 3N
cba: 2N

Which has some different truths:

• For all N, a wins in IRV (c is eliminated, a wins against b)
• For N=1, a is the condorcet winner (& thus the 1st premise, that c becomes the condorcet, doesn't hold)
• For N>=2, a does not win in IRV-Prime (& thus the 2nd premise, that a wins, doesn't hold)

--Marcosb (talk) 00:57, 5 August 2021 (UTC)

So continuing my offline conversations, P4 demonstrates how IRV-Prime fails later-no-harm.

If we change cab voters to cba:

abc 3N + 2 acb 2N bca 3N bac 2N + 1 cba 3N cba 2N

N - 1:

a: 5N + 2 b: 5N + 1 c: 5N

N (aka b vs a): b: 10N + 1 a: 5N + 2

N-Prime (aka b vs c): b: 8N + 3 c: 8N

b wins, which means later-no-harm fails.

Dang it! Thought for sure it satisfied it, but it does not.

Thanks everyone for the discussion & for helping out!

--Marcosb (talk) 03:50, 5 August 2021 (UTC)

A few things:

Electowiki convention is usually to put the number of voters on the left, and the candidates separated by > or = on the right, like in my IIA example. There's a template for this, but it's yet only rarely used. (I used it in my example.) Also, replies can be indented by prepending a number of colons to the beginning of the message, and one usually replies with one indentation level more than the message that one's replying to. (Like I'm doing here.)

Second, while I think your example will work, note that there's the theoretical possibility that it's not an actual later-no-harm proof. It could be that the method fails later-no-help, and that the initial c>a>b ballot "helps" c get elected. Then replacing c>a>b with c>b>a could make c lose as a side effect of the later-no-help noncompliance, rather than because it fails later-no-harm. The example should start with the voters bullet-voting for c instead, c winning, and then the voters changing appending later ranks to make c>b>a and have c excluded -- if that works, otherwise you may have to tweak it a little. Kristomun (talk) 17:53, 5 August 2021 (UTC)

I've transposed the examples on the page you listed (elections 3-5) [to code], but not sure what I'm looking for:

       >>> IrvPrime().results(0,1,2,3,4,5 * 12 + 2,0,1,3,4,5 * 11 + 1,2,0,3,4,5 * 10 +
       ...     3,4,5 * 27)
       [1, 2, 3, 0, 4, 5]
       >>> IrvPrime().results(0,1 * 11 + 1 * 7 + 2 * 12)
       [1, 2, 0]
       >>> IrvPrime().results(0,3,2,1 * 5 + 1,2,0,3 * 5 + 2,0,1,3 * 8 +
       ...    3,0,1,2 * 4 + 3,1,2,0 * 8)
       [0, 3, 2, 1]
       >>> IrvPrime().results(0,2,1,3 * 6 + 0,3,1,2 * 3 + 0,3,2,1 * 3 +
       ...     1,2,0,3 * 4 + 2,0,1,3 * 4 + 3,1,2,0 * 5)
       [2, 0, 3, 1]

(0=A,1=B...; inputs are in >>> & ... lines, outputs are immediately following, where 1st element in the output = winner in single-winner election)

--Marcosb (talk) 20:42, 4 August 2021 (UTC)

Kristomun, thanks again for all your help & for clean-up to make it look nice! I ran out of time thus my lack of responses, but coming back to think about what you're suggesting: how would one prove whether a system is failing later-no-harm or later-no-help? I'm interested to see which one it's failing (it does seem like it may be later-no-help), but unsure how to come up with a proof.

--Marcosb (talk) 16:25, 27 September 2021 (UTC)

The easiest way to do it is probably just to try a lot of elections. First create a random (3-candidate) election with some voters using truncated ballots, note who wins, fill in those truncated ballots randomly one by one, and then checking if at any point a LNH failure occurs.

Let's say that the voter's ballot is A>B before and A>B>C after. If A or B won before and now C wins, that's LNHarm failure. If C won before but A or B wins after, that's LNHelp failure. You *could* try to devise a crafty mathematical proof, but with simple criteria like these, brute force is easier. Kristomun (talk) 21:05, 14 October 2021 (UTC)

Thanks! I think it'd be really nice to get a mathematical proof just because I don't have a lot of faith in simulations. I thought about this a bit more & I think the key is my original proof - I think it DID prove that the method satisfies later-no-harm & condorcet, but what I was missing was later-no-help. I updated the proofs, can you take a look to see if they make sense? --Marcosb (talk) 05:43, 18 October 2021 (UTC)

When it comes to disproofs, simulation can be just as effective as reasoning through the method. This because if you want to prove that some property X is not satisfied, all that's required is a single example. See e.g. https://cdn.paperpile.com/blog/img/lander-1966-700x394.png. If you want to produce a more general proof (like Woodall did) or find out some deeper structure (e.g. why it's impossible), then you'll probably need to reason, but not to merely establish that X is not satisfied. Kristomun (talk) 16:29, 19 October 2021 (UTC)

Arrow/IIA

As I understand it, the reference to satisfying Arrow's theorem is meant to imply that the method satisfies IIA. But I don't think that's possible.

In a Condorcet cycle like this:

35: A>B>C
30: B>C>A
25: C>A>B

Who wins in IRV Prime? If it's A, then eliminating B (irrelevant candidate) should make C win by majority rule. If it's B, then eliminating C makes A win; and if it's C, then eliminating A makes B win. I may be missing something, though! :-) Kristomun (talk) 22:22, 31 July 2021 (UTC)

Running through the IRV-Prime steps, first we do classic IRV, which eliminates C & finds winners={A}:

A: 60
B: 30

We now see if any candidate can win against A (we know B can't), i.e. WinnersPrime={C}:

C: 55
A: 35

And as such C is the winner in IRV-Prime; this is a classic case of A=Rock, B=Scissors, C=Paper; if I phrase it to you as "suppose B & C voters were to go up against A: which candidate should they stand behind?" then it becomes clear what IRV prime is trying to do (i.e. higher preferences of a candidate that can win)

--Marcosb (talk) 22:39, 3 August 2021 (UTC)

In that case, if C is the winner and IRV Prime is majority rule in the two-candidate case, eliminating A (an irrelevant candidate) will make B win, which is a violation of IIA. Kristomun (talk) 09:17, 4 August 2021 (UTC)

You're correct, thanks for that example. It does not fulfill IIA: (sorry I'm still learning this stuff)

 if one candidate (X) would win an election, and if a new candidate (Y) were added to the ballot, then either X or Y would win the election.

But if you look at the ballots, this actually makes sense from a social representation perspective:

35: B>C
30: B>C
25: C>B

B best represents the population.

However, when A enters the race, B no longer has the votes to win, so their voters must now compromise. By definition it's still a "spoiler candidate", but it's the opposite effect: in plurality, a spoiler results in a candidate that could win to lose (by vote splitting); in IRV-Prime, it causes votes for a candidate that was going to lose to shift to those voters' next favorite.

--Marcosb (talk) 16:18, 4 August 2021 (UTC)

That's okay - we all have to start somewhere! It also showed me that it would be a good idea to add the rock-paper-scissors example to the IIA article; I'll do that.

You might be interested in this: w:Independence_of_irrelevant_alternatives#Criticism_of_IIA, particularly the two final paragraphs. As you say, failing IIA might not be a problem, even if it does happen. Kristomun (talk) 17:53, 5 August 2021 (UTC)

Example of LNH failure

Consider the following votes:

102 A
101 B
100 C
5 A>B>C
5 B>C>A
5 C>A>B

A wins IRV (after C is eliminated) The Schwarz set is {ABC} A wins AB. C wins AC. So, WinnersPrime is {AC}. C wins {AC} Thus, C is overall winner.

....

Now, some C voters add a later preference:

102 A
101 B
100 C>B
5 A>B>C
5 B>C>A
5 C>A>B

B wins IRV (after C is eliminated). The Schwarz set is B. So B wins overall. -- unsigned comment by Jameson Quinn - 11:59, 19 October 2021 (UTC) (UTC)