| paper | d4-conf-sagt-2023-0006 |
| 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: Assuming \(\mathrm{P}\ne\mathrm{NP}\), no polynomial-time \(f(m,\tau)\)-approximation exists for any finite, polynomial-time computable factor \(f\), even when \(\tau=2\) and \(\mu_1=\mu_2=1/2\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(m\) projects with per-member costs \(c_j\), and \(\tau\) supported types with binary-rational masses \(\mu_t\), budgets \(b_t\), and additive values \(v_{tj}\), find a set \(W\subseteq M\) maximizing \(\sum_{t}\mu_t\sum_{j\in W}v_{tj}-\sum_{j\in W}c_j\), subject to \(\sum_{j\in W}c_j\leq\sum_t\mu_t\min\!\left(b_t,\sum_{j\in W}v_{tj}\right)\).
The society is a distribution \(\mu\) over complete budget-and-valuation profiles. Project choices remain integral; each type contributes a per-member amount \(q_t\) satisfying \(0\leq q_t\leq\min\!\left(b_t,\sum_{j\in W}v_{tj}\right)\), with \(\sum_t\mu_t q_t=\sum_{j\in W}c_j\).
After type contributions are eliminated, the masses enter only through weighted coefficients, so the mirror may offer little new continuous-optimization structure.
fatal: False
The mirror covers the additive UWO-WP hardness results in Theorems 2 and 3. It leaves aside the paper’s UWO results, its FPTAS for laminar single-minded valuations, its exact algorithm for symmetric valuations, its experiments, and its axiomatic discussion.
The strongest mirror is the paper’s UWO-WP problem: choose funded projects to maximize social welfare while ensuring that every participant can contribute within their budget and still receive nonnegative utility. The paper is not already continuous in ChoCo’s sense: it allows monetary payments, but represents participants as a finite list. The mirror changes the population representation while keeping the funded project set integral.
A plausible regime is a large membership federation choosing recurring, capacity-linked shared services. Members have per-person contribution limits and valuations for proposed services; many share the same complete profile—budget and values for every project. Let \(T\) be the supported types, with rational masses \(\mu_t>0\) summing to \(1\), and let \(\tau=|T|\). Type \(t\) has budget \(b_t\) and additive valuation \(v_t(W)=\sum_{j\in W}v_{tj}\). Let \(c_j\) be project \(j\)’s cost per member, so total costs scale with the population. For a funded set \(W\), a solution gives each type a per-person contribution \(q_t\), with \(0\le q_t\le\min\{b_t,v_t(W)\}\) and \(\sum_t\mu_tq_t=c(W)=\sum_{j\in W}c_j\). It maximizes per-person welfare \(\sum_t\mu_tv_t(W)-c(W)\). Equivalently, \(W\) is feasible exactly when \(c(W)\le\sum_t\mu_t\min\{b_t,v_t(W)\}\). The input is the project data and the \(\tau\) type profiles and masses, encoded as binary rationals; the natural running-time parameters are \(m,\tau\), and input bit length \(L\).
My lead is Cont-UWO-WP-2Type, this problem restricted to two supported types. Theorem 2, proved in the paper in §4.2 using its own Appendix A Lemma 2, says that for every polynomial-time-computable \(f(m)\), even with exactly two agents and additive valuations, no polynomial-time \(f(m)\)-approximation for UWO-WP exists unless \(P=NP\). The continuous version contains those instances exactly: give the two types mass \(1/2\), retain each agent’s budget and valuation, and set \(c_j=C_j/2\), where \(C_j\) was the discrete project cost. Feasibility and welfare are then precisely half their discrete counterparts, so feasible choices, optima, and approximation ratios are preserved. Replicating each type into a large cohort scales total costs with population size but changes none of this. Thus the result predicts hardness transfers (Class B): the difficult choices are over subsets of projects, not over the number of people. The two-type regime is especially persuasive for the mirror because it shows that large population size does not itself remove the hardness.
A second, distinct anchor is Cont-UWO-WP-Equal-Cost, with arbitrary finite support and identical per-person project costs. Theorem 3, proved here in §4.3 via the paper’s Appendix B Lemma 3, is intended to say that for every polynomial-time-computable \(f(n,m)\), UWO-WP with identical project costs has no polynomial-time \(f(n,m)\)-approximation unless \(P=NP\). The printed theorem says “Unless \(P\ne NP\),” which conflicts with Table 1 and the surrounding text; I read it as a typo for the standard \(P\ne NP\) assumption. The reduction from X3C gives a direct population interpretation: make each of the \(n\) discrete agents an equally weighted type, set \(\mu_i=1/n\), retain its budget and valuation vector, and set every continuous project cost to \(1/n\) when the discrete cost is \(1\). Feasibility and welfare are scaled by \(1/n\), preserving the hardness and approximation ratios. Replicating each type \(r\) times gives \(N=rn\) people but still only \(\tau=n\) profiles; each total project cost becomes \(r\), equal across projects. This also predicts Class B, with the reduction’s set-selection and incidence combinatorics intact. A natural follow-up is whether equal-cost hardness persists at fixed small \(\tau\), or whether bounded support enables a tractable approximation regime.
These are faithful mirrors because the decision remains the paper’s: which projects to fund, how much each profile contributes, and whether welfare can be maximized subject to weak participation. Money remains divisible, but projects are not fractional; the continuous object is the society. The paper’s resource-pooling model already supplies the budgets, shared projects, quasi-linear utilities, and participation condition that make the translation recognizable.
The weakest point is the scenario’s cost scaling. For a one-off civic project with fixed total cost, per-person cost vanishes as the population grows, which can make participation constraints uninformative. The case therefore rests on recurring or capacity-proportional services, and on a federation where many members really do share complete budget-and-valuation profiles. That is a substantive regime restriction, but a plausible one. The scope here is only the additive UWO-WP hardness results in Theorems 2 and 3; it does not claim to mirror the paper’s other valuation domains or all of its algorithmic results.
The strongest case against a worthwhile mirror is that UWO-WP has no population-level decision to continuize. For additive valuations, the continuous version reduces to
\[ \max_{W\subseteq M}\ \sum_{j\in W}\left(\sum_t \mu_t v_{tj}-c_j\right) \quad\text{subject to}\quad \sum_{j\in W}c_j\le \sum_t\mu_t\min\!\left(b_t,\sum_{j\in W}v_{tj}\right), \]
with \(W\) still an integral project set. Once \(W\) is chosen, contributions can be assigned within the per-type caps whenever that inequality holds. The population appears only through weighted coefficients; there is no mass allocation to optimize, and the continuous contribution variables can be eliminated. That makes it hard to see this as a case that brings continuous optimization machinery to bear.
For Theorem 2, the two-type mirror is mathematically exact: the half-mass types and halved project costs preserve feasibility and welfare up to scale. But the original hardness instance already has two agents. The mirror therefore gives a continuous demographic interpretation of the same two-profile project-selection problem, without a large-population or population-compression phenomenon. That weakens its value as evidence for a continuization programme, even though it is a valid question and hardness transferring is not itself a reason to reject it.
For Theorem 3, the X3C construction uses \(n\) agents with incidence-dependent valuations, and the proposed encoding uses \(n\) supported types. Replicating those types creates a large population but leaves \(\tau=n\); it does not compress the reduction’s population description. The continuous instance still carries the full incidence structure that drives the project-selection problem. The theorem’s printed “Unless \(P\ne NP\)” is evidently inconsistent with the surrounding text and reduction, but correcting that typo does not change this point.
A stronger version of the mirror is still easy to imagine: a large federation choosing recurring, capacity-linked services, with many members sharing each budget and valuation profile. That is a plausible setting, and scaling costs with membership avoids the one-off-project problem where per-person costs vanish. It also directly answers the objection that budgets and valuations must be identical within a type: those are precisely the complete profiles the high-multiplicity model groups. I cannot honestly rule out that scenario.
So the negative case is limited. These anchors do not reveal a new continuous decision structure; they recast an integral project-selection problem with population data compressed into type weights. But the programme explicitly values high-multiplicity formulations and permits co-scaling costs, so that observation does not defeat the mirrors. The two-type mirror in particular survives the stated standard. A universal claim that no scenario is worthwhile would be stronger than the paper supports.
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.