Research map / Learning theory and algorithms / Submodular and game algorithms
Verifying Proportionality in Temporal Voting
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 the complexity of verifying proportional representation axioms (JR, PJR, EJR and weak variants) in temporal voting, proving coNP-hardness, identifying tractable special cases, and showing GCR and an ILP can find EJR outcomes.
Problem
Verifying whether a given outcome of a temporal approval voting election satisfies justified representation axioms (JR, PJR, EJR and weak variants).
Approach
Shows temporal verification of JR/PJR/EJR is coNP-hard even with very few candidates, identifies polynomial cases (monotonic preferences, |P|=2 for JR under non-empty approvals), gives FPT/XP results, a two-stage greedy cohesive rule that always outputs EJR, and an ILP for EJR outcomes with extra constraints.
Key results
- Verifying w-JR, w-PJR, w-EJR and JR, PJR, EJR in temporal elections is coNP-complete, with hardness holding for JR/PJR/EJR even with |P|=2.
- Verification of JR is polynomial when |P|=2 and every voter approves at least one candidate per round, and verification of (weak) axioms is polynomial for monotonic elections.
- A 2-stage Greedy Cohesive Rule variant always outputs an EJR outcome in time O(2^n poly(n,m,l)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict preferences to be monotonic | Temporal election verification · Monotonic elections | verification complexity | Helped |
| Parameterize verification by the number of voters n | Temporal election verification · General temporal elections | parameterized complexity | Helped |
| Parameterize verification by the combined parameter (m, ℓ) | Temporal election verification · General temporal elections | parameterized complexity | Helped |
| Parameterize verification by the number of rounds ℓ | Weak JR, weak PJR, and weak EJR verification · General temporal elections | parameterized complexity | Hurt |
| Restrict the candidate set to |P| = 2 | JR, PJR, and EJR verification · General temporal elections | verification complexity | Hurt |
| Restrict the candidate set to |P| = 2 | Weak JR verification · General temporal elections | verification complexity | Helped |
| Restrict the candidate set to |P| = 2 and require all approval sets to be non-empty | JR verification · Temporal elections with non-empty approval sets | verification complexity | Helped |
| Require all approval sets to be non-empty | JR, PJR, and EJR verification · General temporal elections | verification complexity | Hurt |
| Use the 2-Stage Greedy Cohesive Rule | Temporal elections · EJR outcome construction | EJR guarantee | Helped |
| Move from the offline setting to the semi-online setting | Temporal EJR outcome selection · Semi-online temporal voting | existence of an EJR-satisfying rule | Hurt |
Surprising findings
- Temporal verification of JR is strictly harder than in multiwinner voting, since the multiwinner JR verification is polynomial-time solvable.
- No rule can satisfy EJR in the semi-online setting, resolving an open question of Chandak et al.
Limitations
- Verification remains coNP-hard for general temporal elections, including with |P|=2 for PJR/EJR and w-JR/w-PJR with empty approvals.
- The GCR-based algorithm runs in exponential time in n.
- The FPT/ILP results are parameterized by the number of voters and are not polynomial in general.
Experimental setup
Baselines: PAV ls-PAV Method of Equal Shares
Builds on: Justified representation (JR) Extended justified representation (EJR) Greedy Cohesive Rule Perpetual voting (Bulteau et al.)
Closest papers by meaning
- Strategyproofness and Proportionality in Party-Approval Multiwinner Elections (AAAI 2023 · similarity 0.90)
- Temporal Fairness in Multiwinner Voting (AAAI 2024 · similarity 0.89)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.89)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.88)
- Proportional Representation in Practice: Quantifying Proportionality in Ordinal Elections (AAAI 2025 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.86)
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.