[EM] NP-hard single-winner methods

Kristofer Munsterhjelm km-elmet at broadpark.no
Sat Nov 27 05:35:51 PST 2010


I'm currently refactoring my voting simulator, and was considering 
including some of the NP-hard single-winner methods: Kemeny, Dodgson, 
and Young (which seems to eb different from Kemeny).

Thus, I wonder if anybody knows reasonable integer programs that give 
candidate scores (or the winner) for either Dodgson or Young, and with 
the input parameters being only the Condorcet matrix (as well as number 
of voters and candidates), rather than having to access the ballots 
directly.

Failing that, does anybody know of algorithms to calculate the scores or 
winners of these methods from the Condorcet matrix alone?

To restate those methods:

A candidate's Young score is the maximum number of voters that, when 
taken as a group, consider the candidate a Condorcet winner. It is equal 
to the electorate if the candidate is a CW, and is 0 if there's no 
subset that considers it a CW. A greater score is better.

A candidate's Dodgson "score" is the number of adjacent candidate 
exchanges on ballots required to make that candidate a CW. Here, a 
lesser score is better, and a CW's score is zero.



More information about the Election-Methods mailing list