| paper | d4-conf-ijcai-2021-0409 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Both addition and deletion are polynomial-time solvable, with bit running time \((m+\tau+L)^{O(1)}\), using exact linear programs with \(\tau+1\) variables and \(m+2\tau+3\) inequalities. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(m\) binary issues, a current mass profile \(\mu_t\) over unconditional approval-ballot types, a target outcome \(p\), and quota \(q\), decide whether \(p\) can be made the unique Minisum optimum by adding available mass \(y_t\) with \(0\le y_t\le\nu_t\) and \(\sum_t y_t\le q\), or by deleting mass \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le q\). For the resulting profile \(\lambda=\mu+y\) or \(\lambda=\mu-x\), the requirement is that \(S_\lambda(p)<S_\lambda(s)\) for every \(s\ne p\), where \(S_\lambda(s)=\sum_t\lambda_t\delta_t(s)\).
Types are complete unconditional approval ballots over the issues; each type carries rational current mass \(\mu_t\) and, for additions, available mass \(\nu_t\). The decision variables are typewise added or deleted masses, constrained by the quota, and the resulting society minimizes weighted dissatisfaction \(S_\lambda(s)=\sum_t\lambda_t\delta_t(s)\); the target must be its unique minimizer.
The model lets the controller choose mass separately by complete ballot type; real eligibility controls may act only on public cohorts that do not align with ballot types.
fatal: False
The mirror covers Theorem 3's CAV-ALL and CDV-ALL questions for unconditional Minisum with binary issue domains; it leaves the other control variants and conditional CMS cases aside.
The strongest positive mirror is Fractional CMS-ALL Voter Control, anchored in Theorem 3. Theorem 3, a result of this paper, says that both CAV-ALL and CDV-ALL are NP-hard even for Unconditional Minisum with binary domains on every issue. CAV-ALL asks whether adding at most \(q\) unregistered voters can make a specified full outcome the unique optimum; CDV-ALL asks the same after deleting at most \(q\) registered voters.
For the mirror, a type \(t\) is a complete ballot: it records the voter’s approval statements and dependencies on every issue. Let \(\mu_t\) be the current mass of type \(t\), and let \(\nu_t\) be the available mass of that type for possible entrants. For addition, choose \(y_t\) with \(0\le y_t\le\nu_t\) and \(\sum_t y_t\le q\); for deletion, choose \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le q\). Given target outcome \(p\), ask whether the resulting mass profile \(\lambda=\mu+y\) or \(\lambda=\mu-x\) makes \(p\) the unique minimizer of
\[
S_\lambda(s)=\sum_t\lambda_t\delta_t(s),\qquad s\in D.
\]
A solution is the mass vector \(y\) or \(x\). Masses and quotas are binary rationals; the measure can be normalized to a probability distribution without changing its minimizers.
In the theorem’s unconditional, binary-domain case, this mirror appears tractable. The objective separates by issue, and \(p\) is the unique optimum exactly when it strictly beats the other value on every issue. Each such margin is linear in the chosen masses. Thus a linear program can maximize a common positive margin subject to the mass bounds and quota; a positive optimum certifies control. This is a genuine continuous-population question about adding or removing voters and enforcing the same all-issues outcome. It drops only one-person granularity. In a large membership organization or online community, for example, eligibility changes may act on shares of large cohorts with repeated approval patterns, where \(N\), the number of people, greatly exceeds \(\tau\), the number of ballot types. The paper’s NP-hardness may dissolve precisely because the mirror replaces subset choice with mass choice.
A second mirror is Mass-CMS Winner Determination, anchored by Corollary 2. That corollary, derived in this paper using known binary-CSP results, says that when each voter has maximum in-degree at most one, CMS is FPT parameterized by treewidth \(tw\) plus maximum domain size \(d\), and is W[1]-hard parameterized by \(tw\) alone and by \(d\) alone. The mass version takes the issue domains and a support list of \(\tau\) complete conditional-ballot types with rational masses \(\mu_t\); it asks for an outcome minimizing \(S_\mu(s)\), and a solution is an optimal outcome.
The hardness is credible in the continuous model: the CSP reduction’s combinatorics lie in the issues, their domains, and their dependency graph, not in voter identities. Give each discrete voter mass \(1/n\) and aggregate identical ballots; the minimizers and the relevant parameters are preserved. Replicating every voter any number of times leaves the same mass profile, so the hard instances can sit in a regime with many more people than types. I expect the W[1]-hardness to transfer. This gives a useful boundary question: with the population represented by masses, the problem is still FPT in \(tw+d\), but which part of the issue structure prevents fixed-parameter tractability when either parameter is left unbounded?
Theorem 1 provides the tractable side of that same winner-determination mirror. It states that if each voter has maximum in-degree at most one and the global dependency graph has constant treewidth, CMS is optimally solvable in polynomial time, even with arbitrary domain cardinalities. The theorem is proved in the paper by reducing to a bounded-treewidth binary CSP optimization problem and applying known algorithms; the paper also notes the weighted-voter generalization. For rational masses, identical ballots can be combined by summing their weights. The predicted result is therefore polynomial-time exact optimization in \(m\), \(\tau\), domain description size, and mass bit length when treewidth is fixed. Unlike the control mirror, this one is an algorithmic question about the existing winner-determination problem.
These mirrors cover voter control of a full outcome and CMS winner determination under the stated in-degree and treewidth regimes. They do not claim to continuize every control variant in the paper. The further questions are whether mass control remains tractable with conditional ballots, especially under bounded treewidth, and how the winner-determination boundary changes when the in-degree exceeds one.
My weakest point is the voter-control mirror: replacing a choice of named voters by divisible mass changes the feasible actions, and that change is exactly why the NP-hardness may disappear. The mirror is persuasive only in a regime where control can in fact be applied to cohorts or proportions; if the controller’s authority is inherently over a few individually named voters, it is a poor analogue. Still, it preserves the paper’s ballots, control direction, quota, target outcome, and unique-optimum requirement. For a high-multiplicity electorate, “remove this share of each ballot type” is a plausible version of the question the authors study.
The strongest case against is that the two winner-determination anchors add little new computational content. For a discrete profile, let \(n_t\) be the number of voters with complete ballot type \(t\). CMS minimizes \(\sum_t n_t\delta_t(s)\); normalizing to \(\mu_t=n_t/n\) multiplies every outcome’s score by the same positive constant, so the winners do not change. Aggregating identical ballots loses no information the objective uses. Theorem 1’s weighted-voter remark already covers this mass-weighted objective, and the CSP hardness behind Corollary 2 concerns the issue structure, not voter identities. A careful account of \(\tau\) and rational bit length could still be useful, but it is hard to present these as open continuous mirrors.
Theorem 3 is a different matter. Fractional control changes the feasible actions: selecting a subset of voters becomes choosing any mass up to the available amount of each type. That is new, and it can be challenged on modelling grounds. In a real eligibility change, the controller may act on age, residence, or another public criterion, rather than choose a fraction of every exact conditional-ballot type. Including those criteria in the complete type can fragment the population; leaving them out can make the model assume control over preferences the controller cannot observe. The paper itself mentions eligibility changes, though, and a large organization or platform could plausibly admit or remove shares of well-defined cohorts. This concern makes the scenario conditional, not impossible.
A stronger version of the control mirror makes the negative case weaker still. For conditional ballots with bounded treewidth and bounded domain size, require the target outcome \(p\) to beat every other outcome by a common margin \(\eta>0\). The constraints \(S_\lambda(s)-S_\lambda(p)\ge\eta\) are linear in the added or deleted masses. If weighted winner determination can separate those constraints, the resulting mass-control question is a well-posed continuous optimization problem. I see no fundamental reason to rule out that regime, though its practical appeal depends on whether cohort-level control is credible.
So the negative case can argue that the winner-determination mirrors are largely already covered by the paper’s weighted extension, and that the new control mirror relies on a stronger, scenario-dependent action model. It cannot honestly defeat every anchor: fractional voter control over large, repeated cohorts remains a plausible continuous question. The requested universal claim is therefore weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.