Modal Ranking: A Uniquely Robust Voting Rule
Authors: Ioannis Caragiannis, Ariel Procaccia, Nisarg Shah
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our results. We give a rather clear-cut solution to the preceding research challenge: There is a voting rule that is robust against any reasonable noise model, and it is unique within a huge family of voting rules. We call this supremely robust voting rule the modal ranking rule. Given a collection of input rankings, the modal ranking rule simply selects the most frequent ranking as the output. To the best of our knowledge, this strikingly basic voting rule has not received any attention in the literature, and for good reason: when the number of voters is not huge compared to the number of alternatives, it is likely that every ranking would appear at most once, so the modal ranking rule does not provide any useful guidance. However, when the number of voters is very large, the modal ranking rule is quite sensible; we will prove this intuitive claim formally. To better understand this result (still on an informal level), we need to clarify two points: What do we mean by reasonable noise model? And what is the huge family of voting rules? Starting from the noise model, we employ some additional notions introduced by Caragiannis et al. (2013). We are interested in noise models that are d-monotone with respect to a distance function d on rankings, in the sense that the probability of a ranking increases as its distance according to d from the ground truth ranking decreases. A voting rule that is accurate in the limit with respect to any d-monotone noise model is said to be monotone-robust with respect to d. So, slightly more formally, the requirement is that the rule be monotone-robust with respect to any distance metric d. Regarding the family of voting rules in which we prove that modal ranking is the unique robust rule, it is formed by the union of three families of rules: generalized scoring rules (GSRs) (Xia and Conitzer 2008; 2009; Xia 2013) with the no holes property, pairwise majority consistent (PM-c) rules, and position dominance consistent (PD-c) rules (Caragiannis, Procaccia, and Shah 2013). GSRs are a large family of voting rules that is known to capture almost all commonly-studied voting rules. Theorem 1 asserts that a GSR with no holes is monotone-robust with respect to all distance metrics if and only if it is the modal ranking rule. The no holes property is a technical restriction, but in Theorem 2 we show that it is quite mild by establishing that all prominent rules that are known to be GSRs have the no holes property. PM-c and PD-c rules together also contain most prominent voting rules (Caragiannis, Procaccia, and Shah 2013). These two families are disjoint, and neither is contained in the family of GSRs. Theorem 3 asserts that PM-c and PD-c rules do not have the desired robustness property, thereby further extending the scope of the modal ranking rule s uniqueness to all rules that are PM-c or PD-c but not GSRs (with no holes). See Figure 1 for a Venn diagram that illustrates the relation between these families of rules. |
| Researcher Affiliation | Academia | Ioannis Caragiannis University of Patras caragian@ceid.upatras.gr Ariel D. Procaccia Carnegie Mellon University arielpro@cs.cmu.edu Nisarg Shah Carnegie Mellon University nkshah@cs.cmu.edu |
| Pseudocode | No | The paper is theoretical and focuses on mathematical proofs and definitions of voting rules; it does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access (e.g., specific repository link, explicit release statement) to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper that does not involve training models on datasets. Therefore, no information about publicly available training data is relevant or provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve data splits for validation or training. Therefore, no information on dataset splits is provided. |
| Hardware Specification | No | This is a theoretical paper and does not involve computational experiments requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper focusing on mathematical proofs and definitions; it does not describe any computational experiments that would require software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe empirical experiments with hyperparameters or training settings. Therefore, no experimental setup details are provided. |