[EM] Immunity from Majority Complaints (IMC) & Condorcet's actual voting method (was Re: Burlington dumps IRV; Immunity from Majority Complaints (IMC) criterion)

[seppley at alumni.caltech.edu]

[I modified the Subject field because Burlington's dumping of Instant
Runoff is only a background context for this message.]
* * * * *
I agree with some of the points Jameson Quinn made in his reply (see
below) to my recent message, but I'll begin with where I disagree.

Jameson's assertion that a criterion should be deemed "too narrow" if it's
satisfied by only one voting method makes no sense to me.  The number of
methods that satisfy a criterion has nothing to do with how desirable it
is for society that the criterion be satisfied, nor with the relative
importance of criteria when a set of criteria can't all be satisfied.

In the case of the Immunity from Majority Complaints criterion (IMC),
satisfaction promotes stability and the perceived legitimacy of the voting
method and winner's mandate.  I presume these would be considered
desirable properties by mainstream political scientists.

Rather than being narrow, IMC is very general in the sense that matters:
The reasons that make satisfaction of IMC desirable apply to most election
contexts, including elections of public offices.
* * * * *
Jameson's assertion that Maximize Affirmed Majorities (MAM) was
"custom-built" also makes no sense.  MAM is no more "custom-built" than
any other voting method, and it was not designed with IMC in mind.  Like
Schulze's method, MAM was designed to satisfy top cycle, independence from
clones, and Mike Ossipoff's three strategy criteria (strong defensive
strategy criterion, weak defensive strategy criterion, and truncation
resistance).  MAM's earliest definition was: the method that selects the
order of finish that minimizes the size of the largest "thwarted"
majority. (Minimizes the largest in the minLEXmax sense.)  That early
definition is equivalent to the algorithmic definition of MAM--both
definitions select the same order of finish--but I think it's best to
define MAM using its (fast) algorithm in case many candidates compete, and
to guide people who wish to implement MAM. (Contrast this with
Kemeny-Young's method, which selects the order of finish that minimizes
the sum of the sizes of the thwarted majorities.  K-Y has no reasonably
fast algorithm.  K-Y also fails Independence from Clones, and of course
IMC.)

Only later, after proofs of MAM's satisfaction of many other criteria,
came the observations related to IMC: that MAM satisfies IMC, that only
MAM satisfies IMC, and that most other voting methods even fail weaker
criteria like WIMC and the even weaker Immunity from 2nd Place Complaints
(I2C) which requires the alternative that finishes second must not be
ranked over the winner by more than half the voters.  I2C is satisfied by
Kemeny-Young and Instant Runoff and of course MAM and presumably some
other methods, and is failed by Schulze, Borda, and many other methods.)

Thus MAM was not custom built, and IMC, WIMC & I2C were bonuses. (Two
other bonuses: MAM satisfies Local Independence of Irrelevant
Alternatives, which is a criterion promoted by Peyton Young in Equity in
Theory and Practice, and more voters rank MAM winners over Schulze winners
than vice versa in  computer simulations.)
* * * * *
MAM is also not "custom-built" in the following sense: MAM is the most
straight-forward interpretation of the voting method advocated by
Condorcet in the conclusion of his 1785 essay on probability and
elections. (Essai sur l'application de l'analyse à la probabilité
des décisions rendues à la pluralité des voix.)

Duncan Black clearly ignored Condorcet's conclusion when he wrote in The
Theory of Committees that Condorcet's method deletes the smallest majority
until an alternative is unbeaten pairwise.  Brams & Fishburn clearly
ignored Condorcet's conclusion when they wrote (several times) in the
social choice literature that Condorcet's method is MaxMin.  A number of
mathematicians clearly ignored Condorcet's conclusion when they criticized
Condorcet's method because, according to them, it elects no one when no
alternative is ranked over all others by majorities.

Here's what Condorcet actually wrote on page lxviii of his essay:

   Il résulte de toutes les réflexions que nous venon de faire,
   cette règle génerale, que toutes les fois qu'on est forcé d'élire,
   il faut prendre successivement toutes les propositions qui ont
   la pluralité, en commençant par celles qui ont la plus grande,
   & prononcer d'après le résultat que forment ces premières
   propositions, aussi-tôt qu'elles en forment un, sans avoir égard
   aux propositions moins probables qui les suivent.

Here's a literal translation for readers who understand English and not
French:

   The result of all the reflections that we have just done,
   is this general rule, for all the times when one is forced to elect:
   one must take successively all the propositions that have
   the plurality, commencing with those that have the largest,
   and pronounce the result that forms from these first
   propositions, as soon as they form it, without regard
   for the less probable propositions that follow them.

(Where Condorcet used the term "proposition" he meant a statement such as
"Candidate A shall finish ahead of candidate B.")

