Imagine trying to rank individual software developers based only on the success of the project teams they join, or ranking genes based on the health outcomes of the combinations in which they express themselves. This is the core challenge of social ranking from coalition performance: deriving a total, transitive ordering of individuals given only an ordinal ranking or evaluation of the groups (coalitions) to which they belong.
By bridging cooperative game theory and social choice theory, recent research provides a principled framework for isolating individual contributions from collective outcomes.
The Ceteris Paribus Principle: Isolating Marginal Contributions
How do we isolate an individual's value when we only observe group-level performance? The cleanest approach relies on the concept of ceteris paribus—all else being equal. To compare individual $i$ and individual $j$, we should look at pairs of coalitions that are completely identical except that one contains $i$ and the other contains $j$.
For any background context $S$ (a coalition containing neither $i$ nor $j$), we can directly compare the performance of $S \cup \{i\}$ against $S \cup \{j\}$. As formalized by Haret et al. (2018), the ceteris paribus majority (CP-majority) rule aggregates these comparisons by counting how often $S \cup \{i\}$ outperforms $S \cup \{j\}$ across all possible background contexts $S$. If $i$ wins the majority of these head-to-head context matchups, $i$ is socially ranked above $j$. This approach effectively treats each background coalition as an independent test environment, isolating the true marginal difference between the two individuals.
Aggregating via Pairwise Voting Rules
Once we establish how individuals compare across various coalitions, the problem maps directly onto preference aggregation in social choice theory. We can view each background coalition context as a "voter" expressing a preference between individual $i$ and individual $j$.
To aggregate these distributed preferences into a single global ranking, the authors frequently adapt classic voting rules. For instance, the Copeland voting rule—extensively analyzed for its computational robustness by Faliszewski et al. (2007)—calculates an alternative's score by subtracting its total pairwise losses from its pairwise wins.
Allouche et al. (2020) apply this Copeland-like logic to coalition data, ranking individuals based on their net wins across all pairwise coalition contests. This connection between voting and ranking is highly versatile; it can even run in reverse. For example, Brandes et al. (2022) demonstrated that network centrality indices can be framed as voting rules where nodes act as both voters and candidates. In their framework, a node's structural importance is determined by aggregating node preferences via rules like Copeland voting, proving that pairwise tournament aggregation is a mathematically rigorous way to surface the most critical components of a system.
Overcoming Intransitivity and Paradoxes
The fundamental challenge of any pairwise aggregation method is the Condorcet paradox: pairwise majorities can easily become cyclical ($A$ beats $B$, $B$ beats $C$, but $C$ beats $A$), making a stable, transitive ranking impossible. In social ranking, researchers use two primary strategies to guarantee a consistent ordering:
- Domain Restrictions: Haret et al. (2018) introduced the concept of social single-peakedness. By constraining the structure of the underlying coalition performance data—ensuring that coalitions align along a shared, one-dimensional structural spectrum—they prove that cyclical paradoxes are entirely avoided, guaranteeing a transitive social ranking.
- Ordinal Power Indices: Instead of running direct head-to-head matchups between individuals, we can compute an absolute score for each individual based on their standalone marginal impact. Khani et al. (2019) introduced the ordinal Banzhaf index for this purpose. For every possible coalition, an individual receives a score of $+1$ if their addition improves the coalition's rank, $-1$ if it worsens it, and $0$ if the rank remains unchanged. By summing these ordinal marginal contributions, every individual receives a scalar score. Because the final social ranking is derived by simply sorting these scores, transitivity is mathematically guaranteed without requiring any domain restrictions on the input data.
Strategic Robustness and Manipulability
If these ranking systems are deployed in real-world scenarios (such as multi-agent systems or collaborative workplaces), can individuals manipulate the outcome? For example, could an agent intentionally underperform when participating in a specific coalition to alter the relative ranking of a rival?
Allouche et al. (2020) evaluated this vulnerability across several prominent social ranking solutions. They discovered a trade-off between responsiveness and strategic immunity:
| Social Ranking Rule | Mechanism | Vulnerable to Manipulation? | Computational Complexity of Finding Manipulation |
|---|---|---|---|
| Lexicographic Excellence | Ranks individuals based on their frequency in the absolute highest-performing coalitions. | No (Robust) | N/A |
| CP-Majority / Copeland-like | Aggregates net wins and losses from pairwise coalition contests. | Yes | NP-hard |
| Ordinal Banzhaf | Sums positive and negative ordinal marginal contributions. | Yes | NP-hard |
While Copeland-like and ordinal Banzhaf rules are theoretically susceptible to strategic manipulation, the authors proved that determining how to successfully manipulate them is NP-hard. This computational barrier provides a practical layer of security, ensuring that these elegant mathematical aggregations remain robust in practice.
Key Foundational Work
Ceteris paribus majority for social ranking (2018) — contributed 6 concept elements to this direction.
Llull and Copeland Voting Broadly Resist Bribery and Control (2007) — contributed 1 concept elements to this direction.