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
