| paper | d4-conf-sagt-2023-0023 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a project set \(C\), unit costs, budget \(B\), tie-breaking order, target \(p\), rational approval-set masses \(\mu_S\), and radius \(\rho\), is there a transfer \(x_{S,S'}\geq 0\) with total outflow from \(S\) at most \(\mu_S\), Hamming cost \(\sum_{S,S'}d_H(S,S')x_{S,S'}\leq\rho\), and resulting distribution \(\mu'\) under which MES-Apr funds \(p\)?
Types are approval sets \(S\subseteq C\) with mass \(\mu_S\). Transfers move mass between types at cost \(d_H(S,S')\). In the mass version of MES-Apr, each type starts with per-person balance \(B\); a unit-cost project \(c\) is affordable at price \(q\) when \(\sum_{S\ni c}\mu'_S\min\{b_S,q\}\geq 1\). The rule selects the affordable project with minimum \(q\), using the given tie-breaking order, and updates balances.
Lemma 2’s construction changes only \(O(n)\) approvals among \(T=14400n^7\) cloned voters, so its normalized manipulation mass vanishes and the theorem offers little evidence that the continuous radius problem is hard.
fatal: False
Covers the unit-cost MES-Apr decision bribery result in Theorem 7 as a mass-minimization question; it leaves the paper’s counting results, other rules, and random-noise experiments aside.
My strongest case is the MES-Apr clause of Theorem 7: MES-Apr-Flip-Bribery is NP-complete even when every project has unit cost. The paper proves this in Appendix B.1, Lemma 2, by adapting a reduction from RX3C; the proof even replaces each voter with \(T=14400n^7\) identical copies. So the anchor is proved here, and its construction already contains a large repeated-type population. I would mirror this result rather than the paper’s sampling experiments: the decision problem asks how much the ballots must change to make a target project win.
The natural regime is a large city PB vote over a fixed project menu. A voter’s type is their complete approval set \(S\subseteq C\); with unit project costs and MES-Apr’s common equal-share rule, that determines their treatment. Each person still submits a whole approval set. A mass \(\mu_S\) means that fraction of the participating population has ballot \(S\). This is plausible when many residents cast ballots but common approval patterns recur, so the number \(N\) of voters is much larger than the number \(\tau\) of distinct observed ballot types. The paper’s city-scale setting makes that a reasonable instance regime, though it does not establish how large \(\tau\) is in its data.
I would call the lead problem Continuous MES-Apr Funding Radius. An instance gives projects \(C\), a fixed tie-breaking order, unit project costs, an integer budget \(B\), a target project \(p\), a rational distribution \(\mu\) over approval sets, and a rational radius \(\rho\). A solution is a mass-transfer plan \(x_{S,S'}\geq 0\): it moves mass from original ballot \(S\) to final ballot \(S'\), with total outflow from \(S\) at most \(\mu_S\). The resulting distribution is \(\mu'\). Its cost is
\[ \sum_{S,S'\subseteq C} d_H(S,S')x_{S,S'}, \]
where \(d_H\) is the number of approvals changed. The question is whether some such plan costs at most \(\rho\) and makes \(p\) a MES-Apr winner under \(\mu'\).
Here is the continuous rule the question uses. Each unit of mass starts with virtual balance \(B\); at any stage, a unit-cost project \(c\) is affordable at price \(q\) when
\[ \sum_{S\ni c}\mu'_S\min\{b_S,q\}\geq 1, \]
where \(b_S\) is the current per-person balance for type \(S\). MES-Apr chooses an affordable project with the smallest such \(q\), resolving ties by the given order, and deducts \(\min\{b_S,q\}\) from each approving person’s balance. It stops when no project can be bought within the budget. This balance convention is scale-equivalent to the finite rule: if \(N\) voters each start with \(B/N\), set \(\mu_S=n_S/N\) and multiply balances and prices by \(N\). The integral affordability sum then becomes the displayed formula. For a finite electorate, the corresponding radius is \(\rho=r/N\). Fractional mass means that some fraction of otherwise identical people can have their ballots changed; nobody receives a fractional approval bundle.
My forecast is Class B: hardness transfers, because the reduction’s central combinatorics concern which project approvals and purchase sequence realize an exact cover, not the identity of individual voters. But Theorem 7 does not prove hardness for this mirror. Its proof relies on bounded, indivisible approval flips, and continuous mass can be split. A fractional manipulation might bypass the exact-cover gadget. Whether the gadget forces a successful transfer to behave integrally—or admits a fractional shortcut—is the key next question. The competing possibility is that fixing a sequence of MES purchases exposes an LP or another tractable continuous-optimization formulation.
This mirror covers one result emphatically: the MES-Apr decision version of Flip-Bribery, interpreted as a population mass radius. It does not claim to continuize the paper’s #P counting problem or its noise-sampling probabilities; those would continuize perturbations rather than make the population itself the continuous object. It also suggests two concrete follow-ups: classify the radius problem in \(m,\tau,L\), and determine how its optimum relates to the finite-electorate bribery radius as \(N\) grows.
The weakest point is the fractional relaxation. The type-mass model is a faithful way to let a large population vary by fractions while every person keeps an integral ballot, and it preserves MES-Apr’s aggregate affordability rule. But preserving the rule does not preserve the reduction’s discrete combinatorics. Until that gap is closed, Class B is a reasoned expectation, not a hardness claim.
The strongest anchor is Theorem 7’s NP-completeness result for MES-Apr-Flip-Bribery with unit-cost projects. The best case against its continuous mirror is a scale mismatch in the proof: Lemma 2 creates \(T=14400n^7\) identical copies of each voter but allows only \(O(n)\) approval flips. If there are \(N_0\) voters before cloning, the successful edits therefore affect at most an \(O(1/(n^6N_0))\) fraction of the cloned population. The reduction establishes hardness for changing a tiny number of ballots inside a huge replicated electorate; it does not establish hardness for changing a consequential share of society.
That weakens the connection between this theorem and a population-mass robustness question. The paper asks about discrete edits and, for its counting results, probabilities over discrete modified instances. A continuous radius asks for the minimum mass whose approval sets must change. Those are related, but the theorem’s construction seems to exploit precisely the gap between an individual flip and a population fraction. Its replicated voters make the construction high-multiplicity in one sense, while its successful manipulation remains atom-sized.
The stronger proposed mirror nevertheless survives that objection. For a large city with a fixed project menu and many residents sharing approval patterns, approval sets are complete MES-Apr types, and the minimum mass transfer needed to fund a target is a sensible question. MES-Apr’s aggregate balance rule admits a natural mass version, and the paper does not already answer its computational complexity. The fact that the reduction’s normalized radius vanishes does not make the radius problem trivial on other instances.
So I cannot honestly defeat every version of this anchor. The paper gives no evidence that its real-world instances have moderate support size \(\tau\), which makes the proposed regime speculative; and its main experimental question concerns random noise, whose population-continuous analogue would be a separate modeling step. But those are reservations about motivation and fit, not fundamental obstructions. The negative case is weak: the best objection is that Theorem 7 is poor evidence for the usefulness or hardness of a population-mass mirror, not that such a mirror is unworthy of study.
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.