Technical Summary: The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions

1. Problem Statement

The paper addresses the challenge of collectively choosing a decision rule for repeated use in democratic design contexts, such as AI alignment, resource allocation (e.g., kidney exchange, food donation), and participatory design. Specifically, the authors focus on linear ranking rules, where a batch of $m$ items $X = (x_1, \dots, x_m)$, each described by a feature vector $x \in \mathbb{R}^d$, is ranked based on a score $s_\theta(x) = \langle \theta, x \rangle$ derived from a fixed scoring vector $\theta$.

The core aggregation problem is defined as follows: Given $n$ voter types with ideal scoring vectors $\theta^{(1)}, \dots, \theta^{(n)}$ and population fractions $\alpha^{(1)}, \dots, \alpha^{(n)}$, how should one select a collective scoring vector $\theta^*$?

The central concern is representational inequality over time. A fixed rule applied repeatedly may consistently align with the preferences of a majority while systematically overriding minority viewpoints. The paper seeks an aggregation mechanism that satisfies Individual Proportionality (IP): if voter type $i$ constitutes a fraction $\alpha^{(i)}$ of the population, the collective ranking should agree with type $i$'s preferred ranking on at least an $\alpha^{(i)}$ fraction of item pairs.

The paper distinguishes between two notions of IP:

1. Long-Run IP: Proportionality holds in expectation over batches drawn from a distribution $\mathcal{D}$.
2. Per-Batch IP: Proportionality holds for every specific batch $X$ (or in expectation over the minimum agreement within a batch).

2. Methodology and Theoretical Framework

2.1. The Failure of the Arithmetic Mean

The standard approach in the literature is the arithmetic mean ($\theta_{\text{arith}}$), defined as the weighted average of individual scoring vectors. The authors cite Feffer et al. [2023] to demonstrate that $\theta_{\text{arith}}$ is severely majoritarian. In "Antipodal Constructions" (where two voter types have diametrically opposed vectors), the arithmetic mean can converge entirely to the majority's vector, resulting in zero agreement for the minority, regardless of the batch size or distribution.

2.2. The Angular Mean ($\theta_{\text{ang}}$)

The primary methodological contribution is the proposal of the angular mean as an alternative aggregation rule. It is defined as the minimizer of the weighted sum of squared angular distances:
$$\theta_{\text{ang}} := \arg\min_{\theta \in S^{d-1}} \sum_{i=1}^n \alpha^{(i)} \angle(\theta, \theta^{(i)})^2$$
Unlike the arithmetic mean, which minimizes Euclidean distance, the angular mean operates on the sphere $S^{d-1}$, respecting the geometric nature of ranking directions.

2.3. Theoretical Analysis

The authors analyze the properties of $\theta_{\text{ang}}$ under the assumption of spherically symmetric item distributions ($\mathcal{D}^\circ$).

• Long-Run IP: They prove that $\theta_{\text{ang}}$ satisfies Long-Run IP (i.e., achieves a proportionality level of at least 1) for any profile. This relies on a fundamental geometric property: the angular mean lies within an angle of $(1 - \alpha^{(i)})\pi$ from every voter's ideal vector $\theta^{(i)}$.
• Per-Batch IP: The paper establishes an impossibility result for Per-Batch IP. No fixed linear ranking rule can guarantee proportionality for every single batch, even when entitlements are integral. This is due to "near-collinear" batches where items align in a way that forces a linear rule to completely disagree with at least one voter type.
• Convergence: However, the authors prove that the gap between Per-Batch IP and Long-Run IP shrinks rapidly as the batch size $m$ increases. Specifically, the deviation is bounded by $O(\sqrt{\frac{\min(\log n, d \log(m/d))}{m}})$.

3. Key Contributions

1. Existence of a Proportional Linear Rule: The paper proves that the angular mean is a simple, interpretable, fixed linear rule that guarantees Long-Run Individual Proportionality for spherically symmetric distributions. This resolves the open question of whether any fixed linear rule can balance disparate opinions without being inherently majoritarian.
2. Fundamental Geometric Property: The authors establish a new theorem (Theorem 3.3) regarding the angular mean in $d$ dimensions: for any profile, the angular mean is guaranteed to lie within an angle of $(1 - \alpha^{(i)})\pi$ from any voter $i$'s vector. This generalizes known 2D results to higher dimensions.
3. Impossibility and Convergence Bounds: The paper formally proves that Per-Batch IP is impossible for fixed linear rules (Theorem 4.3) but demonstrates that the loss incurred by restricting to fixed rules is negligible for large batch sizes (Theorem 4.5).
4. Robustness: The angular mean is shown to be robust; if a scoring vector is close to $\theta_{\text{ang}}$ in angular distance, its proportionality guarantees degrade only additively.

4. Empirical Results

The authors evaluate five aggregation mechanisms on three real-world datasets (Moral Machine, Kidney Exchange, Food Rescue) and their synthetic 2D variants designed to increase voter heterogeneity:

• Rules Tested: Arithmetic Mean ($\theta_{\text{arith}}$), Angular Mean ($\theta_{\text{ang}}$), Geometric Median, Borda Count, and Proportional Sequential Borda (PSB).
• Homogeneous Regimes: On the original datasets where voter preferences are relatively similar, all rules (including the arithmetic mean) perform similarly and satisfy proportionality.
• Heterogeneous Regimes (2D Data): When voter vectors are spread across a wide arc (simulating high disagreement):
  • The arithmetic mean and geometric median fail significantly, often dropping below the proportional entitlement (Long-IP < 1).
  • The angular mean substantially outperforms the arithmetic mean and geometric median, maintaining Long-IP $\ge 1$.
  • PSB (a non-linear, non-fixed rule) performs best, confirming that relaxing the "fixed linear" constraint yields further gains, but the angular mean remains the best performing fixed linear rule.
• Convergence: Empirical results confirm that Per-Batch IP converges to Long-Run IP very quickly as batch size $m$ grows, even for small $m$.

5. Significance and Claims

The paper claims to provide a best-case benchmark for aggregating decision rules. By showing that a fixed linear rule (the angular mean) can satisfy long-run proportionality, the authors argue that lower-information pipelines (which must learn rules from noisy data) should aim to preserve the structure of the angular mean.

The significance lies in:

• Correcting a Majoritarian Flaw: It identifies a simple, interpretable alternative to the arithmetic mean that avoids the "tyranny of the majority" in repeated decision-making.
• Theoretical Guarantees: It provides the first proof that a fixed linear rule can satisfy long-run individual proportionality, a property previously thought difficult or impossible for fixed rules.
• Practical Applicability: The angular mean is computationally tractable (via gradient-based optimization) and robust to non-spherical distributions in practice, making it a viable candidate for real-world applications in AI alignment and participatory design.

The authors remain modest about the limitations, acknowledging that while $\theta_{\text{ang}}$ solves the long-run problem, it cannot achieve the stronger per-batch guarantee without sacrificing the "fixed linear" constraint, a trade-off that diminishes with larger batch sizes.