[EM] Fallacy in Strong FBC Proof

[Alex Small]

I have to retract my proof that any 3-candidate/1-winner ranked election
method that satisifies strong FBC is equivalent to "Top 2 Voting."

One crucial point used throughout the proof is that the linear
inequalities determining whether A or B wins will be of the form

x*(ABC-BAC) + y*(ACB-BCA) + z*(CAB-CBA) > 0 (A wins)
                                        < 0 (B wins)

where ABC, BAC, etc. each refer to the number of people with that
preference and x, y, z are real numbers (not necessarily positive,
although normally we can assume they would be).  Such inequalities clearly
exhibit a "swap symmetry" when we swap candidates A and B.  I persuaded
myself that this is a logical consequence of the neutrality condition. 
Sadly, this is false.

Before explaining the error, I should clarify what I mean when I say that
a single inequality determines whether A or B wins.

For any election method, a candidate must usually meet multiple conditions
to win.  In plurality, A must get more votes than B and more votes than C.
 In Condorcet, A must beat both B and C pairwise, or else satisfy some
alternative conditions.  A given method might apply different conditions
in different situations, especially with methods like Condorcet or IRV.

Consider a region of "Electorate Space" (the 6D space where each
coordinate tells you how many people have a particular preference order)
in which a candidate must satisfy 2 conditions to win.  Maybe we're using
plurality, so that the conditions are having more votes than both of the
other candidates.  Say that A and B both have more votes than C.  There's
only one question remaining:  Which has more votes than the other?  In
that sense, there's only one inequality that matters, since the other
condition (beating C) is automatically satisfied in that vicinity of
electorate space.

Anyway, here's an example where the condition for A or B to win is NOT of
the form above.  Suppose we're using Bucklin.  Say that the electorate is
in the vicinity of

       ABC:  between 49 and 51
       CAB:  19
       BCA:  30
all others:  between  0 and  2

In this case, if A has an absolute majority he'll win.  Otherwise, when we
add in second place votes we see that A will have at least 70 to 72 votes
total, B will have at least 79 votes, and C will have 49 to 51 votes.  So,
if A doesn't get a majority B will win, regardless of how those 2
undecided voters get shuffled around.

The inequality to satisfy is:

ABC + ACB - BCA - BCA - CAB - CBA > 0  A wins
                                  < 0  B wins

This lacks the "swap symmetry" displayed in the form above.  There's no
particular reason to pick Bucklin, but other methods that pick the first
choice of the majority (e.g. IRV, Condorcet) require a little more thought
for constructing the example.  Since it only takes a single valid
counter-example to disprove a statement, this case with Bucklin suffices.

Anyway, because my symmetry assumption was absolutely crucial to my proof,
I have to withdraw it.  I still think it may be possible to apply certain
symmetry conditions as a consequence of neutrality, but it will require
more thought.



Alex


----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em