There's an ambiguity since "plurality" can be defined in two ways: it can
mean the larger of two numbers or it can mean the larger minus the
smaller.  This matters if voters' orders of preference can contain
indifference.  For example, which proposition comes earlier in Condorcet's
order of succession: proposition A supported by 54% and opposed by 46%, or
proposition B supported by 46%, opposed by 34%, with 20% indifferent? 
For the sake of Ossipoff's strategic properties, I interpret plurality as
the larger of two numbers and substitute the word "majority" which has a
similar connotation.  This matches Keith Baker's translation in his 1975
book Condorcet: From Natural Philosophy to Social Mathematics: "... take
successively all the propositions that have a majority, beginning with
those possessing the largest."  Thus proposition A comes earlier than B in
Condorcet's order of succession because A's 54% majority is larger than
B's 46% majority. (If you define plurality the other way, you have
Nicolaus Tideman's Ranked Pairs method, which Tideman "custom built" to
satisfy Independence from Clones and several other criteria, all of which
are satisfied by MAM.)

A key phrase in Condorcet's method is "commencing with those that have the
largest."  It clearly implies Condorcet's method is not Duncan Black's
"delete the smallest majorities until an alternative is unbeaten" nor
Brams & Fishburn's MaxMin.  It should also be fairly clear, after a little
thought, that what Condorcet meant by "the result that forms from these
first propositions, as soon as they form it" is about the transitivity of
the order of finish: The transitivity of larger majorities will cause the
thwarting of smaller "less probable" majorities that conflict.

To avoid confusion, I will use the name Largest Majority First (LMF) to
refer to Condorcet's method.  I will use the term "Condorcet winner" as
it's used in most literature, to refer to a candidate ranked over all
other candidates by majorities, not to refer to the LMF winner.

Here's how I describe LMF, and MAM, using modern terminology:

   Use the voters' orders of preference to count all the majorities
   of the round-robin tournament.  Then construct the order of
   finish a piece at a time by considering the majorities one
   at a time--from largest majority to smallest majority--
   placing each majority's higher-ranked alternative ahead
   of their lower-ranked alternative in the order of finish,
   except when their lower-ranked alternative has already
   been placed ahead of their higher-ranked alternative.

LMF and MAM can be described to a lay audience without needing to explain
subsets of candidates (such as the Smith set or the Schwartz set) or
cycles of majorities or Condorcet winners.  People already know what an
order of finish is.  Even children understand the transitivity of
orderings--if A is ahead of B and B is ahead of C then A is ahead of
C--which is all that's needed to understand the exception at the end of
the definition.

MAM is more refined than LMF, because Condorcet neglected to specify what
to do when two majorities are the same size or a pairing is tied.  Those
cases are rare when there are many voters, as in public elections. 
Technically, Condorcet's lack of specificity in those rare cases means
there is a small family of voting methods (which includes MAM) that are
consistent with LMF, which differ only on how they deal with same-size
majorities and tied pairings.  In a typical public election where no two
majorities are the same size and no pairing is a tie, every method in the
LMF family selects the same order of finish.  Only voting methods in the
LMF family can satisfy IMC.
* * * * *
I agree with Jameson that WIMC can be considered a refinement of the
Condorcet and Smith (a.k.a. top cycle) criteria.  They embody related
majoritarian principles, and satisfaction of WIMC implies satisfaction of
Smith, which in turn implies satisfaction of Condorcet. (And at the top of
the heap is IMC; satisfaction of IMC implies satisfaction of Condorcet,
Smith and WIMC, so IMC can be considered a refinement of Condorcet, Smith
and WIMC.)

However, there's a significant difference between the "majority rule"
argument traditionally made to justify satisfaction of Condorcet and/or
Smith, and the "stability" argument I've made to justify satisfaction of
IMC, WIMC & I2C.  I don't need to advocate majority rule to advocate
satisfaction of IMC, WIMC & I2C because these criteria are about what
happens when "majority rule" is advocated by a thwarted majority.  This
argument could be made to justify Condorcet and Smith too; they cover
fewer cases than WIMC and many fewer cases than IMC, but the cases they
cover are clearly dangerous cases where a thwarted majority could not be
rebutted using their own argument and would have an incentive to enact
change.

I also agree with Jameson that WIMC is more interesting than IMC.  It's
not unusual for a criterion to be more interesting than a stronger one,
because violating the weaker one tends to be more egregious: worse or more
dangerous for society.  As I pointed out, WIMC is about the dangerous case
where more than half the voters prefer a loser over the winner, whereas
IMC also covers less dangerous cases where a majority prefer an Nth place
finisher over an Mth place finisher and N > M > 1.  When Mth is not the
winner (M > 1, in other words) a majority who prefer Nth over Mth would
not be expected to have as strong an incentive to undermine the winner's
mandate or the voting method.

