| paper | d4-conf-aaai-2015-0028 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard for every fixed constant \(\alpha>1\), even when the target share is strictly positive. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a depot, TSP distance data, a finite set of customer types \(T\) with locations, rational masses \(\mu_t>0\) summing to \(1\), and a target type \(t^\star\), let \(C(S)\) be the shortest depot tour serving the locations represented in \(S\), with \(C(\varnothing)=0\). Order types by repeatedly choosing a remaining type with probability proportional to its mass. For each type \(t\), let \(P_t\) be the types before it in this order. Compute or approximate the cohort share \(\Phi_t(\mu)=\mathbb{E}[C(P_t\cup\{t\})-C(P_t)]\) for \(t=t^\star\).
A society is a distribution \(\mu\) over customer types, each type specifying its routing-relevant attributes, including its location. The quantity to compute is the target type's aggregate Shapley share under the size-biased type order; its per-account charge is \(\Phi_{t^\star}(\mu)/\mu_{t^\star}\).
Covers Theorem 1 and its TSP Shapley cost-allocation problem. It leaves the food-bank fair-division case study and the paper's other proposed challenges untouched.
The strongest case is the paper’s TSP Shapley cost-allocation result. The paper’s numbered anchor is Theorem 1: “Unless P=NP, there is no polynomial time \(\alpha\)-approximation to the Shapley value of a customer in a TSP game for any constant factor \(\alpha>1\).” The paper attributes this result to Aziz et al. (2014); it is stated here, not proved here.
I would mirror it with Continuum TSP-Shapley Type-Share. An instance gives a depot and the same kind of TSP distance data as the paper’s game, a finite set \(T\) of customer types, rational masses \(\mu_t>0\) summing to one, and a target type \(t^\star\). A type completely specifies the customer attributes relevant to routing and cost allocation, including its delivery location. For a coalition of types \(S\), let \(C(S)\) be the shortest depot tour serving those types, with \(C(\varnothing)=0\).
Define the type allocation by drawing a random order of \(T\): at each step, choose a remaining type \(t\) with probability proportional to \(\mu_t\). If \(P_t\) is the set of types before \(t\), its cohort share is
\[
\Phi_t(\mu)=\mathbb{E}\!\left[C(P_t\cup\{t\})-C(P_t)\right].
\]
The problem is to compute \(\Phi_{t^\star}(\mu)\), or approximate it within a specified constant factor. Equivalently, one can report the type’s charge per unit mass, \(\Phi_{t^\star}(\mu)/\mu_{t^\star}\). The shares sum to \(C(T)\).
This is a high-multiplicity version of the paper’s customer game, with a direct justification for the allocation rule. Take any finite population with \(N\mu_t\) identical customers of each type, for an \(N\) that clears the mass denominators, and give it the paper’s ordinary Shapley allocation. A type’s route cost changes only when its first member enters a coalition. The order in which types first appear is exactly the size-biased order above, so the total Shapley share of that type is \(\Phi_t(\mu)\). With equal masses, this order is uniform. In particular, one equal-mass type for each customer in an original TSP game gives exactly that customer’s original Shapley value as the type’s cohort share.
A plausible regime is a large delivery system with many cost-bearing customer accounts or beneficiaries consolidated at a finite set of receiving points. Members of a type share the same location and all other relevant service and cost attributes; each type’s mass is its fraction of the population. The number of people can be made arbitrarily large relative to the number of distinct types by adding identical members to each cohort. This fits the paper’s concern with allocating delivery costs and its TSP game, while making the population—not just the cost outcome—the continuous object.
I expect this mirror to be Class B: hardness transfers. The equal-mass construction embeds the discrete customer-value problem directly: an algorithm for the continuous type-share problem would yield the same-factor approximation for Theorem 1’s Shapley value. Thus, absent \(P=NP\), the mirror has no polynomial-time constant-factor approximation either. The reduction’s combinatorics remain in the routing instance and its customer locations; making the population large does not remove them.
This case covers Theorem 1 and the TSP cost-allocation problem behind it. It does not claim to continuize the paper’s food-bank fair-division case study or its broader agenda. Further questions include whether the inapproximability persists for arbitrary rational type masses, and which restrictions on the metric or type support permit exact, approximate, or parameterized algorithms.
The soft spot is that the paper states the result for an individual customer in a finite game, while this mirror allocates a collective share to a type. The clone-limit definition makes that change precise and preserves the original value on the equal-mass instances, but the authors or a referee might still regard the continuous extension as a repackaging of their discrete allocation question. Its strength is that the repackaging corresponds to an actual regime of many indistinguishable customers and gives a precise problem whose hardness can be checked.
The strongest case against this anchor is that the paper’s TSP-game players are customers at delivery locations. The routing cost is incurred for serving the stops; it does not grow just because more people are assigned to an already-served stop. So a large cohort of beneficiaries at a few locations changes the unit being charged: the question becomes how to divide a location’s cost among its beneficiaries, rather than what a customer’s Shapley value is. If the programme requires the paper’s original customer to remain the unit of analysis, this is a poor mirror.
That objection does not defeat the better version, though. Treat accounts at shared receiving points as players, with a type specifying their location and other cost-relevant attributes. The coalition cost is the route through the locations represented in that coalition. Because a type’s first member activates its stop and later members add no route cost, the cohort’s aggregate Shapley share is exactly the marginal cost at the type’s first appearance. In a population with \(N\mu_t\) identical members of each type, those first appearances are ordered size-biased by \(\mu_t\). The proposed \(\Phi_t(\mu)\) is therefore an exact clone-population identity, and replicating every member preserves the type support while making the population arbitrarily large.
That leaves a real negative point: this may be a modest mirror, and its central hardness can be inherited directly from Theorem 1. But the programme explicitly counts such discrete-to-continuous identities and Class B hardness transfers as worthwhile outcomes. The TSP theorem is a named computational result, and the cohort version has a plausible interpretation. I can’t honestly defeat this anchor under the programme’s stated criteria; the case against it is weak.
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.