Approximability and Inapproximability of Dodgson and Young Elections

Ariel D. Procaccia (), Michal Feldmany () and Jeffrey S. Rosenschein ()

Discussion Paper Series from Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem

Abstract: The voting rules proposed by Dodgson and Young are both designed to find the candidate closest to being a Condorcet winner, according to two different notions of proximity; the score of a given candidate is known to be hard to compute under both rules. In this paper, we put forward an LP-based randomized rounding algorithm which yields an O(log m) approximation ratio for the Dodgson score, where m is the number of candidates. Surprisingly, we show that the seemingly simpler Young score is NP-hard to approximate by any factor.

New Economics Papers: this item is included in nep-cdm and nep-pol
Date: 2007-10
View list of references

Downloads: (external link)
http://ratio.huji.ac.il/dp/dp466.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:huj:dispap:dp466

Access Statistics for this paper

More papers in Discussion Paper Series from Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem
Contact information at EDIRC.
Series data maintained by Ron Peretz ().