[EM] Independence of Covered Alternatives

[John]

(Not subscribed at the moment, please copy me directly)

Came up with a runoff method that, when electing one, is independent of
covered alternatives.  Literally has a straightforward elimination process,
it's pretty much Bucklin count in reverse, always elects from the uncovered
set, is totally unaffected by candidates that aren't in the uncovered set,
DEFINITELY not monotonic.  This raises three questions:

1.  What does this mean when using this method for multiple winners?

2.  If there's actually some kind of explanation of the pairwise
relationships here as there is with the Smith set and the uncovered set,
can we make a method that satisfies PSC and provides proportionality for
non-solid coalitions (RNB does) with only the pairwise votes, or some other
reduced amount of information?  (There are several ways to reduce the
information to something summable into a graph like with the pairwise
votes, e.g. noting that at each rank R for each candidate C, other
candidates X appear directly above them on some number N[C,R,X] of ballots,
but none seem to strike me as making any sort of sense)

3.  …is there a way to tweak Ranked Pairs to not look for the uncovered
set, but to be ICA anyway, in the same way that it makes no attempt to
explicitly seek out the Smith set but is ISDA?  (Solving #2 would solve
this, possibly with a process more complicated than Ranked Pairs, and if
the resulting process is complex and non-monotonic I would still consider
Ranked Pairs better due to the ease with which the average joe on the
street understands the Ranked Pairs rule.)


In researching STV, I came across Chris Geller's 2005 work on STV-B (which
turned out to be extremely broken, because Borda compacts top-ranked
choices as you have more candidates), modified it to Nauru-STV (which
avoids that problem, but still cuts back your voting power when you rank a
weak candidate first), and then in trying to fix THAT ended up creating the
Reverse-Bucklin method.

When electing a single winner, Reverse-Negative-Bucklin in
particular—eliminating by Bucklin count rather than vote count—always
elects from the uncovered set, and is independent of covered alternatives.
The multi-winner process is as follows:

1.  Canonicalize all ballots.  If any ranks are empty, renumber all further
ranks to close that gap.

2.  Calculate all vote transfers using the current quotas.  (There is a
process for equal-ranked candidates; let's ignore that for now.)

3.  If any candidate has a quota of votes, elect the SINGLE CANDIDATE who
still has a Bucklin count above quota when truncating at the highest rank,
or else of those new winners retaining a quota at rank R such that none has
a quota at R-1, elect whichever has the highest Bucklin count at rank R.

4.  If all seats are filled, end.

5.  If a candidate was elected, return to 2.

6.  Set r=n for n non-eliminated candidates.

7.  Count up all candidates appearing on all ballots truncated to rank r;
this is their Bucklin count.  [Note:  carry out vote transfers, except that
for non-elected, non-defeated candidates, they transfer their full vote
forward as the Bucklin count; or more simply put, for a given candidate on
a ballot, multiply the fractional transfers of all winning candidates above
them, and if there are no winners above them then the ballot contributes 1
to their Bucklin score]

8.  If any candidates have a Bucklin count below zero, eliminate the
candidate with the lowest Bucklin count, then go to 1.

9.  Set r=r-1.

10.  Go to 7.


Two notes in the multi-winner case:  I have a process for candidates at
equal rankings; and as per step 3, I'm still tinkering around with
transferring the votes (and transferring Bucklin counts in the opposite
way, that being that the full fractional vote transfer passes through any
unelected hopeful when accounting for their Bucklin score) during this
count in a way that's not insane (it's the same problem as transfering
votes under Meek's method, being that it's iterative and so never quite
right—Meek's method even has provisions to deal with an oscillation where
the count never ends).

The single-winner case doesn't have those issues because there are no vote
transfers, in the same way that every STV method that eliminates by
vote-count is equivalent in the single-winner case.


So let's talk about the single-winner case.


There is a reason I specify ONE election and ONE elimination, no batches.
I had thought this was independent of Smith-dominated alternatives because
for Candidate X to have a majority over Candidate Y, Candidate X must
appear above Candidate Y on a majority of ballots (duh).  The approach here
is that when truncating at rank R, all candidates appear on a majority of
ballots; but when truncating at rank R-1, SOME candidates are no longer on
a majority of ballots.  This had a problem:  SOME of those candidates were
in the Smith set; but the candidate who appears on the FEWEST ballots when
truncated to rank R-1 is NEVER IN THE SMITH SET because some candidate
ultimately must appear below ALL Smith candidates on a majority of ballots
below some rank.  Therefore, all non-Smith candidates are eliminated before
any Smith candidate.

