## Trying to understand Dhillon & Mertens's characterization of (normalized) range voting

As of July 2010 I unfortunately have been unable to fully-understand the theorem+proof by Dhillon & Mertens. This page consists of an attempt to at least understand their theorem statement.

THEOREM claimed by Dhillon & Mertens [Relative Utilitarianism, Econometrica 67,3 (May 1999) 471-498]: Normalized continuum-score Range Voting ("normalized" meaning that every voter scores her favorite with the maximum allowable score and her most-hated candidate with the minimum) is the unique voting system (in situations with at least 3 voters and at least 5 candidates) obeying the following axioms:

See also the more-precise theorem statement at bottom.
Note on mysterious names: INDIV, NONT, NOILL, ANON, MON, IRA, CONT are the names of their 7 axioms; they used made-up axiom-names instead of somewhat less-informatively saying, e.g, "axiom 3."
INDIV:
If all voters are totally indifferent, so is society (note: "society" means the output of the voting system).
NONT:
Society is not always indifferent.
NOILL:
If every voter is indifferent except for one voter, then society is not always opposed to her.
ANON:
Permuting the voters has no effect.
IRA:
If a "candidate" which happens to be a lottery among some subset S of candidates, is removed, then the election result (as a full ordering of lotteries among S) is unaltered. [At least, I think that is what they meant. The wording of their axiom actually simply does not parse as valid English, so I am going by the commentary they wrote after their statement of the IRA axiom and in other places.]

Notation for below: "∼" denotes societal indifference, i.e. X∼Y if and only if X≥Y AND Y≥X; and X≥Y if and only if NOT Y>X, and finally ">" denotes societal preference.

MON:
("Monotonicity.") For any three "candidates" (which are lotteries) P, Q, and R, consider two possible elections with the same sets of voters and candidates, but with exactly one voter (say, for concreteness, the last) perhaps changing her vote between the two elections. IF in election#1 R ∼ P ≥ Q AND this last voter is totally indifferent AND in election #2 this last voter changes her opinion on P,Q, and R to P ∼ Q > R, THEN:
if election #2 says Q∼R, then election #2 also says P≥Q.

Utility/vote numerical assumptions for use below: Assume each voter has a real-valued utility for each candidate. Regard a particular voter's utility vector as only defined up to positive rescaling factors and additions of a constant, e.g. (2,3,5) is the "same" as both (4,6,10) and (1,2,4). Therefore we can always regard a utility-vector as "normalized" so max entry is 1 and min is -1, except for the single un-normalizable vector (0,0,...,0) which expresses total indifference and note is quite separate.

Definition of "weak convergence": Consider an infinite sequence of utility vectors U1, U2, U3, ... We shall say this sequence "weakly converges" to a given vector (call it U) if

1. whenever A>B according to U, then A>B according to every Uk with k sufficiently large;
2. the full set of pairwise preference "∼" or ">" relations is the same for Uj as it is for Uk if both j and k are sufficiently large.
CONT:
("Continuity.") Consider an infinite sequence of elections #1, #2, #3, ... in which all votes by all voters are exactly the same except for one special voter V who gets to change her opinions between elections. Suppose V's utility vectors weakly converge to something (which we shall call "election #∞"). THEN: if the societal results in elections #1, 2, 3, ... weakly converge to anything, then the societal result of election #∞ either is that limit result, or is complete indifference. [Their explanation of CONT is unclear because they employ a notation "C(a0)" which was nowhere defined previous to this point in the paper. They also, e.g. employ the word "even" in a way that makes no sense to me. So I was reduced to guessing what they meant by CONT and the above is my guess.]

Dhillon & Mertens' claimed THEOREM (more precisely stated):

1. Normalized range voting satisfies all 7 of the above axioms {INDIV, NONT, NOILL, ANON, MON, IRA, CONT}.
2. If #voters>=3 and #candidates>=5 then any voting system obeying all the above axioms is equivalent to normalized range voting whenever there exist some two voters whose preferences are not exactly equal-but-opposite (i.e. whenever not all voters express utter indifference)

Return to main page