Combinatorial Equivalents

Our proof of the Gibbard–Satterthwaite theorem in Section 3.1 was based on the combinatorial property that we called down-monotonicity, and the fact (Lemma 3.1.5) that if a resolute voting rule is non-manipulable, then it satisfies down-monotonicity. It turns out that the converse of this is also true, so down-monotonicity is fully equivalent to non-manipulability for resolute voting rules.

Notice, however, that we are not assuming Pareto, so the equivalence of down-monotonicity and non-manipulability does not follow from the implications “non-manipulability implies down-monotonicity implies dictatorship implies non-manipulability.” Results in the next chapter, nevertheless, allow a version of this derivation.

Down-monotonicity is not the only combinatorial equivalent of non-manipulability for resolute voting rules. In what follows, we give three others, two of which have appeared in the literature (Muller and Satterthwaite, 1977, and Moulin, 1983), and the third of which is the “resolute version” of the property we called “choice independence of irrelevant alternatives” earlier.

Down-monotonicity is a particularly appealing combinatorial property because it comes in two versions that are easily seen to be equivalent. One of these versions is quite weak: An election winner is unchanged if one voter moves one losing alternative down one spot on his or her ballot. The other version is quite strong: An election winner is unchanged if several voters move several losing alternatives down several spots on their ballots. In what follows, we make use of these two versions of down-monotonicity to show that three other combinatorial properties are equivalent to non-manipulability.