That was…imprecise.

It turns out if candidate X beats candidate Y, and X beats every candidate
Y beats, the same proof for independence of Smith-dominated alternatives
also proves that Y must be eliminated before any alternative X does not
cover can be eliminated.

Basically, because X covers Y, Y cannot replace X in the win set; Y must be
eliminated before X; and, because a majority is the quota, Y cannot cause X
to replace another winner or vice versa, i.e. the elimination order doesn't
matter until only uncovered alternatives remain.  It's totally independent
of covered alternatives, if I have this right.

This does REALLY WEIRD THINGS in the multi-winner case, by the way:

17 Alex ≻ Bobbie ≻ Chris
16 Bobbie ≻ Alex ≻ Chris
11 Dane ≻ Ed ≻ Fran
12 Ed ≻ Fran ≻ Dane
13 Fran ≻ Dane ≻ Ed
16 Giorgi ≻ Hans ≻ Ingrid
15 Ingrid ≻ Hans ≻ Giorgi

Above, when electing 3, quota being a number exceeding 25
(Hagenbach-Bischoff), you end up electing Alex, Fran, and Giorgi.

Fran makes sense:  Ed is the weakest of the three in the first 2 ranks
(11+12, vs 11+13 and 12+13) and is eliminated first, and then it becomes a
runoff to 25 just like any other STV method because they don't lose quota
until rank 1.

You end up electing Giorgi because when evaluating at rank 2, Giorgi and
Ingrid miss quota, and Ingrid appears on fewer ballots up to rank 2, so
Ingrid is deleted, and then you run off the same way.

17 Alex ≻ Bobbie ≻ Chris
16 Bobbie ≻ Alex ≻ Chris
11 Dane ≻ Ed ≻ Fran
12 Ed ≻ Fran ≻ Dane
13 Fran ≻ Dane ≻ Ed
16 Giorgi ≻ Hans ≻ Ingrid
15 Ingrid ≻ Hans ≻ Chris ≻ Giorgi

THIS ELECTS HANS.  Giorgi gets eliminated when evaluating at R=3.

17 Alex ≻ Bobbie ≻ Sam ≻ Chris
16 Bobbie ≻ Alex ≻ Sam ≻ Chris
11 Dane ≻ Ed ≻ Fran
12 Ed ≻ Fran ≻ Dane
13 Fran ≻ Dane ≻ Ed
16 Giorgi ≻ Hans ≻ Ingrid
15 Ingrid ≻ Hans ≻ Chris ≻ Giorgi

THIS elects Giorgi:  Chris only appears on 15 at rank 3, Giorgi appears on
16.  Yes, the presence of Sam up top now matters.

Take note that neither Giorgi nor Hans appear above one another on a quota
of ballots; Hans appears above Chris on a quota in both of the latter two
cases.  That means Chris can't replace Hans in the win set; but at the same
time, it doesn't mean that Giorgi or Ingrid can't replace Hans.  So, if
Chris is a winner, one of Hans, Giorgi, or Ingrid must be a winner.

Likewise, Alex and Bobbie appear above Chris, so Chris can't displace
either of them (if Chris wins, one of Alex or Bobbie must win).

Dane, Ed, and Fran all appear above Chris on a quota of ballots, and vice
versa.  They also appear above every OTHER candidate on a quota of ballots,
AND below every candidate on a quota of ballots. so the win set must
include one of them.

How all of this comes together to make any sense is still a mystery to me.
The principles which drive the behavior of the single-winner case are
active in the multi-winner case, but I don't have a generalization of what
those principles are—what in the heck is the analogue of the "uncovered
set" when your quota is Votes/(1-n) for n winners?  What in here is
analogous to a cycle, and how do they break?

I hate runoffs.  They're ridiculously difficult to count.  These questions
are inherently interesting because they may lead to an equivalent rule that
uses pairwise statistics instead of carrying out a runoff process—that is,
a vastly-superior rule that requires the ballots to be enumerated only
once, rather than repeatedly counted, modified, and recounted (counting
Ranked Pairs in a computer program is vastly simpler than counting Instant
Runoff Voting in a computer program).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20211025/df88e796/attachment.html>