Technical Summary: Proportional Representation in Rank Aggregation

Problem Definition

The paper addresses the problem of rank aggregation, where the goal is to combine a profile of weighted input rankings into a single output ranking. In this setting, a profile $R$ consists of a set of candidates $C$ and a function mapping every possible ranking $\succ$ to a weight $R(\succ) \in [0, 1]$, such that the sum of all weights equals 1. These weights represent the importance of different criteria (e.g., price vs. rating in hotel booking) or the share of voters supporting a specific ranking.

The central challenge identified is that classical Social Welfare Functions (SWFs), such as the Kemeny rule, Borda count, and Condorcet-type rules, are inherently majoritarian. They tend to select the output ranking that minimizes the distance to the highest-weighted input, effectively ignoring minority preferences. For instance, if two inverse rankings have weights of 51% and 49%, standard SWFs often simply return the 51% ranking, failing to represent the 49% group. The paper seeks to design SWFs that guarantee proportional representation, ensuring that every input ranking influences the output in proportion to its weight.

Methodology and Framework

The authors formalize proportionality by defining the utility of an input ranking $\succ$ for an output ranking $\triangleright$ as the number of pairwise agreements between them:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ and } x \triangleright y\}|$$
Since there are $\binom{m}{2}$ total pairwise comparisons for $m$ candidates, an input ranking with weight $\alpha$ should ideally obtain a utility of at least $\lfloor \alpha \binom{m}{2} \rfloor$.

The paper introduces a hierarchy of proportionality axioms inspired by approval-based committee voting and participatory budgeting:

1. Unanimous Justified Representation (uJR): A weakening requiring that any input ranking with weight $\ge 1/\binom{m}{2}$ obtains at least one pairwise agreement.
2. Unanimous Proportional Justified Representation (uPJR): The core axiom requiring that an input ranking with weight $\alpha$ obtains utility at least $\lfloor \alpha \binom{m}{2} \rfloor$.
3. Strong Proportional Justified Representation (sPJR): A strengthening extending the guarantee to groups of rankings. If a subprofile $S$ has total weight $\alpha$, the output must agree with at least $\lfloor \alpha \binom{m}{2} \rfloor$ pairwise comparisons from the union of rankings in $S$.

To achieve these axioms, the authors adapt the concept of priceability from participatory budgeting. They model the construction of the output ranking as a sequential purchasing process where candidates (or pairs of candidates) are "bought" using the budgets of input rankings.

Key Contributions and Results

1. Limitations of Existing Methods

The paper first analyzes the Squared Kemeny rule (proposed by Lederer et al. [2024] for proportional ranking). The authors prove that for $m \ge 5$, the Squared Kemeny rule fails even the weakest axiom, uJR. Specifically, they construct profiles where an input ranking with significant weight receives zero utility from the Squared Kemeny output, demonstrating the need for new mechanisms.

2. The Proportional Sequential Borda Rule (PSB)

To satisfy uPJR, the authors propose the Proportional Sequential Borda rule (PSB).

• Mechanism: PSB operates sequentially. In each round, it selects the candidate maximizing the weighted Borda score based on current budgets. It then updates the budgets of input rankings proportionally to their contribution to the selected candidate's score, effectively "paying" for the candidate's placement.
• Theoretical Guarantee: The authors introduce a structured axiom called rank-priceability, which mirrors priceability in participatory budgeting. They prove that rank-priceability implies uPJR.
• Result: Theorem 4.5 establishes that PSB satisfies rank-priceability and, consequently, uPJR.
• Quantitative Guarantee: Beyond axiomatic satisfaction, Theorem 4.6 proves that PSB guarantees every subprofile $S$ an average utility of at least $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$. This provides a linear lower bound on utility relative to the group's weight.

3. The Flow-adjusting Borda Rule (FB)

The authors show that PSB fails sPJR because its payment scheme does not adequately protect groups of rankings that act in concert. To address this, they introduce pair-priceability, a refined axiom where payments are made for specific pairs of candidates rather than just ranks.

• Mechanism: The Flow-adjusting Borda rule (FB) is a refinement of PSB. Like PSB, it selects the Borda winner sequentially. However, instead of a simple proportional payment, FB determines payments by solving a maximum flow problem in a constructed network. This network ensures that the cost per utility ratio is minimized while respecting budget constraints and pair-wise constraints.
• Result: Theorem 5.5 proves that FB satisfies pair-priceability, which in turn implies sPJR (Theorem 5.3).
• Quantitative Guarantee: Theorem 5.6 shows that FB provides the same linear average utility guarantee as PSB ($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$), ensuring strong fairness for both individuals and groups.

4. Additional Variants

In the appendix, the authors discuss the Ranked Method of Equal Shares (RMES), a variant inspired by the Method of Equal Shares (MES) from participatory budgeting. They show RMES satisfies rank-priceability (and thus uPJR) and offers a slightly different utilitarian profile, selecting the first $\lfloor m/4 \rfloor$ candidates purely based on initial Borda scores.

Significance and Claims

The paper claims to present the first truly proportional Social Welfare Functions for rank aggregation. Its primary significance lies in:

• Bridging Fields: It successfully transfers deep results from approval-based committee voting and participatory budgeting (specifically PJR and priceability) to the domain of rank aggregation.
• Solving an Open Problem: It resolves the open problem of designing SWFs that satisfy uPJR and sPJR, which previous attempts (like Squared Kemeny) failed to achieve.
• Axiomatic and Quantitative Strength: The proposed rules (PSB and FB) are not only proven to satisfy strong axiomatic fairness conditions but also provide robust quantitative guarantees on the average utility for any group of voters, ensuring that minority preferences are not systematically ignored.

The authors note that while their work focuses on pairwise agreement as the utility metric, this is a standard approach in the literature. They suggest future work could explore stronger fairness notions (like EJR or core-stability) and more general utility functions that account for the varying value of different ranking positions.