[EM] Super-majorities in ranked methods

[Blake Cretney]

Recently, I've been studying the issue of how to incorporate some form
of super-majority into a ranked ballot method.  For example, it is
common for a legislative body to require a 2/3 vote to amend its
constitution.  This gives an advantage to the status quo.  If there
are only two options available, the status quo and an alternative,
then the method is obvious.  However, if a body is choosing between
several options, one of which is the status quo, it is not obvious how
to incorporate a super-majority requirement.  I'm not going to discuss
whether super-majority requirements are actually desirable, just how
they can be incorporated into existing voting systems.

I'm going to look at the following methods:  IRV, pair-wise
elimination, Schulze, and Tideman.  The criteria I will use are GITC
(that's the one about clones), Paretto, and stability (which I am
about to define).

Stability--
If alternative X wins for some election, then alternative X must
still win if it is the status quo.

Hopefully my meaning here will become clear with a few examples.

Pairwise elimination--
In this method you repeatedly eliminate the candidate whose pairwise
marginal loss (from among non-eliminated candidates) is highest. 
Eventually only one candidate is left.  This is the winner.

---
Last Challenge

An obvious idea is to separate out the status quo from the other options. 
Carry out an election between the other options to find a provisional winner. 
Then, the provisional winner becomes the overall winner if it has a
super-majority against the status quo.  Otherwise, the status quo (SQ) wins.

Example with IRV.  Use C as SQ.  Require super-majority of 55 to 45

40 A B C
25 B C A
35 C B A

Separating out C, we get
40 A B
60 B A

So, B wins.  B also wins against C by 65 to 35, so B wins over-all.

But consider what happens if someone runs a clone of the SQ.

40 A B C C2
25 B C C2 A
35 C C2 B A

C2 is the provisional winner.  Since C beats C2, C wins over-all.  This is a
clear violation of GITC.

In fact, since cloning should not affect the result, it makes sense to allow
the SQ to run in the provisional race AND challenge at the end.  If doing this
changes the result, our method would fail GITC anyway.

Unfortunately, methods of this type either violate Paretto or GITC.  Here's
an example for Tideman and Schulze.  C is SQ.

40 A B C2 C
25 B C2 C A
35 C2 C A B

Provisional winner is A.  A loses to C.  C wins.  To make an example for any
method, find out who wins in

40 A B C
25 B C A
35 C A B

Then, clone the candidate with a pair-wise victory against this candidate,
with one of the clones unanimously preferred to the other, which is set as SQ.
 Now, if the method passes GITC the same candidate must still provisionally
win.  Since the SQ then beats that candidate, the SQ must win in violation of
Paretto.

---

Disqualification Round

One possibility is to start by eliminating all candidates who do not have a
super-majority against the SQ.  This is a simple solution, but it guarantees a
violation of stability.  Consider pair-wise elimination (IRV, Tideman, and
Schulze react the same for this example).

40 A B C
35 B C A
25 C A B

The greatest defeated is C, by B 75 to 25.

65 A B
35 B C

Now, A wins.  Set A as SQ.  If the election is held again, B is eliminated
because it doesn't have the requisite super-majority against A.  So, the
provisional election is

40 A C
60 C A

So, C is the provisional winner.  If its 60 to 40 win is considered enough of
a super-majority, then a violation of Stability has occurred.

The basic problem is that options are helped by the presence of other options
that they defeat.  When these options are eliminated, it becomes much less
likely to win.

To make an example for any method, using a super-majority set at 60-40, find
who wins for no SQ

40 A B C
35 B C A
25 C A B

set this candidate as SQ.  The result will be a one-on-one race between the
SQ and the candidate that defeats it.  So, either the method is unstable, or
it does not pick the majority winner in a two option race.

---

Final Round Super-Majority

The two methods (IRV and Pairwise elimination) that end in a one-on-one
showdown suggest a possibility.  If one of these options is the SQ, the other
must get a super-majority in order to win.  Otherwise, it ends normally. 
Unfortunately, this violates GITC.  Consider a super-majority requirement of
61 to 39.  B is SQ.

60 A B
40 B A

Clearly B wins.  However, with a B clone introduced

60 A B2 B
40 B2 B A

Either method eliminates B on the first round.  The showdown is between A and
B2.  B2 has no SQ protection, so A wins.  This violates GITC.
---

Pairwise Manipulations.

Consider for the moment only the pairwise methods.  We might hope to enforce
a super-majority requirement by making modifications in the pair-wise matrix
before the method is applied.  For example, we could add votes to the SQ
against each of its opposition.  I'm going to use Pairwise elimination.

40 A B C
35 B C A
25 C A B

   A   B   C
A  X   65  40
B  35  X   75
C  60  25  X

Use C as SQ.  Use Subtract 11 from one side, add to other

   A   B   C
A  X   65  29
B  35  X   64
C  71  36  X

B wins.  But with B as SQ.

   A   B   C
A  X   54  40
B  46  X   86
C  60  14  X

A wins.

I'm not going to go through every possibility along these lines.  The problem
is that it can be more advantageous to have another candidate's victories
increased than your own.  Other people may want to pursue methods along these
lines, but it looks like a dead end to me.
---

