Closed paths in graphs vs. voting theory
Bibliographic Data
| ID | 21405376 |
|---|---|
| Authors | Donald G Saari (University of California, Irvine, corresponding author) |
| Year | 2024 |
| Volume | 97 |
| Issue | 3 |
| Pages | 455-483 |
| Publication date | 2024-11-01 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Theory and Decision (JOURNAL) |
| Journal identifiers | ISSN: 0040-5833 • E-ISSN: 1573-7187 |
| Publisher | Springer Science and Business Media LLC (PUBLISHER) |
| DOI | 10.1007/s11238-024-09981-z |
| OpenAlex | W4396547070 |
| Language | EN |
| References cited | 5 |
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
Arrow · Combinatorics · Discrete mathematics · Graph · Graph theory · Indifference graph · Line graph · Mathematical economics · Pathwidth · Surprise · Voting · Computer Science · Game Theory and Applications · Game Theory and Voting Systems · Mathematics · Merger and Competition Analysis
| Citation velocity | historical |
|---|---|
| Highly cited | No |