| paper | d4-journals-geb-2023-0047 |
| 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: An anonymous rule satisfying all three axioms exists but is not unique in general. Exact efficient core allocation is polynomial-time computable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given a rooted tree \(T\), rational edge costs \(c_e\), population scale \(M\), and a finite-support rational distribution \(\mu\) over customer types \(t=(v,b)\), with \(\sum_t\mu_t=1\), assume every branch has positive surplus. Determine the per-customer bills \(x_t\) that give an efficient allocation in the core against every coalition mass vector \(a_t\in[0,M\mu_t]\), and characterize the unique rule satisfying mass versions of SMP and NSD. A coalition's worth is the maximum of zero and its selected mass's total benefit minus the cost of the minimal subtree connecting the locations of types it selects, where selected masses \(q_t\) satisfy \(0\le q_t\le a_t\).
A fixed gas-distribution tree with costs \(c_e\) serves a population of total mass \(M\), distributed over types \(t=(v,b)\) with mass \(M\mu_t\). Each type receives a per-customer bill \(x_t\); node benefits are \(B_v=M\sum_{t:v(t)=v}\mu_t b_t\). Coalitions select submasses and incur the cost of the minimal subtree connecting their locations; efficiency, the core, mass-SMP, and NSD constrain the bills.
The mirror covers Proposition 4's tree-network allocation and its bill formula for each type; it leaves Proposition 3's convexity proof, the line-model characterization, and the Shapley-value discussion outside the mirror.
My strongest case is a narrow one: the paper has no named NP-hardness or formal complexity-class result, so it cannot anchor a question about whether discrete hardness disappears. It does have a named, explicit allocation result. Proposition 4, proved in the paper’s Appendix K, says that under the assumption that every branch has positive surplus, the tree-network allocation characterized by the core property, split- and merge-proofness (SMP), and no spatial discrimination (NSD) assigns each agent the bill in equation (23). In the paper’s notation, that bill is
\(\displaystyle x_i^{LP}(\Gamma)= \frac{b_i}{B_{l_i}+W_{l_i}} \left( c_{l_i}+ \sum_{j\in p_{l_i0}\setminus\{l_i,0\}} c_j \prod_{k\in p_{l_i j}\setminus\{j\}} \frac{W_k^+}{B_{\pi(k)}+W_{\pi(k)}} \right). \)
Here \(B_v\) is the community’s total benefit, \(W_v\) is the surplus downstream of \(v\), \(W_v^+=W_v+B_v-c_v\), and \(\pi(v)\) is the node preceding \(v\) toward the source. The result gives a closed-form bill for each user, with each edge’s cost shared according to users’ local benefits. The paper calls the rule computationally simple, but does not state a formal polynomial-time bound. A polynomial-time conclusion below is therefore an inference from the formula, not a claim made as a complexity theorem.
The lead mirror is Tree-LP-Allocation\(_\infty\). Its scenario is a large population of gas customers served by a fixed distribution tree. A type is \((v,b)\): a customer at network node \(v\) with willingness to pay \(b\). Customers of the same type are identical for this cost-sharing problem. Let \(\mu_{v,b}\) be the fraction of the population of type \((v,b)\), with \(\sum_{v,b}\mu_{v,b}=1\), and let \(M\) be the population scale. Then \(M\mu_{v,b}\) is the type’s mass, and the community benefit is \(B_v=M\sum_b\mu_{v,b}b\). A city with many customers but relatively few occupied network nodes and customer classes is a plausible regime: \(M\) can be very large while the support size \(\tau\) is much smaller. The type description preserves the paper’s relevant distinctions—location and benefit—rather than assigning one bill to an undifferentiated population.
An instance consists of that finite rational support, the explicit rooted tree, rational edge costs, and the positive-branch-surplus assumptions of the paper. The decision variable is a per-customer bill \(x_{v,b}\); there is no optimization objective, since this is a cost-allocation problem. The requested output is the unique type-level allocation satisfying the mass versions of efficiency and core constraints, SMP, and NSD. More explicitly, a coalition is a mass vector \(a_{v,b}\in[0,M\mu_{v,b}]\). Its worth is the maximum, over selected masses \(q_{v,b}\le a_{v,b}\), of their total benefit minus the cost of the minimal subtree connecting their locations, or zero if that quantity is negative. Core feasibility requires the coalition’s allocated surplus to cover this worth for every coalition mass vector, with equality for the whole society. NSD requires that whenever downstream welfare equals node \(v\)’s benefit, downstream bills net of downstream network cost equal \(v\)’s bill. Splitting or combining cohorts at a location while preserving their total benefit should preserve their aggregate bill.
The expected outcome is tractability: aggregate the type benefits into \(B_v\), then evaluate Proposition 4’s formula for each supported type. This takes time polynomial in the explicit tree size, \(\tau\), and the rational input bit length; that bound is again an inference from the formula. The mirror is recognizable as the authors’ problem because it asks for the same bills, on the same fixed tree, under the same economic assumptions and allocation principles. It covers Proposition 4’s tree-network allocation, not the paper’s out-of-scope problem of constructing a network.
The main weakness is that the paper’s proposition concerns a finite-agent game, not an atomless population. Extending coalition worth and the axioms to fractional masses, then proving the same characterization, is real work; Proposition 4 does not do it for us. Also, the formula already aggregates users through community benefits, so continuization may make the input more natural without revealing a new complexity boundary. Still, this seems like an honest, modest mirror: a precise high-multiplicity version of the paper’s central computed allocation. The first follow-up is to prove the discrete-to-continuous correspondence and give its exact bit-complexity bound.
Proposition 4 is the strongest anchor, but it is not a computational result in the sense ChoCo is charting. It characterizes an allocation by axioms and gives its formula; it does not define a computational problem or establish a complexity bound. The paper calls the rule computationally simple, but that is not a complexity theorem. The proposed mirror turns the formula into a task of evaluating it and infers a polynomial bound. That bound may be right, but it is a new complexity formalization of an axiomatic result, not a continuous mirror of a computational result in the paper.
The natural type model is quite sensible: many customers can share a network location and willingness-to-pay class. A stronger version could use a distribution over \((v,b)\), report bill densities, and replace community sums by integrals, \(B_v=\int b\,d\mu_v\). That avoids the per-customer bill tending to zero when population scale grows. But it also leaves the rule as \(x(v,b)=\alpha_v b\), with coefficients determined from the same node-level aggregates and tree. Computing those coefficients is formula evaluation. Extending the core and SMP axioms to fractional coalitions could be a worthwhile cooperative-game or axiomatic exercise, but it does not supply the paper with a computational question about algorithms, optimization, or complexity.
So the negative case is narrow: this paper appears to offer no named computational result for a continuous mirror to investigate. The broader claim that no scenario could make its high-multiplicity version sensible would be too strong; the customer types are plausible, and I would not use high multiplicity as an objection. The case against rests on the mismatch between the paper’s axiomatic allocation result and ChoCo’s computational remit. If the programme counts formal complexity analyses of explicit allocation rules as in scope, this anchor survives and the negative case is weak.
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.