{"id":"ccb1682d-0064-40e6-a16b-0f3c2c908f85","arxiv_id":"2505.22513","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Temporal voting gets new, stronger proportionality axioms; EJR+ and FJR are always satisfiable, and the full hierarchy of implications and non-implications is mapped.","lead":"This paper designs stronger fairness standards for voting that happens over multiple rounds, where one winner is picked each round. It shows two of its new standards, EJR+ and FJR, can always be met, while several natural even stronger standards cannot be satisfied at all.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.9's EJR+ proof cites the EJR guarantee for ε-lsPAV with ε > 1/ℓ^2, while the proof needs ε < 1/ℓ^2; if the cited theorem does not cover this range, the σ=|S| case is unsupported.","rationale":"The reader's weakest assumption correctly identifies the reliance of Theorem 3.9 on the prior EJR guarantee for ε-lsPAV in the σ=|S| case. My stress-test sharpens this: the manuscript's citation states 'ε > 1/ℓ^2', which is inconsistent with the theorem's own 'ε < 1/ℓ^2' assumption and with the chosen ε = 1/(2ℓ^2). This is the most load-bearing concern because the central claim that EJR+ is satisfiable in every temporal election rests entirely on Theorem 3.9. If the cited theorem is misquoted and actually holds for ε < 1/ℓ^2, the proof is valid modulo a trivial typo; if not, the satisfiability proof has a genuine gap. I checked the surrounding argument: the harmonic-score calculations, the handling of the σ < |S| case, the 'assume r ∈ R' step (fixable by replacing a round in R with r), and the GCR proof of Theorem 4.5 all appear sound. The FJR half of the central claim is not the weak point. Therefore I recommend a conditional acceptance: the paper is acceptable once the cited theorem's exact epsilon condition is verified and the inequality in the citation is corrected if necessary. This does not reflect doubt about the authors' integrity, only a concrete technical checkpoint that should be settled before the claim is relied upon.","tokens_in":37454,"tokens_out":20574,"duration_ms":219048,"concrete_test":"Check the statement of Chandak et al. (2024), Theorem 4.5, and record the exact ε condition under which ε-lsPAV is claimed to satisfy temporal EJR. If the condition is ε < 1/ℓ^2 (or ε in [1/(2ℓ^2), 1/ℓ^2)), then the present manuscript has only a sign typo in the citation, and Theorem 3.9 is sound after correction. If the condition is ε > 1/ℓ^2, then the σ=|S| case is not covered by the cited result; attempt to prove that case directly using the EJR+ machinery, or revise the claim that ε-lsPAV with ε = 1/(2ℓ^2) always outputs EJR+ outcomes.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 3.9, the σ=|S| case is dispatched by citing Chandak et al. [2024, Theorem 4.5] as showing that ε-lsPAV provides EJR for ε > 1/ℓ^2. But the theorem being proved, and the final contradiction, both require ε < 1/ℓ^2. The manuscript even sets ε = 1/(2ℓ^2) for the polynomial-time construction, which lies in the interval [1/(2ℓ^2), 1/ℓ^2), not in (1/ℓ^2, ∞). As written, the citation's inequality direction is incompatible with the proof's assumption. If the cited theorem actually holds for ε < 1/ℓ^2, this is a typographical error and the proof goes through. If it only holds for ε > 1/ℓ^2, then no ε simultaneously gives polynomial time, EJR+ (which needs ε < 1/ℓ^2), and the invoked EJR guarantee, so the satisfiability proof for EJR+ in the σ=|S| case is incomplete. This directly threatens the abstract's claim that EJR+ strengthens EJR while remaining satisfiable in every temporal election. The other flagged issue, the unproved 'we can assume r ∈ R', is fixable by replacing one witnessing round in R with r, and does not undermine the argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies temporal approval voting, where an outcome is a sequence of one candidate per round, and introduces temporal adaptations of EJR+, FJR, FPJR, and the core, together with weak and strong variants. The main results are: (i) EJR+ always has an outcome, can be checked in polynomial time, and is produced by ε-lsPAV for ε < 1/ℓ² (Proposition 3.7 and Theorem 3.9); (ii) FJR always has an outcome, produced by the Greedy Cohesive Rule, albeit not in polynomial time (Theorem 4.5); (iii) sFPJR is satisfiable in polynomial time by Serial Dictatorship when the number of rounds is a multiple of the number of voters and every ballot is non-empty (Theorem 5.3), while sEJR and sEJR+ are unsatisfiable in general (Proposition 3.4 and Appendix D); and (iv) a comprehensive hierarchy of implications and separations among the axioms is established (Propositions 3.3, 3.6, 4.4, 5.2, 6.2, 7.1). The central claim is that EJR+ and FJR strengthen EJR while remaining satisfiable in every temporal election.","tokens_in":37702,"tokens_out":18636,"duration_ms":177793,"significance":"The paper is a solid contribution to the computational social choice literature on temporal voting. Its main value is mapping the frontier of satisfiable proportionality axioms: it shows that EJR+ and FJR, two strengthenings of EJR from multiwinner voting, can be adapted to the temporal setting while retaining satisfiability, and it gives a rich implication hierarchy with explicit counterexamples. The proofs are detailed and mostly self-contained in the appendix, and the polynomial-time verification algorithm for EJR+ (Proposition 3.7) is a concrete strength. The paper does not fit any result to data and has no free parameters; the design choice of (σ,τ)-cohesiveness is explicitly motivated. If the technical issue in Theorem 3.9 noted below is resolved, the paper will be a valuable reference for future work on temporal proportionality.","major_comments":[{"comment":"In the σ = |S| case of the proof of Theorem 3.9, the paper cites Chandak et al. [2024, Theorem 4.5] as showing that ε-lsPAV provides EJR for ε > 1/ℓ². However, the theorem being proved assumes ε < 1/ℓ², and the polynomial-time instantiation described just before the theorem uses ε = 1/(2ℓ²), which lies in [1/(2ℓ²), 1/ℓ²), not in (1/ℓ², ∞). The cited range and the proof's assumption are disjoint, so the σ = |S| case is unsupported as written. The authors should correct the inequality to the actual range covered by Chandak et al. (for example, ε < 1/ℓ² or ε ∈ [1/(2ℓ²), 1/ℓ²)), or supply a direct proof for this case. If the cited theorem really covers only ε > 1/ℓ², then the satisfiability claim for EJR+ in every temporal election is not established by the current proof, which directly affects the abstract's central assertion.","section":"Section 3, Theorem 3.9"}],"minor_comments":[{"comment":"The sentence 'We can assume r ∈ R, with c_r = c' is not justified on the spot. It is correct: since c is approved by every voter in S in round r, replacing any round of the witnessing set R by r preserves the property that at least σ voters in S approve the chosen candidate in each round. Please add this one-line justification.","section":"Section 3, Theorem 3.9"},{"comment":"Several election tables appear corrupted or misaligned in the text, for example the table in Proposition 3.4 and the tables in Proposition F.1 Claims iii and x. The row and column labels do not match the stated numbers of voters and rounds. Please re-typeset these tables so the election data are unambiguous.","section":"Proposition 3.4 and Appendix F"},{"comment":"The proof states 'Since each voter selects the outcome of exactly ℓ/n rounds, we have sat_S(o) ≥ ℓ·|S|/n.' This lower bound additionally relies on the fact that the sets of rounds assigned to different voters are disjoint, which holds for SDR because each round is assigned to exactly one voter. Making this disjointness explicit would improve clarity.","section":"Theorem 5.3"},{"comment":"In the verification algorithm, the condition 'if all voters in S_{r,c,λ} approve o_r in round r, we disregard this set' is correct but could be phrased more explicitly: in that case o_r ∈ ∩_{i∈S_{r,c,λ}} a_{i,r}, so this set cannot witness a violation of EJR+.","section":"Proposition 3.7"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the mismatched inequality direction in the citation used in Theorem 3.9. If the authors confirm that the cited Chandak et al. theorem covers the interval [1/(2ℓ²), 1/ℓ²) or ε < 1/ℓ², the issue is a typographical error and the paper would be acceptable after that correction. I would not reject on this basis. The paper is within scope for a theory journal in social choice and algorithmic game theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper: it is the best current map of proportionality axioms for temporal voting, and its central EJR+ satisfiability proof contains a citation-direction glitch that is very likely a typo but needs to be checked before relying on it.\n\nWhat is new: the authors adapt EJR+, FJR, FPJR, and core stability to the temporal setting. The naive strong variants are unsatisfiable, so they introduce (σ,τ)-cohesiveness as a local measure to define a satisfiable EJR+. They prove EJR+ is satisfiable by ε-lsPAV with ε = 1/(2ℓ²), that GCR gives FJR, and that SDR gives sFPJR when n divides ℓ. They also establish a complete implication hierarchy with a dozen separations. That is real work, and it fills a genuine gap: previous temporal voting papers only had JR/PJR/EJR.\n\nThe proofs look careful. I did not find a false theorem. The one issue that stands out is in Theorem 3.9, the σ=|S| case. The proof says Chandak et al. [2024, Theorem 4.5] gives ε-lsPAV with ε > 1/ℓ² provides EJR. But the theorem statement and the polynomial-time parameter require ε < 1/ℓ². If that citation is actually for ε < 1/ℓ², it's a one-character fix. If not, the σ=|S| case is unproven for the regime the paper uses. I suspect a typo, because the rest of the proof uses exactly the kind of local improvement argument that works for small ε. Still, the authors need to resolve it — a referee should ask for the precise ε range from Chandak et al. or a direct proof.\n\nThe other flagged detail, 'we can assume r∈R', is minor and fixable. The paper is honest about the parts that remain open (poly-time FJR, core satisfiability), which I appreciate.\n\nWho is this for: anyone working on sequential or temporal decision-making, multiwinner approval voting, or the axiomatics of proportionality. It is a theory paper; no data, no parameters. If you work in computational social choice, it deserves a careful read.\n\nMy recommendation: yes, send it to peer review. The potential gap is isolated and likely typographical, and the rest is solid. If the ε question is resolved in revision, this becomes a strong paper.","headline":"A solid and genuinely new map of temporal proportionality axioms, with an isolated and likely fixable citation-direction glitch in the EJR+ satisfiability proof.","tokens_in":38294,"tokens_out":4290,"would_cite":true,"duration_ms":41300,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"Temporal elections always admit outcomes satisfying the strong proportionality axioms EJR+ and FJR.","keywords":["temporal voting","proportional representation","justified representation","extended justified representation+","full justified representation","approval ballots","greedy cohesive rule","epsilon-lsPAV"],"falsifier":"Run $\\varepsilon$-lsPAV with $\\varepsilon = 1/(3\\ell^2)$ on an arbitrary temporal election and check whether the output satisfies EJR+ by the paper's polynomial-time verifier; a single output violating EJR+ would contradict Theorem 3.9. Alternatively, an explicit temporal election for which the Greedy Cohesive Rule of Algorithm 1 returns an outcome violating FJR would falsify Theorem 4.5.","tokens_in":37183,"feed_emoji":"🗳️","tokens_out":6175,"duration_ms":55267,"temperature":0.7,"pith_summary":"This paper extends justified-representation axioms for multiwinner approval voting to settings where one candidate is selected in each of several rounds, and asks which proportionality guarantees can always be met. It introduces temporal versions of EJR+, FJR, full proportional JR, and core stability, and shows that two of them — temporal EJR+ and temporal FJR — are satisfiable in every temporal election. The paper also proves that an EJR+ outcome can be computed in polynomial time, whereas FJR outcomes exist but are not known to be polynomial-time computable. It maps which axioms imply which, including explicit non-implications, giving a hierarchy of proportionality concepts in the temporal setting.","feed_headline":"Strong fairness axioms EJR+ and FJR hold in every temporal election","feed_subtitle":"EJR+ outcomes are polynomial-time computable; FJR outcomes exist for every profile.","key_machinery":"The paper's central objects are $(\\sigma, \\tau)$-cohesive groups of voters: a set $S$ is $(\\sigma, \\tau)$-cohesive if in a chosen set of $\\tau$ rounds, at least $\\sigma$ voters in $S$ approve the same candidate in each round. This local cohesion measure replaces the group size $|S|$ in the demand calculation, and it is what makes temporal EJR+ satisfiable. The two rules doing the heavy lifting are $\\varepsilon$-lsPAV, a local-search variant of proportional approval voting that maximizes the harmonic score, and a modified Greedy Cohesive Rule that partitions voters by their maximum achievable demand $\\mu_S(T)$ and allocates rounds to each part. For sFPJR, the Serial Dictatorship Rule works when the number of rounds is a multiple of the number of voters.","core_discovery":"The central claim is that the temporal setting, in which exactly one candidate is selected per round, still admits the strong proportionality axioms EJR+ and FJR. For EJR+, the paper shows that the temporal $\\varepsilon$-lsPAV rule, with $\\varepsilon < 1/\\ell^2$, always returns an EJR+ outcome (Theorem 3.9), and that EJR+ implies temporal EJR and is polynomial-time verifiable. For FJR, a variant of the Greedy Cohesive Rule outputs an FJR outcome in every temporal election (Theorem 4.5). In contrast, the ‘strong’ versions of these axioms (sEJR+, sFJR) are generally unsatisfiable, and the paper exhibits elections with no sJR outcome, so a useful strengthening requires a careful definition that scales guarantees with the number of voters who agree in a round rather than the whole group size.","pith_inferences":["A testable extension: if one restricts to single-peaked or single-crossing profiles, the strong axioms may become satisfiable in cases where the paper shows they fail in general.","The $(\\sigma, \\tau)$-cohesion idea could be ported to participatory budgeting, where rounds become projects or budget categories, to define stronger proportionality guarantees.","The paper's separation results suggest that any rule satisfying EJR+ and FJR simultaneously would have to combine local-search and greedy-cohesive features; the paper does not propose such a unified rule.","Since EJR+ is polynomial-time verifiable, one could empirically test the gap between EJR+ and FJR by computing both rules on real preference data."],"forward_implications":["Every temporal election has an outcome satisfying temporal EJR+, and such an outcome can be found in polynomial time.","Every temporal election has an outcome satisfying temporal FJR, though the paper leaves open whether it can be computed in polynomial time.","Strong versions of the axioms (sEJR+, sFJR, sJR) are not generally satisfiable, even when every voter approves exactly one candidate per round.","When the number of rounds is divisible by the number of voters and every voter approves at least one candidate per round, Serial Dictatorship provides sFPJR.","The paper establishes a complete implication map: among the axioms in its hierarchy, one implies another exactly when a path exists in the figure."],"supporting_citations":[{"why":"Introduces temporal JR and PJR, establishing the model and the baseline axioms the paper strengthens.","marker":"Bulteau et al. [2021]"},{"why":"Adapts $\\varepsilon$-lsPAV to temporal elections and proves it satisfies temporal EJR; Theorem 3.9 invokes this result for the $\\sigma=|S|$ case.","marker":"Chandak et al. [2024]"},{"why":"Introduces JR/EJR and core stability in multiwinner voting; the paper adapts these concepts to the temporal setting.","marker":"Aziz et al. [2017]"},{"why":"Defines EJR+ in multiwinner approval voting, the axiom whose temporal adaptation is the paper's focus.","marker":"Brill and Peters [2023]"},{"why":"Defines FJR and proves every multiwinner election admits an FJR outcome, the axiom adapted in Section 4.","marker":"Peters et al. [2021]"},{"why":"Studies verification complexity for temporal axioms and gives a GCR variant satisfying temporal EJR, which the paper modifies to prove FJR.","marker":"Elkind et al. [2025c]"},{"why":"Proposes FPJR in multiwinner voting, the collective-guarantee axiom adapted in Section 5.","marker":"Kalayci et al. [2025]"},{"why":"Provides a general approval-voting framework and an FJR-style axiom (BFJR); the paper's FJR existence is also a special case of their Theorem 11.","marker":"Masařík et al. [2024]"}],"fun_headline_variants":["Strong proportionality axioms EJR+ and FJR always satisfiable in temporal voting","Temporal voting: stronger fairness axioms EJR+ and FJR hold in every election","EJR+ and FJR: always satisfiable proportionality for temporal elections","Going beyond EJR in temporal voting: EJR+ and FJR always exist"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that EJR+ is always satisfiable relies on a previously published guarantee that $\\varepsilon$-lsPAV with $\\varepsilon$ in $[1/(2\\ell^2), 1/\\ell^2)$ provides temporal EJR; if that guarantee or the stated $\\varepsilon$ bounds fail, the EJR+ satisfiability proof would not go through.","fun_headline_variants_meta":{"raw":{"variants":["Strong proportionality axioms EJR+ and FJR always satisfiable in temporal voting","Temporal voting: stronger fairness axioms EJR+ and FJR hold in every election","EJR+ and FJR: always satisfiable proportionality for temporal elections","Going beyond EJR in temporal voting: EJR+ and FJR always exist"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000222,"raw_usage":{"total_tokens":1411,"prompt_tokens":858,"completion_tokens":553,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":468}},"tokens_in":474,"tokens_out":553,"duration_ms":5256,"temperature":1.0,"reasoning_tokens":468,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:07:13.668363+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run $\\varepsilon$-lsPAV with $\\varepsilon = 1/(3\\ell^2)$ on an arbitrary temporal election and check whether the output satisfies EJR+ by the paper's polynomial-time verifier; a single output violating EJR+ would contradict Theorem 3.9. Alternatively, an explicit temporal election for which the Greedy Cohesive Rule of Algorithm 1 returns an outcome violating FJR would falsify Theorem 4.5.","supporting_citations":[{"cited_title":"Justified representation for perpetual voting","cited_arxiv_id":null,"evidence_quote":"Introduces temporal JR and PJR, establishing the model and the baseline axioms the paper strengthens."},{"cited_title":"Justified representation in approval-based committee voting","cited_arxiv_id":null,"evidence_quote":"Introduces JR/EJR and core stability in multiwinner voting; the paper adapts these concepts to the temporal setting."},{"cited_title":"Robust and verifiable proportionality axioms for multiwinner voting","cited_arxiv_id":null,"evidence_quote":"Defines EJR+ in multiwinner approval voting, the axiom whose temporal adaptation is the paper's focus."},{"cited_title":"Proportional participatory budgeting with additive utilities","cited_arxiv_id":null,"evidence_quote":"Defines FJR and proves every multiwinner election admits an FJR outcome, the axiom adapted in Section 4."},{"cited_title":"Full proportional justified representation","cited_arxiv_id":null,"evidence_quote":"Proposes FPJR in multiwinner voting, the collective-guarantee axiom adapted in Section 5."}],"review_version":1}