pipette
ENEnglish

Proportionality in Ranking Compression

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

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Appears in the 40th Annual Conference on Neural Information Processing Systems (NeurIPS), 2026