| paper | d4-conf-aaai-2016-0435 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: every promised instance admits zero subsidy. The decision takes \(O(L)\) time including input reading. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given a finite set of provider types \(T\), population masses \(\mu_t>0\) summing to \(1\), and type profiles specifying depots, per-provider demand templates, revenues, costs, and vehicle capacities, define \(v(x)\) as the profit of the fluid routing game for coalition masses \(0\leq x\leq\mu\), with demand and vehicle mass scaled by type mass and route flows allowed to be fractional. Assume \(v\) is differentiable, \(v(0)=0\), and \(v(\mu)>0\); define \(\phi_t=\mu_t\int_0^1 \frac{\partial v(s\mu)}{\partial x_t}\,ds\) and \(\rho_t=\phi_t/v(\mu)\), with \(\phi_t\geq0\). Find nonnegative payment rates \(p_t\) and minimum subsidy \(\delta\geq0\) such that \(\mu_t p_t=(v(\mu)+\delta)\rho_t\) for every \(t\), and \(\sum_t x_t p_t\geq v(x)\) for every coalition mass vector \(x\in[0,\mu]\).
A continuum cooperative logistics game with finitely many provider types, each carrying mass. Coalition value \(v(x)\) comes from a fluid MDVRP in which provider demand and vehicle capacity scale with mass and route assignments may be fractional. Fair shares are normalized Aumann–Shapley contributions; the decision variables are type payment rates \(p_t\) and subsidy \(\delta\), with the objective of minimizing \(\delta\) subject to stability for every coalition mass vector.
The mirror does not establish that finite Shapley shares converge to Aumann–Shapley shares or that the fluid routing value is a faithful limit of discrete CVRG; the proponent flags both as open questions.
fatal: False
Covers the minimum-subsidy stable allocation guarantee of Proposition 4 in a fluid CVRG. It leaves the paper’s other structural propositions, experiments, and the computational complexity of finite Shapley and coalition-value computation outside the mirror.
I find no anchor that meets your rule. The paper states no named result about NP-hardness, polynomial time, FPT, or another complexity classification for CVRG allocation, Shapley computation, core membership, or coalition-value computation. The MDVRP MILP is used to compute coalition values, but its formulation is unnumbered and carries no complexity result; the conclusion even leaves efficient methods for computing \(\delta\)-BSA to future work.
The closest named result is Proposition 4, proved here: Algorithm 1 returns an allocation that is stable, proportional to the normalized Shapley value, and uses the minimum subsidy among allocations with those properties. That is a finite-game optimality claim, not a complexity bound. The other numbered propositions and corollary establish structural properties of CVRG or \(\delta\)-BSA, rather than computational complexity. Proposition 4 is therefore not a qualifying anchor under the stated test.
If Proposition 4 is admitted as an algorithmic anchor despite that gap, my best candidate is Continuous-CVRG Minimum-Subsidy Fair Core, covering only the paper’s minimum-subsidy allocation result. Take many small logistics providers with a finite set of repeated operating profiles: each type specifies a depot, a per-provider customer-demand template, revenues and costs, and vehicle capacity. Let \(\mu_t\) be the fraction of providers of type \(t\), with many providers but relatively few types. For a subcoalition with mass vector \(x\leq\mu\), define \(v(x)\) as its profit in a fluid version of the paper’s routing model, where demand and vehicle mass scale with provider mass and route flows may be fractional.
For a differentiable \(v\), define the type’s Aumann–Shapley contribution as
\[
\phi_t=\mu_t\int_0^1 \frac{\partial v(s\mu)}{\partial x_t}\,ds,
\]
and its normalized share as \(\rho_t=\phi_t/v(\mu)\), assuming these shares are nonnegative and \(v(\mu)>0\). The instance asks for nonnegative payment rates \(p_t\) and minimum subsidy \(\delta\geq0\), with total payments \(v(\mu)+\delta\), in those normalized proportions, such that every subcoalition is stable:
\[
\mu_t p_t=(v(\mu)+\delta)\rho_t \quad\text{for each }t,
\qquad
\sum_t x_t p_t\geq v(x)\quad\text{for every }0\leq x\leq\mu.
\]
A solution is such a vector of rates and subsidy minimizing \(\delta\). I would tentatively expect the routing component to remain hard: fractional mass changes the provider population, but route-column pricing over customer locations may retain its combinatorics. The paper provides no named hardness result to establish whether that would be hardness transfer or continuum-specific hardness. Further questions include whether the finite-game Shapley values converge to these shares, how to separate the stability constraints, and whether the fluid routing value is a faithful limit of discrete CVRG.
This is a plausible setting: a large last-mile market could contain many small providers drawn from a modest number of standardized operating profiles. The mirror keeps the paper’s coalition, routing, stability, and proportional-fairness concerns, while making mass the unit of the provider population.
The soft spot is substantial: the paper’s fairness criterion is the finite Shapley value, while the Aumann–Shapley rule and fluid routing model are additional choices, not consequences of Proposition 4. So this is a concrete possible mirror, but I cannot honestly present it as a case anchored by a qualifying computational result in the paper.
The strongest case against this paper is that it offers almost no stated complexity landscape to continuize. Propositions 1–3 and Corollary 1 establish game properties; Propositions 5–6 establish allocation properties. Proposition 4 is the closest computational anchor: it proves that \(\delta\)-BSA achieves minimum subsidy under its proportionality constraint. But it gives no runtime bound. Its update step maximizes over all \(2^n\) coalitions, and each coalition value requires solving an MDVRP. The paper itself leaves efficient and approximate computation to future work.
That makes the proposed Continuous-CVRG Minimum-Subsidy Fair Core a weak *mirror* of the paper’s computational results. It is still a plausible new problem. A stronger version would start with replicated finite CVRGs, preserve the finite Shapley shares, and ask whether their minimum-subsidy allocations converge to a fluid limit. That would avoid choosing Aumann–Shapley shares without showing they match the finite game. In the fluid formulation, stability reduces to finding the worst coalition mass vector \(x\):
\[
\delta^\star=\max\!\left(0,\ \sup_{x:\,a(x)>0}\frac{v(x)}{a(x)}-v(\mu)\right),
\qquad
a(x)=\sum_t\frac{x_t}{\mu_t}\rho_t,
\]
with infeasibility if \(a(x)=0\) but \(v(x)>0\). This is a concrete computational question involving routing and coalition stability.
I cannot honestly argue that no such scenario is worthwhile. Repeated provider profiles in a large logistics market are plausible, and the fluid model preserves the paper’s central coalition, routing, fairness, and stability concerns. My negative case is narrower: the paper does not supply a complexity result whose boundary this mirror would clarify. The proposed mirror might still be valuable precisely because its complexity is unknown. So the case against is strong as a claim about this paper being a poor anchor for the programme, but weak as the universal claim that no worthwhile continuous mirror exists.
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.