| paper | d4-conf-aldt-2021-0022 |
| 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}\)-complete, even for \(\tau=1\) with universal approval and positive integer costs and budgets. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 9
Given projects \(C\), rational per-unit costs \(q_c\), and supported types \(\theta\) with rational masses \(\mu_\theta\), approval sets \(A_\theta\), and budgets \(b_\theta\), find a funded set \(S\subseteq C\) and contributions \(z_{\theta c}\geq 0\) maximizing \(\sum_\theta \mu_\theta\sum_{c\in S\cap A_\theta}q_c\), subject to \(z_{\theta c}=0\) for \(c\notin A_\theta\), \(\sum_c z_{\theta c}\leq b_\theta\), and \(\sum_\theta\mu_\theta z_{\theta c}=q_c\) for \(c\in S\) and \(0\) otherwise.
A distribution over complete donor types, with per-type contributions as decision variables, all-or-nothing project funding, costs and budgets measured per unit of cohort mass, and mass-weighted utilitarian welfare as the objective.
The mirror covers Proposition 9’s UTIL-hardness branch. It leaves the other welfare objectives, axiomatic results, strategyproofness claims, and experiments outside its scope.
A credible mirror is Mass-UTIL PFC for a recurring charitable campaign with a large, fairly standardized donor cohort. For example, many alumni may face the same slate of projects and pledge cap. Let each type \(\theta\) specify an approval set \(A_\theta\) and per-person budget \(b_\theta\); the society is a rational mass distribution \(\mu\) over those types, with support size \(\tau\). Project costs \(q_c\) are measured per unit of cohort mass, so actual targets grow with the cohort. This makes a small number of approval and budget classes plausible even when the donor count is large.
Here is the problem I would hand to a prover. An instance gives projects \(C\), rational costs \(q_c\), supported types \(\theta\) with rational masses \(\mu_\theta\), approval sets \(A_\theta\), and budgets \(b_\theta\). Find a funded set \(S\subseteq C\) and per-person contributions \(z_{\theta c}\geq 0\) such that contributions go only to approved projects, \(\sum_c z_{\theta c}\leq b_\theta\) for each type, and each funded project is fully paid for: \(\sum_\theta \mu_\theta z_{\theta c}=q_c\) if \(c\in S\), and zero otherwise. Among such outcomes, maximize \(\sum_\theta \mu_\theta\sum_{c\in S\cap A_\theta}q_c\). Call this Mass-UTIL PFC. The solution is the funded set and a feasible contribution schedule attaining maximum utilitarian welfare.
My lead anchor is Proposition 9, proved in this paper by appeal to Proposition 1’s Subset Sum reduction. It says that even with one agent, computing an outcome for UTIL, UTIL-MR, UTIL-IMP, EGAL, EGAL-MR, EGAL-IMP, NASH, NASH-MR, or NASH-IMP is NP-hard. The supplied transcription repeats UTIL-MR in the third slot; the published chapter lists UTIL-IMP there. I rely on the unambiguous UTIL result. [The paper](https://www.cse.unsw.edu.au/~haziz/PFC.pdf)
The reduction survives in Mass-UTIL PFC with just one supported type: mass \(1\), approval set \(C\), budget \(W\), and project costs equal to Subset Sum weights \(a_1,\ldots,a_m\). A set is fundable exactly when \(\sum_{j\in S}a_j\leq W\), and its welfare is \(\sum_{j\in S}a_j\). Thus a UTIL solution reaches welfare \(W\) exactly when the Subset Sum instance has a subset of weight \(W\). Fractional contributions among donors do not remove this obstruction because projects remain all-or-nothing. This is the continuous version of the paper’s project-selection question, not a relaxation of the project outcomes.
I expect hardness to transfer. The reduction’s combinatorics lie in choosing projects, not in the number of agents. The mass model preserves the same choice: a finite instance can be represented by type masses, with costs and budgets expressed per unit of cohort mass. The mirror therefore identifies a boundary where a continuous population does not make the underlying computation easier.
The authors should recognize the question: it retains PFC’s approvals, budget caps, provision-point costs, contributions, funded project set, and utilitarian objective. It changes the society from named agents to masses of agents with the same full type. This covers Proposition 9’s UTIL branch, not the paper’s axiomatic results, incentive claims, or experiments. The related continuous donor model discussed in the paper allows projects to be funded to arbitrary degrees; Mass-UTIL PFC preserves PFC’s indivisible projects, so that outcome-space continuity is not a collision.
The weakest point is that the clearest witness is maximally homogeneous: one type and one aggregate budget. It shows a valid high-multiplicity regime and a meaningful hardness boundary, but it offers no tractability gain. The broader follow-up is whether richer supported populations change the picture: for example, does Mass-UTIL PFC admit useful algorithms when \(m\) or \(\tau\) is bounded, and can the other welfare objectives be defined and analyzed cleanly over a continuum?
The strongest case against this mirror is that Proposition 9’s hardness comes entirely from project selection, with no role for a population at all. Its one-agent Subset Sum reduction becomes ordinary knapsack in Mass-UTIL PFC: use one supported type that approves every project, with budget \(W\) and project costs \(a_1,\ldots,a_m\). A feasible funded set has total cost at most \(W\), and its welfare is that total cost. Thus the optimum reaches \(W\) exactly when the Subset Sum instance has a solution. Adding more identical donors and scaling both their budgets and project costs by the cohort size preserves the same choice.
That makes the result a weak test of what continuization adds: the source theorem is already hard with one agent, and the mirror needs neither multiple types nor a population-dependent algorithm. Most of the paper’s other contributions are axiomatic or experimental, so they do not supply a computational result that could make a stronger population-complexity case.
But this is a reservation about the mirror’s payoff, not a sound reason to reject it under ChoCo’s criteria. A recurring donor cohort with common approvals and budget caps is plausible; PFC does not depend on donor identity once those features are fixed. Fixed project targets may make the large-population limit uninteresting, but scaling targets with the cohort is a recognizable model choice, and the programme explicitly allows that kind of co-modification. The resulting question preserves PFC’s indivisible projects and contribution constraints.
So I cannot honestly defeat the anchor. Its mirror is well-posed and the Subset Sum reduction survives; the fact that the answer may simply confirm hardness from project selection is not, by itself, a disqualifier. The negative case is weak: this looks like a valid, narrow boundary result, though not a compelling demonstration of new population-driven complexity.
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.