Burlington's dumping of Instant Runoff appears to be the aftermath of
Instant Runoff failing WIMC, not just IMC.  I've only had time to read one
of the EM messages discussing the event in Burlington, but the impression
I gathered was that Instant Runoff began by eliminating the Democrat who
was supposedly a Condorcet winner sandwiched between a Progressive to his
left and a Republican to his right.  If this is what happened in
Burlington, it means more than half the voters preferred the 3rd place
finisher (the Democrat) over the winner.  Obviously, no WIMC-based
rebuttal argument can exist anytime a Condorcet winner is defeated, so the
"majority rule" argument that favors a losing Condorcet winner can't be
trumped by a stronger "majority rule" argument.

(If FairVote were smarter or less @#&^$^#&, I think they would seriously
consider the variation of Instant Runoff that permits candidates to
withdraw after the votes are published online, before the winner is
determined.  A candidate who finishes second-if-no-one-withdraws could
choose to withdraw when she and her supporters prefer a
Condorcet-winner-who-finishes-third-if-no-one-withdraws over the
winner-if-no-one-withdraws.  Instant Runoff with Withdrawal is much better
than plain Instant Runoff at complying with WIMC and other criteria, and I
don't think it's less consistent than plain Instant Runoff with FairVote's
ultimate goal of proportional representation.)

Although WIMC is more interesting than IMC, my intuition tells me very few
voting methods satisfy WIMC yet fail IMC.  Here's an example of one such
method, which I'll refer to as Peculiar.  Peculiar is defined to be the
same as MAM (or the same as some other method in the LMF family) in all
scenarios except the following 4-candidate scenario:
   56% rank x over y.
   55% rank w over y.
   54% rank w over z.
   53% rank y over z.
   52% rank z over x.
   51% rank x over w.
In this scenario, Peculiar's order of finish is "arbitrarily" defined to
be wzxy for no good reason other than to provide an example of a voting
method that satisfies WIMC yet fails IMC. (xwyz is the order of finish for
methods in the LMF family.  They first place x ahead of y in the order of
finish, then w ahead of y, then w ahead of z, then y ahead of z.  Then
they thwart the majority who rank z over x because x has already been
placed ahead of y and y has already been placed ahead of z.  Then they
place x ahead of w.)

In this scenario, x is the only alternative ranked by a majority over the
Peculiar winner w.  Peculiar does not fail WIMC here because z is ahead
of x in the Peculiar order of finish and z is ranked over x by a majority
larger than the majority who rank x over w.  Thus Peculiar satisfies WIMC
in all scenarios.   Peculiar fails IMC here due to the majority who rank y
over z; no possible arrangement of a subset of alternatives is consistent
with all three IMC conditions. (For instance, the arrangement z,x,y fails
because the majority who rank z over x is smaller than the majority who
rank y over z.)
* * * * *
Regarding inclusion of IMC and WIMC (and I2C) in Wikipedia, I agree that
Wikipedia's policy regarding source material is an impediment.  However,
Electorama's Electowiki has different guidelines.  An article in
Electowiki and a discussion of IMC, WIMC and I2C in the EM maillist could
help to establish their notability for Wikipedia.

