[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