| paper | d4-journals-jet-2007-0029 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The named characterizations are axiomatic, and Proposition 3.2 validates a structural construction without making a computational complexity claim. The cloning limit is a coherent extension of φ, but its weighted Shapley evaluation is a new computational question rather than a continuous analogue of a qualifying computational result in this paper.
fails bit a — no named computational result to mirror
The proposed limit concerns the per-unit allocation induced by φ under replication of finitely many connection-cost types; it does not mirror the paper’s axiomatic characterizations or establish a continuous computational counterpart to Proposition 3.2.
The strongest plausible population regime is a large utility or communications network with many households at a small number of standardized service locations. A type would be a household’s location and complete connection cost profile; \(\mu_t\) would be the fraction of households of type \(t\). For rational \(\mu\), make \(q\mu_t\) identical copies of each type, give copies of the same type zero connection cost to one another, and use the type cost matrix for links between types. Apply \(\phi\) to this finite instance and aggregate each type’s shares. A possible continuous problem is: does the per-unit-mass allocation \(a_t=\lim_{q\to\infty}q\,\phi_i\), for a copy \(i\) of type \(t\), exist along valid \(q\), and can it be computed? A solution is the vector \(a\), with \(\sum_t\mu_t a_t\) equal to the spanning-tree cost. This preserves the paper’s cost-allocation rule under a high-multiplicity regime, but it is a proposed new evaluation problem, not a result the paper establishes.
There is no qualifying named computational anchor in the paper. The closest relevant result is Theorem 4.2, proved here: \(\phi\) is the unique rule for all minimum cost spanning tree problems satisfying Independence of Irrelevant Trees, Separability, and Equal Share of Extra Costs. Corollary 4.1, also proved here, says it is the unique rule satisfying Strong Cost Monotonicity, Population Monotonicity, and Equal Share of Extra Costs. These are axiomatic characterizations, not claims that a computational problem is in P, hard, or in another complexity class. Proposition 3.2 gives a construction of the irreducible matrix, but makes no complexity claim either. The paper itself says its focus is cost sharing; it does not provide a named computational result to mirror.
So the household-location model is the best positive lead I can offer, but it cannot meet the requested anchor test or be responsibly placed in the tractable/hardness trichotomy from this paper. Its soft spot is also substantive: the paper’s agents are finite nodes in a cost matrix, and taking replication limits may change the cost-sharing problem in ways the authors did not study.
The decisive problem is that the paper supplies no named computational result to mirror. Theorem 4.2 and Corollary 4.1 characterize \(\phi\) by axioms; Proposition 3.2 constructs an irreducible matrix. None states a complexity bound or gives an algorithmic result whose continuous counterpart this programme could classify. Continuizing the axioms would be an axiomatic question, which the programme excludes. Proposition 3.2 is the closest computational-looking result, but its construction is about a finite cost matrix, not a computational problem over populations.
The strongest repair is the proposed cloning limit. It is mathematically coherent, and its limit can be described quite cleanly. With \(q\mu_t\) copies of each type and zero costs between copies of the same type, the cost of a coalition depends only on which types it contains. Write \(v(S)\) for the cost of connecting the types in \(S\), using the irreducible type-level matrix. In a random permutation of the copies, a copy of type \(t\) has a nonzero Shapley marginal only if it is the first copy of \(t\). As \(q\) grows, the order in which types first appear converges to a size-biased random order: each next type is chosen with probability proportional to its mass among the types not yet seen. If \(P_t\) is the set of types preceding \(t\) in that order, the proposed limit is
\[ a_t=\frac{1}{\mu_t}\,\mathbb{E}\!\left[v(P_t\cup\{t\})-v(P_t)\right]. \]
That gives a well-posed computation problem, but it is a new weighted Shapley-value question, not a continuous version of Theorem 4.2, Corollary 4.1, or Proposition 3.2. Its input is still a finite graph on the \(\tau\) types; the masses change the probabilities in the random order, while network construction and the irreducible form remain type-level finite problems. Any complexity study of evaluating this weighted expectation would need its own motivation and results. It does not reveal a computational result in this paper that continuization might explain or change.
The location scenario supports the same concern. If households at a service location are treated as duplicate vertices, they collapse to one vertex in the network and the tree cost is unchanged; only its allocation among residents changes. If distinct homes have distinct connection profiles, the type support grows with the number of homes, so the proposed high-multiplicity regime disappears. A demand-sensitive or capacity-sensitive network could make population masses affect the network itself, but that changes the underlying optimization problem and is not governed by the paper’s results.
The negative case has a real limitation: splitting a fixed network cost among many households at a small number of service locations is sensible, and the cloning limit appears to exist. So I cannot show that the resulting cost-sharing problem is uninteresting. The narrower conclusion is stronger: it is not a worthwhile continuous *mirror of this paper* under ChoCo’s computational criterion. The paper’s named results are axiomatic or structural, and the best computational question the cloning construction suggests is a separate research direction.
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.