Cycles and Intractability in a Large Class of Aggregation Rules
Authors: William S. Zwicker
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the (j, k)-Kemeny rule a generalization of Kemeny s voting rule that aggregates j-chotomous weak orders into a k-chotomous weak order. Special cases of (j, k)Kemeny include approval voting, the mean rule and Borda mean rule, as well as the Borda count and plurality voting. Why, then, is the winner problem computationally tractable for each of these other rules, but intractable for Kemeny? We show that intractability of winner determination for the (j, k)-Kemeny rule first appears at the j = 3, k = 3 level. The proof rests on a reduction of max cut to a related problem on weighted tournaments, and reveals that computational complexity arises from the cyclic part in the fundamental decomposition of a weighted tournament into cyclic and cocyclic components. Thus the existence of majority cycles the engine driving both Arrow s impossibility theorem and the Gibbard-Satterthwaite theorem also serves as a source of computational complexity in social choice. |
| Researcher Affiliation | Academia | William S. Zwicker EMAIL Mathematics Department, Union College, Schenectady, NY 12308 USA |
| Pseudocode | No | The paper describes theoretical concepts, mathematical proofs, and algorithms verbally but does not include any explicitly labeled pseudocode or algorithm blocks with structured steps. |
| Open Source Code | No | The paper does not contain any statements about making source code available, nor does it provide links to repositories or supplementary materials for code. |
| Open Datasets | No | The paper introduces theoretical rules and complexity analysis, using abstract concepts like "weighted tournaments" and "profiles of weak orders." While it presents Example 2 (T28) to illustrate concepts, this is a constructed example within the paper, not a reference to a publicly available dataset used for empirical evaluation. There are no mentions of specific public datasets, links, or citations for data access. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, it does not provide information on training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical, focusing on mathematical proofs and computational complexity. It does not describe any experimental setup or mention specific hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical concepts and complexity analysis. It does not mention any specific software or library dependencies with version numbers that would be required to replicate experimental results. |
| Experiment Setup | No | The paper is theoretical, presenting mathematical proofs and analyses of computational complexity. It does not describe any experimental setup, hyperparameters, or training configurations, as it does not involve empirical experimentation. |