New anti-spoiling method moots Gibbard-Satterthwaite?

Steve Eppley SEppley at alumni.caltech.edu
Tue Oct 28 09:20:50 PST 1997


One of the axioms behind Ken Arrow's "Impossibility" theorem 
is "Independence from Irrelevant Alternatives."  (The IIAC 
criterion.)  Bruce Anderson suggests it may be reasonable to 
modify the meaning of irrelevance so that all members of the 
Smith set are considered relevant.  By doing so it's possible 
for voting methods to simultaneously satisfy all Arrow's axioms 
(where Arrow's IIAC is replaced by Anderson's IIAC).  I suppose 
one could call that the Anderson "Possibility" theorem.

Bruce and others have pointed out that the Gibbard-Satterthwaite 
"Manipulability" theorem (a corollary of Arrow's theorem) 
proves it's impossible for any voting method of interest 
to be entirely free of the possibility that a candidate may 
be a "spoiler" (a non-winning candidate whose presence on the 
ballot changes the outcome for the worse, in the opinion of 
that candidate or its supporters).  

Arrow's IIAC criterion is very hard to satisfy, even if some of
Arrow's other axioms are relaxed.  Markus Schulze has pointed 
out that any method which satisfies the Pairwise Majority 
criterion violates IIAC.

But there appears to be a simple technique to solve this 
problem, or at least solve the aspect of the problem which can 
deter potential candidates from competing for fear of spoiling.
It also seems to provide significant protection from voter 
preference misrepresentation, thereby reducing the incentives 
for voters to misrepresent preferences.

Here's the proposed technique:

   Candidate Withdrawal
   --------------------
   After the voting but before a result is finalized, 
   publish the contents of the ballots and the tentative winner 
   (or better yet, the tentative complete collective order) 
   in a summary format.  Allow candidates to voluntarily 
   withdraw themselves from contention.  (If the candidate is 
   a proposal, not a person running for an office, then allow 
   the sponsor of the proposal to withdraw it.)  Withdrawal 
   effectively removes a candidate from the voters' ballots 
   when tallying the final result.

By "publishing the ballots" I'm not suggesting violating
voters' privacy in elections where a secret ballot is normal. 
In public elections, the published ballots need not include 
info which could identify how anyone in particular had voted.
It would be enough just to publish the pairings matrix.  In 
a partisan election, though, it might help to break down the 
summary according to the party registration of the voter if 
this information is available, since this would help candidates 
considering withdrawal to correlate suspected preference 
misrepresentations with announced strategy recommendations, 
but the technique doesn't depend on the publication of such 
information.

Allowing candidates to withdraw means that Arrow's version of 
IIAC isn't satisfied: Arrow's criterion says that if more 
voters prefer candidate X to candidate Y than vice versa,
then X must come ahead of Y in the collective order.  But 
it seems reasonable to modify IIAC to permit candidates to 
voluntarily push themselves further back in the collective 
order.  (Especially if their alternative is to avoid being on 
the ballot for fear of spoiling, which would remove them 
entirely from the collective order...)  Arrow had no problem 
with "premature withdrawal" before the voting, so why is it an 
axiom that just-in-time "mature withdrawal" must be banned?

If the basic voting method is a preference order method, the 
summary format should include the pairwise preference counts
even if the method isn't a pairwise method.  Providing this 
data would make it easier for candidates (and the voters) to 
determine which candidates ought to withdraw.  Now that fast 
cheap computers are widely available and software to calculate 
pairings is freely available on the internet, there's no good 
reason why the complete pairings can't be calculated.

* *

If there's a candidate which would beat any other if only those 
two were competing, but for some reason a different candidate 
is the tentative winner--perhaps some voters offensively 
misrepresented their preferences in order to create a circular 
tie which might elect their favorite, or perhaps the election 
uses an inferior method, like Instant Runoff, which can 
fail to elect the "beats all" best compromise even with no 
misrepresentations--then one or more candidates can voluntarily 
withdraw and thereby restore the election of the "beats all" 
candidate.  Here's an example which should look familiar:

   3 choices, 100 voters.
      46: ACB       <--  these voters order-reversed their ABC?
      10: BAC
      10: BCA
      34: CBA

   The pairings (even if the basic method isn't pairwise):

                     prefer A     prefer B     prefer C
      A vs B:           46L          54W
      A vs C:           56W                       44L
      B vs C:                        20L          80W

   If the method will elect A given those votes, then candidate
   C has a clear incentive to withdraw: presumably C's personal
   preference order is similar to the preference orders of the 
   34 voters whose first choice is C.  This means that A is
   C's "greater evil" and C would prefer the election of B.  
   If C withdraws then B will be elected since a majority
   ranked B ahead of A.  Therefore C can improve the outcome, 
   in C's opinion, by withdrawing.

   Candidate B can't change the outcome by withdrawing.  The 
   winner would still be A.  

   Candidate A wouldn't want to change the outcome by 
   withdrawing.

Clever voters would not be able to steal elections, and 
preference misrepresentations would tend to backfire.  Unless 
there's something I'm failing to consider...  I haven't looked 
at complicated many-candidate circular scenarios.  In a 
complicated circular tie, some candidates might be willing to 
exchange their withdrawal for promises from another candidate 
on some important issue(s); I don't know whether this would be 
a problem, or a boon which effectively promotes the simultaneous 
election of circular issue-majorities.  (An aside: the best 
argument for proportional representation is that PR is much 
better than non-PR at simultaneously electing circular issue-
majorities.  I've never seen CV&D mention this, or that 
majorities on issues are the true fundamental majorities.  
The majorities they focus on--majority parties, ethnic 
majorities, gender majorities, religious majorities--
are secondary to democracy.)

Parties could do away with primary elections and other means 
of winnowing their contenders down to one champion, if ballot 
access laws permit parties to nominate more than one candidate 
per office.  All the contenders would be free to compete in the 
general election since they can winnow themselves afterward.

* *

It's possible that a candidate could be bribed to withdraw.  
This can be mitigated by using a solid basic method like 
Smith-Condorcet which minimizes the opportunities for gain by 
withdrawing.  (Offensive order-reversal might be further 
punished by "policy bribery": in exchange for withdrawal, 
candidate C might extract from B a promise on some issue
important to C, and to the voters who prefer A but in the 
opposite policy direction.)

Also, there's bound to be scrutiny of any candidate who
withdraws, which would deter betrayals.  (Voters' ballots may
be secret, but unusual actions by candidates or (legislative 
sponsors or proposals) would take place under the glare of the 
news media.  A candidate suspected of betrayal by many of 
his/her supporters wouldn't have a bright political future.)

In the case of voting on propositions instead of people, one 
might not want to trust the sponsor of a proposal.  If the 
intentions of a sponsor are suspect, leading people to fear 
the sponsor might withdraw the best compromise in an act of 
betrayal, a clone proposal could be sponsored by someone more 
trustworthy and the suspect proposal could be ranked last.  
Betrayal would also tend to be self-destructive in the long run 
since it would be hard to disguise: who would vote for a future 
proposal sponsored by someone who has committed betrayal?

* *

This withdrawal technique could mitigate flaws in most voting 
methods.  It obviously can't help "vote for only one, plurality 
wins".  It can't help plain Approval since withdrawal wouldn't 
affect other choices' scores.

It can't help "preference intensity" methods like "vote from
-N to +N on each choice" unless the algorithm renormalizes the
ballots after candidates withdraw (assigning the maximum +N to 
the voter's highest-rated uneliminated choice, for example).  
Renormalization in this manner would tend to defeat the purpose 
of intensity voting, though, since its purpose is to allow a 
passionate minority to defeat a near-indifferent majority.  
Perhaps there's a milder form of renormalization which, 
instead of assigning the maximum +N to the voter's highest-rated 
uneliminated choice, would assign the value that that voter had 
voted on his/her favorite (but eliminated) candidate.

It appears the withdrawal technique could moot the "spoiler" 
flaw and the lesser evil dilemma in any preference order method, 
even non-pairwise methods like Instant Runoff.  But with Instant 
Runoff more candidates may need to withdraw to elect the best 
compromise, and it might be confusing for the public why 
so-called "popular" candidates choose to withdraw to let 
so-called "unpopular" candidates win.  (The Instant Runoff 
fallacy is that a candidate's popularity is measured by the 
number of voters who ranked it first.)  Also, with Instant 
Runoff withdrawals could be routinely needed even when voters 
don't misrepresent preferences:

   3 choices, 100 voters.
      46: ABC
      10: BAC
      10: BCA 
      34: CBA

   Here B beats every other choice pairwise.  But Instant Runoff
   would elect A unless C (or A) withdraws.  With a method that
   always satisfies the Condorcet criterion, no candidate needs
   to withdraw.

* *

It seems sensible to use a method which won't need withdrawals 
as frequently, like Smith-Condorcet.

If the complexity of Smith-Condorcet is a problem, plain 
Condorcet or Simpson-Kramer might solve the problem.  With plain 
Condorcet, there could be (rare) occasions where the tentative 
winner is not a member of the Smith set; in such cases 
withdrawal by one or more members of the Smith set can 
elect a member of the Smith set.

   Example:  4 choices, 100 voters
      19:  S1 S2 S3 C
      18:  S2 S3 S1 C
      18:  S3 S1 S2 C
      15:  C S1 S2 S3
      15:  C S2 S3 S1
      15:  C S3 S1 S2

   The pairings:

                 S1 worse    S2 worse    S3 worse     C worse
   S1 vs S2:        33W         67L
   S1 vs S3:        66L                     34W
   S2 vs S3:                    33W         67L
   S1 vs C:         45W                                 55L
   S2 vs C:                     45W                     55L
   S3 vs C:                                 45W         55L
                   ----        ----        ----        ----
   largest loss:    66          67          67          55

   C is a "Condorcet Loser" (a choice which loses pairwise to
   every other choice) but plain Condorcet elects C since C's
   largest loss is only 55.  S1, S2, and S3 are the members of
   the Smith set.  If any of S1, S2, or S3 withdraws, one of 
   the other members of the Smith set becomes unbeaten and 
   is elected.

In general, if a method can violate the Smith criterion but
satisfies the Condorcet Criterion, then there's always a way
that withdrawals by one or more members of the Smith set will
result in the election of a member of the Smith set.

Simpson-Kramer is similar to plain Condorcet except that it's 
slightly less complex.  Condorcet includes only pair-losses 
when determining each candidate's score (its largest loss).  
But in Simpson-Kramer, each candidate's score is its largest 
pairwise "opposition."  (I hate to use the word opposition, 
since the word connotes an absolute when the voter is really 
expressing a relative preference.  But no one has yet 
invented a term which means "the number of voters who ranked 
a candidate's opponent ahead of the candidate."  Maybe we 
should offer a prize to the person who invents the best term.)  
In other words, Simpson-Kramer considers the candidate's 
pair-wins as well as its pair-losses.  If we want to satisfy 
the criterion to elect the candidate whose election minimizes 
the number of voters who prefer a different winner, then 
Simpson-Kramer performs better on this than Condorcet's 
"largest loss" scores.  (Simpson-Kramer rigorously satisfies it. 
Condorcet only satisfies rigorously a similarly worded criterion 
which counts only the voters who ranked a pair-winner ahead of 
the candidate.)  

Condorcet's deterrence of preference order misrepresentation is
a bit stronger than Simpson-Kramer's, but with the "candidate
withdrawal" feature that difference may not matter. 

* *

If a collective preference order is calculated, rather than
stopping after calculating the winner, withdrawn candidates
should be included in those subsequent calculations. 
Candidates should be able to specify which positions in the
collective order they are withdrawing from contention for.

I proposed in EM long ago an iterative algorithm for determining 
the complete collective preference order, given any preference
order method M:  To calculate the Nth position, remove from 
the ballots the 1st thru (N-1)th finishers and re-tally.  
(If the method is pairwise, a shortcut is to simply delete the 
rows and columns of the pairwise summary matrix which include 
the 1st thru N-1th finishers.)

Here's an example:

   4 choices, 100 voters.
      46: ACBD
      10: BACD
      10: BCAD
      34: CBAD

   Assume a pairwise method is used.

                     prefer A   prefer B   prefer C   prefer D
      A vs B:           46L        54W
      A vs C:           56W                   44L
      A vs D:          100W                               0L
      B vs C:                      20L        80W
      B vs D:                     100W                    0L
      C vs D:                                100W         0L

   Candidate C chooses to withdraw (assuming the method will 
   elect A if C doesn't withdraw).  B is therefore first in 
   the collective preference order since B beats A.  (B wins.)

   To calculate which candidate finished second, B is removed
   from the ballots:

      46: ACD
      10: ACD
      10: CAD
      34: CAD

                     prefer A              prefer C   prefer D
      A vs C:           56W                   44L
      A vs D:          100W                               0L
      C vs D:                                100W         0L

   With B gone, A finishes ahead of C and D (with any method 
   which has been proposed).  This means A finishes in second 
   place, after B.  

   To determine third place, B and A are removed from the 
   ballots:
                                           prefer C   prefer D
      C vs D:                                100W         0L

   C finishes third.  D finishes in fourth place.

C finishes third in spite of having withdrawn.  C's withdrawal 
was only from contention for first place.  Had C (or C's sponsor 
if C is a proposition) wanted to withdraw from contention for 
other places, C would have had to specify that.

---Steve     (Steve Eppley    seppley at alumni.caltech.edu)



More information about the Election-Methods mailing list