[EM] New Thoughts on Strong FBC

[Alex Small]

A while back I concluded that the Gibbard-Satterwaithe (apologies if I
spelled it wrong) Theorem must bar the existence of a ranked method that
never gives an incentive to place somebody other than your favorite in the
first position.

Actually, the GS Theorem only says that there will always be cases where
people have an incentive to vote insincerely.  It's not obvious to me that
it rules out the possibility of a ranked method that gives a privileged
position to your favorite, so that you might have an incentive to
insincerely rank your lower choices but not your first choice.

I've thought of a geometric way to examine this, but I don't know where to
go.  To keep it simple, let's assume 3 candidates.

With 3 candidates there are 6 possible categories of voters (assume that
truncated ballots aren't counted).  The electorate is completely described
by the vector

E = [p(A>B>C), p(A>C>B), p(B>A>C), p(B>C>A), p(C>A>B), p(C>B>A)]


Each p variable represents the percentage of the electorate with a
particular preference order.  Let's restrict ourselves to the
5-dimensional region defined by

E*[1,1,1,1,1,1] = 1  (number of voters conserved)

0 < p(r) < 1 for all possible preference orders r.


An election method M(E) partitions this region into 3 smaller regions
(which might be neither connected nor simply connected), each
corresponding to a win by a different candidate.  (Assume that the
boundaries between regions either give definite results or ties.  Ignore
ties, which have to be resolved by a 5-4 Supreme Court ruling ;)  This
partitioning of the region completely defines the election method.

We can impose a symmetry condition to ensure that the method is unbiased
and non-dictatorial:

Say M(E) = A, where A is a particular candidate.

Define the swap-operator S(A, B) so that

S(A,B)[p(A>B>C), p(A>C>B), p(B>A>C), p(B>C>A), p(C>A>B), p(C>B>A)] =

[p(B>A>C), p(B>C>A), p(A>B>C), p(A>C>B), p(C>B>A), p(C>A>B)]

(In other words, the swap operator corresponds to all voters switching A
and B on their ballots.)

Then M(S(A,B)E) = B


Now, imagine that we fix all but two elements of the vector E.  We've just
defined a line segment.  Move along that line segment across a boundary
between two regions, the first corresponding to a victory by A and the
second corresponding to a victory by B.  As we move along that line
segment we diminish the number of voters in one category and augment the
number of voters in the other category.

If the method is non-manipulable, the voters in the category being
diminshed should prefer A to B, and the voters in the category being
augmented should prefer B to A.  If the voters in both categories prefer A
to B (but have different opinions of C) then moving voters between those
categories should never bring us across the boundary between A and B.  All
three conditions must be satisfied for all possible pairs of voter
categories and regardless of the number of voters in each of the other
categories.  Otherwise, the method is manipulable.

The GS Theorem should be equivalent to saying that our symmetry condition
is incompatible with drawing the 3 regions in a non-manipulable manner.  I
imagine that somebody who's knowledgeable about this kind of geometry
could prove that.


However, strong FBC imposes a weaker condition than non-manipulability:


Once again, hold fixed the number of voters in all but 2 categories,
PROVIDED THAT THE CATEGORIES HAVE DIFFERENT FIRST CHOICES.  Impose the
non-manipulability conditions for all such pairs of voters regardless of
the number of voters in each of the other categories.

If it is possible to prove the GS Theorem in the geometric terms described
earlier, then it should be possible to address the question of strong FBC,
which imposes fewer conditions.  Sadly, I am clueless about how to
proceed, but perhaps if I think about it long enough I'll gain insight.


Anyway, just some thoughts.





Alex


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