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