Ranking compression methods guarantee fair representation in rankings
Proportionality in Ranking Compression
Computer Science and Game TheoryMachine Learning
Summary
Sometimes, we need to shorten a long list of rankings into a smaller set but still keep it fair and representative of the original. The authors studied different ways to measure fairness in this process, called proportionality. They found that two of these fairness ideas can always be achieved efficiently, while a third is harder but works well under certain ranking patterns. This helps make sure that when compressing rankings, important preferences are still respected.
What this means in practice
- •For machine learning engineers: Compress human feedback rankings into smaller sets while preserving fair representation for reinforcement learning systems.
- •For voting system designers: Design multiwinner election methods that guarantee proportional representation in compressed ranking outcomes under certain preference structures.
A theory result. No direct application yet.
Authors
Daniel Halpern, Xinyu Liu, Evi Micha, Yu Peng Ng, Warut Suksompong
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.