IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v84y2016i1d10.1007_s00186-016-0535-3.html
   My bibliography  Save this article

It is difficult to tell if there is a Condorcet spanning tree

Author

Listed:
  • Andreas Darmann

    (University of Graz)

Abstract

We apply the well-known Condorcet criterion from voting theory outside of its classical framework and link it with spanning trees of an undirected graph. In situations in which a network, represented by a spanning tree of an undirected graph, needs to be installed, decision-makers typically do not agree on the network to be implemented. Instead, each of these decision-makers has her own ideal conception of the network. In order to derive a group decision, i.e., a single spanning tree for the entire group of decision-makers, the goal would be a spanning tree that beats each other spanning tree in a simple majority comparison. When comparing two dedicated spanning trees, a decision-maker will be considered to be more satisfied with the one that is “closer” to her proposal. In this context, the most basic and natural measure of distance is the usual set difference: we simply count the number of edges the spanning tree has in common with the proposal of the decision-maker. In this work, we show that it is computationally intractable to decide (1) if such a spanning tree exists, and (2) if a given spanning tree satisfies the Condorcet criterion.

Suggested Citation

  • Andreas Darmann, 2016. "It is difficult to tell if there is a Condorcet spanning tree," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(1), pages 93-104, August.
  • Handle: RePEc:spr:mathme:v:84:y:2016:i:1:d:10.1007_s00186-016-0535-3
    DOI: 10.1007/s00186-016-0535-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-016-0535-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s00186-016-0535-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Andreas Darmann, 2014. "It is hard to agree on a spanning tree," Economics Bulletin, AccessEcon, vol. 34(1), pages 34-40.
    2. Gilbert Laffond & Jean Lainé, 2009. "Condorcet choice and the Ostrogorski paradox," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 32(2), pages 317-333, February.
    3. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    4. Gehrlein, William V., 1985. "The Condorcet criterion and committee selection," Mathematical Social Sciences, Elsevier, vol. 10(3), pages 199-209, December.
    5. Barış Kaymak & M. Remzi Sanver, 2003. "Sets of alternatives as Condorcet winners," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 477-494, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Darmann, Andreas, 2018. "A social choice approach to ordinal group activity selection," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 57-66.
    2. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.

    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. Fatma Aslan & Hayrullah Dindar & Jean Lainé, 2022. "When are committees of Condorcet winners Condorcet winning committees?," Review of Economic Design, Springer;Society for Economic Design, vol. 26(3), pages 417-446, September.
    2. Salvador Barberà & Danilo Coelho, 2008. "How to choose a non-controversial list with k names," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(1), pages 79-96, June.
    3. Edith Elkind & Piotr Faliszewski & Piotr Skowron & Arkadii Slinko, 2017. "Properties of multiwinner voting rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(3), pages 599-632, March.
    4. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2019. "On some k-scoring rules for committee elections: agreement and Condorcet Principle," Working Papers hal-02147735, HAL.
    5. Diss, Mostapha & Mahajne, Muhammad, 2020. "Social acceptability of Condorcet committees," Mathematical Social Sciences, Elsevier, vol. 105(C), pages 14-27.
    6. Darmann, Andreas, 2013. "How hard is it to tell which is a Condorcet committee?," Mathematical Social Sciences, Elsevier, vol. 66(3), pages 282-292.
    7. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2018. "The Chamberlin-Courant Rule and the k-Scoring Rules: Agreement and Condorcet Committee Consistency," Working Papers halshs-01817943, HAL.
    8. Eric Kamwa & Vincent Merlin, 2018. "Coincidence of Condorcet committees," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 171-189, January.
    9. Mostapha Diss & Eric Kamwa & Abdelmonaim Tlidi, 2020. "On Some k -scoring Rules for Committee Elections: Agreement and Condorcet Principle," Revue d'économie politique, Dalloz, vol. 130(5), pages 699-725.
    10. Barberà, Salvador & Coelho, Danilo, 2010. "On the rule of k names," Games and Economic Behavior, Elsevier, vol. 70(1), pages 44-61, September.
    11. Darmann, Andreas, 2018. "A social choice approach to ordinal group activity selection," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 57-66.
    12. Barberà, Salvador & Coelho, Danilo, 2017. "Balancing the power to appoint officers," Games and Economic Behavior, Elsevier, vol. 101(C), pages 189-203.
    13. Mostapha Diss & Ahmed Doghmi, 2016. "Multi-winner scoring election methods: Condorcet consistency and paradoxes," Public Choice, Springer, vol. 169(1), pages 97-116, October.
    14. Edith Elkind & Jérôme Lang & Abdallah Saffidine, 2015. "Condorcet winning sets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(3), pages 493-517, March.
    15. Lombardi, Michele & Yoshihara, Naoki, 2016. "Partially-honest Nash Implementation with Non-connected Honesty Standards," Discussion Paper Series 633, Institute of Economic Research, Hitotsubashi University.
    16. Leo Katz & Alvaro Sandroni, 2020. "Limits on power and rationality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 507-521, March.
    17. Thibault Gajdos & John Weymark, 2005. "Multidimensional generalized Gini indices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(3), pages 471-496, October.
    18. List, Christian & Polak, Ben, 2010. "Introduction to judgment aggregation," Journal of Economic Theory, Elsevier, vol. 145(2), pages 441-466, March.
    19. Aleskerov, Fuad & Karabekyan, Daniel & Sanver, M. Remzi & Yakuba, Vyacheslav, 2012. "On the manipulability of voting rules: The case of 4 and 5 alternatives," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 67-73.
    20. Guido Bonatti & Enrico Ivaldi, 2016. "Un indicatore per la misurazione della partecipazione culturale e sociale nelle regioni italiane," ECONOMIA E DIRITTO DEL TERZIARIO, FrancoAngeli Editore, vol. 2016(2), pages 283-302.

    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:spr:mathme:v:84:y:2016:i:1:d:10.1007_s00186-016-0535-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.