{"id":"fb888924-b817-4f24-af2a-2c4c5a97e0be","arxiv_id":"2502.05949","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Checking justified representation in temporal elections is coNP-hard in general, even with two or three candidates, though monotonic preferences make all six axioms checkable in polynomial time.","lead":"This paper studies how hard it is to check whether a sequence of winners chosen over time fairly represents groups of voters. It proves these checks are computationally harder in temporal voting than in one-shot elections, and identifies special cases where the checks become easy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's CONDITIONAL verdict is based on secondary proof issues, which do not touch Theorem 3.2, the central claim. I examined the maximum-edge-biclique reduction in detail: the WLOG assumption κ > |L|+|R| is achieved by vertex copying and remains polynomial because non-trivial instances have κ ≤ |L|·|R|; dummy voters cannot belong to a violation witness because they receive satisfaction ℓ in every round; and a violating group maps exactly to a biclique with at least κ edges. Thus the central coNP-completeness result stands. The demand-function issue raised by the reader is a definitional contingency rather than an internal inconsistency: the paper identifies the main alternative demand and shows it would make the axioms unsatisfiable, which justifies the choice. I therefore see no load-bearing flaw in the central claim. However, the secondary proof gaps identified by the reader (Proposition 7.4 and Theorem 5.4) still warrant correction or qualification, so the CONDITIONAL verdict should remain unchanged.","tokens_in":21946,"tokens_out":16599,"duration_ms":162270,"concrete_test":"Implement a brute-force verifier for the Appendix A.2 reduction on small random bipartite graphs (e.g., |L|, |R| ≤ 6, κ between 1 and |L|·|R|): construct the election, set o = (q, ..., q), and check that JR, PJR, and EJR are each satisfied exactly when the graph has no biclique with at least κ edges. This independently re-derives the central reduction's correctness without relying on the paper's prose.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified against the central claim (Theorem 3.2). The reduction from Maximum Edge Biclique is sound: with n = κ voters, any group witnessing a JR/PJR/EJR violation must lie in [ν] (dummy voters in N0 are satisfied in every round by o = (q, ..., q)); the rounds where such a group jointly approves p form a biclique with at least κ edges, and conversely a κ-edge biclique gives a group with positive demand and zero satisfaction. The dependence on α(N') = floor(β(N')·|N'|/n) is a modeling choice inherited from Chandak et al. (2024), and the paper explicitly shows that the natural alternative α' = min{β, ℓ·|N'|/n} makes even JR unsatisfiable, so the chosen demand is not arbitrary among the candidates considered. The secondary gaps flagged by the reader (the semi-online proof sketch in §7.3 and the terse W[1]-hardness proof in §B.2) do not affect the coNP-completeness classification of verification, which is the paper's headline contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of verifying whether a given outcome of a temporal (perpetual) approval election satisfies the temporal analogues of justified representation (JR), proportional justified representation (PJR), and extended justified representation (EJR), both in their weak and strong forms. The main results are coNP-completeness of verification for all three strong axioms even with two candidates (Theorem 3.2), coNP-completeness for the weak axioms (Theorem 3.1), FPT/XP results with respect to the number of voters and the combined parameter (m, ℓ), polynomial-time verification for monotonic preferences (Theorems 6.1 and 6.2), a two-stage greedy rule that provably returns EJR outcomes (Theorem 7.1), an ILP formulation for EJR outcomes with additional voter-specific lower bounds (Theorem 7.2, Corollary 7.3), and an impossibility claim for EJR in the semi-online setting (Proposition 7.4).","tokens_in":22130,"tokens_out":30964,"duration_ms":298499,"significance":"The central verification-hardness results are carefully argued and constitute a genuine conceptual contribution: they show that temporal verification is strictly harder than multiwinner verification, since JR verification is polynomial-time in the multiwinner model but coNP-complete here even with two candidates. The paper also contains several useful positive results, including FPT in the number of voters, polynomial algorithms for monotonic preferences, and a constructive EJR rule. The reductions are self-contained and use standard source problems, and the paper is honest about its modeling assumptions, explicitly discussing the alternative demand function and why it is unsatisfiable. However, three secondary technical contributions have proof gaps: Proposition 7.4, the W[1]-hardness proof of Theorem 5.4, and the ILP formulation in Theorem 7.2. These gaps are real but appear fixable, so the appropriate decision is a major revision rather than rejection.","major_comments":[{"comment":"The proof of Proposition 7.4 is invalid. The step \"By symmetry, we can assume without loss of generality that in the first k rounds, we select o_t = p_t for t∈[k]\" is not justified for an arbitrary semi-online rule, which need not be neutral and may break the symmetry of the constructed instance. More seriously, the fixed instance does not have the property that every w-JR outcome fails EJR: for k=4, the outcome o=(p1,p5,p6,p7,p2,p3,p4,p8) satisfies w-JR, and voter 1 in the group [4] has satisfaction 2 = α([4]), so EJR is not violated for the critical group. The impossibility claim requires an adversary argument that reveals preferences round-by-round depending on the rule's past choices; the current proof only analyzes one particular w-JR outcome and cannot be repaired by the stated symmetry argument.","section":"§7.3, Appendix D.2"},{"comment":"The reduction for the case n′/k > k is not correct. The n′′ added voters are described as approving \"every candidate\", which includes the dummy candidate in each round. Since the outcome o consists entirely of dummy candidates, these added voters have satisfaction ℓ > 0 and hence cannot be part of any group witnessing a w-JR violation, which requires every member of the group to have satisfaction 0. Thus the group consisting of the k clique voters together with the n′′ added voters is not a valid witness, and the \"clique ⇒ violation\" direction fails; the clique alone is too small to reach the demand threshold n/k. The converse direction also lacks a proof that any witness must contain at least k vertex voters. The proof should be repaired, e.g., by making the added voters approve all non-dummy candidates and proving n′′ < n/k so that the all-added-voters group is too small; as written, Theorem 5.4 is unsupported.","section":"§5.4 (Theorem 5.4), Appendix B.2"},{"comment":"The ILP in the proof of Theorem 7.2 does not enforce that a selected candidate is actually present in the round type. For each round type τ, variables x_{p,τ} exist for every p∈P′, but a candidate p_V that is not approved by anyone in rounds of type τ (i.e., no original candidate has profile V in that round) can still be assigned x_{p,τ}=κ_τ, satisfying constraint (2) without contributing to any voter's satisfaction. Such a \"phantom\" selection cannot be mapped back to an outcome of the original election, so the claimed correspondence between ILP solutions and EJR outcomes fails. A concrete example is n=2, ℓ=1, with voter 1 approving a and voter 2 approving b; the profile {1,2} is absent from the round, but the ILP allows selecting it. The fix is to restrict variables to the support of τ (or add explicit constraints x_{p,τ}=0 for absent p); with that fix the FPT claim in Corollary 7.3 would go through, but as written the theorem is not established.","section":"§7.2, Appendix D.1"}],"minor_comments":[{"comment":"The axiom is introduced as \"extended justified representation (s-EJR)\"; the acronym should be EJR to match Definitions 2.3–2.4 and the rest of the paper.","section":"Definition 2.5"},{"comment":"The two demand functions are both written as α, producing the self-referential inequality α(N′) ≥ α(N′); please use distinct symbols (e.g., α and α′) for the actual and alternative demand.","section":"Section 2, discussion preceding Example 2.6"},{"comment":"The statement contains a typo: \"togther\" should read \"together\".","section":"Theorem 6.1"},{"comment":"The phrase \"with respect to there parameters\" should read \"with respect to these parameters\".","section":"Section 5, first paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper's headline result, Theorem 3.2, is sound and the central verification-hardness classification makes a solid contribution. My recommendation is driven by three fixable-but-real gaps in secondary claims: Proposition 7.4, Theorem 5.4, and Theorem 7.2. I would not reject; the authors should be asked to repair or, if necessary, remove the affected results. The semi-online impossibility and the ILP formulation are interesting enough that a proper repair is worthwhile, but the current versions should not appear in print."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline result is real: verifying JR/PJR/EJR in temporal elections is coNP-complete even with two candidates, which makes temporal verification strictly harder than multiwinner JR verification. The Maximum Edge Biclique reduction in Theorem 3.2 is clean. I checked the key step: any group witnessing a violation must be a subset of the first ν voters, and the rounds where they jointly approve p form a biclique with at least κ edges; conversely, any κ-edge biclique gives a violating group. The extension to PJR and EJR goes through for the right reason, since all voters outside [ν] have full satisfaction.\n\nThe rest of the paper is also genuinely useful. The FPT and XP results are sensible, and the monotone-preferences algorithm in Section 6 is a nice positive counterpoint. The GCR adaptation giving EJR answers an open question from Chandak et al. and looks correct.\n\nTwo soft spots, both in the appendix. Proposition 7.4 says \"By symmetry, we can assume without loss of generality that in the first k rounds we select o_t = p_t\" for a semi-online rule. That is not a valid wlog: the instance is not symmetric under arbitrary relabelings because future rounds treat p_1..p_k differently from p_n, and a rule need not be label-invariant. The proposition may be true, but the proof needs a proper adversary argument.\n\nThe other gap is Theorem 5.4 (W[1]-hardness w.r.t. ℓ). The reduction from Multicolored Clique is sketched in under a page, and the converse direction does not obviously work once the \"approve everything\" voters are added. A group made of one vertex voter plus several universal voters can reach the quota and agree in all rounds via a star, without containing a clique. That looks like a genuine gap, not just terseness.\n\nNeither gap touches the coNP-completeness classification, which is the paper's main contribution. The demand function α is a modeling choice inherited from Chandak et al., and the paper at least shows the natural alternative is unsatisfiable, so I do not hold that against it.\n\nBottom line: this is a solid within-subfield paper with one important correct theorem and several useful secondary results. It should be refereed seriously, but the two appendix proofs should be fixed or explicitly downgraded to conjectures before publication.","headline":"The core coNP-hardness result for temporal JR/PJR/EJR verification is solid and the paper deserves serious refereeing, but two appendix proofs (Prop 7.4 and Thm 5.4) need real fixes before acceptance.","tokens_in":22713,"tokens_out":7473,"would_cite":true,"duration_ms":78767,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","91B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"In temporal approval elections, checking whether an outcome gives voter groups their proportional share is coNP-complete for JR, PJR, and EJR even with only two candidates, making temporal verification strictly harder than multiwinner…","keywords":["temporal voting","perpetual voting","justified representation","coNP-completeness","parameterized complexity","approval voting","proportional representation","monotonic preferences"],"falsifier":"A concrete test is to run the Theorem 3.2 reduction on a Maximum Edge Biclique instance with κ > |L|+|R|: the all-q outcome is claimed to violate JR exactly when the graph has a κ-edge biclique, so any algorithm that verifies JR on this two-candidate family in polynomial time would refute the theorem, as would a polynomial-time reduction from temporal JR verification to multiwinner JR verification, which would collapse the claimed separation.","tokens_in":2009,"feed_emoji":"🗳️","tokens_out":4080,"duration_ms":97430,"temperature":0.7,"pith_summary":"This paper studies temporal (perpetual) voting, where in each of a fixed number of rounds voters approve candidates and one candidate is selected, and asks how hard it is to verify that a proposed sequence of winners fairly represents groups of voters. The authors prove that verifying any of the standard proportionality axioms—JR, PJR, and EJR, as well as their weak variants—is coNP-complete, and for the strong versions this remains true even when there are only two candidates. Because verifying JR is easy in ordinary multiwinner elections, the temporal setting is strictly harder, not merely a translation of known results. The paper then maps where the hardness breaks: verification is fixed-parameter tractable in the number of voters, tractable when preferences are monotone over time, and W[1]-hard in the number of rounds for the weak axioms. A corollary is a fixed-parameter algorithm for finding EJR outcomes under extra welfare constraints and an impossibility result ruling out EJR in semi-online settings.","feed_headline":"Fairness checks in temporal voting stay hard with only two candidates","feed_subtitle":"A group's proportional claim is hard to certify here, unlike one-shot elections where basic fairness checks are easy.","key_machinery":"The load-bearing object is the demand function α(N') = ⌊β(N')·|N'|/n⌋, where β(N') counts the rounds in which all members of group N' approve a common candidate; it converts group agreement into a number of rounds the group can claim, and each axiom is a check that some or all group members' satisfaction reaches or covers α(N'). The hardness proofs work by constructing elections in which a witnessing group exists exactly when a combinatorial object (clique, independent set, biclique) exists, so that verifying fairness becomes solving an NP-hard search problem. The tractability proofs exploit structural simplifications: for monotone preferences the only groups that matter are the sets N_{p,t}^z of voters sorted by satisfaction, and for two-candidate weak JR it suffices to inspect the set of 'grumpy' voters who approve only the unchosen candidate in every round.","core_discovery":"On the paper's own terms, the central discovery is that proportionality verification in temporal voting is fundamentally harder than in static multiwinner elections. For each of the six axioms (JR, PJR, EJR and their weak forms), telling whether a given outcome satisfies the axiom is coNP-complete; for JR/PJR/EJR hardness persists at |P|=2, and the proof goes through a reduction from Maximum Edge Biclique that encodes a cohesive voter group as a biclique whose edge count exceeds the demand threshold. The only polynomial cases are small candidate sets under special conditions—two candidates with non-empty approvals for JR, and monotonic preferences—while the general hardness extends to W[1]-hardness in the number of rounds for weak axioms. The same machinery yields an FPT algorithm parameterized by the number of voters for finding EJR outcomes with side constraints, a two-stage greedy cohesive rule that always returns an EJR outcome, and a proof that no semi-online rule can guarantee EJR.","pith_inferences":["Because the demand formula α(N') is inherited from earlier work and the alternative min{β(N'), ℓ|N'|/n} makes even JR unsatisfiable, the entire complexity classification is hostage to this modeling choice; a different formalization of temporal proportionality could push the hard/easy boundary in unexpected ways.","The reductions' insensitivity to candidate count but sensitivity to whether approval sets may be empty suggests that the practically important frontier is domain restrictions rather than |P|; the authors explicitly conjecture that hardness persists for |P|=3 with non-empty approvals.","The two-stage greedy cohesive rule suggests a design principle for temporal fairness: partition voters into disjoint cohesive groups and allocate rounds group by group, a decomposition that could seed approximation or fixed-parameter algorithms for welfare-constrained fair outcomes.","The semi-online impossibility implies that practical sequential decision systems—participatory budgeting, repeated recommendations, annual charity selection—should view full EJR as an offline-only guarantee and plan for weaker axioms when decisions cannot be deferred."],"forward_implications":["Temporal proportionality verification cannot reuse multiwinner algorithms: even JR, which is polynomial-time solvable in static elections, becomes coNP-complete here.","With two candidates, strong JR/PJR/EJR verification stays coNP-complete, so the hardness is not an artifact of many candidates; only weak JR with two candidates is polynomial-time solvable.","Monotone elections, where candidates appear over time but never leave and voter preferences are fixed, admit polynomial-time verification of all six axioms.","Finding an EJR outcome that also guarantees each voter a prescribed satisfaction level and maximizes utilitarian welfare is fixed-parameter tractable in the number of voters via an integer linear program.","No rule can satisfy EJR in the semi-online setting, where preferences arrive round by round and each winner must be chosen immediately."],"supporting_citations":[{"why":"Supplies the temporal demand definition and the weak/strong JR-PJR-EJR variants that this paper verifies, and poses the open question about adapting the Greedy Cohesive Rule.","marker":"Chandak et al. (2024)"},{"why":"Introduced temporal JR and PJR and gave the algorithmic template for constructing fair outcomes that the two-stage greedy rule adapts.","marker":"Bulteau et al. (2021)"},{"why":"Defines the multiwinner JR/PJR/EJR axioms and the baseline that JR verification is easy while PJR/EJR verification is coNP-hard, against which the paper's separation claim is measured.","marker":"Aziz et al. (2017)"},{"why":"Establishes NP-hardness of Maximum Edge Biclique, the source problem for the two-candidate coNP-hardness reduction in Theorem 3.2.","marker":"Peeters (2003)"},{"why":"Provides NP-hardness of independent set with maximum degree three, used in the |P|=2 w-EJR reduction.","marker":"Garey, Johnson, and Stockmeyer (1976)"},{"why":"Supplies the W[1]-hardness of multicolored clique that underlies the W[1]-hardness of weak-axiom verification in the number of rounds.","marker":"Cygan et al. (2015)"},{"why":"Gives the fixed-parameter algorithm for integer linear programming with a fixed number of variables, which turns the EJR-finding ILP into an FPT algorithm in n.","marker":"Lenstra Jr. (1983)"},{"why":"Defines the Greedy Cohesive Rule and the FJR axiom in multiwinner voting, the rule whose temporal adaptation is Algorithm 1.","marker":"Peters, Pierczyński, and Skowron (2021)"}],"fun_headline_variants":["Temporal voting makes proportional fairness checks coNP-hard","Hardness result: verifying temporal voting fairness is coNP-complete","Even two candidates can't ease temporal voting fairness verification","Proportionality verification in temporal voting is provably hard","Temporal voting: certifying proportional fairness is coNP-hard"],"cache_read_input_tokens":24832,"weakest_assumption_plain":"Everything in the paper depends on defining a group's demand as the floor of (rounds of full agreement times group size divided by total voters); if proportional representation were formalized with the alternative demand min{β(N'), ℓ·|N'|/n}, even JR becomes unsatisfiable and the whole complexity question evaporates.","fun_headline_variants_meta":{"raw":{"variants":["Temporal voting makes proportional fairness checks coNP-hard","Hardness result: verifying temporal voting fairness is coNP-complete","Even two candidates can't ease temporal voting fairness verification","Proportionality verification in temporal voting is provably hard","Temporal voting: certifying proportional fairness is coNP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000596,"raw_usage":{"total_tokens":2727,"prompt_tokens":820,"completion_tokens":1907,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":1825}},"tokens_in":436,"tokens_out":1907,"duration_ms":15750,"temperature":1.0,"reasoning_tokens":1825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:20:30.404133+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete test is to run the Theorem 3.2 reduction on a Maximum Edge Biclique instance with κ > |L|+|R|: the all-q outcome is claimed to violate JR exactly when the graph has a κ-edge biclique, so any algorithm that verifies JR on this two-candidate family in polynomial time would refute the theorem, as would a polynomial-time reduction from temporal JR verification to multiwinner JR verification, which would collapse the claimed separation.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the temporal demand definition and the weak/strong JR-PJR-EJR variants that this paper verifies, and poses the open question about adapting the Greedy Cohesive Rule."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced temporal JR and PJR and gave the algorithmic template for constructing fair outcomes that the two-stage greedy rule adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the multiwinner JR/PJR/EJR axioms and the baseline that JR verification is easy while PJR/EJR verification is coNP-hard, against which the paper's separation claim is measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of Maximum Edge Biclique, the source problem for the two-candidate coNP-hardness reduction in Theorem 3.2."},{"cited_title":"R.; Johnson, D","cited_arxiv_id":null,"evidence_quote":"Provides NP-hardness of independent set with maximum degree three, used in the |P|=2 w-EJR reduction."},{"cited_title":"V.; Kowalik, .; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; and Saurabh, S","cited_arxiv_id":null,"evidence_quote":"Supplies the W[1]-hardness of multicolored clique that underlies the W[1]-hardness of weak-axiom verification in the number of rounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the fixed-parameter algorithm for integer linear programming with a fixed number of variables, which turns the EJR-finding ILP into an FPT algorithm in n."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Greedy Cohesive Rule and the FJR axiom in multiwinner voting, the rule whose temporal adaptation is Algorithm 1."}],"review_version":1}