Learning Proportional Committees from Violation Feedback
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a learning process where a system proposes groups of size k based on voters' approvals and gets feedback on whether the group fairly represents voters or not. They compare two types of feedback: detailed information about the violation versus just knowing which candidate caused it. They focus on two fairness criteria called PJR+ and EJR+. They find that the number of mistakes (rejections) depends only on the size k, not the number of voters or candidates. For PJR+, the best mistake count is around k, but for EJR+, the bounds are higher and differ depending on feedback type and whether randomness is used.
approval-based committeesproportional justified representation plus (PJR+)extended justified representation plus (EJR+)violation-feedback learningfull-witness feedbackcandidate-only feedbackdeterministic algorithmrandomized algorithmrejection complexity
Authors
Frank Connor
Abstract
We study violation-feedback learning of proportionally representative approval-based committees. In each round, a learner proposes a committee of size $k$. An oracle either accepts the proposal or adversarially selects a representation violation with respect to a single fixed hidden approval profile. We compare \emph{full-witness feedback}, which reveals the violation level, an omitted candidate, and the affected voter group, with \emph{candidate-only feedback}, which reveals only that candidate. The target notions are proportional justified representation plus (PJR+) and extended justified representation plus (EJR+). In every setting we study, the number of rejected proposals can be bounded solely in terms of $k$, with no dependence on the numbers of voters and candidates. For PJR+, the optimal deterministic and randomized rejection complexities equal $k$ under both feedback models. For EJR+, the picture is more nuanced. Under full-witness feedback, we prove an $Ω(k^{3/2})$ deterministic lower bound and give a deterministic polynomial-time algorithm using $O(k^2\log k)$ rejections. Under candidate-only feedback, randomization achieves $O(k^2\log k)$ expected rejections via uniform random deletion, while deterministic exhaustive branching gives a $2^{O(k^2(\log k)^2)}$ rejection bound. Even with full-witness feedback, randomized learners may require $k$ rejections.