| paper | Incentives for Early Arrival in Cost Sharing |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The only named anchor, Theorem 5.3, is not a computational result under the programme’s explicit gate. The paper states that its general-cost decomposition is exponential and leaves polynomial-time implementation as future work. The proposed type-mass formulation is a plausible extension, but it cannot supply the missing computational anchor.
fails bit a — no named computational result to mirror
Theorem 5.3 supplies no algorithmic classification, bound, or computational guarantee, so the proposed synthesis problem is newly introduced rather than a mirror of a named computational result.
fatal: True
The proposed mirror covers the \({0,1}\)-valued and general mechanism-property theorems, including Theorems 3.11, 4.4, and 5.3, but leaves computational complexity and polynomial-time implementation unresolved.
The strongest honest case is a qualified yes, centred on Theorem 5.3, proved in this paper: “eGSFS-CS is SF, OIR, and I4EA.” This is a constructive mechanism theorem, not a theorem saying \( \mathrm{P} \), NP-hardness, or parameterized tractability. If ChoCo’s anchor gate is restricted to explicit complexity classifications, the paper has no qualifying anchor. On the broader algorithmic reading, however, Theorem 5.3 gives a credible mirror.
My lead problem would be Continuum eGSFS Cost-Sharing Synthesis.
Let \( \Theta=\{\theta_1,\ldots,\theta_\tau\} \) be finitely many complete customer types: for example, brand, size, delivery window, and every other attribute affecting production cost or payment. Let \( \mu\in\mathbb{Q}_{\ge 0}^{\Theta} \) with \( \sum_{\theta}\mu_\theta=1 \). Thus \( \mu_\theta \) is the fraction of a large population having type \( \theta \). A realistic regime is a shirt factory receiving millions of orders but only a few hundred recurring order types; customers of one type are interchangeable for the cost-sharing problem.
The cost is a normalized monotone functional \( C:[0,\mu]\to\mathbb{Q}_{\ge0} \), with \( C(0)=0 \). The input should give \( C \) by a finite rational piecewise-linear formula or a finite monotone layer decomposition. If \(N\mu_\theta\) is integral, the associated finite clone instance has \(N\mu_\theta\) customers of type \( \theta \), and coalition \(S\) has normalized composition \(z_\theta(S)=|S\cap\theta|/N\) and cost \(c_N(S)=N C(z(S))\). The factor \(N\) represents an extensive production cost and prevents a fixed setup cost from becoming a singular, one-customer event in the limit.
Customers arrive according to a type-labelled arrival measure. At every prefix, the mechanism sees the arrived mass \(z\) and its arrival history, but not future arrivals. Its decision variable is an online charge kernel \(q\): every arrived unit receives a current nonnegative cost share, and the aggregate shares must satisfy \( \sum_\theta\int q_\theta\,d\lambda_\theta=C(z) \), where \( \lambda_\theta \) is the arrived mass of type \( \theta \). The output is a finite description of this online policy, together with an algorithm for evaluating a customer’s charge at any rational prefix.
The policy must satisfy the continuous versions of the paper’s three properties:
The problem asks whether such a policy exists and, if so, to compute one. Its objective is mechanism synthesis, not minimizing production cost. The finite-clone definition gives the intended semantics: for every denominator \(N\), the policy’s discretization should be anonymous among same-type clones, satisfy the paper’s exact OIR and I4EA conditions, and converge to the stated mass policy and Shapley limits.
I would expect the structured version to be Class A. For a finite layer decomposition, the generalized shuffle and greedy decomposition should plausibly collapse from individual players to type-composition states. The natural target would be an algorithm polynomial in \( \tau \), the number of cost layers, and the encoding length, independent of \(N\). That would be a genuine continuization gain: the paper’s finite construction is exponential in the number of named players, while the continuous instance exposes only finitely many repeated types.
This is recognisably the authors’ problem. It retains online arrival, monotone coalition cost, irrevocable/current cost shares, early-arrival incentives, and Shapley fairness. The shirt-factory example in the paper is already naturally a repeated-type population. What changes is precisely the high-multiplicity regime: names disappear, composition becomes mass, and random permutations become random arrival ranks.
The main weakness is substantial. Theorem 5.3 is stated for an arbitrary set function \(c:2^N\to\mathbb{R}_{\ge0}\), whereas my mirror assumes type-exchangeability and an extensive cost functional \(C(z)\). Also, a literal atomless individual has zero mass, so unilateral delay is otherwise vacuous. I therefore define I4EA through the finite clone lifts and their tagged-customer limit; replacing it by positive-mass cohort deviations would be a genuine extension. Finally, the paper’s greedy-monotone decomposition is explicitly exponential, so the expected Class-A algorithm is an open result, not something already proved by Theorem 5.3.
The resulting research questions are whether eGSFS has a consistent type-level limit, whether the limit can be computed in \( \operatorname{poly}(\tau,K,L) \) time for \(K\) cost layers, how accurately finite clone populations approximate the continuum policy, and whether arbitrary succinct monotone \(C\) creates a Class-C boundary. I would not claim that this mirror covers the paper’s full arbitrary-player theorem; it covers Theorem 5.3 in the repeated-customer, type-composition regime.
The proponent’s anchor fails ChoCo’s first gate. Theorem 5.3 is not a computational result: it asserts existence of an online mechanism satisfying SF, OIR, and I4EA for every finite monotone cost function. It gives no complexity classification, approximation guarantee, parameterized algorithm, or polynomial-time bound. Indeed, the paper explicitly leaves polynomial-time implementation for general costs as future work and acknowledges that its decomposition is exponential. Thus the proposed “Continuum eGSFS Cost-Sharing Synthesis” is a newly invented problem, not a continuous mirror of a named computational theorem.
Even under a broader reading, the mirror has a fundamental semantic problem. The paper’s central predicate is unilateral delay. For a player \(i\), I4EA compares two permutations differing only by moving \(i\) one position later. An aggregate mass vector \(\mu\) contains no such individual deviation. In an atomless population, moving one customer changes no mass at all, so a policy whose state is only the current mass sees identical states and I4EA becomes vacuous.
The proposed repairs each change the problem. A finite-clone lift retains the original discrete question and merely asks for a limiting family of mechanisms. A tagged customer with an arrival rank requires an additional arrival-time or rank mark, so the instance is no longer just a distribution over customer types. A positive-mass cohort deviation replaces unilateral I4EA with a new coalition-level axiom. None is a harmless restatement: each changes the strategic actor or information state.
The construction also has no evident extensive limit. Its proof works by making one named marginal player bear each \(0\)-\(1\) cost layer. For the simple anonymous cost \(C(x)=x\) with one type, extensive scaling gives \(c_N(S)=|S|\). The natural \(0\)-\(1\) decomposition is
\[ |S|=\sum_{r=1}^{N}\mathbf{1}\{|S|\ge r\}, \]
so the number of layers grows with \(N\); in the limit these become a continuum of layers. A fixed finite layer description of \(C\) therefore does not yield a fixed finite eGSFS computation. Conversely, assigning an extensive coefficient to a fixed \(0\)-\(1\) layer makes one marginal clone bear cost of order \(N\), producing a singular rather than an ordinary mass-charge kernel. The proponent’s scaling removes fixed-cost degeneration, but it does not make the paper’s marginal-player construction type-level.
The shirt-factory setting is genuinely a plausible high-multiplicity regime, so this is not an objection to repeated customer types themselves. The problem is that the paper proves nothing about clone consistency, invariance under permutations of same-type customers, or convergence of its shuffle maps and greedy decompositions to a measurable mass policy. Establishing those facts would require a new continuum mechanism-design theory, with a new representation of arrival histories and a new proof of the three properties.
The negative case is therefore strongest under ChoCo’s stated named-result requirement: there is no qualifying computational anchor. If ChoCo permits substantial extensions, a direct anonymous, extensive, arrival-marked cost-sharing model could be worthwhile. I cannot honestly prove that no such new model deserves study. But it would be a re-modeling inspired by the paper, not a continuous mirror of its computational content.
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.