Closed paths in graphs vs. voting theory

In: Theory and decision: an international journal for multidisciplinary advances in decision science

Abstract

AbstractFeatures 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.