Metraipolis › archive › dc_108490c29ff7
Full Justified Representation in Temporal Voting: Efficient Computation and Verification — arXiv:2609.35826
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35826
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T17:25:47.983Z
- SHA-256 of the archived text
28a7f15fc621c94fc0eacdeb29377700bf3675c4f0dfff4051300e251f37ba69- Stable URL of this page
https://metraipolis.com/documento/dc_108490c29ff7
How to cite
Full Justified Representation in Temporal Voting: Efficient Computation and Verification — arXiv:2609.35826 — arXiv (en), https://arxiv.org/abs/2609.35826 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_108490c29ff7 (Metraipolis archive dc_108490c29ff7, sha256 28a7f15fc621c94fc0eacdeb29377700bf3675c4f0dfff4051300e251f37ba69)
BibTeX
@misc{dc108490c29ff7,
title = {Full Justified Representation in Temporal Voting: Efficient Computation and Verification — arXiv:2609.35826},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35826},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_108490c29ff7; sha256 28a7f15fc621c94fc0eacdeb29377700bf3675c4f0dfff4051300e251f37ba69},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35826. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting, since it allows different members of a group to be satisfied by different selected candidates. However, whether an FJR outcome can be computed in polynomial time has remained open. We resolve this question by introducing temporal FJR+, a strengthening of both FJR and extended justified representation+ (EJR+) that can be computed and verified in polynomial time. The axiom measures a group's agreement in each round by the largest number of its members who approve a common candidate, and requires some member to attain the integer part of the group's proportional share of its best attainable average satisfaction, with a shortfall of at most one unit when this share is an integer. We show that verification reduces to counting approvals among the voters below each satisfaction threshold. For computation, we observe that local search for Proportional Approval Voting (PAV) can stop at an outcome violating FJR. Somewhat counterintuitively, the remedy is to subtract a small multiple of the minimum voter satisfaction from the PAV score: every FJR+ violation then admits a single-round change whose improvement guarantees polynomial running time. We further show that temporal FJR+ is strictly stronger than FJR and EJR+ combined, and coincides with lower quota on party-list preferences. Finally, temporal FJR+ and multiwinner FJR+ are incomparable in general, but coincide when approvals are static and each candidate-round pair is treated as a separate candidate. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-30 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.35826 — 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-07T16:57:11.421Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).