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
U_{1},
U_{2},
U_{3}, ...
We shall say this sequence "weakly converges" to a given vector (call it U_{∞})
if
whenever A>B according to U_{∞}, then A>B according to every
U_{k} with k sufficiently large;
the full set of pairwise preference "∼" or ">" relations is the same for
U_{j} as it is for U_{k}
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(a_{0})"
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.]
Normalized range voting satisfies all 7 of the above axioms
{INDIV, NONT, NOILL, ANON, MON, IRA, CONT}.
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)