Closed paths in graphs vs. voting theory

作     者：Saari, Donald G. 

作者机构：Univ Calif Irvine Irvine CA 92697 USA 

出 版 物：《THEORY AND DECISION》 (Theory Decis)

年 卷 期：2024年第97卷第3期

页      面：455-483页

核心收录：

学科分类：0303[法学-社会学] 03[法学] 0201[经济学-理论经济学] 0701[理学-数学] 

基　　金：National Science Foundation project under NSF [CMMI-1923164] 

主　　题：TSP Hamiltonian circuits Greedy algorithm Closed path symmetries Transitive rankings 

摘      要：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.