{"id":"df8e15b9-e46a-4136-acb3-12fd2a0d0e29","arxiv_id":"2505.12451","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For spatial voting with interval-uncertain voter positions, possible-winner problems are polynomial-time solvable for k-truncated rules in 1D, FPT in the number of candidates in all dimensions, yet NP-complete for weighted approval-like rules in 1D.","lead":"This paper studies how hard it is to tell whether a candidate could win an election when voters' positions are only known as intervals. It gives fast algorithms for some voting rules and proves that other cases remain difficult, even with just a few candidates.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5 is false: two jobs from the reduction can have equal deadlines with incomparable endpoint shape sets, so no P-structured order exists and the DP underlying Theorem 1 lacks a valid recursive order.","rationale":"The paper contains several interesting ideas, and the FPT results via fixed-dimensional ILPs (Theorems 4 and 5) and the weighted hardness reductions may be independent and valuable. However, the headline contribution is Theorem 1, a polynomial-time algorithm for PW<1> under k-truncated rules, and its proof funnels entirely through the claim that the reduction yields P-structured jobs. The counterexample above shows Lemma 5 is false as stated: two valid voter intervals with the same deadline can produce endpoint shape sets {(2,1)} and {(1,2)}, which are incomparable. This is not a missing detail or a notational gap; it is a concrete violation of the structural property Definition 3 requires. The reader's weakest-assumption analysis focused on Lemma 1's monotone top-k window behavior; the failure identified here is orthogonal and occurs even if Lemma 1 is granted. Because the DP of Lemma 7 selects a last job j' using the total order and uses the inclusion property to swap jobs, the algorithm has no well-defined recursion on the instances produced by the reduction. The current writeup therefore does not substantiate the main theorem, and the verdict should move from CONDITIONAL to REJECT. If the authors can replace Lemma 5 with a correct structural lemma or provide a different DP decomposition, the result may be recoverable, but the present proof cannot be accepted as is.","tokens_in":26467,"tokens_out":22179,"duration_ms":237841,"concrete_test":"Independently verify Lemma 5 on the two-voter instance above: compute i_L, i_R, r_j, d_j, and F_j(d_j) for voters [10.1,14.9] and [15.1,19.9], then test both possible total orders against Definition 3. Both orders fail the required endpoint-set inclusion. If a revised structural lemma is proposed, re-run the DP recurrence (1) on this pair of jobs and check that it still yields the claimed O(n^{1+k+3k^2} m^3) bound; any correct algorithm must handle these two jobs without relying on a total order of incomparable endpoint shape sets.","verdict_should_be":"REJECT","load_bearing_attack":"Section 3.2, Lemma 5 claims the jobs generated by the reduction are P-structured, with an order by nondecreasing u_j and, for equal deadlines, inclusion of the endpoint shape sets. The proof excludes only the case where the later interval lies to the left of the segment defining a shape; it never handles the opposite case where the later interval lies to the right. That case is real. Take candidates c1=0, c2=10, c3=20, c4=30 and the k=2-truncated vector (2,1). Voter v1 with interval [10.1,14.9] has, for every possible position, top-two candidates c2,c3; hence r1=2, d1=4 and F_1(4)={f(E3)}={(2,1)}. Voter v2 with interval [15.1,19.9] also has r2=2, d2=4, but its top-two candidates are c3,c2, so F_2(4)={f(E4)}={(1,2)}. These two endpoint sets are incomparable. Therefore no total order can satisfy Definition 3's condition that d_j=d_j' implies F_j(d_j) is a subset of F_j'(d_j'). Lemma 5 is false, so the reduction does not produce P-structured instances. The DP in Lemma 7 relies on choosing a last job j' in exactly such an order and on the inclusion property to swap jobs j,j'; with incomparable endpoint sets neither step is justified. Since Lemma 5 is the bridge from PW<1> to shapes scheduling, Theorem 1's polynomial-time claim is not established by this proof.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the possible-winner (PW) problem in spatial voting where each voter's ideal point is known only through a box of intervals in d-dimensional Euclidean space and each candidate's position is known exactly. The main claims are: (i) for any fixed k, PW in one dimension under any k-truncated positional scoring rule is polynomial-time solvable via a reduction to a new 'shapes scheduling' problem; (ii) for any dimension d and any scoring rule or approval voting, PW is fixed-parameter tractable in the number m of candidates; and (iii) a complexity classification for the weighted version in one dimension, including NP-completeness for Borda with four candidates and a dichotomy for two-valued rules. The paper introduces the shapes scheduling model, proves a structural lemma (P-structured jobs), and gives a dynamic program based on a technique of Baptiste.","tokens_in":26789,"tokens_out":11021,"duration_ms":102087,"significance":"If the results were correct, the paper would be significant: it would resolve the tractability of the possible-winner problem for one-dimensional spatial voting with interval uncertainty for the broad and practically relevant class of k-truncated scoring rules with constant k, and it would provide the first FPT algorithms parameterized by the number of candidates for multidimensional spatial voting. The reduction-to-scheduling framework is a potentially useful new idea, and the weighted-case classification addresses an open direction. However, the central positive result of Section 3 rests on a structural lemma that is false, so the main theorem is not established by the proofs given.","major_comments":[{"comment":"Lemma 5 is false. The proof orders jobs by nondecreasing upper bounds u_j and considers a shape f(E) that lies in F_{d_j}^{(j)} but not in F_{d_j'}^{(j')}. It treats only the case where the later interval lies to the left of the segment E, leading to u_j < e_1 and a contradiction. The opposite case, where the later interval lies to the right of E, is never ruled out. This case actually occurs. Take candidates at 0, 10, 20, 30 and the 2-truncated rule (2,1). Voter v1 with interval [10.1,14.9] has r_1=2, d_1=4 and F_2^{(1)}={(2,1)}. Voter v2 with interval [15.1,19.9] also has r_2=2, d_2=4, but F_2^{(2)}={(1,2)}. These two endpoint sets are incomparable, so no total order can satisfy Definition 3's condition that equal deadlines imply inclusion of the endpoint shape sets. Thus the jobs generated by the reduction are not necessarily P-structured. Since Lemma 6 (the swap argument) and Lemma 7 (the DP) both rely on the existence of this order and on the inclusion property to swap jobs with equal deadlines, the dynamic program in Section 3.3 cannot be applied to the instances produced by the reduction. Consequently, Theorem 1, the paper's main positive result, is not proved.","section":"Section 3.2, Lemma 5"},{"comment":"The integer program given for the FPT algorithm does not constrain the variables x^z_tau when z is not in the type tau. The text says that a voter of type tau may vote exactly according to the vectors in tau, yet variables x^z_tau are introduced for every z in Z and no constraint forces x^z_tau=0 for z not in tau. As written, the ILP can assign voters to voting vectors that are not allowed by their type, producing solutions that do not correspond to any profile completion. The constraint sum_z x^z_tau = n_tau does not repair this. This needs an explicit restriction (for example, defining x^z_tau only for z in tau, or adding x^z_tau=0 for z not in tau) before Theorem 4 is established.","section":"Section 4, integer program for Theorem 4"}],"minor_comments":[{"comment":"The statement of Lemma 6 refers to a job j'' that is never defined in the proof; the proof uses j and j'. This makes the lemma difficult to parse and should be corrected.","section":"Section 3.3, Lemma 6"},{"comment":"The notation F_{d_j}^{(j)} is used for the set of shapes at start time d_j-k, but the reader is left to infer this. The paper should define this explicitly, since the subscript d_j does not match the start-time convention used elsewhere.","section":"Section 3.2 and Definition 3"},{"comment":"The recurrence in Lemma 7 uses an undefined term b(S_j', f(j')). It presumably represents the contribution to the objective when job j' is scheduled in shape f(j'), but it is never defined in the text.","section":"Section 3.3, Lemma 7"},{"comment":"There are several typographical and grammatical errors, including 'V oting' in the title, 'traceable' for 'tractable' in Section 5, and 'P +n + 2' in the proof of Theorem 6. These should be corrected.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The paper's main result (Theorem 1) is not supported because Lemma 5 is false, as demonstrated by a concrete counterexample. This is a load-bearing error in the central proof: the reduction does not produce P-structured instances, and the dynamic program of Section 3.3 cannot be applied. A fix would require substantial changes to the reduction or the algorithm, not a small correction. The FPT result in Section 4 also has a missing constraint in the ILP, though that one may be easier to repair. Given these issues, I recommend rejection, unless the authors can supply a corrected reduction or a different proof of polynomiality for one-dimensional k-truncated rules."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the main claim is not proven. Lemma 5, the bridge from possible winners to shapes scheduling, is false. The promised P-structured order does not exist, so the DP in Section 3.3 has no valid recursive basis.\n\nCounterexample: take candidates at 0, 10, 20, 30 and the 2-truncated rule (2,1). Voter 1 with interval [10.1,14.9] always ranks c2,c3 as its top two, so its endpoint shape set is {(2,1)}. Voter 2 with interval [15.1,19.9] always ranks c3,c2, so its endpoint shape set is {(1,2)}. Both jobs have the same deadline, but neither shape set is a subset of the other. Therefore no total order satisfies Definition 3's inclusion condition. Lemma 5's proof only handles the case where the later interval lies to the left of the segment defining the shape; the right-side case is exactly this counterexample. Since Lemma 6's swap argument and the DP's choice of a 'last job' use the inclusion property, Theorem 1's proof collapses at this point.\n\nCredit where it is earned: the reduction idea is natural, the shapes scheduling framework is a nice contribution, and the parameterized results are genuinely useful. Theorem 4's FPT algorithm via voter types and an ILP in fixed dimension is plausible, as is the approval-voting variant. The weighted dichotomy for two-valued rules and the Borda hardness for m=4 (Theorems 6 and 7) are independent of the broken lemma and look mostly solid, though I did not verify every case in Theorem 6. The paper builds honestly on Imber et al. and gives detailed proofs, which is why the false lemma stands out as a real error rather than a sloppy statement.\n\nThe notational issues the reader flagged (j'' vs j, j') are minor by comparison. The real problem is that the reduction does not produce P-structured instances in general. I cannot tell from this version whether a different proof strategy can save Theorem 1; the property as defined is simply not satisfied.\n\nWho this paper is for: researchers in computational social choice working on possible winners and spatial voting. The FPT and weighted results may be worth citing on their own, but the polynomial-time result for truncated rules should not be cited as established until Lemma 5 and the DP are repaired. A serious referee should see this paper, because the problem is important and some results are valuable, but the current version is not acceptable.","headline":"The paper's headline result, polynomial-time possible winners for constant-k truncated rules in 1D, is not established: the reduction to shapes scheduling relies on Lemma 5, and Lemma 5 is false.","tokens_in":27335,"tokens_out":4736,"would_cite":false,"duration_ms":51366,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B12","91B14","68Q17","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the possible-winner problem in one-dimensional spatial voting is polynomial-time solvable for every fixed top-k scoring rule, and fixed-parameter tractable in the number of candidates in any dimension.","keywords":["possible winner problem","spatial voting","positional scoring rules","k-truncated voting rules","approval voting","shapes scheduling","fixed-parameter tractability","weighted voters"],"falsifier":"Compare the paper's dynamic program with exhaustive search over all finitely many position segments for small one-dimensional instances under truncated Borda; any mismatch about whether a designated candidate can win would refute the claimed polynomial-time algorithm.","tokens_in":26247,"feed_emoji":"🗳️","tokens_out":9866,"duration_ms":96406,"temperature":0.7,"pith_summary":"The paper asks when a designated candidate can still win an election in the spatial model when each voter's ideal point is known only by an interval in each issue. Its central result is that in one dimension, for any scoring rule that gives positive weight to only a fixed number k of top ranks, the possible-winner question can be decided in polynomial time; the previous tractable cases were much narrower. In higher dimensions, where the same question is NP-complete even for simple rules, the paper shows the problem is fixed-parameter tractable in the number of candidates for every positional scoring rule and for approval voting. It also maps the weighted one-dimensional case: two-valued rules are easy exactly when they approve at least half the candidates, and Borda becomes NP-complete already at four candidates. A reader should care because these results draw a much clearer boundary between tractable and intractable uncertainty in a natural model of elections.","feed_headline":"Top-k possible winners in 1-D spatial voting now poly-time","feed_subtitle":"One-dimensional truncated rules become easy, and fixed candidate counts stay tractable in any dimension.","key_machinery":"The load-bearing device is the reduction from voter uncertainty to shapes scheduling. A shape is a vector saying how many machines a job occupies in each of k consecutive time slots; in the voting instance, time slot t is candidate c_t, and a voter-job's shape at start time t records the scores the voter could give to candidates c_t, ..., c_{t+k-1} from some feasible position. The generated job set is P-structured: every job has the same processing length, interior times share one global set of shapes, and jobs can be ordered so that deadlines and deadline shape sets are monotone. A dynamic program, built on a known equal-length jobs scheduling recursion, then decides whether the jobs fit on M* machines with all machines busy during the slot of the designated candidate. The monotonicity of a voter's top-k window as her ideal point moves rightward is what makes the instance P-structured.","core_discovery":"The paper establishes that the one-dimensional possible-winner problem can be solved in $O(n^{1+k+3k^2}m^3)$ time for every k-truncated positional scoring rule with constant k. The proof converts each voter into a job in a new 'shapes scheduling' problem, where time slots are candidates and the shape a job occupies records the scores the voter would hand to a sliding window of k candidates; a feasible schedule with all M* machines busy at the target candidate's slot is exactly a preference completion in which that candidate wins. For d >= 2 dimensions, it proves that the same problem is fixed-parameter tractable when the parameter is the number m of candidates, for any positional scoring rule, by typing each voter according to which of finitely many voting vectors it can realize and solving a fixed-variable integer program. The same FPT conclusion holds for approval voting. For weighted voters in one dimension, the paper gives a dichotomy for two-valued rules and proves that Borda is NP-complete even when there are only four candidates.","pith_inferences":["The FPT result suggests that the practical bottleneck is the number of candidates, not the dimension; one natural test is whether the same voter-typing argument survives when distances are not Euclidean.","The weighted dichotomy implicates the weights themselves, rather than spatial geometry alone, as the source of NP-hardness; a plausible extension is that other multi-valued scoring rules become hard in the weighted setting once the rule gives positive weight to fewer than half the candidates.","The shapes-scheduling formulation could be reused directly for the necessary-winner problem, since the same schedule already encodes upper bounds on every candidate's score."],"forward_implications":["Any fixed-top-k truncated rule in one dimension, including k-truncated Borda and common contest scoring vectors, becomes polynomial-time solvable.","In any number of dimensions, the possible-winner problem for every positional scoring rule is fixed-parameter tractable in the number of candidates, so few-candidate elections remain solvable even in high-dimensional issue spaces.","Approval voting, NP-complete in every dimension, is also fixed-parameter tractable in the number of candidates.","For weighted voters on a line, a two-valued rule is tractable exactly when it approves at least half of the candidates in every candidate count; otherwise the problem is NP-complete.","Weighted Borda is NP-complete with only four candidates on a line, in contrast to the polynomial-time unweighted one-dimensional case."],"supporting_citations":[{"why":"Defines the partial spatial voting model and supplies the prior tractability and NP-completeness results that this paper extends.","marker":"[22]"},{"why":"Supplies the equal-length jobs scheduling recursion that the shapes-scheduling dynamic program generalizes.","marker":"[2]"},{"why":"Introduces the possible-winner and necessary-winner questions that frame the paper's problems.","marker":"[25]"},{"why":"Provides the subroutine for deciding feasibility of systems of polynomial inequalities, used to check whether a voter can realize a given approval vector.","marker":"[21]"},{"why":"Provides the fixed-variable integer programming algorithm whose runtime underlies the FPT results.","marker":"[26]"},{"why":"Provides the improved fixed-variable integer programming algorithm used for the claimed FPT bounds.","marker":"[30]"},{"why":"Establishes single-peaked manipulation hardness that the weighted Borda reduction adapts, and connects to an open manipulation problem that the paper mentions.","marker":"[20]"}],"fun_headline_variants":["1-D spatial voting possible winners: poly-time for k-truncated","Spatial voting with missing data: FPT by candidate count","Weighted possible winners in 1-D: dichotomy for two-valued","Possible winners in d-D: FPT when candidates are few","Spatial voting incompleteness: easier in 1-D, still FPT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction behind the main polynomial-time result assumes that, as a voter's ideal point moves rightward on the line, the set of candidates in her top k moves rightward monotonically without skipping; if a different tie-breaking rule or a different distance made the set skip around, the scheduling construction would no longer be valid.","fun_headline_variants_meta":{"raw":{"variants":["1-D spatial voting possible winners: poly-time for k-truncated","Spatial voting with missing data: FPT by candidate count","Weighted possible winners in 1-D: dichotomy for two-valued","Possible winners in d-D: FPT when candidates are few","Spatial voting incompleteness: easier in 1-D, still FPT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1379,"prompt_tokens":941,"completion_tokens":438,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":557,"tokens_out":438,"duration_ms":4470,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:32:18.349905+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the paper's dynamic program with exhaustive search over all finitely many position segments for small one-dimensional instances under truncated Borda; any mismatch about whether a designated candidate can win would refute the claimed polynomial-time algorithm.","supporting_citations":[{"cited_title":"Imber, J","cited_arxiv_id":null,"evidence_quote":"Defines the partial spatial voting model and supplies the prior tractability and NP-completeness results that this paper extends."},{"cited_title":"Baptiste","cited_arxiv_id":null,"evidence_quote":"Supplies the equal-length jobs scheduling recursion that the shapes-scheduling dynamic program generalizes."},{"cited_title":"Konczak and J","cited_arxiv_id":null,"evidence_quote":"Introduces the possible-winner and necessary-winner questions that frame the paper's problems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the subroutine for deciding feasibility of systems of polynomial inequalities, used to check whether a voter can realize a given approval vector."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the fixed-variable integer programming algorithm whose runtime underlies the FPT results."},{"cited_title":"Reis and T","cited_arxiv_id":null,"evidence_quote":"Provides the improved fixed-variable integer programming algorithm used for the claimed FPT bounds."},{"cited_title":"Faliszewski, E","cited_arxiv_id":null,"evidence_quote":"Establishes single-peaked manipulation hardness that the weighted Borda reduction adapts, and connects to an open manipulation problem that the paper mentions."}],"review_version":1}