[EM] Progress on strong FBC

[Alex Small]

I think I'm close to proving that strong FBC is incompatible with
monotonicity.  I'd appreciate constructive feedback on my arguments.

Suppose that the winner of a 3-way election is candidate A.  Now, consider
the voters with the preference B>C>A.  I'll argue that if a method
disallows truncation and satisfies montonicity and strong FBC then those
voters can never, under any circumstances, act in a way that causes B to
win, no matter how close the race is under whatever method we're using. 
(I realize this is very non-rigorous phrasing, but I can make it more
rigorous later.)

First, two definitions:

Monotonic:  A method is monotonic if
1.  A group of voters with identical preference orders, all following the
same strategy, can never cause a winning candidate to lose by insincerely
ranking him higher and holding constant the relative rankings of the other
candidates.
and
2.  A group of voters with identical preferences orders, all following the
same strategy, can never cause a losing candidate to win by insincerely
ranking him lower and holding constant the relative rankings of the other
candidates.

Strong Favorite Betrayal Criterion:  A method fails this criterion if a
group of voters with identical preference orders, all following the same
strategy, prefer the result obtained by insincerely ranking another
candidate ahead of their favorite over the result obtained by any other
strategy that sincerely ranks their favorite candidate in first place.

Now, suppose that candidate A wins the election.  If a group of voters
with the preference order B>C>A can cause B to win by insincerely
reporting B>A>C on their ballots then the method is non-monotonic.  Those
voters ranked A higher while holding constant the relative rankings of B
and C, and caused A to go from winner to loser.

Now, all other insincere strategies available to these voters involve
ranking another candidate ahead of B, their favorite.  If there was ever a
circumstance under which one of those strategies switched the outcome from
A to B then those voters would prefer the result obtained by betraying
their favorite to the result obtained by any other strategy.  (Even if
insincerely voting B>A>C caused C to win, these voters prefer B to C, so
they'd still prefer the result of favorite betrayal.)

This implies that no action of the voters in the category B>C>A can ever
change the outcome from A to B if we require monotonicity and strong FBC,
and don't consider the possibility of truncation.

To think of this in geometric terms:

With 3 candidates there are 6 preference orders.  If we represent the
electorate with a vector E, and specify that each element of the vector
indicates the number of voters with a particular preference order, then
we're working in a 6-dimensional space.  If we only look at vectors that
correspond to a given number of voters N, then we're working on a
5-dimensional hypersurface.

An election method will partition this 5-D hypersurface into 3 regions
corresponding to victories by A, B, or C.  It will also specify
4-dimensional regions corresponding to ties between A and B, B and C, or A
and C.  For the sake of completeness, it will also specify 3-D regions
corresponding to a 3-way tie.

Now, say we're in 5-D region where A wins.  No matter how close to the A-B
boundary we might be, no action by the faction B>C>A can cross that
boundary.  This seems to imply (although I haven't proven it yet) that if
we were stuck on the 4-D hypersurface corresponding to an A-B tie, no
action by the faction B>C>A could take us out of that hypersurface and
into the region corresponding to A's victory.

The problem is that each possible strategic adjustment by the B>C>A
faction corresponds to a different translation vector.  They have 5
possible strategic adjustments (sincere voting is not an adjustment). 
These 5 adjustments give 5 linearly independent vectors.

Requiring that none of these 5 translations move us into the region where
B wins means that all 5 of these linearly independent translations must
keep us in a 4-D hypersurface.  That is geometrically impossible.

Now, none of this is rigorous, but I think I could make it rigorous with a
little work.  Moreover, the conditions that I've imposed are fairly
restrictive:  only 3 candidates, no truncation, and monotonicity.  Still,
it's getting us somewhere.  I'd appreciate any comments that people might
have.




Alex


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