[EM] Final Conclusion on strong FBC!!!!!!

[Alex Small]

Yesterday I posted to the list a proof of the Gibbard-Satterthwaite (GS)
Theorem.  I said that if my methods are valid then I can reach conclusions
on strong FBC.  I won't post my proof yet, because it is lengthy and I
want to streamline it.  However, I will give the conclusion and sketch the
forthcoming proof.

In elections with 3 candidates, there is only 1 way to remove any
incentive to insincerely rank another candidate ahead of your true
favorite:  "Top 2 Voting", AKA "Negative Voting" AKA "Anti-Plurality
Voting".  Each voter ranks the candidate, and a single point is assigned
to each voter's first and second choices.  The candidate with the most
points wins.  All other ranked methods fail strong FBC (if all voters and
all candidates are treated equally, so that Random Ballot is excluded, as
well as methods that only elect a certain candidate in a very tiny set of
cases.)

Let us first recall the fundamental requirement of strong FBC, that a
voter either cannot improve the outcome by strategic voting, or that
swapping second and third choices will have the same effect as insincerely
ranking somebody ahead of your favorite.

I began by looking at the boundary between the region where A wins and the
region where B wins in the 5D space of electorates.  Although there are 6
factions of voters, a basic symmetry requirement on swapping A and B in
the rankings means that I only need to examine the strategic incentives
(or lack thereof) for 3 factions.  Another symmetry requirement enables us
to draw conclusions on the A-C and B-C boundaries after examining the A-B
boundary.

Since each faction can have either no incentive to vote strategically, or
an incentive to betray #2, there are 2^3 = 8 cases to consider:

The case where all 3 factions have no incentive to vote strategically
violates the GS Theorem.  It places such severe restrictions on the
normals to boundaries that we encounter Condorcet's paradox.

Likewise, in 6 other cases, severe restrictions are placed on the normals
to the boundaries.  The normals are not the ones you would get from
Condorcet, but there are electorates which fall into a cyclic region:  One
restriction says A>B, another says B>C, and a third says C>A.  Since the
severe restrictions on the normals to boundaries exclude the possibility
of an auxillary procedure in cyclic regions, strong FBC leads to a
paradox.

The only case that does not produce a paradox is "top 2 voting."  If we're
near the boundary where A and B are tied, the factions A>B>C and B>A>C
have an incentive to betray #2.  The factions C>A>B, C>B>A, B>C>A, and
A>C>B have no incentive to vote insincerely.  Although the incentives for
each faction place severe constraints on the normals to boundaries, the
normals to the boundaries are not linearly independent, and it can be
shown that cycles are then forbidden.

(It is possible to exclude cycles when the normals are linearly
independent, but rather than having a single rule "A beats B if
<condition>" you have "A beats B if <condition 1> and <condition 2> or
<condition 3>..."  Examples of ranked methods like that are Condorcet,
IRV, and Bucklin.)


Assuming there are no holes in the reasoning, there's still one weakness: 
The reasoning employed is specific to the case of 3 candidates.  The case
of 4 or more candidates is very difficult, because there are many more
cases to examine.  It would be nice if there were some sort of inductive
argument:  "If for N candidates one cannot satisfy strong FBC while
distinguishing between #1 and #2, then for N+1 candidates the same holds."

Anybody have an idea for that?





Alex


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