TL;DR
This paper introduces a novel "ceteris paribus majority" principle for social ranking, which ranks individuals based on how coalitions they belong to perform, holding all other factors constant. They provide an axiomatic characterization and explore how to avoid paradoxes by restricting the input data, drawing parallels to single-peaked preferences in voting theory.
What Problem Does This Paper Address?
Imagine you need to rank individuals or objects based on how well groups (coalitions) they are part of perform. This is common in areas like comparing researchers in a department based on team projects, or ranking political parties by their alliances. The challenge is that we often only have ordinal information about coalition performance – we know coalition A is better than coalition B, but not by how much. This paper tackles how to derive a social ranking of individuals from such "power relations" between coalitions. A key difficulty is that standard approaches can lead to paradoxical outcomes (like A > B, B > C, but C > A), similar to the Condorcet paradox in voting.
Methods
The core contribution is the ceteris paribus majority principle. This principle compares two individuals, say i and j, by looking at pairs of coalitions that differ only by the presence of i versus j. For example, if we have a ranking of coalitions like S U {i} > S U {j}, this is interpreted as evidence that i is better than j, ceteris paribus (all else being equal). The authors formalize this by counting how many such comparisons favor i over j versus j over i.
They then provide an axiomatic characterization of this principle for the case of comparing just two individuals, using properties like Equality of Coalitions (EC), Neutrality (N), and Positive Responsiveness (PR). To address the paradoxes that can arise with more than two individuals, they introduce a domain restriction called social single-peakedness. This property, analogous to single-peaked preferences in voting theory, imposes a structure on the power relation that guarantees the resulting social ranking is transitive (no cycles). They also explore how to handle incomplete power relations, where not all coalition comparisons are known, by introducing an "Informative CP-Majority" that prioritizes comparisons from more informed coalitions.
Datasets
Not discussed in the paper. The paper uses hypothetical examples to illustrate its concepts.
Key Insights and Ideas
- "Ceteris Paribus" is Key: The idea of comparing individuals by isolating their specific contribution within otherwise identical coalitions is a powerful way to derive rankings from complex group performance data.
- Bridging Voting Theory and Coalition Analysis: The paper effectively translates concepts from social choice theory (like single-peakedness) to the domain of coalition rankings, offering a new perspective on how to analyze group dynamics.
- Incompleteness as Information: The paper highlights that missing information in coalition rankings isn't just a void; it can be structured (e.g., by "ignorance level") and used to refine ranking methods, giving more weight to comparisons derived from more complete data.
- Paradoxes are Manageable: The introduction of social single-peakedness demonstrates that by imposing reasonable structural constraints on the input data (the power relation), problematic cyclical rankings can be avoided.
Key Results
- The ceteris paribus majority rule is characterized by EC, N, and PR axioms for the two-alternative case.
- Social single-peakedness of the power relation is shown to be a sufficient condition to guarantee the transitivity (no cycles) of the ceteris paribus majority social ranking.
- An "Informative CP-Majority" rule is proposed to handle incomplete power relations, prioritizing comparisons from coalitions with less "ignorance."
Limitations and Future Work
- Sufficiency vs. Necessity: While social single-peakedness guarantees transitivity, the paper notes it's a sufficient, not necessarily necessary, condition. Future work could explore other domain restrictions that also prevent cycles.
- Axiomatic Characterization of ICP-Majority: The paper omits the axiomatic analysis of the Informative CP-Majority rule due to space constraints, leaving it as a direction for future research.
- Broader Information Exploitation: The authors suggest exploring social ranking solutions that leverage more general information from the power relation beyond just ceteris paribus comparisons.
- Applications: The paper mentions potential applications in multi-criteria decision making (MCDM) for comparing criteria importance, which could be a fruitful area for further investigation.
- Robustness: Analyzing the robustness of these social ranking solutions to small changes in the power relation is also identified as an open problem.
Summary updated