{"id":"c1bea1a1-4e0b-499e-89d5-14eabd67c52c","arxiv_id":"2412.09005","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Winner determination under Conditional Minisum Approval is hard to speed up beyond brute force under SETH/ETH, but becomes polynomial for group-dichotomous ballots or bounded per-voter vertex cover with a constant number of voters.","lead":"This paper maps the computational difficulty of the Conditional Minisum Approval voting rule, showing that no algorithm can beat brute-force search unless the Strong Exponential Time Hypothesis fails. It also identifies two ballot or dependency restrictions under which the rule becomes efficiently computable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's claimed dichotomy is unproven: the 'otherwise NP-hard' direction is a one-sentence reference to [MP21]/[KSTW01] with no reduction, and the statement is ill-posed as a per-instance dichotomy.","rationale":"I read the paper in good faith. Theorems 1 and 2 give credible SETH/ETH lower bounds; the constructions are explicit and the running-time bookkeeping works. Theorem 6 is a clean structural argument and appears correct. Theorem 3 has an ambiguity in the domain of constraint issues ('all |Sigma|^2 possible outcomes' vs 'satisfying assignments'); read as satisfying assignments the reduction goes through, so this is a fixable exposition issue rather than a fatal flaw. The real load-bearing concern is Theorem 4: it is the paper's dichotomy and 'essentially tight' claim, yet one direction is unproved and the statement is not precisely formulated. The reader identified the same gap. My proposed check would settle it: either a complete reduction appears, or the claim is downgraded. Because the rest of the paper's positive results and lower bounds remain credible, a conditional acceptance pending the Theorem 4 proof is the right verdict; hence no change to the reader's verdict.","tokens_in":14260,"tokens_out":36512,"duration_ms":389517,"concrete_test":"Complete the proof of Theorem 4 in two steps: (1) Give an explicit polynomial reduction from an NP-hard problem (e.g., Min-2SAT or Vertex Cover) to cms instances with Delta=1 that are not group-dichotomous, and prove the objective is preserved exactly; this replaces the '[MP21] reduction' sentence. (2) Re-state the dichotomy at class level and check whether the [BL16] hardness construction already cited in Section 4.1 yields the needed non-group-dichotomous hard instances. If step (1) cannot be supplied, the 'otherwise NP-hard' claim should be replaced by the known [BL16] hardness of the unrestricted class, and the paper's boundary claim weakened accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central boundary claim is Theorem 4 (Section 4.1): group-dichotomous instances are poly-time and all others are NP-hard, even for Delta=1. The tractability half reduces group-dichotomous cms to min-csp with constraints of a special DNF form, but the proof does not spell out how multi-statement ballots (e.g., two group-dichotomous statements such as {0_u:0_v} and {1_u:1_v} for the same issue) map to constraints with the same dissatisfaction count. The intractability half is asserted in one sentence: 'By following the reduction proving hardness from [MP21]...' No construction is given, no verification that the resulting cms instances are non-group-dichotomous, and no mapping from the referenced [KSTW01] classification is supplied. Moreover, NP-hardness is a property of a class of instances, not of a single non-group-dichotomous instance; as written, 'otherwise it is NP-hard' is not a meaningful dichotomy. If the intended claim is only that the unrestricted class is NP-hard, that is already covered by [BL16] and should be stated as such; if a genuine dichotomy is claimed, an explicit reduction is required. This gap is load-bearing because the paper's advertised contribution is that the computational boundary is exactly mapped.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of the Conditional Minisum Approval (cms) rule in multi-issue elections. The first part establishes lower bounds: Theorem 1 gives a SETH-based result showing that no algorithm can solve cms in time d^{(1-epsilon)m} times a polynomial in the input size, matching the trivial brute-force d^m bound up to a subexponential factor; Theorem 2 gives an ETH lower bound of the form f(m)d^{o(m)} for instances with maximum in-degree Delta=2; Theorem 3 gives an ETH lower bound of the form d^{o(m/log m)} for Delta=1 instances. The second part proposes two tractable restrictions: Theorem 4 claims that on binary issues, cms is polynomial-time solvable when all ballots are group-dichotomous and NP-hard otherwise, even for Delta=1; Theorem 6 shows that when the number of voters is constant, Delta=1, and each voter's dependency graph has bounded vertex cover number, the global dependency graph has bounded treewidth, so cms is polynomial-time solvable. The paper also discusses the tightness of these restrictions.","tokens_in":14479,"tokens_out":18363,"duration_ms":177702,"significance":"If the results are correct, the paper provides a valuable and fairly complete tractability map for a central rule in conditional approval voting. The lower bounds are significant: Theorem 1 is a strong SETH-based optimality result for the brute-force algorithm, and Theorems 2 and 3 show that hardness persists even under very simple ballot structures such as in-stars and out-stars on three vertices. Theorem 6 is a clean positive result: it identifies a local, easily checkable restriction on each voter's dependency graph that implies the bounded-treewidth condition needed for the existing algorithm of Markakis and Papasotiropoulos. The proofs of Theorems 2 and 6 are transparent and appear correct, and the paper gives explicit reductions from k-multicolored clique and 2-CSP. The main weakness is Theorem 4: the hardness direction of the claimed dichotomy is not proven by the argument in the text, and the theorem's statement is ambiguous as a per-instance dichotomy. The paper's advertised contribution of exactly mapping the tractability boundary depends on this theorem, so the gap is load-bearing.","major_comments":[{"comment":"The hardness half of Theorem 4 is not established. NP-hardness is a property of a class of instances, not of a single non-group-dichotomous instance, so the statement 'otherwise it is NP-hard' is ill-posed if read per instance. The proof's one-sentence appeal to [MP21] and [KSTW01]—'By following the reduction proving hardness from [MP21]...'—does not supply a reduction, does not verify that the produced cms instances satisfy Delta=1, and does not show that they are non-group-dichotomous. The reference to [KSTW01] also does not justify the claim, because that paper's classification applies to constraint languages, not to the particular DNF form described earlier. The conclusion may be recoverable by citing the existing NP-hardness of cms from [BL16] and observing that those hard Delta=1 instances are not group-dichotomous, but that argument is not made and the current proof is not a valid derivation. This is a load-bearing point because the paper advertises Theorem 4 as exactly locating the tractability boundary.","section":"Section 4.1, Theorem 4"},{"comment":"The construction of the constraint issues I_{uv} is ambiguous and, under the literal reading, the reverse direction of the reduction fails. The text says that D_{uv} is 'a list of all the |Sigma|^2 possible outcomes of the corresponding constraint,' but the reverse direction relies on the outcome of I_{uv} being a satisfying assignment of that constraint. If D_{uv} contains all |Sigma|^2 pairs, then an outcome that selects a non-satisfying pair for I_{uv} will satisfy every voter regardless of the values of I_u and I_v, because no voter was added for that pair; the extracted assignment may then violate the constraint while total dissatisfaction is zero. The proof should restrict D_{uv} to the set of satisfying assignments of the constraint, and it should also address constraints with no satisfying assignments.","section":"Section 3, Theorem 3"},{"comment":"The encoding of the case where a voter approves both 0_j and 1_j for issue I_j is unclear and appears to contain a simplification error. As printed, the constraint (x_j ∧ ∧_k y_k) ∨ (\\bar{x}_j ∧ ∧_k \\bar{y}_k) is not equivalent to ∧_k y_k; the displayed formula therefore does not support the claimed reduction to min-cut. The proof also does not state how multiple conditional statements for the same issue are aggregated into constraints, which matters because a group-dichotomous ballot may contain more than one statement for a single issue. Please restate this part of the reduction explicitly and verify the equivalence for each allowed statement type.","section":"Section 4.1, tractability proof of Theorem 4"}],"minor_comments":[{"comment":"The paragraph discussing structural graph parameters says the hardness proofs are 'as strong as they could be' because the number of vertices in the global dependency graph equals m and upper-bounds pathwidth and vertex cover number; this is correct but should be stated more carefully, since the upper bound by m is trivial and does not by itself imply optimality of the running-time exponents.","section":"Section 3, after Theorem 3"},{"comment":"The proof says the pathwidth of the voters' dependency graphs equals 1; for a disjoint union of paths the pathwidth is at most 1, and saying 'equals 1' is harmless for nonempty paths, but the wording could be tightened.","section":"Section 4.2, Observation 2"},{"comment":"The proof of bounded treewidth for the global dependency graph is correct but terse: it should explicitly say that every edge of the first voter's graph has at least one endpoint in the vertex cover C, so adding C to every bag of the tree decomposition of the second voter's graph yields a valid tree decomposition of the union. This would help readers who are not experts in treewidth.","section":"Section 4.2, Theorem 6"},{"comment":"There are duplicated passages and typographical artifacts in the introduction (for example, a paragraph beginning 'This work examines the feasibility of conditional approval voting...' repeats the contribution summary), and several OCR-style misspellings such as 'V oting' and 'di fferent' appear throughout the text.","section":"Section 1 and abstract"},{"comment":"The concluding sentence states that the paper 'effectively and completely resolves the question of efficient computation' of cms; given the gaps in Theorem 4, this claim is too strong as written and should be moderated.","section":"Section 5, Conclusions"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and contains several results that are likely correct and valuable, especially Theorems 2, 3, and 6. The main obstacle is Theorem 4: the hardness direction is not proven in the text, although it may be salvageable by a direct appeal to [BL16]. Theorem 3 also needs a domain correction. If the authors repair these points, I would be inclined to accept the paper; the current version is not ready for publication because the paper's central 'exact boundary' claim rests on an unsupported proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the Amanatidis et al. paper on conditional minisum approval. The headline is that the paper overclaims: Theorem 4, the “group-dichotomous iff poly-time” boundary, is not established. The 'otherwise NP-hard' direction is one sentence: \"By following the reduction proving hardness from [MP21]...\" No reduction is given, and the logic is circular — it assumes the thing you'd need to prove to transfer the [KSTW01] classification. Also, as written, \"if the instance is group-dichotomous then cms can be optimally solved, otherwise it is NP-hard\" is not a meaningful per-instance dichotomy; NP-hardness is a property of a class. The stress-test note is right that this is load-bearing, because the paper's contribution is advertised as a complete mapping of the tractability boundary.\n\nBut there is real content here. The SETH lower bound (Theorem 1) is tight: it shows the brute-force d^m algorithm is essentially optimal. The ETH lower bounds for Delta=2 with in-stars (Theorem 2) and Delta=1 with out-stars (Theorem 3) are genuinely strong and improve on the earlier treewidth-based bound. Theorem 6, the per-voter vertex cover bound for constant voters, is a clean structural result and a nice observation that bounded per-voter pathwidth doesn't imply bounded global treewidth. Those parts check out.\n\nMinor soft spots: Theorem 3's proof defines the domain of constraint issues as \"all |Sigma|^2 possible outcomes\" but the reverse direction requires the domain to be exactly the satisfying assignments of the constraint; otherwise the voter construction doesn't enforce consistency. This is fixable with a clarification. Also, the tractability half of Theorem 4 doesn't spell out how multi-statement ballots map to min-csp constraints with the same dissatisfaction count; the constraint set may need more than one constraint per voter-issue pair.\n\nThe paper is worth serious refereeing. The lower bounds alone justify it. I'd recommend conditional acceptance: require the authors to either turn the Theorem 4 intractability direction into an explicit reduction or restate the claim as \"the unrestricted class is NP-hard\" (already known from [BL16]) and drop the dichotomy language. The ambiguity in Theorem 3 should be clarified. If they fix these, the paper is a solid contribution to the tractability literature for this voting rule.\n\nI'd bring it to the reading group — the Theorem 4 gap is a useful case study in how hard it is to prove a dichotomy.","headline":"The lower bounds are solid, but the advertised dichotomy in Theorem 4 is not proven as written; the intractability half is a one-sentence reference.","tokens_in":15089,"tokens_out":2630,"would_cite":true,"duration_ms":24869,"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":"This paper claims that finding the winner under Conditional Minisum Approval Voting is essentially as hard as brute-force search, and that only group-dichotomous ballots or bounded per-voter dependency structure make it polynomial.","keywords":["conditional approval voting","multi-issue elections","winner determination","computational complexity","SETH","exponential time hypothesis","vertex cover number","treewidth"],"falsifier":"To test the dichotomy, write out the reduction promised in Theorem 4: if any non-group-dichotomous conditional-approval instance with $\\Delta=1$ maps to a min-CSP instance whose constraints are all two-term DNF formulas, the claimed NP-hardness is false; likewise, in Theorem 3, verify that every constraint-issue domain $D_{uv}$ contains only satisfying assignments of the corresponding 2-CSP constraint, since otherwise the reverse direction of the reduction breaks.","tokens_in":13984,"feed_emoji":"🗳️","tokens_out":15426,"duration_ms":146159,"temperature":0.7,"pith_summary":"The paper sets out to map exactly when the Conditional Minisum Approval Voting rule (CMS) can be computed efficiently. Voters submit conditional approval ballots over interdependent issues, and the rule selects the outcome minimizing total dissatisfaction. Under the Strong Exponential Time Hypothesis, the paper establishes that no algorithm can substantially beat the obvious exhaustive search over all $d^m$ outcomes, and under the Exponential Time Hypothesis this near-brute-force hardness persists even when each voter's preferences depend on at most one other issue ($\\Delta=1$). It then identifies two restrictions that make CMS polynomial-time solvable: group-dichotomous binary ballots, in which voters approve only coherent all-zeros or all-ones configurations, and dependency graphs with bounded vertex cover number per voter when the number of voters is constant. Both restrictions are shown to be essentially tight, giving a clean tractability landscape and a practical guideline for when conditional approval voting can be used.","feed_headline":"Conditional approval voting hits brute-force hardness","feed_subtitle":"Only group-dichotomous ballots or bounded per-voter structure give polynomial-time winners.","key_machinery":"The argument is carried by voters' dependency graphs: each voter $i$ has a directed graph $G_i$ whose edges say which issues' outcomes the voter's approval on an issue depends on, and $\\Delta$ is the maximum in-degree across voters. The brute-force benchmark is the $O(d^m)$ algorithm that tries every outcome. For hardness, three reductions do the work: k-SAT clauses encoded as conditional ballot statements (SETH lower bound), k-multicolored clique encoded as a star dependency graph (ETH lower bound at $\\Delta=2$), and 2-CSP encoded as out-star dependencies (ETH lower bound at $\\Delta=1$). For tractability, the group-dichotomous restriction turns each conditional ballot into a constraint that is a disjunction of one positive conjunction and one negative conjunction, a class reducible to min-cut; and the vertex cover number of a voter's graph (the size of the smallest set of issues touching every declared dependency), when bounded per voter and with constantly many voters, lets the proof augment a tree decomposition of one voter's graph by another voter's vertex cover to obtain bounded treewidth of the global dependency graph, unlocking the known polynomial algorithm.","core_discovery":"The central discovery is a computational dichotomy for CMS: worst cases are essentially brute-force hard, and two natural restrictions are the polynomial-time islands. On the negative side, for every $\\epsilon>0$ an algorithm running in time $d^{(1-\\epsilon)m}\\cdot|P|^{O(1)}$ would falsify SETH; under ETH, no $f(m)d^{o(m)}$ algorithm exists even when $\\Delta=2$ and every conditional dependency graph is an in-star, and no $d^{o(m/\\log m)}$ algorithm exists even when $\\Delta=1$ and every conditional dependency graph is an out-star. On the positive side, for binary issues the group-dichotomous restriction—voters approve only all-zeros or all-ones configurations—reduces CMS to a minimum-constraint-satisfaction instance whose constraints are each a disjunction of one positive conjunction and one negative conjunction, a class solvable in polynomial time via min-cut; the paper claims that without this restriction the problem is NP-hard even at $\\Delta=1$. In the structural direction, when $\\Delta=1$ and the number of voters is constant, bounded vertex cover number in each voter's dependency graph forces bounded treewidth of the global dependency graph, so the known bounded-treewidth algorithm applies; this is tight because bounded pathwidth per voter does not suffice.","pith_inferences":["A testable extension: on real participatory-budgeting or committee ballots, one can measure what fraction of conditional approvals are group-dichotomous; if that fraction is high, the min-cut algorithm becomes a practical solver, a question the paper does not itself test.","The SETH and ETH lower bounds target exact winner determination only; they leave open whether approximating the minimum total dissatisfaction within a constant factor is easier, which would be a natural next step.","The proof of the vertex-cover result only needs the per-voter graphs to combine into bounded treewidth, so the same argument should work for any per-voter structural parameter that implies bounded vertex cover or bounded treewidth, a generalization the paper does not state.","Because both positive restrictions can be checked locally on individual ballots, the results give election organizers a practical pre-vote test: enforce group-dichotomy or bound each voter's declared dependencies before the election, and the winner can be computed in polynomial time."],"forward_implications":["Under SETH, any exact algorithm for CMS must have running time $d^{\\Omega(m)}$ in the worst case, so an election run under the rule should either have few issues or explicitly impose one of the tractable restrictions.","The ETH lower bounds imply that restricting each voter's conditional preferences to a single dependency (in-stars or out-stars on three issues) does not make the problem easy, so simple syntactic limits on ballot complexity cannot rescue the rule.","Group-dichotomous binary instances are polynomial-time solvable through min-cut, which means voters who express package-style preferences (all of these together or none) can be aggregated efficiently.","With a constant number of voters and $\\Delta=1$, bounded vertex cover number per voter yields polynomial-time winner determination, covering natural profiles where each voter names a few critical issues that influence many others.","Both positive results are tight: removing group-dichotomy brings back NP-hardness, and allowing a nonconstant number of voters makes the vertex-cover restriction insufficient."],"supporting_citations":[{"why":"It introduced the conditional approval framework and proved that CMS is NP-hard, giving the baseline hardness this paper strengthens.","marker":"[BL16]"},{"why":"It established the bounded-treewidth characterization and supplied the hardness reduction that Theorem 4 invokes and Theorem 5 relies on.","marker":"[MP21]"},{"why":"It formulated SETH, the assumption behind the near-brute-force lower bound of Theorem 1.","marker":"[IP01]"},{"why":"It gives the ETH lower bound for multicolored clique that Theorem 2 reduces from.","marker":"[CHKX06]"},{"why":"It gives the ETH lower bound for 2-CSP that Theorem 3 reduces from.","marker":"[Mar10]"},{"why":"It shows that the two-term DNF min-CSP class reduces to min-cut, providing the polynomial algorithm in Theorem 4.","marker":"[KS96]"},{"why":"It classifies min-CSP constraints and is the source of the claimed NP-hardness for non-group-dichotomous instances.","marker":"[KSTW01]"},{"why":"It shows grids have unbounded treewidth, supporting Observation 2's claim that bounded per-voter pathwidth does not force global bounded treewidth.","marker":"[RS86]"}],"fun_headline_variants":["CMS voting rule: brute-force hardness unless restricted","CMS rule: SETH-hard to beat brute force","Two restrictions make conditional minisum voting tractable","Group-dichotomous ballots make CMS polynomial-time","CMS hardness matches brute force under SETH and ETH"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dichotomy of Theorem 4 rests on an unstated transfer: the hardness half assumes that every hard min-CSP constraint that is not a two-term DNF can be encoded as a conditional-approval instance that is not group-dichotomous at $\\Delta=1$, but the paper asserts this in one sentence and gives no reduction.","fun_headline_variants_meta":{"raw":{"variants":["CMS voting rule: brute-force hardness unless restricted","CMS rule: SETH-hard to beat brute force","Two restrictions make conditional minisum voting tractable","Group-dichotomous ballots make CMS polynomial-time","CMS hardness matches brute force under SETH and ETH"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000617,"raw_usage":{"total_tokens":2853,"prompt_tokens":924,"completion_tokens":1929,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":1868}},"tokens_in":540,"tokens_out":1929,"duration_ms":13612,"temperature":1.0,"reasoning_tokens":1868,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:26:11.253042+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To test the dichotomy, write out the reduction promised in Theorem 4: if any non-group-dichotomous conditional-approval instance with $\\Delta=1$ maps to a min-CSP instance whose constraints are all two-term DNF formulas, the claimed NP-hardness is false; likewise, in Theorem 3, verify that every constraint-issue domain $D_{uv}$ contains only satisfying assignments of the corresponding 2-CSP constraint, since otherwise the reverse direction of the reduction breaks.","supporting_citations":[],"review_version":1}