{"id":"beac517a-3207-4107-8823-888af39212c2","arxiv_id":"2502.07454","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A suite of convex-hull forbidden substructures, reduction rules, ILP, and QCP recognizes 2-Euclidean elections quickly, solving 283 more PrefLib instances than the previous algorithm.","lead":"Researchers built fast practical tests for whether voters' rankings of candidates can be explained by placing voters and candidates as points on a plane, with each voter preferring closer candidates. The new software resolves all but 60 of 7,743 real-world PrefLib preference datasets, compared with 343 unresolved by the previous algorithm.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ILP constraint (15) is not a necessary condition: with four concyclic candidates, two disjoint bisectors adjacent twice make the sum exceed 1, so a true 2-Euclidean election is rejected.","rationale":"The paper's headline contribution is a practical recognition/refutation pipeline; a central component is the ILP of Section 5, whose correctness is stated as Theorem 5.21. The reader's conditional verdict focused on the informal perturbation proof of Lemma 2.6 and the absence of released code. The more decisive problem is in constraint (15): it is not a necessary property of 2-Euclidean embeddings. The geometric counterexample with four concyclic candidates shows that all constraints can be derived from a valid embedding except that the LHS of (15) exceeds 1. Therefore the ILP is unsound as a refutation tool; some of the 4231 reported ILP-solved instances may be misclassified. The convex-hull Theorem 3.4 and the reduction rules may well be correct, but the paper's overall correctness claim and its empirical headline numbers depend on the invalid ILP constraint. A revision that replaces (15) with a true encoding of 4-cycles (e.g., requiring the four regions to be adjacent in the embedding graph) would be needed before the practical claims can be trusted. Given the false theorem in a core algorithmic contribution, the appropriate verdict is REJECT rather than CONDITIONAL.","tokens_in":45861,"tokens_out":34979,"duration_ms":350896,"concrete_test":"Evaluate the ILP, or just constraint (15), on the 2-Euclidean election with candidates at unit-circle angles 0° (A), 30° (B), 80° (C), 150° (D) and voters placed one in each of the 12 sectors of the bisector arrangement. Compute the two 4-tuples for C_{BC|AD}: {S3,S2,S4,S9} and {S9,S8,S10,S3}. If all involved x_v are forced to 1 by constraint (1), the sum in (15) is 2, violating the claimed bound, and the Gurobi model will report infeasible for a known yes-instance.","verdict_should_be":"REJECT","load_bearing_attack":"Section 5.3.1, constraint (15), is not correct as stated. Its justification — that two bisectors intersect at most once and hence there is at most one 4-cycle — conflates nonemptiness of four permutations with the existence of a 4-cycle in the embedding graph. When several bisectors are concurrent, the dual graph around the intersection is a cycle of length larger than 4; the permutations v, v∘τ_ab, v∘τ_cd, v∘τ_ab∘τ_cd can all be nonempty in non-adjacent sectors without forming any 4-cycle. A concrete witness: place the four candidates on the unit circle at angles 0°, 30°, 80°, 150°. All six perpendicular bisectors pass through the origin, with directions 15°, 40°, 55°, 75°, 90°, 115° and their opposites; this is a nice candidate embedding. Let the election contain all 12 sector votes. The disjoint bisectors BC and AD are adjacent twice in the cyclic order, at 55°–75° and at 235°–255°. The two 4-tuples {S3,S2,S4,S9} and {S9,S8,S10,S3} both have all four regions nonempty, so the left-hand side of (15) is at least 2 for {a,b}={B,C}, {c,d}={A,D}. Yet the embedding graph is merely a 12-cycle and contains no 4-cycle for either tuple. Thus a genuine 2-Euclidean election violates (15); Theorem 5.21 is false, and the ILP can return false no-certificates.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a practical toolkit for deciding whether a given preference profile is 2-Euclidean. It introduces a new forbidden-substructure refutation based on the controversity graph of voters (Theorem 3.4), several candidate-reduction rules with explicit solution lifting, an ILP that encodes necessary conditions on the embedding graph, and a QCP formulation with an epsilon-scaling bounding-box scheme. Experiments on PrefLib report that the combined pipeline reduces the number of unresolved instances from 343 to 60 and resolves 98.7% of instances in under one second. The main theoretical claims are Theorem 3.4 (convex-hull refutation), Theorem 5.21 (correctness of the ILP constraints), and Lemma 6.2 (QCP equivalence); most proofs are constructive, and the experimental comparison with the EST algorithm is thorough.","tokens_in":46156,"tokens_out":44037,"duration_ms":396541,"significance":"If the results hold, this is a useful practical advance in recognizing 2-Euclidean preferences. The reduction rules are proven correct with explicit embedding-lifting algorithms, the QCP epsilon-scaling equivalence is proved cleanly, and the benchmark study is extensive and directly compares with the previous EST algorithm. The main caveat is that one load-bearing perturbation lemma, Lemma 2.6, is only sketched; a complete proof is needed before the 'nice embedding' framework supporting the ILP can be regarded as fully sound. I also examined the alleged counterexample to ILP constraint (15) based on four concyclic candidates; it does not survive scrutiny, because if all four permutations in a tuple from C_{ab|cd}(v) are nonempty, Observation 5.3 forces them to form a 4-cycle in the embedding graph. The proof of (15) should nevertheless be written out more carefully, since the current one-sentence justification is too terse.","major_comments":[{"comment":"The proof of Lemma 2.6 is only a sketch. The sentence 'by similar arguments as in Lemma 2.5 we can ensure that no triplets of candidates become collinear and no pair of bisectors becomes a parallel pair' omits the central argument: one must show that a sufficiently small perpendicular movement of candidate a exists that simultaneously preserves all nonempty regions, avoids all positions that create a collinear candidate triple, avoids all positions that create a new parallel pair, and strictly reduces the number of parallel pairs. Because Theorem 2.8 and hence the ILP section's use of 'nice' embeddings depend on this lemma, please provide a complete argument, including an explicit description of the finite set of forbidden positions and a proof that it cannot cover the allowable open region.","section":"Section 2.6 (Lemma 2.6)"},{"comment":"The correctness argument for constraint (15) is too terse as written. The text says that two bisectors intersect at most once and therefore there is at most one 4-cycle for the pair, but it does not address the possibility of three or more concurrent bisectors. I checked the proposed concyclic counterexample and it does not invalidate the constraint: if all four permutations v, v∘τ_ab, v∘τ_cd, and v∘τ_ab∘τ_cd are nonempty, then each consecutive pair in the 4-tuple differs by a consecutive swap, so by Observation 5.3 the four vertices form a 4-cycle in D_γ; two such 4-cycles for the same pair of bisectors would force the two bisectors to intersect twice. The proof should nevertheless be expanded to state this explicitly, since Theorem 5.21 certifies the soundness of the whole ILP.","section":"Section 5.3.1, Eq. (15)"}],"minor_comments":[{"comment":"The phrase 'we propose practical approach' should read 'we propose a practical approach'.","section":"Abstract"},{"comment":"The phrase 'has nonzero (possibly infinite) measure' is informal; it would be clearer to say that the region has nonempty interior and hence positive area, possibly infinite.","section":"Section 2.6 (Lemma 2.4)"},{"comment":"The term 'opposite arc' is used without a formal definition; please define it in terms of the cyclic order of the intersection points on the bounding circle.","section":"Section 5.1.1 (Lemma 5.11)"},{"comment":"The sentence 'Observe that if we sum over all distinct constraints of the form (15)' is confusing; I suggest rephrasing to 'Consider all constraints of the form (15), one for each 4-subset of candidates.'","section":"Section 5.3.1"},{"comment":"There is a typo: 'the constrains with the sum' should be 'the constraints with the sum'.","section":"Section 7.2"},{"comment":"The per-dataset table and the solver-combination figure are information-dense and hard to parse; splitting the table or using clearer column headers would improve readability.","section":"Section 7.3 / Figures 12 and 16"},{"comment":"The paper does not mention availability of code or data; providing a repository would strengthen the reproducibility of the experimental claims.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the expected scope of a computational social choice journal and I see no citation or novelty concerns. The main technical risk is the informal proof of Lemma 2.6; I would encourage the editor to request a complete proof rather than accept the current sketch. The suspected issue with constraint (15) appears to be a false alarm, but the authors should still clarify the proof. Once the perturbation lemma is fully proved and the ILP soundness argument is tightened, the paper should be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read this with the stress-test note in hand, and the note lands. The paper builds a genuinely useful practical toolkit: the convex-hull controversity graph (Theorem 3.4) is a new, correctly-proved forbidden substructure; the reduction rules come with explicit lifting constructions; and the QCP bounding-box/scaling idea is a sensible improvement over EST. The empirical headline numbers—60 unresolved PrefLib instances, 98.7% under one second—are plausible given that most instances are killed by the 3-8 pattern or the convex hull alone, both of which are on solid ground.\n\nThe soft spot is Section 5.3.1. Constraint (15) says each pair of bisectors can contribute at most one 4-cycle in the embedding graph. The justification conflates 'four regions around an intersection are nonempty' with 'those regions form a 4-cycle in the weak dual.' When several bisectors are concurrent, the dual around that vertex is a 2k-cycle, and the four 'quadrant' regions are not adjacent to each other as a 4-cycle. The stress-test gives a concrete counterexample: four concyclic candidates at angles 0°, 30°, 80°, 150° with all 12 sector votes. This is 2-Euclidean, yet the left-hand side of (15) for {B,C} and {A,D} is 2, so the ILP would declare it non-2-Euclidean. That makes Theorem 5.21 false and the ILP unsound as a refutation tool. The lazy constraint-generation scheme would add this violated constraint and then report infeasible, so this is not a mere theoretical edge case; it can produce false no-certificates. The fix is to encode actual 4-cycles in the embedding graph (e.g., with auxiliary variables for edges), not just the co-existence of four nonempty regions.\n\nA smaller issue: Lemma 2.6's perturbation argument is hand-waved ('by similar arguments'), and since the convex-hull and ILP properties rely on 'nice' embeddings, that lemma deserves a formal proof. It is probably true, but the paper underestimates the gap.\n\nNet: the convex-hull and reduction-rule parts are solid enough for publication; the ILP component needs repair before its no-certificates can be trusted. The paper should still go to peer review—the ideas are worth refereeing, and a careful referee should catch exactly this. I would not cite the ILP result until corrected, but I would follow future revisions.","headline":"A practical, mostly sound toolkit for refuting 2-Euclidean preferences, but the ILP's 4-cycle constraint is incorrect and can reject true 2-Euclidean elections.","tokens_in":97,"tokens_out":5701,"would_cite":false,"duration_ms":253319,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes a graph-theoretic obstruction—the controversity graph of a 2-Euclidean election has maximum degree at most two and any cycle is connected—and uses it, with reduction rules and ILP/QCP solvers, to classify almost all…","keywords":["2-Euclidean preferences","Euclidean embedding","forbidden substructures","controversity graph","convex hull","integer linear programming","quadratically constrained programming","PrefLib"],"falsifier":"Take one of the 60 unresolved PrefLib instances, run the QCP solver with growing bounding boxes until it returns an explicit 2-Euclidean embedding, then compute the controversity graph; if the graph has a vertex of degree at least 3 or a cycle plus another component, Theorem 3.4 is false. A direct computer search over verified 2-Euclidean elections on five candidates looking for such a graph would also settle the theorem.","tokens_in":45638,"feed_emoji":"🗳️","tokens_out":4639,"duration_ms":43097,"temperature":0.7,"pith_summary":"The paper tries to make the recognition of 2-Euclidean elections practical, despite the problem being ∃R-complete in general. Its main theoretical contribution is a new class of forbidden substructures: in any 2-Euclidean election, the corresponding controversity graph must have maximum degree at most two, and if it contains a cycle, that cycle must be the whole connected component. This gives a fast refutation test that, together with the known 3-8 pattern, reduction rules, and ILP/QCP solvers, resolves most real-world preference data in under a second.","feed_headline":"Convex-hull test cuts unresolved voting datasets from 343 to 60","feed_subtitle":"Four-voter hull patterns plus reduction rules classify 98.7 percent of PrefLib instances in under one second","key_machinery":"The controversity graph CG(C,V) has a vertex for each voter who is uniquely on one side of some candidate-pair bisector, and an edge for each pair of voters that are jointly on one side of a bisector. In a nice 2-Euclidean embedding these vertices must occupy the convex hull of the voter set and edges encode consecutiveness on that hull, forcing the graph to be a path, a cycle, or a disjoint union of paths—hence the degree and connectivity restrictions. The ILP adds further combinatorial constraints drawn from the region-count upper bound, the embedding graph's distance-preserving structure, and bisector-crossing bounds.","core_discovery":"The central claim is Theorem 3.4: if an election is 2-Euclidean, then its controversity graph CG(C,V) has maximum degree at most 2 and, if it contains a cycle, the graph is connected. Consequently, an election whose controversity graph has a vertex of degree at least 3, or a cycle plus any other component, is immediately certified as not 2-Euclidean. The proof runs through a nice 2-Euclidean embedding, where controversial voters must lie on the convex hull and controversial pairs must be consecutive on it.","pith_inferences":["My inference: the empirical equivalence of Hull and Hull++ hints that, on PrefLib-sized profiles, checking all four-voter subelections may capture every convex-hull obstruction; proving this would yield a polynomial-time no-certificate for a wide class of real-world elections.","My inference: if the paper's conjecture that Reduction Rule 1+ cannot remove more than three copied tail-block candidates is correct, then the block-copy reduction is exactly tight, and any extension would need a fundamentally different construction.","My inference: the convex-hull approach may generalize to d-Euclidean elections through controversial subsets mapped to faces of the higher-dimensional convex hull; the paper leaves this open, but a degree-bound analogue would likely give a similar practical refutation test.","My inference: the ILP's lazy variable creation, beginning with the actual votes and adding permutations only as needed, may itself be a reusable pattern for other ∃R-complete recognition problems where the search space is factorial."],"forward_implications":["An election whose controversity graph has a degree-3 vertex or a disconnected cycle is provably not 2-Euclidean, and this refutation can be checked in polynomial time by scanning candidate pairs and voter triples.","The hull-based refutation, restricted in practice to four-voter subelections, matches the full version on all PrefLib instances, suggesting that small voter subsets capture most real-world convex-hull obstructions.","The reduction rules preserve 2-Euclideanness and removed 1,729 candidates across 802 PrefLib instances, making many previously hard instances tractable for the EST baseline as well.","The improved QCP formulation with a growing bounding box supplies yes-certificates, solving 39 nontrivial yes-instances that no other component could handle.","Combining all components lowers the number of unresolved PrefLib instances from 343 to 60, with 98.7% of instances resolved in under one second."],"supporting_citations":[{"why":"Supplies the region-count upper bound ub(m) used in ILP constraint (2).","marker":"[2]"},{"why":"Gives the 3-8 pattern, the forbidden structure on three voters and eight candidates used as a no-certificate.","marker":"[4]"},{"why":"Shows small elections (at most two voters, or three voters with at most seven candidates) are always 2-Euclidean, supporting the trivial-case classification and the tightness of the 3-8 pattern.","marker":"[7]"},{"why":"The EST algorithm is the previous baseline whose unresolved count (343) and running times the paper compares against.","marker":"[17]"},{"why":"Characterizes maximal non-2-Euclidean profiles on four candidates, used to justify skipping candidate subsets below size five in the ILP.","marker":"[23]"},{"why":"Defines the PrefLib benchmark datasets on which all experiments are run.","marker":"[32]"},{"why":"Establishes ∃R-completeness of recognizing multidimensional Euclidean preferences, motivating the use of incomplete forbidden-substructure heuristics.","marker":"[35]"}],"fun_headline_variants":["Convex-hull test resolves 98.7% of instances in under 1s","Forbidden substructures slash unresolved PrefLib from 343 to 60","Practical 2-Euclidean recognition with forbidden substructures","New graph test rapidly detects 2-Euclidean preferences","ILP and reduction rules beat prior 2-Euclidean algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on Theorem 2.8's guarantee of a nice 2-Euclidean embedding—in particular Lemma 2.6's claim that parallel bisectors can always be perturbed away, which the paper argues informally by analogy with Lemma 2.5; if a boundary case defeats that perturbation, the convex-hull refutation loses its foundation.","fun_headline_variants_meta":{"raw":{"variants":["Convex-hull test resolves 98.7% of instances in under 1s","Forbidden substructures slash unresolved PrefLib from 343 to 60","Practical 2-Euclidean recognition with forbidden substructures","New graph test rapidly detects 2-Euclidean preferences","ILP and reduction rules beat prior 2-Euclidean algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001182,"raw_usage":{"total_tokens":4875,"prompt_tokens":933,"completion_tokens":3942,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":3848}},"tokens_in":549,"tokens_out":3942,"duration_ms":24745,"temperature":1.0,"reasoning_tokens":3848,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:42:11.221505+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take one of the 60 unresolved PrefLib instances, run the QCP solver with growing bounding boxes until it returns an explicit 2-Euclidean embedding, then compute the controversity graph; if the graph has a vertex of degree at least 3 or a cycle plus another component, Theorem 3.4 is false. A direct computer search over verified 2-Euclidean elections on five candidates looking for such a graph would also settle the theorem.","supporting_citations":[{"cited_title":"Bennett and William L","cited_arxiv_id":null,"evidence_quote":"Supplies the region-count upper bound ub(m) used in ILP constraint (2)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the 3-8 pattern, the forbidden structure on three voters and eight candidates used as a no-certificate."},{"cited_title":"2-Dimensional Euclidean Preferences","cited_arxiv_id":"2205.14687","evidence_quote":"Shows small elections (at most two voters, or three voters with at most seven candidates) are always 2-Euclidean, supporting the trivial-case classification and the tightness of the 3-8 pattern."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The EST algorithm is the previous baseline whose unresolved count (343) and running times the paper compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the PrefLib benchmark datasets on which all experiments are run."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes ∃R-completeness of recognizing multidimensional Euclidean preferences, motivating the use of incomplete forbidden-substructure heuristics."}],"review_version":1}