Answer: An anonymous rule satisfying all three axioms exists but is not unique in general. Exact efficient core allocation is polynomial-time computable.
Proposition 4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIn the game with tree-network the allocation characterized by core property, SMP and NSD assigns to agent i bill (23).
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
Let \(T\) be a finite tree rooted at the supplier \(0\), with \(m\geq1\) nonroot vertices and fixed, nonnegative rational edge costs \(c_e\). Customers occupy nonroot vertices, each of which has positive customer mass; benefits per customer are positive rationals.
A society is given by its support: the list of the \(\tau\) types \(t=(v_t,b_t)\) with positive mass, each with its mass \(\mu_t\) as a binary rational, where \(\sum_t\mu_t=1\). The support size \(\tau\) is not the number of possible types. The population scale \(M>0\) is rational, actual masses are \(n_t=M\mu_t\), and \(L\) is the total input bit length; state running times in \(m,\tau,L\).
Write \(c_v\) for the cost of the edge entering \(v\), \(D_v\) for its strict descendants, \(C(D_v)=\sum_{u\in D_v}c_u\), \(B_v=\sum_{t:v_t=v}n_tb_t\), and \(W_v=\sum_{u\in D_v}B_u-C(D_v)\). Assume positive branch surplus: \(B_v+W_v-c_v>0\) at every nonroot vertex.
For any real coalition vector \(0\leq a_t\leq n_t\), let \(H(q)\) be the union of paths from \(0\) to vertices with \(q_t>0\), with empty-union cost zero. Its worth is \(V(a)=\max\{0,\max_{0\leq q\leq a}[\sum_tq_tb_t-\sum_{e\in H(q)}c_e]\}\); edge costs are incurred in full whenever used.
An anonymous billing rule assigns a real per-customer bill \(x_t\) to each type throughout this domain. Core requires \(\sum_tn_t(b_t-x_t)=V(n)\) and \(\sum_ta_t(b_t-x_t)\geq V(a)\) for every such coalition vector.
Mass SMP permits merging equal rational masses \(h>0\) from \(k\geq2\) customer blocks at one vertex, with benefits \(b_1,\ldots,b_k\), into one mass-\(h\) block with benefit \(\sum_i b_i\), and permits the inverse split. Neither operation may reduce the participants' total bill; equivalently, their total bills before and after coincide. Other masses and benefits stay fixed; recompute \(M\) and normalize \(\mu\) after each operation.
Put \(X_v=\sum_{t:v_t=v}n_tx_t\). Mass NSD requires, at every nonroot vertex, \(W_v=B_v\Longrightarrow\sum_{u\in D_v}X_u-C(D_v)=X_v\).
Does an anonymous billing rule satisfying core, mass SMP and mass NSD exist uniquely? Is exact computation of an efficient core allocation possible in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite customers, core, local split/merge-proofness and NSD are claimed to characterize the locally proportional billing rule, given by an explicit formula; the tree value-sharing game is also shown convex. [Verified source](https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2022/wp_tse_1356.pdf).
No result settling this exact mass model was located.
An anonymous rule satisfying core, mass SMP and mass NSD exists, but is not unique in general. An exact efficient core allocation can be computed in time polynomial in \(m,\tau,L\).
Both conclusions hold for the stated model, including core constraints for all real coalition vectors. The nonuniqueness persists even among rules that depend continuously on the vertex benefits.
Let \(T_v=\{v\}\cup D_v\), let \(p(v)\) be the parent of \(v\), and define
\(S_v=B_v+W_v,\qquad P_v=S_v-c_v.\)
The positive branch-surplus assumption states precisely that \(P_v>0\). If \(\operatorname{ch}(v)\) denotes the children of \(v\), then the definitions give
\(W_v=\sum_{w\in\operatorname{ch}(v)}P_w,\qquad S_v=B_v+\sum_{w\in\operatorname{ch}(v)}P_w.\)
Consequently, \(S_v>0\), and
\(r_v=\frac{P_v}{S_v}=1-\frac{c_v}{S_v}\)
satisfies \(0<r_v\leq1\).
Set \(R_0=1\) and recursively define \(R_v=R_{p(v)}r_v\). The proposed per-customer surplus and bill are
\(y_t=b_tR_{v_t},\qquad x_t=b_t(1-R_{v_t}).\)
Thus \(y_t=b_t-x_t>0\), and \(0\leq x_t<b_t\).
For an ancestor \(v\) of \(v_t\), including \(v=v_t\), define
\(d_{t,v}=\frac{c_v}{S_v}\,b_t\prod_{u\in(v,v_t]}r_u,\)
where \((v,v_t]\) is the vertex path excluding \(v\), and an empty product equals \(1\). For other vertices, set \(d_{t,v}=0\).
These are nonnegative per-customer contributions to the edge entering \(v\). Telescoping along the path from \(v_t\) to the root gives
\(\sum_v d_{t,v}=b_t(1-R_{v_t})=x_t.\)
We next verify that each edge is paid exactly.
Define the aggregate residual benefit of a subtree, after charging all its edges, by
\(F_v=\sum_{t:v_t\in T_v}n_tb_t\prod_{u\in[v,v_t]}r_u.\)
Induction from leaves gives
\(F_v=r_v\left(B_v+\sum_{w\in\operatorname{ch}(v)}F_w\right)=r_vS_v=P_v.\)
Here the induction hypothesis is \(F_w=P_w\), and the identity defining \(S_v\) supplies the second equality. Therefore
\(\sum_t n_td_{t,v} =\frac{c_v}{S_v}\left(B_v+\sum_{w\in\operatorname{ch}(v)}F_w\right) =c_v.\)
Summing over edges proves budget balance:
\(\sum_t n_tx_t=\sum_{v\ne0}c_v.\)
For any real vector \(0\leq q\leq n\), an edge receiving a positive contribution from \(q\) belongs to \(H(q)\). Moreover, nonnegativity and \(q_t\leq n_t\) imply
\(\sum_t q_td_{t,v}\leq\sum_t n_td_{t,v}=c_v.\)
Hence
\(\sum_t q_tx_t =\sum_v\sum_t q_td_{t,v} \leq\sum_{e\in H(q)}c_e.\)
Now fix any coalition vector \(0\leq a\leq n\). For every \(0\leq q\leq a\), positivity of the surplus shares yields
\(\sum_t a_ty_t \geq\sum_t q_ty_t =\sum_t q_tb_t-\sum_t q_tx_t \geq\sum_t q_tb_t-\sum_{e\in H(q)}c_e.\)
Also \(\sum_t a_ty_t\geq0\). Taking the maximum in the definition of worth proves
\(\sum_t a_ty_t\geq V(a).\)
It remains to check efficiency. Every nonroot vertex has positive customer mass, so \(H(n)=T\). Choosing \(q=n\) gives
\(V(n)\geq\sum_t n_tb_t-\sum_{v\ne0}c_v=\sum_t n_ty_t.\)
The already proved coalition inequality, applied to \(a=n\), gives the reverse inequality. Thus
\(V(n)=\sum_t n_ty_t=\sum_{v\ne0}(B_v-c_v).\)
The construction is therefore an efficient core allocation.
Merging equal masses \(h\) at a vertex \(v\) preserves its aggregate benefit, because
\(\sum_{i=1}^{k}hb_i=h\sum_{i=1}^{k}b_i.\)
Every \(B_u\), and therefore every \(S_u,r_u,R_u\), remains unchanged. The participants’ bills before and after are respectively
\(h(1-R_v)\sum_{i=1}^{k}b_i \quad\text{and}\quad h(1-R_v)\left(\sum_{i=1}^{k}b_i\right).\)
They coincide. The same calculation proves invariance under the inverse split. Recomputing \(M\) and normalizing the masses does not affect these actual aggregate benefits.
The rule is anonymous because it assigns bills using only the society and the customer’s type.
The subtree calculation above implies
\(\sum_{t:v_t\in T_v}n_ty_t=R_{p(v)}P_v.\)
Applying this identity to the children of \(v\) gives
\(\sum_{u\in D_v}\sum_{t:v_t=u}n_ty_t =R_v\sum_{w\in\operatorname{ch}(v)}P_w =R_vW_v.\)
Consequently,
\(\sum_{u\in D_v}X_u-C(D_v)=W_v(1-R_v),\)
whereas
\(X_v=B_v(1-R_v).\)
If \(W_v=B_v\), these quantities are equal, exactly as mass NSD requires.
This proves existence on the entire stated domain.
Consider the two-edge chain \(0\to1\to2\). Write
\(w=B_2-c_2.\)
Positive branch surplus is equivalent to
\(w>0,\qquad B_1+w>c_1.\)
Choose aggregate bills of the form
\(X_1=d,\qquad X_2=c_1+c_2-d,\)
and bill proportionally within each vertex:
\(x_t=\frac{X_{v_t}}{B_{v_t}}b_t.\)
We first establish a sufficient interval for core membership:
\(\max\{0,c_1-w\}\leq d\leq\min\{c_1,B_1\}.\)
Indeed, these inequalities imply \(0\leq X_1\leq B_1\) and \(0\leq X_2\leq B_2\), so every surplus share is nonnegative.
For any \(q\) supported only at vertex \(1\), its total bill is at most \(X_1\leq c_1\). If \(q\) has positive mass at vertex \(2\), its total bill is at most \(X_1+X_2=c_1+c_2\). The empty vector has zero bill. Thus, in every case,
\(\sum_t q_tx_t\leq\sum_{e\in H(q)}c_e.\)
The argument in Section 3 proves all real-coalition core inequalities. Budget balance proves efficiency.
Let
\(d_0=\frac{c_1B_1}{B_1+w},\qquad U=\min\{c_1,B_1\},\qquad f=\frac{(B_1-w)^2}{1+(B_1-w)^2}.\)
The locally proportional construction has \(X_1=d_0\). This value belongs to the sufficient interval: \(0\leq d_0\leq U\), and
\(d_0-(c_1-w)=\frac{w(B_1+w-c_1)}{B_1+w}>0.\)
For any fixed \(\theta\in[0,1]\), define
\(d_\theta=d_0+\theta f(U-d_0).\)
Because \(0\leq\theta f\leq1\), this remains in the sufficient interval. Therefore it defines an efficient core rule.
Its coefficients depend only on \(B_1,B_2,c_1,c_2\), which mass split/merge preserves. Hence it satisfies mass SMP.
At vertex \(1\), NSD is triggered precisely when \(B_1=w\). Then \(f=0\), so
\(d_\theta=d_0=\frac{c_1}{2},\qquad X_2-c_2=c_1-d_\theta=d_\theta=X_1.\)
At vertex \(2\), the NSD hypothesis is impossible because \(W_2=0<B_2\). Thus every member of the family satisfies mass NSD. Each also depends continuously on the vertex benefits.
For a rule on all trees, use this construction on two-edge chains and the rule from Section 2 on all other trees. The preceding proofs verify every required axiom throughout that domain.
Take \(c_1=c_2=1\), with one type at each vertex, both having mass \(1\) and benefit \(3\). This is encoded by \(M=2\) and \(\mu_1=\mu_2=1/2\).
Here \(B_1=B_2=3\), \(w=2\), and
\(d_0=\frac35,\qquad U=1,\qquad f=\frac12.\)
The rules with \(\theta=0\) and \(\theta=1\) give respectively
\((X_1,X_2)=\left(\frac35,\frac75\right) \quad\text{and}\quad (X_1,X_2)=\left(\frac45,\frac65\right).\)
They are distinct anonymous rules satisfying all three axioms. Uniqueness therefore fails.
The underlying issue is substantive: split/merge preserves the vertex benefits, while conditional NSD constrains bills only on its equality locus. In the [cited paper, Appendix K, equation (121)](https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2022/wp_tse_1356.pdf#page=48), an identity is attributed to NSD without imposing that equality hypothesis. Such an inference is unavailable under the axioms stated here.
The allocation from Section 2 requires:
This uses \(O(m+\tau)\) rational arithmetic operations.
To verify polynomial bit complexity, let \(D\) be the product of the denominators of all input rationals. Its binary length is \(O(L)\). Each term \(M\mu_tb_t\), and each edge cost, has denominator dividing \(D\). Thus all \(B_v,S_v,P_v\) have \(O(L)\)-bit numerators and denominators after reduction. Each \(r_v\) also has \(O(L)\)-bit numerator and denominator.
A path product contains at most \(m\) such factors, so every \(R_v\), and every output bill or surplus share, has \(O(mL)\)-bit numerator and denominator. Using ordinary exact integer arithmetic and fraction reduction, a conservative running-time bound is
\(O\!\left((m+\tau)(mL)^3\right)\)
bit operations.
Thus exact efficient core allocation is polynomial-time computable directly from the support representation, without expanding rational masses into individual customers.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions correctly: an anonymous rule satisfying core, mass SMP, and mass NSD exists, uniqueness fails in general, and an exact efficient core allocation is polynomial-time computable from the support representation. I found no major or minor mathematical issues.
Every nonroot vertex has positive aggregate benefit \(B_v\), because its customer mass and all benefits are positive. The definitions of strict descendants give
\(W_v=\sum_{w\in\operatorname{ch}(v)}P_w\), with \(P_w=B_w+W_w-c_w\).
Consequently, the stated positive branch-surplus assumption gives \(P_v>0\), while \(S_v=P_v+c_v>0\). Since costs are nonnegative, \(0<r_v=P_v/S_v\leq1\). All divisions and path products in the construction are therefore well-defined.
This reasoning includes leaves, zero-cost edges, and the case \(m=1\).
The definitions \(R_v=R_{p(v)}r_v\), \(y_t=b_tR_{v_t}\), and \(x_t=b_t(1-R_{v_t})\) correctly imply \(y_t>0\) and \(0\leq x_t<b_t\).
The edge contribution formula is consistent with these bills. Along the customer’s path, each summand has the form
\(b_t(1-r_v)\prod_{u\in(v,v_t]}r_u\).
These terms telescope to \(b_t(1-R_{v_t})\), as claimed. In particular, the absence of factors for ancestors above the charged edge is correct.
The recurrence for \(F_v\) correctly separates customers at \(v\) from customers in its child subtrees:
\(F_v=r_v(B_v+\sum_w F_w)\).
At a leaf, this gives \(F_v=r_vB_v=P_v\). With the stated induction hypothesis \(F_w=P_w\), the recurrence gives \(F_v=r_vS_v=P_v\) at every vertex.
The aggregate contribution to the edge entering \(v\) is consequently
\((c_v/S_v)(B_v+\sum_w F_w)=c_v\).
Summing over edges proves exactly the claimed budget balance. Zero-cost edges cause no exception.
This argument handles the continuous coalition domain directly.
For any \(0\leq q\leq n\), nonnegative edge contributions and the coordinatewise bounds give
\(\sum_t q_td_{t,v}\leq c_v\).
If an edge is outside \(H(q)\), every customer using that edge has zero selected mass, so its aggregate contribution is zero. Therefore
\(\sum_t q_tx_t\leq\sum_{e\in H(q)}c_e\).
For every \(q\leq a\), positivity of \(y_t\) justifies
\(\sum_t a_ty_t\geq\sum_t q_ty_t\).
Combining this with the bill bound gives the required inequality for each candidate in the definition of \(V(a)\). Nonnegativity of the allocated surplus also covers the zero alternative.
Thus taking the maximum proves the core inequality for every real \(a\), including the empty coalition. No discretization or finite-customer theorem is being used.
Positive customer mass at every nonroot vertex ensures \(H(n)=T\). Evaluating the worth objective at \(q=n\) and using budget balance gives
\(V(n)\geq\sum_t n_ty_t\).
The already established coalition inequality at \(a=n\) gives the reverse inequality. Hence the claimed efficiency identity follows. The argument does not assume, without justification, that serving everyone maximizes grand-coalition worth.
An equal-mass merge preserves the affected vertex’s aggregate benefit, since its benefit before and after is \(h\sum_i b_i\). It therefore preserves every \(B_u,S_u,r_u,R_u\). The participants’ total bill is unchanged by the stated proportional formula. The inverse split satisfies the same equality.
This remains valid for operations involving only part of a type’s mass or creating a benefit already present in the support: the coefficient at the vertex remains unchanged. Recomputing \(M\) and normalizing \(\mu\) changes the representation but does not change the aggregate benefits used by the rule. Positive branch surplus and positive customer mass at each vertex are preserved.
The rule is anonymous because identical types in the same society receive identical per-customer bills.
The subtree surplus identity
\(\sum_{t:v_t\in T_v}n_ty_t=R_{p(v)}P_v\)
follows correctly by factoring the ancestor product from the already verified formula for \(F_v\). Summing over child subtrees then gives descendant surplus \(R_vW_v\).
Subtracting that surplus from descendant benefit and then subtracting descendant costs gives
\(\sum_{u\in D_v}X_u-C(D_v)=W_v(1-R_v)\).
Since \(X_v=B_v(1-R_v)\), NSD follows exactly when its hypothesis \(W_v=B_v\) holds.
On the two-edge chain, the stated branch-surplus conditions are correct: \(w=B_2-c_2>0\) and \(B_1+w>c_1\).
The proposed interval for \(d\) is genuinely sufficient. Its bounds imply:
Proportional billing therefore yields nonnegative bills and surplus shares. A selection supported only at vertex \(1\) pays at most \(c_1\); a selection reaching vertex \(2\) pays at most \(c_1+c_2\). These are the relevant path costs. The earlier core argument remains valid with nonnegative, rather than strictly positive, surplus shares.
The computation
\(d_0-(c_1-w)=w(B_1+w-c_1)/(B_1+w)>0\)
is correct. Together with \(0\leq d_0\leq\min\{c_1,B_1\}\), it places \(d_0\) in the sufficient interval.
Since \(0\leq f<1\) and \(0\leq\theta\leq1\), \(d_\theta\) lies between \(d_0\) and \(U\), so it remains admissible. The coefficients depend only on quantities preserved by mass SMP.
At vertex \(1\), NSD is triggered precisely by \(B_1=w\); then \(f=0\) and \(d_\theta=c_1/2\), giving the required equality. At vertex \(2\), the hypothesis cannot hold because \(W_2=0<B_2\).
The family is continuous in the vertex benefits on the stated domain. Extending it by the Section 2 rule on other tree shapes is legitimate because the permitted split/merge operations preserve the tree.
The example satisfies all input restrictions and branch-surplus assumptions. Its arithmetic is correct:
\(w=2\), \(d_0=3/5\), \(U=1\), and \(f=1/2\).
Thus the two aggregate billing vectors are indeed \((3/5,7/5)\) and \((4/5,6/5)\). The previously verified family establishes that both arise from globally defined admissible rules. This disproves uniqueness.
The source comparison is also accurate as a description of the displayed argument: Appendix K attributes equation (121) to NSD without stating the equality hypothesis at that step. The paper states NSD conditionally. This observation is supplementary; the mass-model counterexample stands independently. See the [cited paper, NSD and Appendix K](https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2022/wp_tse_1356.pdf).
The claimed \(O(m+\tau)\) rational-operation count is correct for aggregation and the two tree traversals.
The denominator argument is valid: the product \(D\) of all input denominators has \(O(L)\) bits, and each term \(M\mu_tb_t\) and each cost has denominator dividing \(D\). Repeated use of \(M\) in different summands does not require additional powers of its denominator in a common denominator.
Aggregate numerators and denominators have \(O(L)\) bits, including the size increase from summation. Thus each \(r_v\) has \(O(L)\)-bit numerator and denominator. Products along paths of at most \(m\) vertices have \(O(mL)\)-bit representations, as do the outputs.
Ordinary exact arithmetic with fraction reduction fits within the conservative bound \(O((m+\tau)(mL)^3)\). The proof therefore establishes polynomial bit complexity, not merely polynomial arithmetic complexity.
No additional clarification or repair is needed. The output establishes existence, general nonuniqueness, and polynomial-time exact efficient core allocation under the stated assumptions.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.