IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-03834509.html
   My bibliography  Save this paper

Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results

Author

Listed:
  • Dominik Peters

    (LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique)

  • Lan Yu
  • Hau Chan

    (University of Nebraska–Lincoln - University of Nebraska System)

  • Edith Elkind

    (University of Oxford)

Abstract

A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989b) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomial-time winner determination algorithm. For the utilitarian version, we prove that winner determination remains NP-hard for the Borda scoring function; indeed, this hardness results extends to a large family of scoring functions. However, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We then explore the power and limitations of this framework: we develop polynomial-time algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NP-hard to check whether a given profile is single-peaked on a tree that is isomorphic to a given tree, or on a regular tree.

Suggested Citation

  • Dominik Peters & Lan Yu & Hau Chan & Edith Elkind, 2022. "Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results," Post-Print hal-03834509, HAL.
    • Handle: RePEc:hal:journl:hal-03834509
    DOI: 10.1613/jair.1.12332
    Note: View the original document on HAL open archive server: https://hal.science/hal-03834509
    as

    Download full text from publisher

    File URL: https://hal.science/hal-03834509/document
    Download Restriction: no
    File URL: https://libkey.io/10.1613/jair.1.12332?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Ariel Procaccia & Jeffrey Rosenschein & Aviv Zohar, 2008. "On the complexity of achieving proportional representation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 30(3), pages 353-362, April.
    2. Clemens Puppe & Arkadii Slinko, 2019. "Condorcet domains, median graphs and the single-crossing property," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 67(1), pages 285-318, February.
    3. Demange, Gabrielle, 1982. "Single-peaked orders on a tree," Mathematical Social Sciences, Elsevier, vol. 3(4), pages 389-396, December.
    4. Monroe, Burt L., 1995. "Fully Proportional Representation," American Political Science Review, Cambridge University Press, vol. 89(4), pages 925-940, December.
    5. Danilov, Vladimir I., 1994. "The structure of non-manipulable social choice rules on a tree," Mathematical Social Sciences, Elsevier, vol. 27(2), pages 123-131, April.
    6. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    7. Chamberlin, John R. & Courant, Paul N., 1983. "Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule," American Political Science Review, Cambridge University Press, vol. 77(3), pages 718-733, September.
    8. Roberts, Kevin W. S., 1977. "Voting over income tax schedules," Journal of Public Economics, Elsevier, vol. 8(3), pages 329-340, December.
    9. Trick, Michael A., 1989. "Recognizing single-peaked preferences on a tree," Mathematical Social Sciences, Elsevier, vol. 17(3), pages 329-334, June.
    10. Fan-Chin Kung, 2015. "Sorting out single-crossing preferences on networks," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(3), pages 663-672, March.
    11. Schummer, James & Vohra, Rakesh V., 2002. "Strategy-proof Location on a Network," Journal of Economic Theory, Elsevier, vol. 104(2), pages 405-428, June.
    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. Hans Peters & Souvik Roy & Soumyarup Sadhukhan, 2021. "Unanimous and Strategy-Proof Probabilistic Rules for Single-Peaked Preference Profiles on Graphs," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 811-833, May.
    2. repec:spo:wpmain:info:hdl:2441/4ccevsvsdm96qpv5fgamlf1p1p is not listed on IDEAS
    3. Sidartha Gordon, 2015. "Unanimity in attribute-based preference domains," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(1), pages 13-29, January.
    4. Chatterji, Shurojit & Sanver, Remzi & Sen, Arunava, 2013. "On domains that admit well-behaved strategy-proof social choice functions," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1050-1073.
    5. Vannucci, Stefano, 2020. "Single peaked domains with tree-shaped spectra," Mathematical Social Sciences, Elsevier, vol. 108(C), pages 74-80.
    6. Sidartha Gordon, 2014. "Unanimity in Attribute-Based Preference Domains," SciencePo Working papers Main hal-01061994, HAL.
    7. repec:spo:wpecon:info:hdl:2441/4ccevsvsdm96qpv5fgamlf1p1p is not listed on IDEAS
    8. Masashi Umezawa, 2012. "The replacement principle for the provision of multiple public goods on tree networks," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(2), pages 211-235, February.
    9. Madhuparna Karmokar & Souvik Roy & Ton Storcken, 2021. "Necessary and sufficient conditions for pairwise majority decisions on path-connected domains," Theory and Decision, Springer, vol. 91(3), pages 313-336, October.
    10. Chatterji, Shurojit & Sen, Arunava & Zeng, Huaxia, 2016. "A characterization of single-peaked preferences via random social choice functions," Theoretical Economics, Econometric Society, vol. 11(2), May.
    11. Bonifacio, Agustín G. & Massó, Jordi, 2020. "On strategy-proofness and semilattice single-peakedness," Games and Economic Behavior, Elsevier, vol. 124(C), pages 219-238.
    12. Gopakumar Achuthankutty & Souvik Roy, 2018. "On single-peaked domains and min–max rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(4), pages 753-772, December.
    13. Sidartha Gordon, 2014. "Unanimity in Attribute-Based Preference Domains," SciencePo Working papers hal-01061994, HAL.
    14. Bettina Klaus, 2001. "Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces," Theory and Decision, Springer, vol. 51(1), pages 13-29, August.
    15. Ernesto Savaglio & Stefano Vannucci, 2012. "Strategy-proofness and unimodality in bounded distributive lattices," Department of Economics University of Siena 642, Department of Economics, University of Siena.
    16. repec:hal:wpspec:info:hdl:2441/4ccevsvsdm96qpv5fgamlf1p1p is not listed on IDEAS
    17. Bandhu, Sarvesh & Mondal, Bishwajyoti & Pramanik, Anup, 2022. "Strategy-proofness of the unanimity with status-quo rule over restricted domains," Economics Letters, Elsevier, vol. 210(C).
    18. Ernesto Savaglio & Stefano Vannucci, 2014. "Strategy-proofness and single-peackedness in bounded distributive lattices," Papers 1406.5120, arXiv.org.
    19. Achuthankutty, Gopakumar & Roy, Souvik, 2017. "On Top-connected Single-peaked and Partially Single-peaked Domains," MPRA Paper 78102, University Library of Munich, Germany.
    20. repec:hal:spmain:info:hdl:2441/4ccevsvsdm96qpv5fgamlf1p1p is not listed on IDEAS
    21. Michel Breton & Vera Zaporozhets, 2009. "On the equivalence of coalitional and individual strategy-proofness properties," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(2), pages 287-309, August.
    22. Haris Aziz & Markus Brill & Vincent Conitzer & Edith Elkind & Rupert Freeman & Toby Walsh, 2017. "Justified representation in approval-based committee voting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 461-485, February.
    23. Chatterji, Shurojit & Zeng, Huaxia, 2023. "A taxonomy of non-dictatorial unidimensional domains," Games and Economic Behavior, Elsevier, vol. 137(C), pages 228-269.
    24. Alcalde-Unzu, Jorge & Vorsatz, Marc, 2018. "Strategy-proof location of public facilities," Games and Economic Behavior, Elsevier, vol. 112(C), pages 21-48.

    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:hal:journl:hal-03834509. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.