| paper | d4-conf-aaai-2026-3878 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
Given a finite project set \(P\), budget \(b\), project costs \(c(p)\), DNS satisfaction values \(s(p)\), and a finite-support rational distribution \(\lambda\) over approval types \(A\subseteq P\), with \(\sum_A\lambda_A=1\), define welfare by \(W(S)=\sum_{p\in S}s(p)\sum_{A\ni p}\lambda_A\). Each type starts with per-person wallet \(r_A=b\). For project \(p\), its MES price \(\rho\) satisfies \(\sum_{A\ni p}\lambda_A\min(r_A,\rho s(p))=c(p)\); select an affordable project with minimum price and update the approving types’ wallets by their per-person contributions. Complete MES by greedily selecting remaining projects in decreasing order of weighted welfare per cost. Relative to the maximum-welfare feasible integral project set, does this rule always attain ratio at least \(2\sqrt{c_{\min}/b}-(c_{\min}+c_{\max})/b\), and is that guarantee asymptotically tight over continuous societies?
A society is a finite-support distribution over approval-ballot types, each carrying mass \(\lambda_A\). Projects remain indivisible; MES tracks each type’s per-person wallet, charges mass-weighted contributions, and is completed by Greedy. The objective is utilitarian welfare over selected projects, compared with the best feasible integral bundle.
For rational masses, the model often reduces to grouping identical finite voters, so it may add no population-specific computational structure; the proponent acknowledges this limitation.
fatal: False
The mirror covers the DNS utilitarian guarantee for Greedy-completed MES and can ask whether the proportional-rule tightness construction persists for mass cohorts. It leaves the other welfare comparisons, negative parameterization results, and the guarantee for Greedy using a different satisfaction function aside.
The strongest honest positive case is a natural continuous-population version of the paper’s welfare-guarantee analysis. But there is an important limit: it has no named complexity-classification result. Its numbered results give algorithmic performance guarantees, not claims that a problem is in P, NP-hard, FPT, or similar. So they are useful anchors only if the anchor rule includes approximation guarantees; they do not meet the stricter complexity-anchor requirement as written.
The best performance anchor is Theorem 2, proved here: for every DNS satisfaction function, Greedy-completed MES has utilitarian guarantee
\[
2\sqrt{\frac{c_{\min}}{b}}-\frac{c_{\min}+c_{\max}}{b}.
\]
A second, narrower anchor is Proposition 5, also proved here: for cost satisfaction, for every \(k_1,k_2\in\mathbb{N}\) with \(k_2\ge k_1\), there is an instance with \(c_{\min}=b/k_2\) and \(c_{\max}=b/k_1\) on which any EJR1 rule has ratio at most
\[
\frac{2}{\lfloor\sqrt{b/c_{\min}}\rfloor}-\frac{c_{\min}+x c_{\max}}{b},
\quad
x=\left\lfloor\sqrt{k_2}\frac{c_{\min}}{c_{\max}}\right\rfloor_{\rm frac},
\]
where \(x\) is the fractional part of \(\sqrt{k_2}c_{\min}/c_{\max}\). Along the paper’s stated parameter sequences, this approaches the MES guarantee. Neither result classifies a computational problem’s complexity.
If approximation guarantees count as anchors, the lead mirror is Continuous-Population MES Guarantee. Let the types be approval sets \(A\subseteq P\), with mass \(\lambda_A\) and \(\sum_A\lambda_A=1\). Keep projects indivisible, with costs \(c(p)\), total budget \(b\), and DNS satisfaction \(s(p)\). Each type starts with per-unit wallet \(r_A=b\). For a project \(p\), its MES price \(\rho\) solves
\[
\sum_{A\ni p}\lambda_A\min(r_A,\rho s(p))=c(p).
\]
MES selects the affordable project with lowest price and updates each approving type’s wallet by its per-unit contribution. Greedy completion then orders remaining projects by welfare-to-cost ratio. Welfare of a selected set \(S\) is
\[
W(S)=\sum_{p\in S}s(p)\sum_{A\ni p}\lambda_A,
\]
and the benchmark is the maximum welfare over feasible integral project sets. The question is: what is the largest guarantee \(g\), as a function of \(b,c_{\min},c_{\max}\), that holds for every finite-support society, and is it sharp? The expected answer is the Theorem 2 bound; Proposition 5 suggests the corresponding proportionality barrier for cost satisfaction. If this must be placed in the programme’s trichotomy, I expect the guarantee proof to transfer tractably, but that is not a complexity classification.
A plausible regime is a large municipal PB process where many residents share a small number \(\tau\) of approval ballots, with \(n\gg\tau\). Types are complete approval ballots; mass is the population share holding each ballot. The authors should recognize the model: it preserves their projects, MES payments, proportionality condition, and utilitarian objective. Rational type masses reproduce finite profiles after cloning; arbitrary masses extend that aggregate model.
The weak point is decisive under the strict anchor rule: the paper’s results concern welfare quality, and the mass formulation largely aggregates identical voters. They do not expose a new computational bottleneck or show that population multiplicity changes the complexity landscape. So this is a credible performance-guarantee mirror, but not a qualifying positive case for the programme’s complexity anchors.
The strongest objection is at the programme’s entry point: Theorem 2 and Proposition 5 are welfare-guarantee results, not computational results. Theorem 2 bounds MES’s utilitarian ratio; Proposition 5 gives a family of instances showing that proportional rules cannot do much better. Neither classifies a computational problem nor supplies an algorithm for one. In the programme’s terms, these are distortion and performance analyses.
The population mirror itself is coherent. In a municipal PB process, many residents can share an approval ballot. Give each approval type \(A\) mass \(\lambda_A\), and track its per-person remaining budget \(r_A\). The MES price equation becomes
\[
\sum_{A\ni p}\lambda_A\min(r_A,\rho s(p))=c(p),
\]
with \(r_A=b\) initially. This is a sensible model, and I would not object that PB lacks a high-multiplicity regime. But for rational masses \(\lambda_A=n_A/n\), this is just the finite rule with identical voters grouped and budgets rescaled. MES still processes finitely many projects; its type-level sums introduce no new computational task.
Both anchors then transfer as welfare statements. Theorem 2’s bound is expressed in project costs and budget, not population size, and its voter sums can be written as weighted sums over types. Proposition 5’s small voter groups become positive-mass cohorts in the continuous model; the witness does not require targeting a measure-zero individual. Those transfers may be worth recording in PB theory, but they do not create the complexity landscape ChoCo is set up to chart.
A stronger proposal would seek the sharp guarantee as a function of support size \(\tau\), or compute a worst-case society distribution for given project costs. That is a coherent continuous optimization question, but it is a new adversarial instance-design problem, not a mirror of either named result. Computing the benchmark welfare for a fixed society would instead retain the project-selection knapsack problem, with masses supplying its coefficients; the paper’s guarantee theorems do not study that computational task.
So the negative case is strongest on relevance, not on whether a continuous PB model makes sense. The proposed mirror is easy to state and plausible, but its anchors yield inherited welfare inequalities rather than a computational question. If the programme counts sharp welfare guarantees as qualifying computational anchors, this objection weakens substantially; the paper alone does not support the broader claim that no worthwhile continuous mirror could exist.
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.