TL;DR
This paper investigates the "manipulability" of social ranking rules, which determine how to rank individuals based on coalition performance. The authors show that while the "Lexicographic Excellence" rule is robust against manipulation, three other common rules (Copeland-like, Kramer-Simpson-like, and Ordinal Banzhaf) are susceptible. They further demonstrate that detecting manipulation for these rules is computationally hard (NP-hard) and provide simulation results on their vulnerability.
What Problem Does This Paper Address?
In many real-world scenarios, like elections, parliaments, or business organizations, we need to rank individuals based on the collective performance of groups (coalitions) they belong to. This is the domain of "social ranking rules." A crucial question in social choice theory is whether these rules can be "manipulated." Manipulation occurs when an individual can strategically alter their behavior (e.g., by weakening the performance of coalitions they are part of) to achieve a better individual ranking for themselves. This paper tackles the problem of understanding which social ranking rules are susceptible to such manipulation and how computationally difficult it is to detect or perform such manipulations.
Methods
The paper introduces a formal definition of manipulation for social ranking rules, where an individual can only degrade the ranking of coalitions they are part of. They then analyze four specific social ranking rules:
- Copeland-like and Kramer-Simpson-like: These rules are based on "Ceteris Paribus" (CP) comparisons, meaning they compare individuals based on their relative success in pairwise coalition comparisons. Copeland-like uses a net flow of pairwise wins/losses, while Kramer-Simpson-like focuses on the worst pairwise defeat.
- Ordinal Banzhaf: This rule is inspired by the Banzhaf index and counts the number of positive and negative "ordinal marginal contributions" an individual makes to coalitions.
- Lexicographic Excellence (lexcel): This rule ranks individuals based on the frequency of their presence in the highest-ranked coalitions, using a lexicographical comparison of these frequencies.
The authors prove theoretical results about the manipulability of these rules and analyze the computational complexity of detecting manipulation, showing it to be NP-hard for three of the rules. They also conduct simulations to empirically assess the frequency and impact of manipulations.
Datasets
Not discussed in the paper. The paper uses synthetic power relations generated for simulation purposes, not pre-existing datasets.
Key Insights and Ideas
- Not all social ranking rules are created equal: While some rules are inherently robust to manipulation (like Lexicographic Excellence), others are quite vulnerable. This highlights the importance of choosing the right rule based on desired properties.
- Lexicographic Excellence's "blindness" is its strength: The lexcel rule's focus on only the very best coalitions makes it hard for an individual to strategically influence its outcome by degrading other coalitions.
- Detecting manipulation is hard: For the Copeland-like, Kramer-Simpson-like, and Ordinal Banzhaf rules, determining if an individual can manipulate is an NP-hard problem. This means that finding a manipulation can be computationally very expensive, especially as the number of individuals grows.
- Real-world vulnerability: Simulations suggest that manipulable rules are indeed frequently manipulable, with the probability of a manipulable case increasing significantly with the number of individuals. The KS-like and Ordinal Banzhaf rules appear particularly vulnerable.
Key Results
- Lexicographic Excellence is not manipulable.
- Copeland-like, Kramer-Simpson-like, and Ordinal Banzhaf rules are manipulable.
- Determining manipulability for these three rules is NP-hard.
- Simulations show that the percentage of manipulable cases increases with the number of individuals, reaching very high levels (e.g., 99.6% for KS-like with n=4).
- The probability of an individual being ranked first through manipulation also increases with the number of individuals.
- Copeland-like appears to be more resistant to manipulation than the other two manipulable rules, with fewer potential manipulators on average.
Limitations and Future Work
The authors acknowledge that their definition of manipulation is limited to individuals acting alone and only degrading coalitions they belong to. Future work could explore:
- Axiomatic characterization of strategy-proof SRC rules: Developing rules that are guaranteed to be manipulation-proof from an axiomatic perspective, similar to Gibbard and Satterthwaite's work in social choice.
- Domain restrictions: Investigating how limiting the types of power relations considered might affect manipulability.
- Coalitional manipulation: Studying scenarios where groups of individuals might collude to manipulate the ranking.
- Simultaneous manipulation: Analyzing the game-theoretic aspects of multiple individuals attempting to manipulate at once.
Summary updated