IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp466.html
   My bibliography  Save this paper

Approximability and Inapproximability of Dodgson and Young Elections

Author

Listed:
  • Ariel D. Procaccia
  • Michal Feldmany
  • Jeffrey S. Rosenschein

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.

Suggested Citation

  • Ariel D. Procaccia & Michal Feldmany & Jeffrey S. Rosenschein, 2007. "Approximability and Inapproximability of Dodgson and Young Elections," Discussion Paper Series dp466, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    • Handle: RePEc:huj:dispap:dp466
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp466.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Young, H. P., 1977. "Extending Condorcet's rule," Journal of Economic Theory, Elsevier, vol. 16(2), pages 335-353, December.
    2. Christian Klamler, 2004. "The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(1), pages 91-102, August.
    3. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ariel D Procaccia & Michal Feldmany & Jeffrey S Rosenschein, 2007. "Approximability and Inapproximability of Dodgson and Young Elections," Levine's Bibliography 122247000000001616, UCLA Department of Economics.
    2. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    3. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    4. Berghammer, Rudolf & Schnoor, Henning, 2015. "Control of Condorcet voting: Complexity and a Relation-Algebraic approach," European Journal of Operational Research, Elsevier, vol. 246(2), pages 505-516.
    5. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    6. Dan S. Felsenthal & Hannu Nurmi, 2016. "Two types of participation failure under nine voting methods in variable electorates," Public Choice, Springer, vol. 168(1), pages 115-135, July.
    7. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    8. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2019. "On some k-scoring rules for committee elections: agreement and Condorcet Principle," Working Papers hal-02147735, HAL.
    9. Maurice Salles, 2017. "Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerôme Lang, and Ariel Procaccia (eds), Handbook of Computational Social Choice, Cambridge: Cambridge University Press, 535 pages, ISBN 978-110744698-4," Post-Print halshs-02084709, HAL.
    10. Cascón, J.M. & González-Arteaga, T. & de Andrés Calle, R., 2019. "Reaching social consensus family budgets: The Spanish case," Omega, Elsevier, vol. 86(C), pages 28-41.
    11. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    12. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    13. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    14. Sanchari Deb & Kari Tammi & Karuna Kalita & Pinakeswar Mahanta, 2018. "Review of recent trends in charging infrastructure planning for electric vehicles," Wiley Interdisciplinary Reviews: Energy and Environment, Wiley Blackwell, vol. 7(6), November.
    15. Kenneth J. Arrow & Timothy J. Kehoe, 1994. "Distinguished Fellow: Herbert Scarf's Contributions to Economics," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 161-181, Fall.
    16. Kubale, Marek, 1996. "Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors," European Journal of Operational Research, Elsevier, vol. 94(2), pages 242-251, October.
    17. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    18. Hannu Nurmi, 2004. "A Comparison of Some Distance-Based Choice Rules in Ranking Environments," Theory and Decision, Springer, vol. 57(1), pages 5-24, August.
    19. Danny Nguyen & Igor Pak, 2020. "The Computational Complexity of Integer Programming with Alternations," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 191-204, February.
    20. Akbari, Sina & Escobedo, Adolfo R., 2023. "Beyond kemeny rank aggregation: A parameterizable-penalty framework for robust ranking aggregation with ties," Omega, Elsevier, vol. 119(C).

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp466. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.