IDEAS home Printed from https://ideas.repec.org/a/kap/theord/v97y2024i3d10.1007_s11238-024-09981-z.html
   My bibliography  Save this article

Closed paths in graphs vs. voting theory

Author

Listed:
  • Donald G. Saari

    (University of California)

Abstract

Features of graphs that hinder finding closed paths with particular properties, as represented by the Traveling Salesperson Problem—TSP, are identified for three classes of graphs. Removing these terms leads to a companion graph with identical closed path properties that is easier to analyze. A surprise is that these troubling graph factors are precisely what is needed to analyze certain voting methods, while the companion graph’s terms are what cause voting theory complexities as manifested by Arrow’s Theorem. This means that the seemingly separate goals of analyzing closed paths in graphs and analyzing voting methods are complementary: components of data terms that assist in one of these areas are the source of troubles in the other. Consequences for standard decision methods are in Sects. 2.5, 3.7 and the companion paper (Saari in Theory Decis 91(3):377–402, 2021). The emphasis here is on paths in graphs; incomplete graphs are similarly handled.

Suggested Citation

  • Donald G. Saari, 2024. "Closed paths in graphs vs. voting theory," Theory and Decision, Springer, vol. 97(3), pages 455-483, November.
    • Handle: RePEc:kap:theord:v:97:y:2024:i:3:d:10.1007_s11238-024-09981-z
    DOI: 10.1007/s11238-024-09981-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11238-024-09981-z
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11238-024-09981-z?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. Donald G. Saari, 2019. "Arrow, and unexpected consequences of his theorem," Public Choice, Springer, vol. 179(1), pages 133-144, April.
    2. Merrill M. Flood, 1956. "The Traveling-Salesman Problem," Operations Research, INFORMS, vol. 4(1), pages 61-75, February.
    3. Donald G. Saari, 2021. "Seeking consistency with paired comparisons: a systems approach," Theory and Decision, Springer, vol. 91(3), pages 377-402, October.
    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. Donald G. Saari, 2023. "Selecting a voting method: the case for the Borda count," Constitutional Political Economy, Springer, vol. 34(3), pages 357-366, September.
    2. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    3. Arthur Charpentier & Romuald Élie & Carl Remlinger, 2023. "Reinforcement Learning in Economics and Finance," Computational Economics, Springer;Society for Computational Economics, vol. 62(1), pages 425-462, June.
    4. Chen, Hanwen & Liu, Siyi & Wang, Junjie & Wu, Zhijuan, 2022. "The effect of geographic proximity on corporate tax avoidance: Evidence from China," Journal of Corporate Finance, Elsevier, vol. 72(C).
    5. Jose Gonzalez-Velarde & Salvador Garcia-Lumbreras & Alberto Garcia-Diaz, 2008. "A multi-stop routing problem," Annals of Operations Research, Springer, vol. 157(1), pages 153-167, January.
    6. Carlos Contreras-Bolton & Victor Parada, 2015. "Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem," PLOS ONE, Public Library of Science, vol. 10(9), pages 1-25, September.
    7. Cristina Maria Păcurar & Ruxandra-Gabriela Albu & Victor Dan Păcurar, 2021. "Tourist Route Optimization in the Context of Covid-19 Pandemic," Sustainability, MDPI, vol. 13(10), pages 1-17, May.
    8. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    9. Arthur Charpentier & Romuald Elie & Carl Remlinger, 2020. "Reinforcement Learning in Economics and Finance," Papers 2003.10014, arXiv.org.
    10. Ioannou, Petros & Giuliano, Genevieve & Dessouky, Maged & Chen, Pengfei & Dexter, Sue, 2020. "Freight Load Balancing and Efficiencies in Alternative Fuel Freight Modes," Institute of Transportation Studies, Working Paper Series qt3ns4b894, Institute of Transportation Studies, UC Davis.
    11. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    12. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    13. Yenny Villuendas-Rey & José L. Velázquez-Rodríguez & Mariana Dayanara Alanis-Tamez & Marco-Antonio Moreno-Ibarra & Cornelio Yáñez-Márquez, 2021. "Mexican Axolotl Optimization: A Novel Bioinspired Heuristic," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    14. Sihan Wang & Cheng Han & Yang Yu & Min Huang & Wei Sun & Ikou Kaku, 2022. "Reducing Carbon Emissions for the Vehicle Routing Problem by Utilizing Multiple Depots," Sustainability, MDPI, vol. 14(3), pages 1-18, January.
    15. Remigiusz Iwańkowicz, 2021. "Effective Permutation Encoding for Evolutionary Optimization of the Electric Vehicle Routing Problem," Energies, MDPI, vol. 14(20), pages 1-18, October.
    16. Seokgi Lee & Hyun Woo Jeon & Mona Issabakhsh & Ahmad Ebrahimi, 2022. "An electric forklift routing problem with battery charging and energy penalty constraints," Journal of Intelligent Manufacturing, Springer, vol. 33(6), pages 1761-1777, August.
    17. Zhouchun Huang & Qipeng Phil Zheng & Eduardo Pasiliao & Vladimir Boginski & Tao Zhang, 2019. "A cutting plane method for risk-constrained traveling salesman problem with random arc costs," Journal of Global Optimization, Springer, vol. 74(4), pages 839-859, August.
    18. Kate, Joeri ten & Teunter, Ruud & Kusumastuti, Ratih Dyah & van Donk, Dirk Pieter, 2017. "Bio-diesel production using mobile processing units: A case in Indonesia," Agricultural Systems, Elsevier, vol. 152(C), pages 121-130.
    19. Przemysław Kowalik & Grzegorz Sobecki & Piotr Bawoł & Paweł Muzolf, 2023. "A Flow-Based Formulation of the Travelling Salesman Problem with Penalties on Nodes," Sustainability, MDPI, vol. 15(5), pages 1-28, February.
    20. Katrin Heßler & Stefan Irnich, 2020. "A Branch-and-Cut Algorithm for the Soft-Clustered Vehicle-Routing Problem," Working Papers 2001, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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:kap:theord:v:97:y:2024:i:3:d:10.1007_s11238-024-09981-z. 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.