EconPapers    
Economics at your fingertips  
 

Approximability and Inapproximability of Dodgson and Young Elections

Ariel D. Procaccia (arielpro@cs.huji.ac.il), Michal Feldmany (mfeldman@huji.ac.il) and Jeffrey S. Rosenschein (jeff@cs.huji.ac.il)

Discussion Paper Series from The Federmann Center for the Study of Rationality, the 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.

Pages: 13 pages
Date: 2007-10
New Economics Papers: this item is included in nep-cdm and nep-pol
References: Add references at CitEc
Citations:

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp466.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp466.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp466.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: https://EconPapers.repec.org/RePEc:huj:dispap:dp466

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin (menahem.simkin@mail.huji.ac.il).

 
Page updated 2024-12-28
Handle: RePEc:huj:dispap:dp466