Research map / Learning theory and algorithms / Submodular and game algorithms
Maintaining Proportional Committees with Dynamic Candidate Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies proportional multiwinner voting when candidate sets change over time (incremental, decremental, fully-dynamic), giving robust or amortized-recourse algorithms for PSC, PJR+, EJR+, and q-core/proportional fairness, and impossibility results otherwise.
Problem
Maintaining proportional committees as candidates join or leave, while keeping the committee changes (recourse) small at each time step, under ordinal, approval, and proportional clustering preferences.
Approach
Extends static proportionality axioms (PSC, PJR+, EJR+, q-core) to dynamic candidate sets and asks how few swaps per update suffice; uses counting/exchange arguments, maximally affordable subcommittees, and a pre-clustering procedure to get robust or amortized algorithms, and proves lower bounds where none exist.
Key results
- Robust incremental algorithm satisfying PSC (Theorem 3.1); no robust decremental PSC algorithm, with Omega(log log k) replacements needed after one deletion (Proposition 3.2).
- Fully-dynamic PJR+ algorithm with amortized 2 changes per step (Theorem 5.4); fully-dynamic Theta(log k)-EJR+ with amortized 2 changes (Theorem 5.5).
- Fully-dynamic algorithm that is 2+sqrt(5) (~4.24)-proportionally fair and in the 5-q-core for clustering (Theorem 4.1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a robust incremental algorithm that repairs PSC after candidate additions | Ordinal preferences · Ordinal preferences, incremental | committee changes per update | Helped |
| Require PSC after candidate deletions | Ordinal preferences · Ordinal preferences, decremental | replacements after one deletion: Ω(log(log(k))) | Hurt |
| Require rank-JR in incremental or decremental settings | Ordinal preferences · Ordinal preferences, incremental and decremental | amortized changes per round: Ω(√k) | Hurt |
| Use the fully-dynamic clustering algorithm | Proportional clustering · Proportional clustering, fully dynamic | proportional fairness approximation: 4.24-proportionally fair | Helped |
| Use the fully-dynamic clustering algorithm | Proportional clustering · Proportional clustering, fully dynamic | q-core approximation: 5-q-core | Helped |
| Maintain PJR+ with a robust incremental algorithm | Approval preferences · Approval preferences, incremental | committee changes per update | Helped |
| Maintain PJR+ in a fully-dynamic setting | Approval preferences · Approval preferences, fully dynamic | amortized changes per iteration: 2 | Helped |
| Use a fully-dynamic approximate EJR+ algorithm | Approval preferences · Approval preferences, fully dynamic | EJR+ approximation: Θ(log(k)) | Helped |
| Use an incremental α-EJR+ algorithm for α > 1 | Approval preferences · Approval preferences, incremental | EJR+ approximation: α > 1 | Helped |
| Use a locally stable algorithm for incremental EJR+ | Approval preferences · Approval preferences, incremental, single addition | EJR+ committee changes | Helped |
| Require a robust decremental algorithm to maintain PJR+ | Approval preferences · Approval preferences, decremental | committee changes per update | Hurt |
Surprising findings
- No robust decremental or fully-dynamic PJR+ algorithm exists, and rank-JR admits no incremental or decremental algorithm with o(sqrt(k)) amortized changes.
- Clustering proportionality (5-q-core) matches the best known offline bound, unlike the more negative picture suggested by prior work on the chen et al. score-based setting.
Experimental setup
Metrics: robustness (|f(t) ∩ f(t+1)| ≥ k-1) amortized number of changes per time step approximation ratio for proportional fairness q-core approximation factor
Baselines: STV expanding approvals rule MES GJCR PAV
Builds on: proportional solid coalitions (PSC) PJR+ / EJR+ (Brill and Peters 2023) greedy justified candidate rule Greedy Capture / spatial expanding approvals rule Do et al. 2022 online committee selection
Closest papers by meaning
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.90)
- Verifying Proportionality in Temporal Voting (AAAI 2025 · similarity 0.89)
- Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting (AAAI 2024 · similarity 0.89)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.88)
- Temporal Fairness in Multiwinner Voting (AAAI 2024 · similarity 0.88)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.