| paper | d4-conf-atal-2011-0140 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: for \(m=1\), output \(y_t=pq_t\log(N\sum_{s\in T}\mu_sq_s)\) in \(O(\tau L)\) bit operations, with total expression length \(O(\tau L)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a population scale \(N\), finite DER types \(T\), rational distribution \(\mu\), positive per-unit outputs \(q_t\), and price \(p>0\), with accurate estimates, compute type payments \(y_t\) that distribute \(pQ\log Q\) and give every submass \(\nu\), where \(0\leq\nu_t\leq N\mu_t\), at least its value \(pQ_\nu\log Q_\nu\). Here \(Q=N\sum_{t\in T}\mu_tq_t\), \(Q_\nu=\sum_{t\in T}\nu_tq_t\), and \(v(0)=0\).
Each type is a complete DER description, including its output and accurate production estimate; type \(t\) has mass \(N\mu_t\). The decision is the per-unit payment \(y_t\), with total payment \(\sum_t N\mu_t y_t\). The paper’s allocation is \(y_t=pq_t\log Q\), which distributes the grand-coalition value and leaves every submass at least its own value.
The mirror covers Theorem 1 under its accurate-estimate condition. It leaves aside the pricing incentives, prediction-error analysis, membership protocols, and empirical simulations.
The strongest credible mirror is narrow: continuum CVPP core allocation. The regime is plausible. A large deployment of standardized, controllable DERs—such as similar storage units following the same settlement schedule—could have hundreds of thousands of units but only a modest number of types. A type records everything relevant to the paper’s game, including per-unit production and the matching production estimate. Mass records how many units have that type. Accurate estimates are a substantive restriction, but it is exactly the condition in the paper’s stability result.
The closest named anchor is Theorem 1, proved in this paper. It says that for a cooperative \(C=\{1,\ldots,n\}\) with characteristic value \(v(S)=\mathrm{prod}_S\log(\mathrm{prod}_S)\cdot\mathrm{price}\), the allocation that pays each member according to Eq. 2, proportionally to its production when its estimate is accurate, lies in the core. In other words, the grand coalition’s value is fully distributed, and no subset of members can obtain more by leaving and forming its own cooperative.
A precise population version is: given a population scale \(N\), a finite set of DER types \(T\), a rational type distribution \(\mu\), positive per-unit outputs \(q_t\), and price \(p>0\), with accurate estimates, compute a core-stable payment per unit of each type. For a subpopulation \(\nu\) with \(0\leq\nu_t\leq N\mu_t\), define its output as \(Q_\nu=\sum_t\nu_tq_t\), its value as \(v(\nu)=pQ_\nu\log Q_\nu\), and the grand-coalition output as \(Q=N\sum_t\mu_tq_t\). The paper’s proportional allocation has payment density \(y_t=pq_t\log Q\). The requested solution is an allocation that distributes \(v(N\mu)\) and gives every subpopulation at least its own value. This one does: the allocated payment to \(\nu\) is \(pQ_\nu\log Q\), and \(Q_\nu\leq Q\). Define \(v(0)=0\).
I expect this problem to be tractable: the allocation is explicit, and the core condition follows from output monotonicity. It is a genuine population mirror because the possible blockers are subpopulations of a continuum society, rather than coalitions formed by counting named individuals. Natural follow-up questions include whether the guarantee survives uncertain production estimates and which other reward functions preserve it.
There is an important qualification: Theorem 1 is a stability theorem, not a named complexity result such as an NP-hardness or polynomial-time classification. The paper mentions general NP-hardness of core nonemptiness in passing, citing [5], but does not give it as a numbered result of its own. So if the required anchors must be numbered complexity results, this paper has no eligible anchor. Theorem 1 is the strongest nearby result to mirror, but the mirror’s main weakness is that it extends a structural guarantee into a continuum game; it does not fill the programme’s computational-complexity gap.
The negative case rests on the paper’s missing computational result. It has no numbered theorem classifying the complexity of a problem or giving an algorithm. Theorem 1 is a core-stability guarantee for a payment rule. The passing claims about truthful reporting and the membership-ranking procedure are mechanism properties and empirical findings, not complexity results. The cited NP-hardness of core nonemptiness concerns cooperative games generally; the paper does not reduce its CVPP problem to that problem or study its computational complexity.
The proposed DER scenario is plausible: a large fleet of standardized units could form a small number of complete types. Theorem 1 also has a natural mass version. For a subpopulation with output \(Q_\nu\le Q\), its proportional payment is \(pQ_\nu\log Q\), while its value is \(pQ_\nu\log Q_\nu\). That is a coherent continuous core claim.
But “compute a core-stable payment” supplies a new search framing, not a computational problem the paper investigates. The paper already gives the payment rule; its theorem establishes stability. The continuous version changes the quantified coalitions to submasses, while leaving the result as a structural guarantee. Asking for algorithms or complexity for a broader core-separation problem, uncertain forecasts, or alternative reward functions could open a worthwhile computational project. Those would be new problems beyond this anchor. The paper’s forecast and membership sections do not supply another anchor: their computations depend on agents’ histories and empirical data, and the paper makes no complexity claim about them.
So I would argue against counting this as a ChoCo computational mirror, while acknowledging that the continuous population model itself is sensible. The universal claim that no scenario could yield a worthwhile continuous mirror is harder to defend: the fleet scenario survives the multiplicity test, and the continuous core statement is well-posed. The honest weakness of the negative case is that its force comes from the programme’s computational scope, not from showing that the population continuization is incoherent.
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.