| paper | d4-conf-ecai-2025-0692 |
| 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{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given projects \(P\), rational per-capita costs \(c_j>0\), a public budget \(L\), and a binary-encoded rational distribution \(\mu\) over complete voter types \(t=(s_t,d_t,u_t)\), with weight \(w_t=s_t-d_t\), compute the DA-Pareto outcome and a feasible funding witness. First choose \(B^*\in\arg\max\{S_\mu(B):\sum_{j\in B}c_j\le L\}\), where \(S_\mu(B)=\sum_t\mu_t w_t\sum_{j\in B}u_t(p_j)\). Then choose a support-maximizing bundle among \(B^*\) and bundles \(B\) that weakly improve every positive-mass type’s utility over \(B^*\), strictly improve at least one type, and can be funded within \(L\) plus donations from strictly benefiting types. Aggregate donations \(x_{t,j}\) must satisfy \(x_{t,j}=0\) when \(u_t(p_j)=0\), \(\sum_{j\in B}x_{t,j}\le\mu_t d_t\), and \(\sum_{j\in B}x_{t,j}>0\) only for types strictly benefiting over \(B^*\); public funding and donations together must cover each selected project’s cost. Return the selected bundle and its funding witness.
A continuous population with mass \(\mu_t\) on each complete type \(t=(s_t,d_t,u_t)\); project bundles remain indivisible, while support, public resources, and type donation capacities are measured per capita. The decision is DA-Pareto’s support-maximizing eligible bundle, including its public-budget baseline \(B^*\) and a feasible funding witness.
The case does not establish how often real DAO or public-budgeting rounds have repeated complete types, including identical real-valued ballots and donation caps.
fatal: False
The mirror covers DA-Pareto’s baseline optimization and full outcome computation, including the donation-dependent eligible bundles. Theorem 5’s DA-Greedy polynomial-time result is a comparison; the paper’s axiomatic and strategic results are not mirrored here.
A credible continuous mirror exists for computing the paper’s DA-Pareto outcome. Its population model is natural for a large DAO or public budgeting round with \(N\gg\tau\): many participants share a complete type—same stake, donation cap, and cumulative ballot—so the society is described by masses \(\mu_t\) on \(\tau\) types. Repeated stake tiers and ballot patterns make that plausible in some settings, though it is not a claim about every election.
For type \(t\), let \(u_t\) be its ballot, \(s_t\) its stake, \(d_t\) its donation cap, and \(w_t=s_t-d_t\) its voting weight. The support for bundle \(B\subseteq P\) is
\[
S_\mu(B)=\sum_t\mu_t w_t\sum_{j\in B}u_t(p_j),
\]
while each member of type \(t\) gets utility \(\sum_{j\in B}u_t(p_j)\). Costs, public budget, and aggregate donations are expressed per capita: type \(t\) can contribute at most \(\mu_t d_t\). This is the permitted co-scaling of money with population size. Projects remain indivisible; everyone receives the same integral bundle \(B\).
My anchor is Theorem 5, a result of this paper, not an imported citation; the displayed text states it but does not show its proof. It says that computing DA-Pareto’s public-budget-only support-maximizing bundle \(B^*\) is NP-hard even for PB scenarios; DA-Pareto’s subsequent loop enumerates exponentially many bundles; and DA-Greedy runs in polynomial time. I rely chiefly on the first claim. The latter two show both the algorithmic cost of the Pareto rule and a contrasting rule in the same paper.
Lead question — Continuous DA-Pareto Winner. Given projects \(P\), rational per-capita costs \(c_j>0\), public budget \(L\), and a binary-encoded rational distribution \((\mu_t)\) over complete types \((s_t,d_t,u_t)\), compute DA-Pareto’s output, including its baseline \(B^*\), winning bundle, and a feasible funding witness. Specifically, first find
\[
B^*\in\arg\max_{B\subseteq P:\,\sum_{j\in B}c_j\le L} S_\mu(B).
\]
Then consider \(B^*\) and bundles \(B\) that weakly improve every positive-mass type’s utility over \(B^*\), strictly improve at least one type, and can be funded by the public budget plus contributions from strictly benefiting types. Contributions must go only to projects the contributing type supports, and type \(t\)’s total contribution cannot exceed \(\mu_t d_t\). Return a support-maximizing eligible bundle and its funding witness; fix a lexicographic tie-break if a single-valued output is needed.
I expect this exact problem to be Class B: discrete hardness transfers. The baseline is knapsack over project choices, so the combinatorics lie in \(m\), the project agenda, rather than in population multiplicity. In particular, the paper’s knapsack baseline can be represented with one voter type and zero donation cap by encoding item values in that type’s rational cumulative ballot. Repeating that type to represent a large population leaves the maximizing bundle unchanged. Thus replacing the voter list by mass does not erase the anchored hardness. It also does not rely on making project outcomes divisible.
The scope is narrow: this mirrors Theorem 5’s DA-Pareto computation, not every result in the paper or its strategic analysis. Natural follow-ups are whether the donation-dependent enumeration admits useful parameterized or approximate algorithms in \(m,\tau\), and whether an approximation can preserve the rule’s axioms. The paper’s polynomial DA-Greedy result also motivates asking whether its running time can be expressed directly in the compressed input size \((m,\tau)\).
The weakest point is that the paper’s practical motivation does not establish that exact complete types are few: ballots, stakes, and donation caps can all vary, making \(\tau\) approach \(N\). This is a sound mirror for clustered populations and a useful hardness boundary, but it is not by itself evidence that continuization makes this particular rule tractable.
The strongest objection is that the proposed compression may not describe the motivating populations. A complete type here includes a voter’s exact stake, donation cap, and cumulative ballot. Stakes and donation caps can vary from person to person, while cumulative ballots are real-valued, so a large DAO may have \(\tau\) close to its voter count. Grouping nearly identical voters would change the model: small changes can affect whether a project is affordable or whether a bundle strictly benefits a type. In that regime, the distribution is not a useful compressed description.
That objection does not defeat the best mirror, though. A DAO or public budgeting process with repeated stake tiers, common donation caps, and standardized ballots gives many voters the same complete type. More decisively, the paper’s knapsack baseline can be encoded with one type, so its hardness survives at \(\tau=1\). That is a genuine continuous-population instance, not a limit that loses the relevant object. The hardness lies in project selection, but that is not a reason to dismiss the question: it makes the mirror a meaningful boundary case.
DA-Greedy offers less of a distinct result, since its support calculations already aggregate voters and the continuous implementation looks like a straightforward compressed-input version of the finite algorithm. But that does not undo the DA-Pareto anchor. I can make a serious case that the mirror’s relevance depends on whether exact complete types recur in practice; I cannot honestly make the universal case that no worthwhile scenario exists.
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.