Answer: \(\mathrm{NP}\)-hard for every fixed constant \(\alpha>1\), even when the target share is strictly positive.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateUnless P=NP, there is no polynomial time α- approximation to the Shapley value of a customer in a TSP game for any constant factor α > 1. We have therefore considered heuristic methods based on Monte Carlo sampling (Mann and Shapley 1960; Castro, Gomez, and Tejada 2009), and on approximating the cost of the optimal route.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 given by its support: the list of \(\tau\) customer types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
The input also specifies \(m\) locations including a depot \(0\), each type's nondepot location, a target \(t^\star\in T\), and finite strictly positive binary-rational travel costs \(d_{ij}\) for distinct locations. Symmetry and the triangle inequality are not assumed; let \(L\) be the total input bit length.
For \(S\subseteq T\), let \(C(S)\) be the minimum cost of a tour starting and ending at the depot and visiting each distinct location represented in \(S\) exactly once, with no other locations visited; \(C(\varnothing)=0\).
Generate an ordering by repeatedly selecting one remaining type \(t\) with probability \(\mu_t/\sum_{u\text{ remaining}}\mu_u\), then removing it. Let \(P_t\) contain the types preceding \(t\), and define the cohort share \(\Phi_t(\mu)=\mathbb E[C(P_t\cup\{t\})-C(P_t)]\).
For a fixed constant \(\alpha>1\), an approximation \(\widehat\Phi\) must have the same sign as \(\Phi_{t^\star}\) and satisfy \(|\Phi_{t^\star}|/\alpha\leq|\widehat\Phi|\leq\alpha|\Phi_{t^\star}|\), returning zero when the share is zero.
Does approximating \(\Phi_{t^\star}(\mu)\) admit a deterministic algorithm polynomial in \(m,\tau,L\) for some constant \(\alpha>1\), or is it NP-hard for every fixed constant \(\alpha>1\)?
For discrete TSP games, constant-factor approximation of an individual Shapley value is reported NP-hard for every constant factor greater than one; the full study treats general travel costs, without a triangle-inequality assumption ([Aziz et al.](https://users.cecs.anu.edu.au/~charlesg/shapley_2016.pdf)).
No complexity result for the specified mass-biased cohort rule was verified.
For every fixed constant \(\alpha>1\), approximating the specified cohort share is \(\mathrm{NP}\)-hard. This holds even when every type occupies a distinct location, all masses are dyadic rationals, all travel costs are positive integers, and the target share is strictly positive.
The proof below establishes hardness directly for the mass-biased rule.
Fix \(\alpha>1\), and choose a fixed integer \(A>\alpha\). We reduce from directed Hamiltonian cycle, which is \(\mathrm{NP}\)-complete. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
Let \(G\) be a loopless directed graph with vertex set \(\{1,\ldots,n\}\), where \(n\geq2\). For each vertex \(i\), introduce three locations \(a_i,b_i,c_i\), and introduce one additional location \(z\). Designate \(b_1\) as depot \(0\).
There is one type at every nondepot location. The target type occupies \(z\). Thus \(m=3n+1\) and \(\tau=3n\). Let \(S\) denote the \(r=3n-1\) ordinary types, excluding the target.
Set \(M=3n+4A^2\). Assign cost \(1\) to precisely these directed arcs:
Every other arc between distinct locations has cost \(M\). Call the cost-\(1\) arcs *cheap*.
All costs are finite, strictly positive, and binary-encoded integers.
The cyclic sequence
\(c_1,b_1,a_1,c_2,b_2,a_2,\ldots,c_n,b_n,a_n,c_1\)
uses only cheap arcs. Rotating it to start at \(b_1\) gives a permitted depot tour through all ordinary locations, of cost \(3n\).
Conversely, every permitted tour for \(S\) has exactly \(3n\) arcs. Each costs at least \(1\), so its cost is at least \(3n\). This proves the claim.
Consider a cheap tour through all locations, regarded cyclically so that the depot has a predecessor and successor.
The only cheap arcs entering or leaving \(b_i\) connect it to \(a_i\) or \(c_i\). Its predecessor and successor must be distinct: otherwise the tour would revisit that neighbor. Consequently, every triple occurs consecutively in one of two orientations:
Contract each triple to one block.
A forward block exits at \(c_i\). Its cheap connections to another block enter some \(a_j\), forcing that next block to be forward. Its other possible cheap exit goes to \(z\), whose successor is \(a_1\), again entering a forward block.
A backward block exits at \(a_i\). Its only cheap connection outside its triple is \(a_i\to c_{i+1}\), forcing the next block to be backward.
Because \(z\) is visited, its predecessor is some \(c_i\) and its successor is \(a_1\). Both corresponding blocks are forward. Following the contracted tour therefore forces every block to be forward.
Every connection between consecutive forward blocks represents an arc of \(G\). The connection through \(z\) has the form \(c_i\to z\to a_1\), and its existence likewise means that \(i\to1\) belongs to \(G\). Thus the cyclic order of the blocks is a directed Hamiltonian cycle of \(G\).
Conversely, suppose \(G\) has a directed Hamiltonian cycle. Replace each vertex \(i\) by its forward triple \(a_i,b_i,c_i\). For the cycle arc entering vertex \(1\), replace the corresponding connection \(c_i\to a_1\) by \(c_i\to z\to a_1\). Every resulting arc is cheap. Rotating the cycle to start at depot \(b_1\) gives the required tour. This proves the equivalence.
Define \(D=C(S\cup\{z\})-C(S)\).
If \(G\) is Hamiltonian, Claim 2 gives a tour with \(3n+1\) cheap arcs. No tour can cost less, since every arc costs at least \(1\). Therefore \(D=1\).
If \(G\) is not Hamiltonian, every full tour contains an arc of cost \(M\). Hence \(C(S\cup\{z\})\geq M\), giving \(D\geq M-3n=4A^2\).
Set \(B=(3n+1)M\). For every coalition \(U\), we have \(0\leq C(U)\leq B\): a nonempty coalition has a permitted tour with at most \(3n+1\) arcs, each costing at most \(M\). Consequently, every target marginal has absolute value at most \(B\), and \(|D|\leq B\).
Choose nonnegative integers \(h,k\) satisfying \(2^h\geq2r\) and \(2^k\geq16rB\), taking the smallest such integers. Define \(a=2^{-h}\) and \(\varepsilon=a\,2^{-k}\).
Choose one ordinary type \(w\), and assign masses
\(\mu_z=\varepsilon,\qquad \mu_u=a\ \text{for }u\in S\setminus\{w\},\qquad \mu_w=1-(r-1)a-\varepsilon.\)
These masses sum to \(1\). Since \(\varepsilon\leq a\) and \(ra\leq1/2\), we have \(\mu_w\geq1/2\). Thus every mass is positive, every ordinary mass is at least \(a\), and all masses are dyadic rationals.
We next justify the needed ordering probability.
Pairwise ordering lemma. Under the specified sequential rule, for distinct types \(x,y\),
\(\Pr(x\text{ precedes }y)=\mu_x/(\mu_x+\mu_y).\)
To prove this, let \(R\) be the other remaining types, and let \(p_R\) denote the probability that \(x\) precedes \(y\). With \(W=\mu_x+\mu_y+\sum_{u\in R}\mu_u\), conditioning on the next selection gives
\(p_R=\mu_x/W+\sum_{u\in R}(\mu_u/W)p_{R\setminus\{u\}}.\)
For \(R=\varnothing\), the asserted formula follows directly from the selection rule. Substituting the formula for smaller sets into this recurrence proves it for \(R\), because
\(p_R=\mu_x/W+\bigl(W-\mu_x-\mu_y\bigr)\mu_x/\bigl(W(\mu_x+\mu_y)\bigr)=\mu_x/(\mu_x+\mu_y).\)
Now let \(E\) be the event that the target is last. By the union bound and the lemma,
\(\Pr(E^c)\leq\sum_{u\in S}\varepsilon/(\varepsilon+\mu_u)\leq r\varepsilon/a=r\,2^{-k}\leq1/(16B).\)
Write \(X=C(P_z\cup\{z\})-C(P_z)\), so that \(\Phi_z=\mathbb E[X]\).
On \(E\), every ordinary type precedes the target, so \(X=D\). On \(E^c\), the bounds \(|X|\leq B\) and \(|D|\leq B\) imply \(|X-D|\leq2B\). Therefore
\(|\Phi_z-D|\leq\mathbb E[|X-D|]\leq2B\Pr(E^c)\leq1/8.\)
Combining this with the full-coalition gap yields:
In particular, the target share is strictly positive in both cases. The argument allows arbitrary negative marginal contributions on exceptional orderings; their total effect is covered by the error bound.
Suppose an algorithm returns an approximation satisfying the task’s requirements.
If \(G\) is Hamiltonian, then
\(\widehat\Phi\leq\alpha\Phi_z\leq9\alpha/8<9A/8<2A.\)
If \(G\) is not Hamiltonian, then
\(\widehat\Phi\geq\Phi_z/\alpha\geq(4A^2-1/8)/\alpha>(4A^2-1/8)/A=4A-1/(8A)>2A.\)
Thus comparing the output with the integer threshold \(2A\) decides whether \(G\) has a directed Hamiltonian cycle.
For fixed \(\alpha\), the integer \(A\) is fixed. We have \(M=O(n)\), \(B=O(n^2)\), and \(h,k=O(\log n)\). Every mass and cost therefore has \(O(\log n)\) bits, and the complete constructed instance has polynomial length, with \(m=3n+1\) and support size \(\tau=3n\).
The construction and decoding form a polynomial-time reduction using one approximation call. Hence the requested approximation is \(\mathrm{NP}\)-hard for every fixed \(\alpha>1\); a deterministic algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned question. It establishes \(\mathrm{NP}\)-hardness for every fixed constant \(\alpha>1\), including instances with dyadic masses, positive integer costs, distinct type locations, and a strictly positive target share.
I found no major or minor mathematical issues. No additional clarification is needed.
The cited source problem is directed Hamiltonian cycle: deciding whether a directed graph has a directed cycle visiting every vertex exactly once. Its \(\mathrm{NP}\)-completeness is the standard result cited from [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). Restricting to loopless graphs with \(n\geq2\) does not affect hardness: loops cannot participate in such a Hamiltonian cycle, and smaller instances are trivial.
The constructed instance satisfies the task’s input requirements:
The construction uses directed costs, as permitted by the task. It makes no symmetry or triangle-inequality assumption.
Claim 1 is correct.
The displayed cycle visits all \(3n\) ordinary locations, including the depot, exactly once cyclically. Its within-triple arcs and its connections \(a_i\to c_{i+1}\) are all cheap. Rotating the cycle to begin at the depot yields a valid tour of cost \(3n\).
Every permitted tour for this coalition has exactly \(3n\) arcs, each costing at least \(1\). Thus the lower bound matches the exhibited tour:
\[ C(S)=3n. \]
Claim 2 is correct in both directions.
For each \(b_i\), the only cheap incoming and outgoing neighbors are \(a_i\) and \(c_i\). A full tour has \(3n+1\geq7\) locations, so its predecessor and successor at \(b_i\) must be distinct. Therefore the three locations form a consecutive forward or backward block. This remains valid for the block containing the depot because the proof treats the tour cyclically.
The orientation argument accounts for every possible cheap connection:
Following the single contracted tour from \(z\) consequently forces every block to be forward. Each interblock connection then corresponds to an arc of \(G\), including the connection through \(z\), which corresponds to an arc entering vertex \(1\). The resulting cyclic block order visits each vertex of \(G\) exactly once.
Conversely, replacing each vertex of a Hamiltonian cycle by its forward triple and inserting \(z\) into the connection entering vertex \(1\) produces precisely the claimed cheap full tour.
No mixed-orientation cheap full tour escapes this argument.
The stated gap follows.
In a Hamiltonian instance, a full tour has \(3n+1\) arcs and achieves cost \(3n+1\), giving \(D=1\).
In a non-Hamiltonian instance, every full tour contains an expensive arc. The weaker lower bound used in the proof, \(C(S\cup\{z\})\geq M\), is valid because all remaining costs are positive. Hence
\[ D\geq M-3n=4A^2. \]
The bound \(0\leq C(U)\leq B\), with \(B=(3n+1)M\), is valid for every coalition. The empty coalition has cost zero; every nonempty coalition admits a tour with at most \(3n+1\) arcs, each costing at most \(M\).
Since both costs in a marginal lie in \([0,B]\), their difference has absolute value at most \(B\). This correctly handles potentially negative marginals.
The masses also satisfy all required conditions. From \(2^h\geq2r\), one has \(ra\leq1/2\); from \(k\geq0\), one has \(0<\varepsilon\leq a\). Therefore
\[ \mu_w=1-(r-1)a-\varepsilon\geq1-ra\geq1/2. \]
The masses sum exactly to one, every ordinary mass is at least \(a\), and every mass is a positive dyadic rational.
The pairwise ordering lemma is proved rigorously by induction on the number of other remaining types.
The recurrence includes the immediate selection of \(x\), the zero contribution from selecting \(y\), and all selections of other types. Its substitution and simplification are correct.
The event that \(z\) is not last is exactly the union of events that \(z\) precedes some ordinary type. Thus the union bound gives
\[ \Pr(E^c) \leq\sum_{u\in S}\frac{\varepsilon}{\varepsilon+\mu_u} \leq r\,2^{-k} \leq\frac1{16B}. \]
No independence assumption is needed.
On \(E\), the predecessor coalition is exactly \(S\), so \(X=D\). On its complement, \(|X-D|\leq2B\). Consequently,
\[ |\Phi_z-D|\leq2B\Pr(E^c)\leq\frac18. \]
Both resulting bounds are correct:
\[ \frac78\leq\Phi_z\leq\frac98 \]
in the Hamiltonian case, and
\[ \Phi_z\geq4A^2-\frac18 \]
otherwise. In particular, both cases have strictly positive shares.
Because the share is positive, the task’s approximation guarantee gives positive output and the usual multiplicative inequalities.
In the Hamiltonian case,
\[ \widehat\Phi\leq\frac{9\alpha}{8}<\frac{9A}{8}<2A. \]
In the non-Hamiltonian case,
\[ \widehat\Phi \geq\frac{4A^2-1/8}{\alpha} >\frac{4A^2-1/8}{A} =4A-\frac1{8A} >2A. \]
All inequalities hold for the chosen integer \(A>\alpha>1\). The threshold therefore separates every permitted approximation output, with no equality ambiguity.
For fixed \(\alpha\), \(A\) is fixed, \(M=O(n)\), \(B=O(n^2)\), and \(h,k=O(\log n)\). The residual mass \(\mu_w\) also has an \(O(\log n)\)-bit dyadic representation. Encoding all directed costs therefore produces an instance of polynomial length, and construction and threshold comparison require polynomial time.
The single approximation call yields the claimed hardness reduction.
The write-up is verifiable as submitted. Its claimed restrictions and complexity conclusion are supported by the argument; no repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.