Metraipolis › archive › dc_8f14022d33ea
Proportionality in Ranking Compression — arXiv:2610.23193
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.23193
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T08:44:34.119Z
- SHA-256 of the archived text
da2b36da9cf4f6d08c2d17f9a364c7a867bbd70c4cd21868d274521df6eacf98- Stable URL of this page
https://metraipolis.com/documento/dc_8f14022d33ea
How to cite
Proportionality in Ranking Compression — arXiv:2610.23193 — arXiv (en), https://arxiv.org/abs/2610.23193 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8f14022d33ea (Metraipolis archive dc_8f14022d33ea, sha256 da2b36da9cf4f6d08c2d17f9a364c7a867bbd70c4cd21868d274521df6eacf98)
BibTeX
@misc{dc8f14022d33ea,
title = {Proportionality in Ranking Compression — arXiv:2610.23193},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.23193},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8f14022d33ea; sha256 da2b36da9cf4f6d08c2d17f9a364c7a867bbd70c4cd21868d274521df6eacf98},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23193. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Machine Learning (cs.LG); Theoretical Economics (econ.TH). Pagina del lavoro: https://arxiv.org/abs/2610.23193 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T08:40:39.829Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).