| paper | Cost Sharing under Private Valuation and Connection Control |
| authors | — |
| venue | AAMAS 2023 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper contains no numbered theorem, lemma, proposition, or corollary classifying a computational problem. Propositions 4.3, 4.6, and 4.8, along with the later theorems, establish mechanism-design properties and impossibilities rather than computational complexity. A typed-population extension may be worthwhile, but it cannot supply the missing computational anchor.
fails bit a — no named computational result to mirror
The proposed extension concerns continuous analogues of Propositions 4.3, 4.6, and 4.8; it leaves the CVM and RSM property theorems without computational mirrors.
Under ChoCo’s strict anchor rule, this paper has no qualifying result. It contains no numbered theorem, lemma, proposition, or corollary asserting NP-hardness, membership in \(P\), parameterized tractability, an approximation algorithm, or a comparable computational classification.
The closest results are Proposition 4.3, proved here, which shows that truthfulness, feasibility, efficiency, and budget balance are incompatible; Proposition 4.6, also proved here, which rules out any nontrivial welfare approximation under truthfulness, feasibility, and budget balance; and Proposition 4.8, which rules out a positive budget-balance ratio. Theorems 5.2–5.9 and 6.2–6.9 prove properties of CVM and RSM. These are mechanism-design and axiomatic results, not computational-complexity results. Algorithm 1 is exponential-looking, and both mechanisms invoke minimum-Steiner-tree computations, but the paper does not state or prove a complexity classification for them.
The strongest honest near-mirror would therefore be an extension of Proposition 4.3, not a valid ChoCo anchor. Consider a utility or telecommunications network with many customers distributed among finitely many location–valuation–access types. A type \(t\) contains its network role, valuation \(v_t\), and available incident links; \(\mu_t\) is the fraction of customers of that type. A continuous mechanism chooses served masses \(y_t\), a connected template edge set \(F\), and per-customer charges \(p_t\), with welfare
\[ W(y,F)=\sum_t v_t y_t-\sum_{e\in F}c_e. \]
Budget balance would require
\[ \sum_t y_t p_t=\sum_{e\in F}c_e, \]
while feasibility requires \(p_t\le v_t\). The question would be:
Given a finite typed network, rational type masses \(\mu\), valuations, and edge costs, does there exist a mechanism that is efficient, feasible, budget balanced, and immune to valuation and link-withholding deviations by every positive-mass cohort?
Call this \( \mathrm{CCS\text{-}Existence}_\infty \). It is recognizable as the paper’s problem in a plausible high-multiplicity setting: households or firms are numerous, but only finitely many location, valuation, and connectivity roles occur. The natural expectation is that Proposition 4.3’s impossibility survives for a two-cohort chain \(s-a-b\), provided deviations are allowed by an entire positive-mass cohort. The analogous questions for welfare approximation and budget-balance ratios would mirror Propositions 4.6 and 4.8.
That formulation is only an extension, however. Literal individual truthfulness becomes nearly vacuous in an atomless population: one person’s report has zero effect on aggregate selection, connectivity, or total cost. Replacing individual deviations by positive-mass coalition deviations changes the strategic predicate. The network also cannot be represented by \(\mu\) alone; a finite template graph or type-to-type connectivity kernel is required. Finally, fixed shared-edge costs and per-capita edge costs produce different high-multiplicity limits.
Thus the best positive claim is that the paper supplies a credible high-multiplicity mechanism-design object, especially around Proposition 4.3. But it supplies no qualifying computational anchor, so this cannot honestly be presented as a Class A, B, or C ChoCo result. The main follow-up questions are whether clone-consistent link semantics can be defined, whether shared infrastructure costs should scale with population, and whether the resulting typed-network optimization problem has a meaningful complexity classification.
The negative case is strongest at the programme’s strict anchor rule: this paper supplies no computational result to continuize. Propositions 4.3, 4.6, and 4.8 are mechanism-design impossibilities; Theorems 5.2–5.9 and 6.2–6.9 verify axiomatic properties of CVM and RSM. None classifies an instance problem by complexity, gives an approximation algorithm, or studies a parameterized computational task. Algorithm 1 is an exponential-looking procedure, and the mechanisms invoke minimum-Steiner-tree computations, but the paper proves no computational statement about either.
The proposed \( \mathrm{CCS\text{-}Existence}_\infty \) is therefore a new research problem, not a continuous version of Proposition 4.3. It also has an awkward computational interface: “does there exist a mechanism?” quantifies over arbitrary functions on a continuous valuation domain. Unless one specifies a finitely represented mechanism class, the question is not an ordinary decision problem. Once such a class is imposed, that restriction—not Proposition 4.3—supplies the computational content.
There is a plausible high-multiplicity story here: repeated households at finitely many network locations with repeated valuations and access roles. The objection is not that valuations must be individual-specific; complete clone types resolve that. The difficulty is that the paper’s strategic object is simultaneously a named node and the controller of named incident edges. A mass vector does not determine what happens to those edges.
If an edge is shared by a type-cohort, one individual has either an \(O(1)\) veto over infrastructure despite having zero population mass, or no veto at all. Requiring the whole cohort to withhold the edge replaces individual truthfulness by a coalition or cohort deviation. If edges are replicated between clones, the finite graph has been replaced by a blow-up graph whose costs, incidence pattern, and sharing rules must be newly specified. If infrastructure is treated as a facility serving mass, one has yet another model. These are not choices like replacing strict inequalities by weak ones; they determine the strategic game itself.
That defeats the Proposition 4.3 anchor. A two-cohort chain \(s-a-b\) with positive masses and cohort-level deviations may well reproduce an analogous impossibility. But with individual deviations, the atomless limit removes the pivotality on which the argument relies; with cohort deviations, the result concerns a new \(\tau\)-player mechanism. And the two-cohort witness itself contains no population-level computational problem. Enlarging it to arbitrary typed networks could be worthwhile, but that would be a new typed network-mechanism programme, not a mirror supplied by this paper.
The same problem defeats Proposition 4.6. Its welfare-ratio argument is still a two-node mechanism impossibility, not an approximation algorithm or a complexity classification. Replacing counts by masses and allowing cohort deviations merely reweights the same witness. A richer question about choosing served masses, network edges, and payments would be a prize-collecting network-design mechanism problem; the paper neither formulates nor analyzes it.
Proposition 4.8 fares no better. Its zero budget-balance-ratio example depends on how two named agents can report valuations and withhold links. In a continuum, individual deviations are non-pivotal; under cohort deviations, the truthfulness predicate has changed; under clone-specific edges, the zero-cost connection has changed meaning. Any surviving analogue requires precisely the additional modelling conventions that turn it into a new problem.
Thus the proponent’s strongest concession is also the negative conclusion: there is a sensible high-multiplicity extension, but it is only an extension. The paper gives no computational anchor, and every proposed mirror either loses the strategic phenomenon in the atomless limit or restores it by introducing a new cohort-level network model. The universal claim that no imaginable scenario could ever be interesting is not provable, but under ChoCo’s standards this paper should not be greenlit as a continuous-computational mirror.
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.