Proportionality in Ranking Compression

Daniel Halpern; Xinyu Liu; Evi Micha; Yu Peng Ng; Warut Suksompong

cs.GTOct 16, 2026

Proportionality in Ranking Compression

Authors: Daniel Halpern, Xinyu Liu, Evi Micha, Yu Peng Ng, Warut Suksompong

Organizations: Google Research · U. of Southern California · National University of Singapore

Abstract

Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.

Figures & tables

Panel of Figure 1 — Figure 1: An example instance with $(n,m,k)=(6,4,3)$ and the corresponding DAG. The constraints below each vertex indicate the lower bound $q_{S}$ whenever it is nonzero. The solid blue path $\emptyset\!\to\!\{1\}\!\to\!\{1,2\}\!\to\!\{1,2,4\}\!\to\!\{1,2,3,4\}$ and the dashed green path $\emptyset\!\to\!\{3\}\!\to\!\{3,4\}\!\to\!\{1,3,4\}\!\to\!\{1,2,3,4\}$ correspond to the rankings $(1,2,4,3)$ and $(3,4,1,2)$ , respectively.

Panel of Figure 2 — Figure 2: A graph representing part of the constraints in the proof of Theorem 3 .

Rank Aggregation

Rank aggregation combines ranked lists or pairwise preferences into a consensus ordering for tasks such as search, recommendation, and model evaluation.

See all 30 papers

The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions
May 12, 2026Carmel Baharav, Niclas Boehmer, Bailey Flanigan +1Sequential Decision Making Group Fairness
MIT, USA · Hasso Plattner Institute, University of Potsdam, Germany
Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees
Sep 28, 2026Georgios PapasotiropoulosSocial Choice Theory Approximation Algorithms
University of Warsaw
Proportional Representation in Temporal Voting with Ranked Preferences
Sep 24, 2026Noam Hazon, Leora Schmerler, Nicholas TehSocial Choice Theory
Department of Data Science and AI, Ariel University · Department of Computer Science, University of Oxford

May 12, 2026J/K move · Enter open · S save

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

Carmel Baharav, Niclas Boehmer, Bailey Flanigan, Maximilian T. Wittmann

MIT, USA · Hasso Plattner Institute, University of Potsdam, Germany

Sequential Decision Making Group Fairness Shared Decision-Making

Open paper AskPDF arXiv

AI alignment and participatory design motivate a new democratic design problem: how to collectively choose a decision rule to use repeatedly. We study this problem for linear ranking rules, which repeatedly rank items

x_j

within batches

X=(x_1,\dots,x_m)\in(\mathbb{R}^d)^m

, where each item's ranking is dictated by its score

\langle θ^*,x_j\rangle

according to a fixed scoring vector

θ^*

. Given voters' preferred scoring vectors

θ^{(1)},\dots,θ^{(n)}

and their population fractions

α^{(1)},\dots,α^{(n)}

, we ask how to choose a collective vector

θ^*

satisfying individual proportionality (IP): every voter type

i

should agree with the resulting rankings to an

α^{(i)}

-proportional degree, either on average over time (long-run IP) or even within each batch (per-batch IP). The default rule, the arithmetic mean of the

θ^{(i)}

, has been shown to be severely majoritarian; more generally, it is not clear that any fixed linear rule can balance many voters' disparate opinions. Our main result is that, surprisingly, there is a simple rule that does satisfy long-run IP: the angular mean, the spherical analog of the arithmetic mean. We then show that exact per-batch IP is impossible for fixed linear rules, but that the gap between per-batch and long-run IP shrinks quickly with batch size. Experiments on three real-world preference datasets show that all rules perform similarly when voters' preferences are homogeneous, while the angular mean substantially improves proportionality in high-disagreement regimes.

Abstract

Rank Aggregation

Explore similar work

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

Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees

Proportional Representation in Temporal Voting with Ranked Preferences