| paper | d4-conf-atal-2021-0239 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact optimization and the decision problem are polynomial-time solvable; for \(m=1\), an exact algorithm uses \(O(\tau^2L^2)\) bit operations. Feasibility holds exactly when \(\kappa\le\max_i v_iS_i\). A threshold is optimal exactly when \(\kappa\le v_1\), or an index \(i\ge2\) satisfies \(a_i=\kappa\), \(a_j<a_i\) for every \(j<i\), and \(B_i\le U_i\), with the quantities defined above. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given an excludable project, finite valuation types \(0\le v_1<\dots<v_\tau\le1\), rational masses \(\mu_j\) summing to \(1\), and per-capita cost \(\kappa>0\), maximize served mass \(\sum_j\mu_jx_j\) over service fractions \(x_j\in[0,1]\) and average payments \(p_j\ge0\), subject to \(v_jx_j-p_j\ge v_jx_k-p_k\) for all \(j,k\), \(v_jx_j-p_j\ge0\), and \(\sum_j\mu_jp_j=\kappa\) (report infeasibility if necessary). Characterize when the threshold rule serving all types above \(t\), none below \(t\), and a fraction at \(v_j=t\) when needed, with served agents paying \(t\), attains the optimum.
A population of total mass \(1\) with \(\tau\) valuation types \(v_j\) and masses \(\mu_j\); choose the fraction \(x_j\) served and average payment \(p_j\) for each type, maximizing served mass subject to truthfulness, individual rationality, and per-capita budget balance \(\kappa\), corresponding to total project cost \(N\kappa\).
The proposed LP allows type-level probabilistic menus rather than the paper’s coalition-contingent largest-unanimous schemes, so Theorem 5 does not establish optimality in this broader class.
fatal: False
The mirror covers the excludable public-project objective of maximizing consumers and asks when serial cost sharing is optimal. It leaves aside social welfare, the nonexcludable model, the paper’s fixed-cost finite-agent setting, and its dynamic-programming and neural-network methods.
This paper has no numbered theorem classifying a problem as NP-hard, in P, or in another complexity class. Its numbered results are mechanism-optimality claims instead. The strongest one for a population mirror is Theorem 5, proved in the paper, though its characterization tool comes from Ohseto [12]: in the excludable model, with two agents, log-concavity of \(f\) makes serial cost sharing optimal for expected consumers, and log-concavity plus welfare-concavity makes it optimal for expected social welfare. With three agents, the consumer-count claim also requires \(f\) to be nonincreasing; the welfare claim requires all three conditions. I would use its consumer-count result as the anchor.
My proposed mirror is Continuum Excludable Public-Project Design. Its instance is a valuation distribution \(\mu\) with finite support \(V=\{v_1,\ldots,v_\tau\}\), where each \(v_j\in[0,1]\) and each rational mass \(\mu_j\) is the fraction of a large population with that valuation. Think of a crowdfunding pool with many people in a small number of benefit tiers: \(N\) is large while \(\tau\ll N\). Each person in a tier has the same valuation and faces the same terms. The project is binary and excludable.
To preserve a meaningful per-person cost as the population grows, let the project cost be \(N\kappa\), for rational \(\kappa>0\). This is a deliberate co-modification: the project’s cost scales with the potential population, not with the number who receive access. A mechanism offers each reported valuation \(v_j\) a service fraction \(x_j\in[0,1]\) and an average payment \(p_j\ge0\). A fraction of a type’s mass may be served, while every individual still receives either access or no access. The mechanism must satisfy
\[ v_jx_j-p_j\ge v_jx_k-p_k\quad\text{for every }j,k, \qquad v_jx_j-p_j\ge0, \qquad \sum_j\mu_jp_j=\kappa. \]
The first condition is truthfulness, the second individual rationality, and the third exact cost recovery per unit of population. The problem is to find a feasible mechanism maximizing served mass, \(\sum_j\mu_jx_j\), or decide whether that maximum reaches a specified threshold.
The continuum version of serial cost sharing is a common price \(t\): serve the mass with \(v\ge t\), charging each served person \(t\). In this model, \(t\) must satisfy \(t\,\mu([t,1])=\kappa\). The question is whether this rule remains optimal under suitable shape conditions on \(\mu\), or which truthful, individually rational cost schedule beats it.
I expect this precisely stated finite-support menu problem to be Class A: its constraints and objective are linear, so a rational-input LP solves it in time polynomial in \(\tau\) and the input bit length. That is a result about the proposed mirror, not a complexity theorem from the paper. Further questions include whether serial cost sharing is optimal for log-concave mass distributions, and whether optimal values converge from the paper’s finite-agent stochastic model to this mass model.
The mirror covers the paper’s excludable public-project problem and its objective of maximizing consumers. I think the authors would recognize the same design tradeoff—truthful access, voluntary payments, and project funding—but the connection is a proposed extension, not an identity established by Theorem 5.
The weak point is substantial: Theorem 5 concerns only two and three agents drawing values from a continuous prior, whereas the mirror has many agents grouped into repeated valuation types and scales project cost with population. The paper’s result motivates the question but does not establish that serial cost sharing, or its optimality conditions, survive this change.
Theorem 5 is a weak anchor for ChoCo’s computational brief. It gives sufficient conditions under which serial cost sharing is optimal for exactly two or three agents; it says nothing about complexity, running time, or an algorithmic guarantee. The paper’s computational methods are a discretized dynamic program and neural-network experiments, not a numbered complexity result. That does not make a mirror question illegitimate, but it means Theorem 5 itself does little to establish the kind of computational gap ChoCo is meant to chart.
The strongest repair is the proponent’s cohort model: many people share a small set of valuations, project cost scales with population, and the question is whether serial cost sharing remains optimal among truthful, individually rational mechanisms. That is a coherent mass model, and it avoids the limit becoming trivial. But it also changes the paper’s central economic assumption: its project has fixed cost \(1\), independent of population and consumption. Under that assumption, the per-person share vanishes as the population grows. For an excludable project with a continuous valuation distribution and no atom at zero, a coalition of nearly the whole population can fund the fixed cost while charging each member a vanishing amount. The optimal served fraction therefore tends to \(1\), leaving the paper’s consumer-count objective with a trivial limit. The interesting finite-\(N\) differences survive only as lower-order corrections that the mass model discards.
Scaling cost to \(N\kappa\) rescues a nontrivial problem, but it makes the model a growing-cost project rather than the fixed-cost project the paper studies. That co-modification can be sensible for some applications, so it is not a categorical scope violation. The proponent’s LP also asks a broader screening question: its allocation and payment menus are type-level, while the paper’s characterized mechanisms are cost-share schemes over coalitions with exact cost recovery. The LP may be a useful problem in its own right, but it does not show that Theorem 5’s small-agent result has a direct continuous counterpart.
So the case against is strongest for the faithful fixed-cost limit: the anchor is not computational, and the natural population limit erases the consumer-count tradeoff. It is weaker against every possible mirror. A growing-cost cohort version remains plausible, and the authors might recognize it as a related public-project problem. I can argue that it is an extension rather than a compelling continuation of this paper’s central results, but I cannot honestly rule out its value in every scenario.
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.