d4-journals-mss-2019-0001

My strongest positive case is narrow: the paper’s painting construction has a credible high-multiplicity mirror, but the paper does not establish a named complexity result of the kind the programme most wants.

The anchor is Proposition 2, proved in this paper. It states that for every multiple-source spanning-tree problem \((N,M,C)\) and every minimal tree \(t\), the painting allocation \(f^{P,t}(N,M,C)\) equals the folk rule \(F(N,M,C)\). Thus the painting result does not depend on the choice of minimal tree or on the Phase 1 tree used to connect the sources. This is a computational correctness result: the painting procedure computes the same allocation as the folk rule. It is not, however, a theorem that the problem is in P or hard, and the paper gives no numbered complexity classification. Theorem 1 is an axiomatic characterization, so I would not use it as a computational anchor.

My lead mirror would be Mass-Weighted Folk Allocation. Its instance is a finite support \(T\) of agent types, a finite source set \(M\), rational masses \(\mu_t>0\) summing to \(1\), and a symmetric nonnegative rational cost matrix \(C\) on \(T\cup M\). A type is a cohort at a shared connection terminal: its members have the same connection-cost profile, and their local links to that terminal are free. A society with millions of agents but only tens of such cohorts is a plausible regime—for example, customers served through a finite set of municipal or industrial connection hubs. The decision variable is the type-level allocation of the minimum network’s cost. The underlying network objective remains to minimize total connection cost; the allocation problem itself asks for the payment vector the rule prescribes.

Here is a precise version. List the distinct positive edge costs as \(0<\lambda_1<\cdots<\lambda_r\), and set \(\lambda_0=0\). For each \(q\), let \(D^q_{uv}=1\) when \(c_{uv}\ge\lambda_q\), and \(D^q_{uv}=0\) otherwise. Let \(P_q\) be the connected components of the zero-cost graph for \(D^q\), and let \(p_q\) count those components that contain a source. For type \(t\), write \(S_q(t)\) for its component, and \(\mu(S_q(t))\) for the total mass of agent types in that component. The requested solution is the aggregate payment \(A_t\) for each type, where

\(A_t=\mu_t\sum_{q=1}^{r}(\lambda_q-\lambda_{q-1})\left(p_q-1+\frac{\mathbf{1}[S_q(t)\cap M=\varnothing]}{\mu(S_q(t))}\right).\)

This is the mass-weighted version of the paper’s simple-problem folk-rule formula, extended over a canonical threshold decomposition. The output is a rational vector \(A\), with total payments equal to the minimum tree cost.

The paper’s painting procedure suggests how to compute the same vector: find a minimum tree on the type terminals and sources, connect the sources as in Phase 1, then paint each unfinished edge by the mass of types currently assigned to it. If edge \(e\) has assigned mass \(Q_e\), a painting increment \(\Delta\) charges type \(t\) an aggregate amount \(\mu_t\Delta/Q_e\). The cost of the source tree is divided in proportion to mass. The question corresponding to Proposition 2 is whether this mass-based procedure always returns the displayed allocation, independently of the choices of minimum trees and source-connecting tree.

I expect this problem to be tractable in \(\tau=|T|\), \(|M|\), and the input bit length: there are at most \(\binom{\tau+|M|}{2}\) cost levels, and each level requires only a component calculation. The painting implementation also has finitely many edge-removal stages. This tractability assessment is mine; the paper does not state it as a complexity theorem.

There is a concrete high-multiplicity bridge. For rational \(\mu\), choose \(n\) with \(n\mu_t\) integral and replace each type by \(n\mu_t\) named agents, joining agents of the same type at zero cost. On these instances, aggregating the discrete folk-rule payments by type gives exactly the mass-weighted formula above. That makes the mirror an exact identity for a sensible instance regime, not just a continuous reinterpretation of the story.

The mirror covers Proposition 2’s painting-to-folk computation, not the paper’s full axiomatic characterization or arbitrary agent-specific cost matrices. The follow-up questions are whether the continuous painting procedure is choice-independent, whether this weighted rule inherits the paper’s axioms, and what changes when members of a type have nonzero costs between them.

The weak point is that the shared-terminal assumption materially restricts the original model: the paper allows arbitrary pairwise costs among individual agents. It is plausible for cohorts sharing infrastructure, and the discrete aggregation identity supports it, but authors could reasonably regard it as a specialized instance family. Also, Proposition 2 supplies correctness, not a complexity separation or a hard problem whose hardness might dissolve. This is a modest positive case for a continuous mirror, not evidence that the paper opens a substantial new complexity landscape.