arXiv:2503. 01985v2 Announce Type: replace-cross Abstract: In the classic committee election setting each voter approves a subset of candidates and the goal is to select $k$ winners based on these preferences.
By Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczy\'nski, Piotr Skowron
The paper investigates proportional representation in a temporal voting setting where a single candidate is chosen each round and voters submit ranked preferences that may evolve over time. It extends classic proportionality axioms—justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC)—to accommodate various ways of determining which top-ranked candidates are considered approved, ranging from a fixed common cutoff to individual, round‑specific cutoffs. The authors analyze which axioms can be guaranteed under different informational assumptions about future rounds, showing that while EJR is unattainable, JR, PJR, and PSC can be achieved with a fixed cutoff if all preferences are known in advance; varying cutoffs reduce guarantees, yet PJR can still be achieved efficiently for groups that agree in every round, and PSC can be satisfied without future knowledge. They also demonstrate that checking these axioms is often coNP‑complete, though some stronger axioms may be easier to verify.
By Noam Hazon, Leora Schmerler, Nicholas Teh
arXiv:2608. 11500v1 Announce Type: cross Abstract: Full justified representation (FJR) is among the strongest known satisfiable proportionality axioms for approval-based committee elections.
By Nicholas Teh
The paper proposes a transparent, user‑configurable rule for selecting arguments in deliberative polls, replacing opaque learned rankers. It formalises argument selection over bipolar justification sets, introduces seven civic recommender criteria, and presents a one‑hop reversed endorsement flow rule that meets them. Experiments on 17,000 simulated runs show the rule performs comparably to random on coverage but outperforms other methods on endorsement mass and robustness under adversarial pressure.
By Muntaser Syed, Markus Zanker, Marius Silaghi
The paper studies how to safely delegate action approval to multiple AI reviewers when the reviewers themselves may be misaligned. It introduces a weaker condition—k‑robust coalitional alignment—under which a threshold rule that tolerates up to k disapprovals guarantees that the principal’s expected utility is at least as good as a baseline policy. The authors extend this characterization to sequential decision‑making in discounted MDPs and show that full‑panel coverage of reward functions ensures safety in Nash equilibria, while more permissive thresholds can lead to unsafe outcomes. Experiments demonstrate that collective review can remain sound even when individual reviewers are not fully aligned, provided some disapprovals are allowed.
By Natalie Collina, Surbhi Goel, Aaron Roth, Sikata Bela Sengupta
The paper introduces a derandomization framework for stochastic majority vote classifiers, converting PAC‑Bayesian guarantees into deterministic majority vote guarantees. By applying disintegrated PAC‑Bayesian theory to the space of vote weight vectors, the authors derive two families of high‑probability generalization bounds for both data‑independent and data‑dependent ensembles. These bounds naturally lead to a self‑bounding learning algorithm that optimizes deterministic majority vote performance.
By Julien Bastian (LabHC), Benjamin Leblanc (LabHC, UJM, MALICE), Pascal Germain (LabHC, UJM, MALICE), Amaury Habrard (LabHC, UJM, MALICE), Guillaume Metzler (ERIC), Emilie Morvant (LabHC), Paul Viallard (MALT)