Regards,
Steve
---------------
Jameson Quinn wrote:
> IMC seems to me to be too narrow to be a general criterion, if only one
> custom-built voting system passes it. WIMC is an interesting refinement of
> Condorcet and Smith. But neither belongs on Wikipedia without a "reliable"
> citation.
>
> Jameson
> ------------------
> 2013/7/5 <seppley at alumni.caltech.edu>
>
>> FairVote wrote (elsewhere, cited in EM): "... the use of instant runoff
>> voting (IRV) for mayor was repealed this week by a margin of less than
>> 4%
>> in Vermont's largest city of Burlington. ..."
>>
>> That looks like a case where a voting method's failure of the Immunity
>> from Majority Complaints criterion (IMC) led to the voters dumping the
>> voting method.
>>
>> IMC is a criterion I wrote about in the EM maillist many years ago.
>> It's
>> motivation is this:  Suppose a majority rank x over y but x does not
>> finish ahead of y (in the election's order of finish).  They may
>> complain
>> that x should have finished ahead of y, using "majority rule" as their
>> argument.  If they are not rebutted, the voting method is on the
>> chopping
>> block since a majority have considerable power to enact change.  In the
>> most dangerous case, where y is the winner, y's mandate is undermined
>> and
>> the complaining majority would be especially motivated to replace the
>> voting method in order to elect x.  It would be problematic to try to
>> rebut (and placate) them by arguing the merits of criteria
>> (reinforcement,
>> participation, monotonicity, etc.) for which there is no consensus
>> regarding importance since the majority might not consider those
>> criteria
>> important, or might not understand them.  So it is desirable to be able
>> to
>> turn their own "majority rule" argument against them.  Therefore, the
>> voting method should satisfy the following criterion:
>>
>> Immunity from Majority Complaints (IMC)
>> ---------------------------------------
>> Let V(a,b) denote the number of voters who rank a over b, for all
>> alternatives a & b.
>> For all x & y, if V(x,y) > V(y,x) and the order of finish does not place
>> x
>> ahead of y, there must exist an arrangement a1, a2, ..., ak of a subset
>> of
>> the alternatives such that a1 = y and ak = x and all three of the
>> following conditions hold for each ai in {a1, a2, ..., ak-1}:
>>
>>      (IMC-1)  A majority rank ai over ai+1.
>>      (IMC-2)  The number of voters who rank ai over ai+1
>>                 is at least as large as V(x,y).
>>      (IMC-3)  ai is ahead of ai+1 in the order of finish.
>>
>> IMC-2 means the majority who rank ai over ai+1 is at least as large as
>> the
>> complaining majority for every ai in {a1, a2, ..., ak-1}. (When there
>> are
>> many voters, as in a public election, two pairwise majorities will
>> rarely
>> be exactly the same size.  So the majority who rank a1 over a2, the
>> majority who rank a2 over a3, etc., will all usually be larger than the
>> complaining majority.)
>>
>> Satisfaction of IMC allows the complaining majority to be rebutted using
>> their own argument:  By IMC-1 & IMC-2, majorities at least as large as
>> the
>> complaining majority said x should finish behind ak-1, ak-1 should
>> finish
>> behind ak-2, ..., and a2 should finish behind y.  And they do finish
>> that
>> way, by IMC-3.
>>
>> Condition IMC-3 matters because if some ai does not finish ahead of
>> ai+1,
>> the complaining majority can point out a flaw in the rebuttal: the
>> voting
>> method thwarted the majority who rank ai over ai+1 because it found
>> sufficient evidence that they are wrong about ai & ai+1; therefore those
>> voters do not contribute evidence that x should finish behind y.
>> This would be especially problematic if ak-1 does not finish ahead of x,
>> since in that case no evidence remains that x should finish behind any
>> alternative.
>>
>> Only one voting method satisfies IMC: Maximize Affirmed Majorities
>> (MAM).
>>
>> Satisfaction of IMC implies satisfaction of many other desirable
>> criteria:
>> top cycle (also known as the Smith set criterion), Condorcet,
>> independence
>> from clones, minimal defense (also known as Ossipoff's strong defensive
>> strategy criterion), etc.
>>
>> Most voting methods not only fail IMC, they also fail a criterion weaker
>> than IMC: Weak Immunity from Majority Complaints (WIMC): If more than
>> half
>> of the voters prefer some x over the winner w, there must exist an
>> alternative z such that both of the following hold:
>>      (WIMC-1) The number of voters who rank z over x is
>>                at least as large as the number of voters
>>                who rank x over w.
>>      (WIMC-2) z is ahead of x in the order of finish.
>>
>> WIMC is weaker than IMC in three ways:
>> (1) WIMC covers only the most dangerous case in which a majority prefer
>> a
>> loser over the winner.
>> (2) The complaining majority in WIMC is an absolute majority, more than
>> half the voters.
>> (3) Perhaps a less comprehensive rebuttal could suffice:  By the
>> complainers' own "majority rule" argument, x should finish behind z (and
>> does).  Thus x shouldn't be the winner (and isn't).
>>
>> WIMC is stronger than the Smith set criterion (which is stronger than
>> the
>> Condorcet criterion) because satisfaction of WIMC implies the winner is
>> in
>> the Smith set (also known as the top cycle, defined as the smallest
>> non-empty subset such that every alternative in the subset is ranked by
>> more than half the voters over every alternative not in the subset).
>> (Proof: Suppose the winner is not in Smith; we must show WIMC is
>> violated.
>>  Since Smith isn't empty and an order of finish is acyclic, we can pick
>> x
>> in Smith such that no alternative in Smith finishes ahead of x.  Thus
>> all
>> alternatives ahead of x are not in Smith, so no alternative ahead of x
>> is
>> ranked over x by a majority.)  So it is easy to show that every voting
>> method that fails the Condorcet criterion also fails WIMC and IMC.
>> These
>> include Hare (a.k.a. Instant Runoff and the Alternative Vote) and Borda.
>> They also include Approval voting, which fails in spirit since polling
>> can
>> establish the existence of a majority who prefer a loser over the
>> winner,
>> in the cases where the restrictive ballot format does not elicit that
>> information.
>>
>> Should IMC and WIMC be added to Wikipedia?
>>
>> Regards,
>> Steve