[EM] EM Metrics

Kristofer Munsterhjelm km-elmet at broadpark.no
Thu Jan 29 02:04:15 PST 2009

Paul Kislanko wrote:
> Seeing "RRV" used in a post reminded me of some earlier discussions. 
> Analysis of team computer rankings in sports that do NOT have 
> round-robin schedules use "Retrodictive Ranking Violations" to 
> characterize computer ratings with A>B after B has won a match against 
> A. (This is not an "error", since the rating that has A>B may have 
> noticed A has 10 wins over {C}s, each of which has beaten B.)
> But this leads to a thought.
> Suppose an Election Method results in an ordered list of alternatives 
> {1st 2nd 3rd....} (trivial for Plurality, and well-defined for any 
> method if we accept {2nd, 2nd, 5th, 5th, 5th,...} for ranked methods 
> that result in "ties")
> For each ranked ballot (for plurality we assume a "ranked ballot" that 
> looks like {1st, last, last, last, ...}, for approval we assume a 
> "ranked ballot" that looks like {1st, 1st, 1st, .... last, last, last} ) 
> we can find RRV(ballot) = SUM over pairs(x,y) (Altx > Alty in EM but 
> Alty > Altx in ballot)
> This is just the Kendall tau rank correlation "distance" = # of swaps 
> required by a bubble sort to turn {ballot} into {EM result}
> Something like that could be exploited to avoid the nebulous notion of 
> utility and define (voter(s) who cast {ballot})'s (lack of) 
> "satisfaction index" unambiguously and entirely with respect to the EM 
> used to form the election results list.

Isn't that just the metric that Kemeny-Young tries to optimize? Try 
every possible social ordering, and for each pair of preferences 
consistent with that ordering, the score is the sum of the number of 
voters that agree with it.

This can be calculated by the Condorcet matrix alone.

Assuming I'm correct, we can look at Kemeny to see where taking this to 
an extreme will get us. Kemeny has some nice properties, and it's the 
only Condorcet method that meets Reinforcement (if the rank is the same 
in two districts, it's also the same in those districts combined). 
However, it is not cloneproof, and one can't determine the winner in 
polytime unless P = NP.

This, in turn, leads one to ask: what polytime method gets closest to 
the Kemeny ideal? What cloneproof one does, and what method that is both?

More information about the Election-Methods mailing list