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. Lei, Chao & Ouyang, Yanfeng, 2024. "Average minimum distance to visit a subset of random points in a compact region," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
    3. 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).
    4. Herer, Yale T., 1999. "Submodularity and the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 489-508, May.
    5. 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.
    6. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    7. Doppstadt, C. & Koberstein, A. & Vigo, D., 2016. "The Hybrid Electric Vehicle – Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 825-842.
    8. 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).
    9. Maximilian Zähringer & Sebastian Wolff & Jakob Schneider & Georg Balke & Markus Lienkamp, 2022. "Time vs. Capacity—The Potential of Optimal Charging Stop Strategies for Battery Electric Trucks," Energies, MDPI, vol. 15(19), pages 1-18, September.
    10. 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.
    11. 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.
    12. Burcu B. Keskin & İbrahim Çapar & Charles R. Sox & Nickolas K. Freeman, 2014. "An Integrated Load-Planning Algorithm for Outbound Logistics at Webb Wheel," Interfaces, INFORMS, vol. 44(5), pages 480-497, October.
    13. 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.
    14. Kemal Ihsan Kilic & Leonardo Mostarda, 2022. "Novel Concave Hull-Based Heuristic Algorithm For TSP," SN Operations Research Forum, Springer, vol. 3(2), pages 1-45, June.
    15. Alonso Tabares, Diego & Mora-Camino, Felix & Drouin, Antoine, 2021. "A multi-time scale management structure for airport ground handling automation," Journal of Air Transport Management, Elsevier, vol. 90(C).
    16. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    17. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
    18. van Lon, Rinde R.S. & Ferrante, Eliseo & Turgut, Ali E. & Wenseleers, Tom & Vanden Berghe, Greet & Holvoet, Tom, 2016. "Measures of dynamism and urgency in logistics," European Journal of Operational Research, Elsevier, vol. 253(3), pages 614-624.
    19. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    20. 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.

    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.