Answer: All limits exist. Their additive approximation is deterministically computable in time polynomial in \(m,\tau,L,1/\varepsilon\) for every fixed \(k\).
Theorem 5.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Shapley value can be computed in polyno- mial time on matching games defined over any class of graphs having bounded treewidth.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite compatibility graph \(H=(T,F)\) with \(\mathrm{tw}(H)\le k\) and rational population shares \(\mu_t>0\) summing to \(1\), form \(G_q\) for each \(q\) with \(q\mu_t\in\mathbb{Z}\) by creating \(q\mu_t\) agents of each type and joining agents whose types are adjacent in \(H\). For each type \(t\), let \(\phi_{q,t}\) be the Shapley payoff of any one of its agents. Does \(\lambda_t=\lim_{q\to\infty}\phi_{q,t}\) exist, and, for fixed \(k\), can it be approximated within additive error \(\varepsilon\) in time polynomial in \(|T|\), the bit length of \(\mu\), and \(1/\varepsilon\)?
A society is given by its support: a nonempty list \(T\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
The input includes a finite simple undirected compatibility graph \(H=(T,F)\) with \(\operatorname{tw}(H)\le k\). Write \(m=|F|\), and let \(L\) be the total binary input length, including a rational accuracy parameter \(0<\varepsilon<1\).
For each positive integer \(q\) satisfying \(q\mu_t\in\mathbb Z\) for every \(t\), construct \(G_q\) with \(q\mu_t\) agents of type \(t\). Two agents are adjacent exactly when their distinct types are adjacent in \(H\); agents of the same type are never adjacent.
A coalition's worth is the maximum matching cardinality in its induced subgraph, with each matched edge worth \(1\). Let \(\phi_{q,t}\) be the standard Shapley payoff of one type-\(t\) agent, without rescaling. Limits are taken through all admissible integers \(q\). An additive approximation to \(\lambda\) means estimates satisfying \(\max_{t\in T}|\widehat\lambda_t-\lambda_t|\le\varepsilon\).
Do all limits \(\lambda_t=\lim_{q\to\infty}\phi_{q,t}\) exist? If so, is their additive approximation computable deterministically in time polynomial in \(m,\tau,L,1/\varepsilon\) for every fixed \(k\), or is this approximation problem NP-hard for some fixed \(k\)?
Exact Shapley computation for finite unweighted matching games is polynomial-time when the agent graph has bounded treewidth. [Greco, Lupia and Scarcello](https://www.ijcai.org/proceedings/2017/0145.pdf)
Convergence of Shapley payoffs under replication is known for assignment games and their two-sided multiple-partners generalization. [Luo, Pérez-Castrillo and Sun](https://iris.unive.it/retrieve/9dfb939f-0faf-41bf-951e-0bc0124e79e4/1-s2.0-S0022053124000760-main.pdf)
The search located no result settling the stated approximation problem for general compatibility graphs encoded by support and rational masses.
All the limits exist. For every fixed \(k\), their additive approximation is computable deterministically in time polynomial in \(m,\tau,L,1/\varepsilon\).
The proof has two parts. First, the limiting payoff is an expectation over Gaussian perturbations of a fractional matching dual. Second, bounded treewidth permits deterministic approximation of this expectation by compressing distributions of a constant number of boundary costs.
For an integer capacity vector \(n\in\mathbb Z_{\geq 0}^{T}\), let \(V(n)\) be the matching cardinality in the corresponding agent graph. Equivalently,
\(\displaystyle V(n)=\max\left\{\sum_{e\in F}b_e:\ b_e\in\mathbb Z_{\geq 0},\ \sum_{e\ni t}b_e\leq n_t\ \text{for every }t\right\}.\)
Indeed, a matching determines these edge multiplicities. Conversely, feasible integer multiplicities can be realized by allocating distinct agents of each type to its incident edges and pairing the allocated agents along each compatibility edge.
For real capacities \(x\in\mathbb R_{\geq 0}^{T}\), define the fractional relaxation
\(\displaystyle f(x)=\max\left\{\sum_{e\in F}b_e:\ b_e\geq 0,\ \sum_{e\ni t}b_e\leq x_t\ \text{for every }t\right\}.\)
Flooring every edge variable of an optimal fractional solution gives a feasible integer solution. Consequently,
\[\displaystyle 0\leq f(n)-V(n)\leq m. \tag{1}\]
The bound is independent of the capacities.
The primal linear program is feasible and has a finite optimum. Strong linear programming duality therefore gives
\[\displaystyle f(x)=\min_{y\in P}x\cdot y,\qquad P=\{y\in[0,1]^T:\ y_u+y_v\geq 1\ \text{for every }uv\in F\}. \tag{2}\]
To justify the upper bounds in this dual, first take the usual dual with \(y_t\geq 0\). Replacing each coordinate exceeding \(1\) by \(1\) preserves every edge constraint and cannot increase the objective when \(x\geq 0\).
Lemma 1. Every vertex of \(P\) has coordinates in \(\{0,\tfrac12,1\}\).
Proof. Let \(y\) be a vertex, and consider the coordinates strictly between \(0\) and \(1\). On these coordinates, form the graph of tight edge constraints \(y_u+y_v=1\).
A tight edge cannot connect a strictly fractional coordinate to a coordinate equal to \(0\) or \(1\): the equality would force the other coordinate to be \(1\) or \(0\), respectively.
If a connected component of the tight-edge graph were bipartite, increase its coordinates on one bipartition class by a sufficiently small amount and decrease those on the other class by the same amount. The opposite perturbation is also feasible. Tight constraints remain equalities, and all other constraints remain satisfied for sufficiently small perturbations. This contradicts extremality.
Thus every such component contains an odd cycle. Alternating the equations \(y_u+y_v=1\) around that cycle forces its coordinates to equal \(\tfrac12\), and connectivity propagates this value throughout the component. ∎
Define the finite set
\(\displaystyle \mathcal D=P\cap\{0,\tfrac12,1\}^{T}.\)
Since a linear function on the compact polytope \(P\) attains its minimum at a vertex, Lemma 1 implies
\[\displaystyle f(x)=\min_{y\in\mathcal D}x\cdot y\qquad(x\geq 0). \tag{3}\]
Let
\[\displaystyle c=f(\mu),\qquad \mathcal A=\{y\in\mathcal D:\ \mu\cdot y=c\}. \tag{4}\]
The set \(\mathcal A\) is nonempty.
Let \(Z=(Z_t)_{t\in T}\) have independent coordinates
\(\displaystyle Z_t\sim N(0,\mu_t).\)
Define
\[\displaystyle Y(Z)=\operatorname*{arg\,min}_{y\in\mathcal A}Z\cdot y. \tag{5}\]
This minimizer is almost surely unique. For distinct \(y,y'\), the difference \(Z\cdot(y-y')\) is a centered normal random variable with variance
\(\displaystyle \sum_{t\in T}\mu_t(y_t-y'_t)^2>0,\)
because every \(\mu_t\) is positive. A finite union of the corresponding equality hyperplanes has probability zero.
We will prove
\[\displaystyle \boxed{\lambda_t=\mathbb E[Y_t(Z)]\quad\text{for every }t\in T.} \tag{6}\]
Fix an admissible \(q\), and write \(n_t=q\mu_t\). Assign independent uniform priorities in \([0,1]\) to all agents. Their priority order is a uniform random permutation.
Conditioning on the priority \(p\) of a distinguished type-\(t\) agent, its predecessor counts are independent and satisfy
\(\displaystyle X_v\sim\operatorname{Bin}(n_v-\mathbf 1_{\{v=t\}},p).\)
The definition of the Shapley value therefore gives
\[\displaystyle \phi_{q,t}=\int_0^1\mathbb E[V(X+e_t)-V(X)]\,dp. \tag{7}\]
Here \(e_t\) is the type-\(t\) unit vector.
Adding one agent increases matching cardinality by either \(0\) or \(1\): removing the new agent from a matching removes at most one matched edge. Thus the integrand lies in \([0,1]\).
Put \(r(n)=V(n)-f(n)\). By (1), \(r(n)\in[-m,0]\).
Condition on all coordinates of \(X\) except \(X_t\). If \(B\sim\operatorname{Bin}(n_t-1,p)\), then
\[\displaystyle \left|\mathbb E[r(X+e_t)-r(X)]\right|\leq m\,d_{\mathrm{TV}}(B+1,B). \tag{8}\]
For a binomial distribution, unimodality gives
\(\displaystyle d_{\mathrm{TV}}(B+1,B)=\max_j\Pr(B=j).\)
For each fixed \(p\in(0,1)\), this maximum tends to zero as \(n_t\) tends to infinity. One explicit justification is Fourier inversion:
\(\displaystyle \Pr(B=j)\leq\frac1{2\pi}\int_{-\pi}^{\pi}|1-p+pe^{i\theta}|^{n_t-1}\,d\theta.\)
Using
\(\displaystyle |1-p+pe^{i\theta}|^2=1-4p(1-p)\sin^2(\theta/2)\)
and \(\sin(|\theta|/2)\geq|\theta|/\pi\) for \(|\theta|\leq\pi\), the integral is bounded by a constant times
\(\displaystyle ((n_t-1)p(1-p))^{-1/2}.\)
Since \(\mu_t>0\), \(n_t\) tends to infinity along every admissible sequence. Hence, for fixed \(p\in(0,1)\),
\[\displaystyle \mathbb E[V(X+e_t)-V(X)]-\mathbb E[f(X+e_t)-f(X)]\longrightarrow 0. \tag{9}\]
This smoothing step is necessary: a bounded error in function values alone would not imply convergence of their discrete marginal differences.
Fix \(p\in(0,1)\), and set
\(\displaystyle a_q=\sqrt{qp(1-p)},\qquad Z_q=\frac{X-qp\mu}{a_q}.\)
The coordinatewise binomial central limit theorem, together with independence, gives
\[\displaystyle Z_q\ \xrightarrow{\mathrm d}\ Z. \tag{10}\]
The missing distinguished agent changes the type-\(t\) mean by \(-p\), which disappears after division by \(a_q\).
For any \(y\in\mathcal D\),
\[\displaystyle X\cdot y=qp\,\mu\cdot y+a_qZ_q\cdot y. \tag{11}\]
If \(y\notin\mathcal A\), its strictly positive primary gap \(\mu\cdot y-c\) contributes an amount of order \(q\). On a bounded set of perturbations, this eventually dominates the perturbation term, which has order \(\sqrt q\). Thus such a candidate cannot minimize either \(X\cdot y\) or \((X+e_t)\cdot y\).
Among candidates in \(\mathcal A\), the minimizer is selected by \(Z_q\cdot y\). Away from their equality hyperplanes, their perturbation gaps are bounded below on compact sets. Multiplication by \(a_q\) makes these gaps eventually exceed \(1\), whereas adding \(e_t\) changes each candidate cost by \(y_t\in[0,1]\). Consequently, the same candidate minimizes both expressions, and
\(\displaystyle f(X+e_t)-f(X)=Y_t(Z_q)\)
on every compact set separated from those hyperplanes, for all sufficiently large \(q\).
The excluded region can have arbitrarily small limiting probability: first choose a sufficiently large bounded region, then sufficiently small neighborhoods of the finitely many hyperplanes. Their Gaussian probabilities tend to zero because the relevant Gaussian linear forms are nondegenerate. By (10), the same probability bounds hold asymptotically for \(Z_q\).
Finally, (3) implies \(0\leq f(X+e_t)-f(X)\leq 1\). These bounds and the preceding argument yield
\[\displaystyle \mathbb E[f(X+e_t)-f(X)]\longrightarrow\mathbb E[Y_t(Z)]. \tag{12}\]
Combining (9) and (12) proves convergence of the integrand in (7), for every \(p\in(0,1)\), to the same quantity. Dominated convergence applied to (7) proves (6).
This establishes existence for all finite compatibility graphs, without a treewidth assumption. It also gives
\[\displaystyle 0\leq\lambda_t\leq 1,\qquad \sum_{t\in T}\mu_t\lambda_t=f(\mu), \tag{13}\]
because every selected vector belongs to \(\mathcal A\).
Fix a total lexicographic order on \(\mathcal D\), to resolve ties whenever perturbations are discrete. For any perturbation vector \(z\), let \(Y(z)\) be the first minimizer of \(z\cdot y\) over \(\mathcal A\).
We use Kolmogorov distance
\(\displaystyle d_K(U,W)=\sup_x|\Pr(U\leq x)-\Pr(W\leq x)|.\)
For any rational \(0<\eta<1\), one can deterministically construct independent, finitely supported rational random variables \(\widetilde Z_t\) such that
\[\displaystyle d_K(\widetilde Z_t,Z_t)\leq\eta, \tag{14}\]
with support sizes and construction time polynomial in \(L,1/\eta\). Their atoms can all have a common dyadic denominator, and their probabilities can all have a common rational denominator.
Here is an explicit construction justification.
Start with a standard normal variable. Truncate its distribution to \([-R,R]\), conditioning on that interval, where \(R=\lceil4/\eta\rceil\). Chebyshev’s inequality bounds the removed probability by \(R^{-2}\leq\eta/16\). Round to a rational grid of mesh at most \(\eta/16\). Since the standard normal density is bounded by \(1\), these two operations give Kolmogorov error at most \(\eta/8\), using \(O(\eta^{-2})\) atoms.
Approximate the resulting cell probabilities by nonnegative rationals, with total variation error at most \(\eta/8\), and normalize them exactly. These probabilities are ratios of integrals of \(e^{-x^2/2}\) over bounded intervals. The integrand and its derivative are bounded; Riemann quadrature with polynomially many subdivisions, and rational approximations of the exponential, suffice for the required accuracy. Rounding the unnormalized weights to one common dyadic denominator before normalization gives a common rational denominator afterward.
For type \(t\), multiply the atoms by \(\sqrt{\mu_t}\), then round them to one common dyadic grid with atom error at most \(\sqrt{\mu_t}\eta/4\). An atom perturbation of this size adds at most \(\eta/4\) to Kolmogorov distance from the corresponding normal distribution.
The required binary precision is polynomial in \(L+\log(1/\eta)\): a positive input rational satisfies \(\mu_t\geq 2^{-L}\), so no reciprocal of a small mass appears in the number of grid points. Square roots can be approximated by rational bisection. This proves (14) and the stated complexity properties.
Condition on every perturbation coordinate except \(z_v\). Divide \(\mathcal A\) into the at most three groups specified by \(y_v\in\{0,\tfrac12,1\}\).
Within each group, the minimizing vector and its tie resolution are independent of \(z_v\). The global choice is therefore the lower envelope of at most three affine functions of \(z_v\), with distinct slopes. Their pairwise intersections give at most three exceptional points. Thus \(Y_t(z)\), as a function of \(z_v\), is constant on at most four intervals and at most three singleton points.
If two scalar distributions have Kolmogorov distance at most \(\eta\), their probabilities on any interval or singleton differ by at most \(2\eta\). Since \(Y_t\in[0,1]\), replacing one coordinate distribution changes its conditional expected value by at most \(14\eta\).
Replace the coordinates one at a time. Independence permits the preceding conditional argument even when other coordinates have already been discretized. Hence
\[\displaystyle \left|\mathbb E[Y_t(\widetilde Z)]-\lambda_t\right|\leq14\tau\eta. \tag{15}\]
The remaining task is to approximate the expectation over this finite product distribution without enumerating all its outcomes.
A boundary-cost vector will have \(r\) feasible states. Write it as \(C=(C_1,\ldots,C_r)\), and attach labels \(\ell=(\ell_1,\ldots,\ell_r)\in\{0,\tfrac12,1\}^r\).
For each unordered pair of states, use the difference coordinate \(C_a-C_b\). There are
\(\displaystyle d_r=\binom r2\)
such coordinates.
Lemma 2. Let \((C,\ell)\) have a finite rational distribution, and let \(0<\delta<1\). There is a deterministic compression to at most
\[\displaystyle 3^r(4/\delta+2)^{d_r} \tag{16}\]
representative atoms, preserving total probability, with the following guarantee.
For every subset \(A\) of feasible states and every fixed outside-cost vector \(h\), couple an original atom and its representative. The minimizing state of \(C_a+h_a\) over \(a\in A\), with a fixed tie rule, changes with probability at most \(2d_r\delta\). The entire label vector is preserved by the coupling.
Proof. For one difference coordinate, sort its distinct values and their marginal masses. Put every value of mass exceeding \(\delta\) in a singleton bin. Between these values, greedily group consecutive values into bins of mass at most \(2\delta\).
There are \(O(1/\delta)\) bins. Every completed nonsingleton bin, except a possible final bin before a heavy singleton or at the end, has mass exceeding \(\delta\); and there are at most \(1/\delta\) heavy singletons. In particular, \(4/\delta+2\) bins suffice.
Do this separately for all \(d_r\) difference coordinates. Partition the original atoms by their coordinate bins and by their entire label vector. In every nonempty cell, choose one original atom as representative and transfer the cell’s total mass to it. This gives (16).
For any threshold, a difference coordinate can change its comparison with that threshold only within the bin containing the threshold. A heavy singleton cannot change the comparison; every other such bin has mass at most \(2\delta\).
The winner of \(C_a+h_a\) is determined by the pairwise comparisons
\(\displaystyle C_a-C_b\ \mathrel{\lessgtr}\ h_b-h_a,\)
including equality. A union bound over the difference coordinates bounds the probability that any required comparison changes by \(2d_r\delta\). The labels were included in the cell partition, so they are preserved exactly. ∎
In particular, when the final payoff is the preserved label of the winning state, compression changes its expectation by at most \(2d_r\delta\). The same bound holds when each winning state determines a fixed outside payoff in \([0,1]\).
Fix \(k\). A width-\(k\) tree decomposition can be found deterministically in polynomial time under the promised treewidth bound. This is precisely the hypothesis covered by [Bodlaender’s fixed-treewidth algorithm](https://epubs.siam.org/doi/10.1137/S0097539793251219).
Convert it to a rooted nice decomposition with empty root and leaves, introduce, forget, and binary join nodes. Let \(M\) be its number of nodes; this is polynomial in \(m,\tau\), with constants depending on \(k\).
For a bag \(B\), a boundary state assigns a value in \(\{0,\tfrac12,1\}\) to each vertex of \(B\). There are at most
\[\displaystyle s=3^{k+1} \tag{17}\]
states. Check each edge constraint in bags containing its endpoints.
Assign a vertex’s objective contribution when that vertex is forgotten. Every vertex is forgotten exactly once: the bags containing it form a connected subtree. At a join, the two child interiors are disjoint, so their perturbations are independent.
We run the following algorithm separately for each target type \(t\).
For every feasible boundary state \(a\), first compute the minimum primary interior cost
\(\displaystyle p_a=\min\sum_{v\text{ in the interior}}\mu_v y_v.\)
These are deterministic rational values.
At a forget node, retain only extensions attaining the minimum primary cost for the parent state. At a join, add child primary costs. At an introduce node, restrict to compatible child states.
This is ordinary finite-state dynamic programming. Its correctness follows by splitting an assignment into its boundary values and interior choices. In particular, conditional on a boundary state, a globally primary-optimal assignment must use a primary-optimal interior assignment: replacing a nonoptimal interior while keeping the boundary fixed would strictly reduce the total primary objective.
Thus these transitions describe precisely the configurations in \(\mathcal A\), without listing them.
Let every discrete perturbation atom have denominator \(D\), so \(\widetilde z_v=a_v/D\). Fix an ordering of the types, and let \(i(v)\) be the position of \(v\). Put
\(\displaystyle B_0=3^\tau,\qquad d_v=2y_v\in\{0,1,2\}.\)
Use the integer objective
\[\displaystyle J(y)=\sum_{v\in T}\left(B_0a_vd_v+3^{\tau-i(v)}d_v\right). \tag{18}\]
The first part is \(B_0\) times the integer \(2D\,\widetilde z\cdot y\). The second part is the base-three code of the assignment, lying between \(0\) and \(B_0-1\). Therefore minimizing \(J\) is exactly equivalent to minimizing \(\widetilde z\cdot y\) and then resolving ties lexicographically.
For every feasible state \(a\), store:
If \(t\) is outside the interior, use label \(0\); its actual value will be supplied when it is forgotten or by the outside continuation.
At a forget node, combine the child message distribution with the independent finite perturbation distribution of the forgotten vertex. At a join, combine the independent child distributions. Perform the finite-state minimizations exactly, and then apply Lemma 2 to the resulting joint cost-and-label distribution.
This point requires more than a local dynamic programming error estimate.
Start with the exact finite-product computation. Insert compressions one at a time in postorder. When inserting a compression at a node, its descendants may already be compressed, but its ancestors have not yet been compressed.
Condition on all outside messages and perturbations. They are independent of the message being compressed. Because the ancestors still perform exact minimizations, the entire outside continuation has the following form:
If \(t\) is in the node’s interior, the output is its stored label for the winning state. Otherwise, the outside continuation determines its label from that state. Both descriptions depend on the interior message only through the winning boundary state and, when relevant, the stored label.
Lemma 2 therefore bounds the change in the conditional expected output by
\(\displaystyle 2\binom s2\delta.\)
Integrating over the outside randomness gives the same unconditional bound. Telescoping over the postorder insertion of all \(M\) compressions yields
\[\displaystyle \left|\widehat\lambda_t-\mathbb E[Y_t(\widetilde Z)]\right|\leq2M\binom s2\delta. \tag{19}\]
At the empty root, \(\widehat\lambda_t\) is computed exactly as the expectation of its stored label.
Choose
\(\displaystyle \eta=\frac{\varepsilon}{64\tau},\qquad d_*=\max\{1,\binom s2\},\qquad \delta=\frac{\varepsilon}{16Md_*}.\)
Equations (15) and (19) give, for every type,
\[\displaystyle |\widehat\lambda_t-\lambda_t|\leq14\tau\eta+2M\binom s2\delta\leq\frac{7\varepsilon}{32}+\frac{\varepsilon}{8}=\frac{11\varepsilon}{32}<\varepsilon. \tag{20}\]
It remains to verify the claimed running time.
For fixed \(k\), both \(s\) and \(\binom s2\) are constants. By (16), every compressed distribution has support size at most
\(\displaystyle R_*=3^s(4/\delta+2)^{\binom s2},\)
which is polynomial in \(M,1/\varepsilon\). A forget transition combines at most \(R_*\) message atoms with a polynomial number of unary perturbation atoms. A join combines at most \(R_*^2\) pairs. Compression only requires sorting difference coordinates and aggregating rational probabilities.
The numerical magnitudes cause no hidden exponential running time:
All calculations after discretization are exact integer or rational operations on numbers of polynomial bit length. Repeating the computation for all \(\tau\) target types adds only a polynomial factor.
Therefore the total deterministic running time is
\(\displaystyle \operatorname{poly}_k(m,\tau,L,1/\varepsilon),\)
where the polynomial’s exponent may depend on the fixed treewidth bound.
Every replication limit exists and is given by the Gaussian selection formula (6). For every fixed support-treewidth bound, the compression algorithm computes all limits to the requested additive accuracy in deterministic time polynomial in \(m,\tau,L,1/\varepsilon\).
The argument uses the treewidth of the support graph directly; it does not require the replicated agent graphs to have bounded treewidth.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the task, with two minor formal qualifications. It establishes existence of every replication limit and a deterministic additive approximation algorithm whose running time is polynomial in the stated parameters for every fixed treewidth bound.
I found no false central step, missing substantive lemma, or obstruction to the compression error argument.
The integer optimization correctly describes matchings in the replicated graph. Feasible edge multiplicities can be realized because each type has enough distinct agents to allocate to its incident edges. This uses exactly the stipulated adjacency between compatible, distinct types.
Flooring a fractional solution preserves all capacity constraints and loses at most one unit per support edge. Thus the capacity-independent bound in (1) is valid, including when some capacities vanish or the graph has no edges.
The fractional program is feasible and bounded. Its usual dual has nonnegative coordinates and the stated edge inequalities. Capping coordinates at \(1\) preserves feasibility and cannot increase the objective for nonnegative capacities, so (2) follows.
Lemma 1 is correct. A strictly fractional coordinate cannot have a tight edge to an integral coordinate. A bipartite component of the fractional tight-edge graph admits the two opposite sufficiently small perturbations described, including when the component is an isolated vertex. Finiteness of the constraints ensures that slack constraints remain satisfied. A nonbipartite component contains an odd cycle, which forces all its coordinates to \(1/2\).
Consequently, minimizing over \(\mathcal D\) gives the fractional optimum, and \(\mathcal A\) is finite and nonempty.
Conditioning on the distinguished agent’s uniform priority gives independent binomial predecessor counts with the stated parameters. Equation (7) therefore represents the standard, unrescaled Shapley payoff.
The matching marginal is between \(0\) and \(1\). For the residual \(r\), its range has length at most \(m\), which justifies the factor \(m\), rather than \(2m\), in (8) under the usual total variation convention.
The identity between the total variation distance of a binomial law and its unit translate and the binomial’s largest atom follows from unimodality. The Fourier estimate is also valid: the stated trigonometric inequality yields a Gaussian integral bound of the required order for fixed \(p\in(0,1)\).
Since every mass is positive, every \(n_t\) tends to infinity through admissible replication sizes. Thus (9) follows. The proof correctly avoids inferring marginal convergence from the bounded function-value error alone.
The covariance in (10) is correct. Dividing each binomial variance by \(qp(1-p)\) gives the limiting variance \(\mu_v\). The distinguished agent’s missing contribution changes its coordinate mean by only \(-p\), which vanishes after normalization. Independence gives the joint normal limit.
Distinct candidates in \(\mathcal A\) have a nondegenerate Gaussian cost difference because every mass is positive. Hence the Gaussian minimizer is almost surely unique.
The exclusion of candidates outside \(\mathcal A\) is justified: there are finitely many candidates, their positive primary gaps are fixed, and on bounded perturbation sets the primary cost separation grows faster than the perturbation term.
On compact sets separated from the equality hyperplanes, the winning candidate in \(\mathcal A\) has a uniformly positive perturbation gap. Eventually its scaled gap exceeds the largest possible change caused by adding \(e_t\). The same candidate then minimizes both objectives, giving the asserted fractional marginal.
The exceptional regions can have arbitrarily small asymptotic probability. Together with bounded fractional marginals, this proves (12). Dominated convergence in (7) establishes the limit through all admissible integers.
Equation (13) follows directly from selection inside \(\mathcal A\). Isolated types and the edgeless graph cause no failure of this reasoning.
The truncation and rounding estimates have sufficient slack. The stated truncation radius gives removed probability at most \(\eta/16\), and the grid size is polynomial in \(1/\eta\).
The probability approximation can be achieved using the indicated quadrature and rational exponential evaluations with polynomially many operations and polynomial precision. Scaling by a small mass requires more binary precision, but does not require a number of atoms proportional to its reciprocal. The lower bound on positive input masses justifies this distinction.
The conditional lower-envelope argument is correct. Within each fixed-slope group, the selected candidate is independent of the varied coordinate. Three affine functions have at most three pairwise intersection points. Allowing four intervals and three singleton points therefore gives a valid upper bound.
Kolmogorov distance controls the probability difference of each such interval or singleton by \(2\eta\). The bound \(14\eta\) per coordinate and the telescoping bound (15) follow. Independence remains available during successive replacements.
Minor issue — parameter bookkeeping. The general construction claim states polynomial time in \(L,1/\eta\) for an arbitrary rational \(\eta\), without including its encoding length. For the actual choice of \(\eta\), that encoding length is polynomially bounded by the task parameters, so this does not affect the algorithm.
Minimum clarification: Include the binary encoding length of \(\eta\) in the general construction-time statement, or explicitly restrict that statement to the parameter used in Section 6.
The binning argument is valid. Heavy values are preserved exactly; every other bin has marginal mass at most \(2\delta\). The stated bin-count bound accommodates bins interrupted by heavy singletons.
Choosing representatives separately within each label-and-bin cell preserves the entire label vector. For a fixed comparison threshold, a comparison can change only within the corresponding nonsingleton bin. The union bound over pairwise differences therefore gives the stated error bound. Preserving all pairwise comparisons also preserves the winner under the fixed tie rule.
Minor issue — empty subsets. Lemma 2 quantifies over every subset \(A\), including the empty subset, for which a minimizing state is undefined. Its dynamic programming application uses nonempty eligible sets, so this does not invalidate any approximation bound.
Minimum clarification: Restrict the lemma to nonempty subsets \(A\).
The cited decomposition theorem applies. For each fixed bound, it finds a decomposition of that width whenever the promised bound holds. This is the guarantee stated in [Bodlaender’s article](https://epubs.siam.org/doi/10.1137/S0097539793251219).
The boundary state count is correct. Charging vertex objectives when vertices are forgotten avoids duplication, including at joins. The connectedness condition for bags containing a vertex ensures its unique forget event.
The primary optimization is valid: an interior assignment that is not primary-optimal for its boundary state cannot belong to a globally primary-optimal assignment. The described transitions therefore retain exactly the relevant primary-optimal choices.
The integer secondary objective correctly encodes lexicographic tie resolution. Its perturbation component is an integer multiple of \(B_0\), and the assignment code lies between \(0\) and \(B_0-1\). Thus the code cannot reverse a strict perturbation-cost comparison.
The label bookkeeping is sufficient. At a join, a target in the interior belongs to exactly one child interior; a target still on the boundary receives its value when forgotten.
The postorder argument addresses the main potential difficulty correctly.
When a compression is inserted, all ancestors still perform exact minimizations. After conditioning on outside data, each eligible boundary state has a fixed outside cost. The interior message affects the final choice through its boundary costs and, when applicable, its preserved labels.
The outside data are independent of the compressed message because their forgotten vertex sets are disjoint. Earlier compressions preserve this separation.
Consequently, Lemma 2 applies conditionally with the same uniform error bound. Averaging and telescoping over the insertions justify (19). No independence between boundary-state costs is assumed or needed.
The constants in (20) check out:
\[ 14\tau\eta=\frac{7\varepsilon}{32}, \qquad 2M\binom{s}{2}\delta\leq\frac{\varepsilon}{8}. \]
Their sum is \(11\varepsilon/32<\varepsilon\).
For fixed treewidth, the state count and the number of difference coordinates are constants. The compressed support bound is therefore polynomial in \(M,1/\varepsilon\). Forget transitions and joins enumerate only polynomially many combinations.
The numerical claims are also sound. Primary costs, dyadic perturbations, integer tie codes, and probability denominators have polynomial binary lengths. Probability multiplication follows disjoint forgotten vertex sets, and compression only aggregates probabilities. Repeating the computation for every target adds a polynomial factor.
The algorithm thus meets the requested additive accuracy and deterministic running-time bound. The two minor qualifications above require only changes to the statements, with no new mathematics.
⟨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.