| paper | d4-conf-aaai-2021-1873 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) unit-cost projects, an integer budget \(b\), and districts \(i\in[k]\) with approval-type masses \(\mu_{i,A}\in\mathbb{Q}_{\ge 0}\) summing to \(1\), let \(\alpha_i=\sum_A\mu_{i,A}\), \(v_i(W)=\sum_A\mu_{i,A}|A\cap W|\), and \(f_i=\max_{Q\subseteq P,\ |Q|\le\lfloor\alpha_i b\rfloor}v_i(Q)\). Given a rational threshold \(q\), decide whether there is a funded set \(W\subseteq P\) with \(|W|\le b\), \(v_i(W)\ge f_i\) for every district, and \(\sum_i v_i(W)\ge q\).
The society is a distribution over resident types \((i,A)\), where \(i\) is a district and \(A\) is an approval set; each type carries mass \(\mu_{i,A}\). The decision variables are \(y_j\in\{0,1\}\) for funded projects, with budget, district-fairness, and welfare-threshold constraints as stated in the mirror question.
Clearing denominators reduces rational-mass inputs to integer district-project utility matrices, so the mass representation adds no independent computational structure; this limits novelty, but the proponent already acknowledges that the hardness comes from project-district incidence.
fatal: False
The mirror covers Theorem 1’s NP-completeness result for approval votes, proportional budgets, and unit-cost projects. It leaves the integrality-gap result and the lottery and DF1 algorithmic guarantees unmirrored.
My lead mirror is Continuous Approval District-Fair Welfare Decision, anchored only on Theorem 1, which the paper proves here by reduction from X3C. The theorem says that deciding whether there is a budget-feasible, district-fair outcome with social welfare at least a given threshold is NP-complete—even with approval votes, budgets proportional to district sizes, one voter per district, and unit-cost projects.
Consider a large city or regional fund choosing among \(m\) indivisible public projects. A resident’s type is \((i,A)\): their district \(i\) and the set \(A\) of projects they approve. Let \(\mu_{i,A}\) be the binary-rational fraction of the population with that type, with total mass \(1\) and support size \(\tau\). This is a plausible high-multiplicity regime when many residents in each of a growing number of districts share a ballot type: for \(k\) districts, one can have \(N=Rk\) residents but only \(\tau=k\) supported types, for arbitrarily large \(R\). District identity belongs in the type because it determines which fairness guarantee applies.
Let \(\alpha_i=\sum_A\mu_{i,A}\) be district \(i\)’s population share, and let the city have an integer budget \(b\) with unit-cost projects. For a funded set \(W\subseteq P\), define district welfare by \(\mathrm{val}_i(W)=\sum_A\mu_{i,A}|A\cap W|\), total welfare by \(\mathrm{SW}(W)=\sum_i\mathrm{val}_i(W)\), and the district’s separate-election benchmark by \(f_i=\max\{\mathrm{val}_i(Q):Q\subseteq P,\ |Q|\le\lfloor\alpha_i b\rfloor\}\). The decision problem takes these data and a rational threshold \(q\), and asks whether there is a set \(W\) with \(|W|\le b\), \(\mathrm{val}_i(W)\ge f_i\) for every district, and \(\mathrm{SW}(W)\ge q\). A solution is the funded set \(W\). This keeps the paper’s district guarantee and indivisible project choices intact; only residents’ approvals become masses.
The hardness transfer is direct. In the paper’s hard instances, let \(k\) be the number of one-voter districts, give each corresponding continuous type mass \(1/k\), and set \(b=k\). Each district then has mass \(1/k\), a proportional budget of one project, and the same approval set as its paper voter. Every district utility and the welfare threshold are scaled by \(1/k\), so the feasible funded sets and yes/no answer are unchanged. The mirror is NP-hard by this embedding; in this unit-cost formulation its district benchmarks are computable by selecting the top \(\lfloor\alpha_i b\rfloor\) project values, so the decision problem is in NP as well. I expect hardness to transfer (Class B): the X3C structure remains in the district-project approval pattern and the choice of a project set. Fractional population masses do not remove that combinatorics.
The authors would have a strong reason to recognize this as their problem: they explicitly interpret district welfare under approval voting as the number of district voters approving a project, and define fairness against what each district could obtain with its proportional budget. The mirror replaces those approval counts with approval mass while retaining that same benchmark. Its scope is specifically Theorem 1’s hardness result; it does not claim to mirror the lottery or DF1 approximation results.
The weakest point is that the continuous population does not change the central optimization much: the paper already works with aggregate district-project welfare values, and the hardness comes from project and district incidence, not from voter multiplicity. So this is a clear high-multiplicity formulation and a credible Class B case, but not a claim that continuization creates a new tractable method. Natural follow-up questions are whether the mass version has useful parameterized algorithms for fixed \(k\) or small \(\tau\), and how the paper’s approximation guarantees behave with binary-rational masses.
The only anchor is Theorem 1, and the strongest objection is that its proposed mirror seems to change the representation of the instance more than the computational problem.
For approval ballots, define \(a_{ij}=\sum_{A\ni x_j}\mu_{i,A}\), the mass in district \(i\) approving project \(x_j\). Every welfare value in the proposal is determined by these marginals:
\[
\mathrm{val}_i(W)=\sum_{x_j\in W}a_{ij}.
\]
The joint distribution over complete ballots contributes nothing else: fairness, the benchmark, and the objective all reduce to the same district-by-project utility matrix used in the paper. For rational masses, take a common denominator \(D\) and set \(n_{i,A}=D\mu_{i,A}\). Then \(D\,\mathrm{val}_i(W)\) and \(D f_i\) are integer approval counts and benchmarks; the feasible project sets are unchanged, and the welfare threshold becomes \(Dq\). The denominator has polynomial bit length in the input. With unit-cost projects, the benchmark remains the top \(\lfloor\alpha_i b\rfloor\) projects. So the stronger version—with large, mixed populations and many supported ballot types—still reduces to the paper’s integer utility formulation by scaling. Theorem 1’s one-voter-per-district hard instances also embed directly as masses \(1/k\).
That leaves no evident population-driven computation for the mirror to expose: the districts remain separately constrained fairness units, while voter multiplicities enter only as coefficients in their utility matrix. Increasing the support or making the ballot distribution richer does not change that. A genuinely different type-dependent objective or constraint might make mass distributions computationally operative, but it would add structure absent from this paper and weaken the claim that it mirrors Theorem 1.
This is a limited negative case. Replicating ballots gives a plausible high-multiplicity city, and Theorem 1 supplies a clear computational anchor. By the programme’s own standard, inherited hardness can still make a mirror worthwhile. I can argue that this particular mirror offers little beyond a denominator-scaling translation and an immediate Class B classification; I cannot honestly rule out that the explicit high-multiplicity dictionary is itself worth documenting.
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.