[EM] Condorcet and the Muller-Satterthwaite Theorem

[Alex Small]

I recently learned of the Muller-Satterthwaite Theorem:  pareto efficient
and monotonic social choice functions are dictatorial.  I was always under
the impression that Condorcet, at least in some implementations, was
monotonic and pareto efficient.  Let's first consider Pareto:

If A and B are in the innermost unbeaten set, and if every voter prefers A
to B, then B's defeat will be stronger than any other defeat (barring a
tie with another candidate who loses a contest 100% to zero).  That defeat
will never be dropped and hence B will never become "undefeated" (after
disregarding weak defeats).  Hence B will lose.

As far as monotonicity:  Suppose A wins all pairwise contests.  If a voter
moves candidate A up in his rankings, without changing the relative
rankings of the other candidates, A will still win all pairwise contests. 
Hence improving the CC's ranking cannot cause him to lose.

If A is not the Condorcet Candidate, but one such candidate exists, then a
voter moving A down in his rankings (without changing the relative
rankings of any other candidates) will not knock the Condorcet Candidate
off of his pedestal.  Hence demoting a non-Condorcet candidate cannot
cause him to win (if a CC exists).

Say there is a cyclic ambiguity.  Let's use winning-votes to keep life
simple, and assume no truncation (truncation might invalidate some of the
assumptions of the Muller-Satterthwaite Theorem).  Say A is the winner. 
Upgrading your ranking of A, leaving all other relative rankings
unchanged, will only increase other candidates' magnitudes of defeat.  It
may even cause A to win ALL pairwise contests.  So promoting A does not
hurt him.

Finally, say there is a cyclic ambiguity and A is not the winner. 
Demoting A in your rankings, all other relative rankings unchanged, will
not lessen the strength of any of his defeats.  It may increase the
strength of the defeat, and it may even cause another candidate to win all
pairwise contests.  Hence demoting a candidate will not help him win if
there's an ambiguity.



Where did I go wrong?




Alex


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