[EM] Problem solved (for pure rank ballots): ICC & AFB incompatible (essentially)
Abd ul-Rahman Lomax
abd at lomaxdesign.com
Fri Jan 26 20:08:04 PST 2007
Warren's proof is on the web page
http://rangevoting.org/SimmonsSmithPf.html, but there is a typo in it
and the original proof, quoted here from the Range Voting list, is a
little simpler to read.
>Theorem:
>These criteria, for a single-winner voting system based on
>pure-rank-order-ballots, are incompatible:
>1. AFB = avoids favorite betrayal
>2. ICC = immune to candidate cloning
>3. reduces to simple majority vote in 2-candidate case
>4. symmetry under candidate renaming
>5. tiebreaks (if any) are random equally likely.
>6. adding a new candidate to the election whom all voters unanimously
>rank unique-bottom, does not change the winner.
>
>Proof:
>Consider these 3 votes:
[Election 1:]
>A>B>C
>C>A>B
>B>C>A
>by symmetry axiom 4 this is a perfect 3-way tie.
Accepted.
>However we shall argue under axioms 1-3 that A must win, which is a
>contradiction that establishes the proof.
>If A does not win, then B or C does.
>
>If B wins, then the C-voter would betray C to vote A>C>B getting
[Election 2:]
>A>B>C
>A>C>B
>B>C>A
>and then {B,C} is a clone set and hence by axioms 2 and 3 then A must win
>and hence the betrayal worked and hence we get a contradiction with
>axiom 1.
This is the sticking point. if (B,C) is a clone set, and ICC is
satisfied, then it must be true that, in election 2, combining (B,C)
must not change the winner. Therefore Election 2 has the same winner as
Election 3:
A>BC
A>BC
BC>A
Because this is the two-candidate case (A and BC), A must win. So A
must win Election 2. (Which might seem obvious, but I need to
remember that this is an unstated method. We only know the winner in
the two-candidate case, which is why the election was reduced as it
was. I had not understood that. ICC is necessary here to prove that A
wins the second 3-candidate election, if B won the first. Warren will
proceed to
A won because of FB by a C voter. Was this a gain?
Without FB by anyone, what is the expected value of the election to
the C voter? If we assign 1 to the election of C, 0 to the election
of A, and -1 to the election of B, then the expected value of the
election is 0. I.e., multiplying the probabilities of the election
( 0 * 1/3 - 1 * 1/3 + 1 * 1/3 )
If C betrays C to cause the election of A by dishonestly elevating A,
the value of this is 0.
(This is not proof, this is an approach to understanding what is going on.)
C has not gained, in this analysis. However, if we can consider
preference strength, which is problematic with ranked ballots, we can
arrange the preference strengths such that C *does* gain. But we are
analyzing a "pure ranked election" with information that isn't
present in the election.
This is simply another variation on how preference strength can alter
the outcome.
It is essentially unfair to Ranked methods to judge them by assuming
preference strength below the value of one rank. The attempt here by
Warren is guided, I can see, by a desire to show why Range methods
are better than Ranked methods.
But there are, again, much simpler ways to show that.
The assumption here is that the C voter gains something by betraying
C. Where did that assumption come from? Favorite Betrayal is a
problematic criterion, because it depends upon assuming a gain on the
part of the voter, a gain that is, in this case, unbalanced. I.e.,
for the vote shift by the C voter to be a gain, there must be
asymmetry in the preferences. I think this was stated by Venzke or
Forest, I forget which, as C>A>>B.
But by using >>, which is identical in expression in a ranked system
to >, to manipulate votes, we are only saying that if there are
considerations not expressed on the ballot by a method, a method
which allows those considerations to be expressed will be superior.
I still think the proof is problematic, but now for a different
reason. It is problematic because it is almost a tautology. If in a
three candidate election, a voter may shift the winner from an
*average* outcome of the value of the middle candidate (as ranked by
the voter) to a certain outcome of the middle candidate, then we have
no basis in the information provided by the ballot to conclude that
this is a gain. But we can assume it.
Ranked methods, however, act as if it is assumed that ranks are equal
in preference strength. Following this assumption, the C voter does
not gain by FB, which would mean that the FB criterion is not violated.
Clearly, however, the assumption does not correspond to reality.
Here, Warren et al are apparently considering that the utility step
between candidates is unequal, i.e, that C>A and A>>B. By allowing
that condition, and then considering it, they construct an example of
FB failure (i.e., a gain to the voter through FB) *if* ICC is satisfied.
Warren goes through the other cases, necessary for a formal proof. I
think that the "A must win" because if B wins FB or ICC are violated,
and if C wins FB or ICC are violated, is confusing. It's technically
correct. He doesn't mean that A must win, actually, he is showing
that there is a contradiction to symmetry.
HOWEVER, having come this far, I get a horrible thought: this proof
is based on the assumption that one of the candidates wins the
election (pick one). And if that candidate wins, then the voter can,
after the election, dissatisfied with the outcome, change his vote?
FB would require that the voter, anticipating a negative outcome,
betrays his favorite, and increases the probability of satisfaction,
the utility of the election. However, for this to represent true FB,
the voter must have some *expectation* that this will improve the
outcome. In Election 1, if the voter has that expectation, and -- say
it is the C voter -- raises A, betraying C, the voter must prefer an
increased probability of the election of A over B to the simultaneous
decreased probability of the election of C over B. This is another
way of saying that the preference strength of the C>A pair is weaker
than the strength of the A>B pair.
Having thoroughly confused myself, I must put this down for the
night. What has become clear to me is that the problem here is the
effective assumption of equal preference strength in ranked
elections, while, in this example, unequal preference strength is
required for the application of the FB criterion to make sense.
More information about the Election-Methods
mailing list