Anyone Passes=Everyone Passes

Another idea is to say that if no one gets a super-majority against the SQ,
then the SQ wins, otherwise the election is held as normal.  This violates
either Paretto or GITC.  I'll assume both are obeyed in order to form a
contradiction.

Assume a super-majority of 80-20 is required.  Determine who wins this

40 A B C
35 B C A
25 C A B

I'll assume A wins, but explain how to form the example for B or C.  Take one
of the losers and set it as SQ.  I'm going to use B.  No candidate has an
80-20 victory against any other, so this SQ must win on the example above. 
Clone this candidate and set the non-SQ clone to beat the SQ on every ballot.

B is SQ
40 A B2 B C
35 B2 B C A
25 C A B2 B

Now, if the method meets GITC, either our chosen option (B) or its clone (B2)
must win.  If the method meets Paretto, this means the clone (B2) must win. 
Since the clone (B2) is not the SQ, and after the initial check the method
proceeds without regard to SQ, the clone (B2) must win the election even
without any SQ.

But, also by GITC, this means that our chosen option (B) would have to win in
the initial example given, and this option was chosen to be this winning
option.

---

Use of Method Orderings

Most methods can be used to completely order a list of options, instead of
picking a single winner.  One possibility is to completely order the options,
and then pick the highest qualifying option.  Since the list would be made
without regard to who was SQ, we might hope that the resulting method would be
stable.

But consider an ordering

1. A
2. B
3. C (SQ)

with A->B->C->A each -> corresponding to a super-majority

With C as SQ, A is disqualified, so B wins.  However, with B as SQ, A is no
longer disqualified, so it wins.

One way to make this work is to require that an option, in order to qualify,
must both get a super-majority against the SQ, and not have any
super-majorities against it from any higher options.  This way, it has a
"right" to win, but also will be able to hold on to the victory when it is SQ.

This is the first method I have mentioned which achieves the goals I set out.
 However, let me suggest a reason not to be entirely satisfied.  We might
expect that the super-majority requirement would be of vanishing effect as it
is reduced to a simple majority.  However, even if the super majority is set
equivalent to a simple pair-wise majority (victory), this method will still
has a significant bias in favor of the status quo.

To design a method where the SQ is not so favoured, it was necessary to
discard another property.  The above method ensures that only an option with a
super-majority against the SQ may win.  However, this is not necessary.  We
might instead decide that it is enough that SOME candidate has a
super-majority against the SQ.

I am going to assume that a super-majority is defined in such a way that a
super-majority is considered greater than other majorities for the purposes of
each of the following methods.  All of them involve effectively creating a
path of super-majorities from the new winner to the SQ.

Schulze

If no option ranked higher than the SQ has a path of super-majorities leading
to it, than the SQ wins.  Otherwise, pick the highest ranked option with a
path of super-majorities leading from it to the SQ.  

Pairwise-elimination

When no remaining majorities are super-majorities, the procedure ends and the
SQ wins.  When the SQ is defeated, the responsible candidate (the candidate
with the victory) becomes the new SQ for the remainder of the procedure.

The inherited SQ trait is necessary to avoid violation of GITC, as follows:

Super-Majority of 80 vs. 20 required.  C is SQ.  

40 A B C
35 B C A
25 C A B

C wins.

vs.

40 A B C2 C
35 B C2 C A
25 C2 C A B

C is eliminated by C2, C2 is eliminated by B, A wins. 

Tideman

Proceed with Tideman as normal, but when all the super-majorities are
exhausted, every candidate without a locked path to SQ is eliminated
(alternately you could lock a SQ victory against each of them).  Then,
continue as normal.

Equivalently, carry out Tideman as normal.  Tideman gives you a complete
ordering of the options.  Pick SQ itself if it is ranked higher than all
options that have locked super-majority paths to SQ.  Otherwise, pick the
highest ranked option that has a locked super-majority path to SQ.  

Stability

I'm not going to prove stability for Pairwise elimination right now, but I
will for Schulze and Tideman.  Understand that for Schulze a super-majority
path is simply a path made up of super-majorities.  For Tideman consider it a
path of locked super-majorities.

Consider that both methods work by

1.  Listing all candidates in a way unaffected by who is SQ.
2.  Picking the FIRST candidate who is not disqualified.

Now, the SQ itself is never disqualified, so these methods cannot allow the
SQ to move further down the list, only up the list.

If we start with no SQ, then the first option on the list must win.  So,
since the SQ can only move up, it follows that in this case the SQ cannot move
at all, and the method will be stable.

The only example of instability would be an SQ that starts at one position,
after an election moves up to a second position, and after an identical
election (one that produces the same list) moves to a still higher position. 
I will call these option C, B, and A, respectively.

For B to win when C is SQ, B must have a super-majority path to C.  For A to
win when B is SQ, A must have a super-majority path to B.  So, A must have a
super-majority path to C.  But, if A has a super-majority path to C, it is not
disqualified when C is SQ, so B cannot win when C is SQ.  Any attempt to form
a violation of stability results in contradiction.

---

Blake Cretney