Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already for weighted mass MC-nets.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor a game represented as embedded MC-nets or weighted MC-nets, computing the SS-value is #P-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational type distribution \(\mu\) and a finite mass-rule description of a partition-function game, form \(g_q\) by taking \(q\mu_t\) identical agents of each type \(t\), evaluating the rules on coalition masses normalized by \(q\), and computing their finite SS-values. Under the promise that \(A_t=\lim_{q\to\infty,\ q\mu\in\mathbb{Z}_{\ge 0}^{\tau}}\sum_{i:\,\mathrm{type}(i)=t}\mathrm{SS}_i(g_q)\) exists, compute a rational estimate of \(A_t\) within additive error \(\epsilon\).
A society is specified by its support: \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
A mass pattern is a conjunction of positive tests \(x_t\geq a_t\), where \(0<a_t\leq\mu_t\) is binary rational, and negative tests \(x_t=0\); positive and negative type sets are disjoint, and every pattern has at least one positive test. Rule weights are signed binary rationals.
The input uses either embedded or weighted mass MC-nets. An embedded rule \((\alpha_1\mid\alpha_2,\ldots,\alpha_k)\to c\) contributes \(c\) to \((S,P)\) exactly when \(S\) satisfies \(\alpha_1\) and each remaining pattern is satisfied by some coalition in \(P\setminus\{S\}\); witnesses need not be distinct.
A weighted rule consists of nonempty blocks of pairs \((\alpha\to c)\). It is satisfied by \(P\) when its coalitions can be assigned to blocks so that every pattern has a satisfying coalition in its block. A satisfied rule contributes to \(S\in P\) the sum of weights of all its pattern occurrences satisfied by \(S\), counted once regardless of witnessing assignments. Game values sum contributions across rules.
For each positive integer \(q\) with \(q\mu\in\mathbb Z_{\geq0}^{\tau}\), form \(N_q\) with \(q\mu_t\) distinct agents of type \(t\). Coalitions are nonempty, \(P\) partitions \(N_q\), and patterns are evaluated on \(x_t(S)=|S\cap N_{q,t}|/q\); weights remain fixed, defining \(g_q\).
Define \(\mathrm{SS}_i(g_q)\) as the expected payoff in this process: agents leave the grand coalition in a uniformly random order; after \(k\) previous departures, the departing agent joins each existing outside coalition \(T\) with probability \(|T|/(k+1)\), or starts a new coalition with probability \(1/(k+1)\). Its payoff is the value of the remaining coalition before departure minus its value after departure, using the respective partitions; an empty remaining coalition has value zero.
Given a designated support type \(t\) and binary-rational \(0<\epsilon<1\), promise that \(A_t=\lim_{q\to\infty,\ q\mu\in\mathbb Z_{\geq0}^{\tau}}\sum_{i\in N_{q,t}}\mathrm{SS}_i(g_q)\) exists as a finite real number. Compute a rational \(\widehat A_t\) with \(|\widehat A_t-A_t|\leq\epsilon\). Let \(m\) be the syntactic size of the rule description and \(L\) the total binary input length, including \(\epsilon\).
Is this promised additive-estimation problem solvable deterministically in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time Turing reductions?
Exact computation of an individual finite SS-value is \(\#\mathrm P\)-hard for both embedded and weighted MC-nets. [Skibski](https://arxiv.org/html/1909.01769v2).
The literature search located no complexity result for the specified mass-rule replication limit with additive estimation.
The promised problem is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions when weighted mass MC-nets are permitted. Hardness holds with one weighted rule, equal dyadic type masses, no negative tests, nonnegative weights, and fixed error \(\epsilon=1/8\).
I interpret the two representations as permitted alternatives in the input. Under that interpretation, the weighted subclass settles the stated worst-case question. The proof does not establish hardness for the embedded-only restriction.
The reduction below proves existence of the required limits on every oracle instance. It does not rely on finite-player exact-computation hardness.
Fix an integer \(B\geq2\), a dyadic number \(d\) satisfying \(0<d<1/B\), and a power of two \(\tau\). Give every support type mass \(1/\tau\).
For every nonempty set \(C\) of types, define the pattern
\(\displaystyle \alpha_C=\bigwedge_{s\in C}\left(x_s\geq\frac d\tau\right).\)
Consider one weighted rule with \(B\) blocks, each containing exactly one occurrence \(\alpha_{C_b}\to c_b\). Require
\(\displaystyle C_1=\{t\},\qquad c_1=c>0,\qquad c_b=0\quad(2\leq b\leq B).\)
Define the monotone Boolean function
\(\displaystyle h(z)=\bigvee_{b=1}^{B}\ \bigwedge_{s\in C_b}z_s,\qquad z\in\{0,1\}^{\tau}.\)
For a type \(s\), let \(\phi_s(h)\) be its pivotal probability: put the types in uniformly random order, change their coordinates from zero to one in that order, and record the unique coordinate that first makes \(h\) true. Such a coordinate exists because all clauses are nonempty, so \(h(0)=0\) and \(h(1)=1\).
At an admissible replication size \(q\), every type has \(q/\tau\) agents. Pattern satisfaction is equivalent to requiring at least
\(\displaystyle a_q=\left\lceil\frac{qd}{\tau}\right\rceil\)
agents of each specified type.
Because every block contains one pattern, the weighted rule is satisfied precisely when there is a matching assigning distinct satisfying coalitions to its \(B\) blocks. Once these witnesses have been assigned, all additional coalitions can be assigned arbitrarily. Thus its value to the remaining coalition \(R\) is
\(\displaystyle c\,\mathbf1\{|R\cap N_{q,t}|\geq a_q\}\,\mathbf1\{\text{the rule is satisfied}\}.\)
This uses exactly the contribution convention in the question.
Ignore agent types temporarily. After \(k\) departures, the outside partition follows the Chinese restaurant process with parameter one: an existing table of size \(a\) receives the next agent with probability \(a/(k+1)\), and a new table starts with probability \(1/(k+1)\). This is also the cycle-partition process of uniform random permutations. [McCullagh, *Chinese restaurant process*](https://www.stat.uchicago.edu/~pmcc/pubs/partition10.pdf).
Here are the properties needed below, with proofs.
Number tables by order of creation and let \(A_i(k)\) be table \(i\)'s size after \(k\) departures.
The first table's size \(X_k=A_1(k)\) is uniform on \(\{1,\ldots,k\}\). This follows by induction from the transition probability \(X_k/(k+1)\). Moreover,
\(\displaystyle \mathbb E\left[\frac{X_{k+1}}{k+2}\,\middle|\,X_k\right]=\frac{X_k}{k+1}.\)
Consequently \(X_k/(k+1)\) is a bounded martingale. Its almost-sure limit has the uniform distribution on \((0,1)\), since the distributions of \(X_k/(k+1)\) converge to that distribution.
Conditional on the next departure not joining the first table, the probabilities for all other tables and for starting a new table are those of another parameter-one Chinese restaurant process. Its random choices can be generated independently of the first-table membership process. Iterating this decomposition gives independent uniform random variables \(U_i\) and limiting frequencies
\(\displaystyle V_i=U_i\prod_{\ell<i}(1-U_\ell),\qquad \frac{A_i(k)}k\longrightarrow V_i\quad\text{almost surely}.\)
The remaining mass after the first \(M\) frequencies is
\(\displaystyle 1-\sum_{i=1}^{M}V_i=\prod_{i=1}^{M}(1-U_i).\)
Its expectation is \(2^{-M}\). Since these products decrease, their limit is zero almost surely. Hence \(\sum_iV_i=1\).
Coordinatewise convergence and this equality imply convergence in \(\ell^1\): first control finitely many coordinates, then bound both tails by their total masses. In particular,
\[\displaystyle \sup_{0\leq k\leq q}\sum_i\left|\frac{A_i(k)}q-\frac{k}{q}V_i\right|\longrightarrow0 \quad\text{almost surely}.\tag{1}\]
Indeed, for large \(k\) the expression is \((k/q)\|A(k)/k-V\|_1\); the finitely many smaller \(k\) contribute at most \(2k/q\).
Let \(Z_1>Z_2>\cdots\) be the frequencies \(V_i\) in decreasing order. Every \(Z_j\) is positive. The strict inequalities hold almost surely: for two birth-ordered frequencies, conditioning on the uniforms other than the later frequency's final uniform factor makes equality have probability zero.
Each \(V_i\) has an atomless distribution. Since every \(Z_j\) equals some \(V_i\), a countable union shows
\[\displaystyle \Pr(Z_j=r)=0\qquad\text{for every fixed }r>0.\tag{2}\]
Conditional on the untyped seating process, any encountered coalition of size \(a\) consists of a uniformly random \(a\)-element subset of the agents. The same assertion holds for the remaining coalition.
The sampling-without-replacement Hoeffding bound therefore gives, for every type \(s\),
\(\displaystyle \Pr\left(\left|\frac{|S\cap N_{q,s}|}{q}-\frac{|S|}{q\tau}\right|>\eta\right) \leq 2e^{-2\eta^2q}. \)
There are at most \((q+1)^2\) encountered coalitions, counting their occurrences at different stages. A union bound gives a simultaneous failure probability at most
\[\displaystyle 2\tau(q+1)^2e^{-2\eta^2q}.\tag{3}\]
Taking \(\eta=q^{-1/4}\), this probability tends to zero. Consequently, uniformly along the process, a coalition whose normalized size exceeds \(d\) by a fixed positive amount satisfies every \(\alpha_{C_b}\); one whose size is below \(d\) by a fixed positive amount satisfies none.
The concentration event is invariant under every permutation of type labels. This symmetry will retain the information carried by ties at the threshold.
Put \(j=B-1\) and define
\(\displaystyle p_{B,d}=\Pr\left(Z_j>\frac d{1-d}\right). \)
We prove the following limit identity for every support type \(s\):
\[\displaystyle \lim_{q\to\infty,\ \tau\mid q} \sum_{i\in N_{q,s}}\mathrm{SS}_i(g_q) = c\,p_{B,d}\bigl(\mathbf1\{s=t\}-\phi_s(h)\bigr). \tag{4}\]
In particular, the designated type's limit is
\[\displaystyle A_t=c\,p_{B,d}\bigl(1-\phi_t(h)\bigr).\tag{5}\]
Write \(F_q(k)\) for rule satisfaction after \(k\) departures.
Outside-coalition edges in the matching problem only appear: outside coalitions grow, and all tests are positive. The remaining coalition's edge to each block can disappear at most once. Thus there are at most \(B\) edge-deletion stages.
Between those stages, matching feasibility is nondecreasing. Hence \(F_q\) has at most \(B\) downward changes and at most \(B+1\) upward changes. The indicator that the remaining coalition satisfies \(\alpha_{\{t\}}\) has at most one change.
It follows that the total variation of the remaining coalition's value is at most
\[\displaystyle c(2B+2).\tag{6}\]
The absolute sum of payoffs to any one type is bounded by the same quantity, uniformly in \(q\). Therefore events of probability tending to zero have a vanishing contribution to expected type payoffs.
Fix an untyped realization with distinct limiting frequencies and
\(\displaystyle Z_j>\frac d{1-d}.\)
Set \(u_*=d/Z_j\). Then \(u_*<1-d\). At departure fraction \(u_*\), equation (1) describes the following limiting configuration:
All inequalities except the distinguished table's equality are strict. By continuity, choose a small interval about \(u_*\), lying strictly before \(1-d\), throughout which those other coalitions remain separated from \(d\).
Equations (1) and (3) imply that, with probability tending to one, throughout this interval the remaining coalition and the \(B-2\) larger outside tables satisfy every pattern, while all smaller outside tables satisfy none.
There are therefore \(B-1\) coalitions that can fill any block. The rule becomes satisfied exactly when the distinguished table satisfies at least one block pattern. Its satisfaction condition is precisely \(h\), evaluated on that table's type-threshold indicators.
Every type crosses its threshold \(a_q\) within this interval. These crossing times are distinct, because one departure adds only one type to the table. Their order is uniform:
Conditional on those events and the untyped process, permuting type labels permutes the threshold-crossing order. Thus all orders have equal probability. The type causing activation is consequently distributed according to \(\phi_s(h)\).
At activation the remaining coalition's value changes from zero to \(c\), so the activating agent receives payoff \(-c\).
After this interval, the \(B-1\) larger outside tables satisfy every pattern. Whenever the remaining coalition still satisfies \(\alpha_{\{t\}}\), assign it to block one and assign those outside tables to the other blocks. Its value therefore remains \(c\) until its type-\(t\) count drops below \(a_q\). That departure has type \(t\) and receives payoff \(+c\).
Now suppose
\(\displaystyle Z_j<\frac d{1-d}.\)
Whenever the remaining coalition can still satisfy its type-\(t\) threshold, its departure fraction is at most \(1-d+o(1)\), by (3). At those times the \(j\)-th largest outside table is separated below \(d\), by (1).
For sufficiently accurate concentration, at most \(j-1=B-2\) outside coalitions can satisfy any block pattern. Including the remaining coalition gives at most \(B-1\) possible witnesses, insufficient for the \(B\) blocks. Thus the remaining coalition's value is zero throughout.
The excluded boundary \(Z_j=d/(1-d)\) has probability zero by (2). For almost every untyped realization, the preceding geometric separation holds for all sufficiently accurate approximations.
The high-probability events used above are type-permutation invariant. On their activation part, the pivotal order is therefore exactly uniform; on their nonactivation part, all payoffs are zero. Their probabilities converge respectively to \(p_{B,d}\) and \(1-p_{B,d}\).
Combining this with the uniform bound (6) proves (4). In particular, every instance in this family satisfies the finite-limit promise.
For each \(B\), choose
\(\displaystyle d=2^{-\lceil\log_2(4B)\rceil},\qquad \rho=\frac d{1-d}.\)
Then
\(\displaystyle \frac1{8B}<d\leq\frac1{4B},\qquad \rho<\frac1{2B}.\)
Let \(C_\rho\) count limiting frequencies greater than \(\rho\). Thus \(p_{B,d}=\Pr(C_\rho\geq j)\), where \(j=B-1\), and \(C_\rho\leq8B\).
We calculate a factorial moment. For a uniform permutation of \(q\) elements, the expected number of ordered distinct cycles with specified lengths \(\ell_1,\ldots,\ell_j\) is
\(\displaystyle \frac1{\ell_1\cdots\ell_j}\)
when their sum is at most \(q\), and zero otherwise. To verify this, choose ordered disjoint supports, put a cycle on each support, and permute the remaining elements:
\(\displaystyle \frac{q!}{(q-\sum_i\ell_i)!\prod_i\ell_i!} \cdot\prod_i(\ell_i-1)! \cdot\frac{(q-\sum_i\ell_i)!}{q!} =\frac1{\prod_i\ell_i}. \)
The uniform-permutation description follows directly by inserting the next element either as a singleton cycle or after one of the existing elements, each of the \(k+1\) choices having probability \(1/(k+1)\).
Summing the cycle calculation and taking its Riemann-sum limit gives
\[\displaystyle \mathbb E\binom{C_\rho}{j} = \frac1{j!} \int_{\substack{x_i>\rho\\ \sum_i x_i\leq1}} \frac{dx_1\cdots dx_j}{x_1\cdots x_j}. \tag{7}\]
The passage to expectations is justified by limiting-frequency convergence, absence of frequencies equal to \(\rho\), and the uniform bound on the count.
The integration domain contains \([1/(2B),1/B]^j\), so
\(\displaystyle \mathbb E\binom{C_\rho}{j}\geq\frac{(\log2)^j}{j!}. \)
Since \(\binom{C_\rho}{j}\leq2^{8B}\mathbf1\{C_\rho\geq j\}\),
\[\displaystyle p_{B,d}\geq\frac{(\log2)^j}{j!\,2^{8B}} \geq2^{-(B^2+9B)}=:p_0. \tag{8}\]
For the last inequality, use \(\log2\geq1/2\), \(j\leq B\), and \(j!\leq B^B\leq2^{B^2}\).
Thus the unknown factor in (5) is positive and has a sufficiently large polynomial-bit lower bound.
Let \(G\) be a simple graph on \(n\geq1\) vertices. Write \(a_k\) for its number of independent sets of cardinality \(k\).
For each \(r\in\{0,\ldots,n\}\), introduce a designated type \(t\), vertex types \(v_1,\ldots,v_n\), and auxiliary types \(y_1,\ldots,y_r\). Define
\[\displaystyle h_r(z)= z_t \ \vee\ \bigvee_{\ell=1}^{r}z_{y_\ell} \ \vee\ \bigvee_{\{u,v\}\in E(G)}(z_{v_u}\wedge z_{v_v}). \tag{9}\]
Realize this function using the weighted-rule family:
The duplicate singleton does not change \(h_r\), and ensures
\(\displaystyle B=|E(G)|+r+2\geq2.\)
Choose \(\tau\) as the smallest power of two at least \(\max\{n+r+1,B\}\); all remaining types are irrelevant to \(h_r\).
The designated type is pivotal exactly when the types preceding it contain no auxiliary type and their vertex set is independent. For a fixed independent set \(I\) of size \(k\), the probability that precisely \(I\) precedes \(t\), among the relevant types, is
\(\displaystyle \frac{k!(n+r-k)!}{(n+r+1)!}.\)
Irrelevant padded types do not affect the uniformly random induced order on relevant types. Consequently,
\[\displaystyle \phi_t(h_r)= \sum_{k=0}^{n}a_k\,\frac{k!(n+r-k)!}{(n+r+1)!}. \tag{10}\]
The factor \(p_{B,d}\) need not be computed analytically.
For a calibration instance, keep the same \(B,d,\tau,c\), but give the \(B\) blocks distinct singleton types, including the designated type \(t\). Only its block has weight \(c\).
Its Boolean function is the disjunction of those \(B\) types, so \(\phi_t=1/B\). Equations (5) give, respectively,
\[\displaystyle A=c\,p(1-\phi),\qquad A^{\mathrm{cal}}=c\,p(1-1/B), \tag{11}\]
where \(p=p_{B,d}\) and \(\phi=\phi_t(h_r)\).
Put
\(\displaystyle D=(2n+1)!,\qquad K=B^2+9B+\lceil\log_2D\rceil+4,\qquad c=2^K. \)
Make both oracle queries with \(\epsilon=1/8\). Normalize their returned estimates by \(c\), obtaining \(\widehat a,\widehat z\). Their normalized errors are at most
\(\displaystyle e=\frac1{8c}\leq\frac{p_0}{128D}.\)
Define
\(\displaystyle \widehat p=\frac{\widehat z}{1-1/B}, \qquad \widehat\phi=1-\frac{\widehat a}{\widehat p}. \)
Because \(B\geq2\),
\(\displaystyle |\widehat p-p|\leq2e,\qquad \widehat p\geq p_0/2.\)
Writing \(a=p(1-\phi)\), we have \(0\leq a\leq p\), and therefore
\[\displaystyle |\widehat\phi-\phi| \leq \frac{|\widehat a-a|+(a/p)|\widehat p-p|}{\widehat p} \leq\frac{6e}{p_0} <\frac1{4D}. \tag{12}\]
By (10), \(D\phi_t(h_r)\) is an integer: every factorial denominator in that formula divides \(D\). Rounding \(D\widehat\phi\) to the nearest integer thus recovers \(\phi_t(h_r)\) exactly.
This works for every permissible oracle response, not merely for a particular estimator.
The recovered quantities yield the rational linear system
\(\displaystyle \phi_t(h_r)=\sum_{k=0}^{n}M_{rk}a_k,\qquad M_{rk}=\frac{k!(n+r-k)!}{(n+r+1)!}, \quad 0\leq r,k\leq n. \)
We verify that its matrix is nonsingular.
The beta integral gives
\(\displaystyle M_{rk}=\int_0^1x^k(1-x)^{n-k}(1-x)^r\,dx.\)
Suppose \(b=(b_0,\ldots,b_n)\) lies in its kernel, and set
\(\displaystyle f(x)=\sum_{k=0}^{n}b_kx^k(1-x)^{n-k}.\)
Then \(\int_0^1f(x)(1-x)^r\,dx=0\) for every \(r\) from zero to \(n\). The polynomials \((1-x)^r\) span all polynomials of degree at most \(n\), including \(f\). Hence
\(\displaystyle \int_0^1f(x)^2\,dx=0,\)
so \(f\) is identically zero. For \(0<x<1\), division by \((1-x)^n\) gives
\(\displaystyle \sum_{k=0}^{n}b_k\left(\frac{x}{1-x}\right)^k=0.\)
This polynomial vanishes for all positive arguments, implying every \(b_k=0\). The matrix is nonsingular.
Exact rational linear algebra therefore recovers every \(a_k\). In particular, it decides whether \(G\) has an independent set of size at least any supplied threshold. Independent Set is \(\mathrm{NP}\)-complete, equivalently via complementation from Clique. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The reduction uses \(2(n+1)\) oracle queries. In every query:
The rational matrix entries and recovered quantities have polynomial bit length, so the subsequent arithmetic is polynomial-time. Equation (4) proves finite existence of every type's limit on every constructed instance, checking the promise rather than assuming it.
Thus the stated problem allowing weighted input is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. A deterministic algorithm polynomial in \(m,\tau,L\) for all permitted inputs would imply \(\mathrm P=\mathrm{NP}\).
The hardness comes from threshold ties and existential block assignment, which retain Boolean pivotal probabilities even though macroscopic coalition compositions concentrate. No claim about the embedded-only restriction follows from this reduction.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with one minor expositional gap. The argument establishes \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions for the promised problem allowing weighted inputs. I found no false central step or gap requiring new mathematics. The embedded-only restriction remains unclassified, as the prover explicitly acknowledges.
1. Scope and validity of the constructed instances
The weighted subclass suffices for the worst-case problem whose input permits either representation. The conclusion does not require hardness for each representation separately.
Every constructed pattern satisfies the task’s restrictions:
For equal masses \(1/\tau\), admissible replication sizes are exactly the positive multiples of \(\tau\). The integer threshold \(a_q=\lceil qd/\tau\rceil\) correctly implements the mass test, including replication sizes at which the threshold is not integral.
2. Weighted-rule semantics
The matching characterization is correct for the special case of one pattern occurrence per block. A coalition assigned to one block cannot witness a different block, so satisfying all blocks requires distinct witnessing coalitions. Conversely, a matching covering the blocks permits all remaining coalitions to be assigned arbitrarily.
Only the occurrence in block one has nonzero weight. Consequently, the remaining coalition’s value is exactly the displayed product of the designated-pattern indicator and global rule-satisfaction indicator. This correctly respects the task’s convention that contributions depend on satisfied occurrences, independently of the witnessing assignment.
The duplicate singleton block used later changes the matching requirement while leaving the Boolean disjunction unchanged. The proof correctly retains that change through its parameter \(B\).
3. Outside-coalition process and limiting frequencies
The seating probabilities agree exactly with the parameter-one Chinese restaurant process. The cited source also identifies this process with the cycle partition of uniform permutations. [McCullagh, *Random permutations and partition models*](https://www.stat.uchicago.edu/~pmcc/pubs/partition10.pdf).
The first-table calculation is correct:
The residual-process decomposition supports the independent uniform stick factors. The argument that the residual products decrease to zero almost surely is valid: their expectations tend to zero, and the products are bounded.
Coordinatewise convergence together with total limiting mass one justifies the claimed convergence in \(\ell^1\). The subsequent uniform-in-stage bound in equation (1) correctly separates large stages from finitely many small stages.
The claims about ranked frequencies also check out. Positivity and summability permit the decreasing ranking; pairwise equality has probability zero by the stated conditioning argument. Atomlessness of each birth-ordered frequency implies atomlessness of every ranked frequency through a countable union. Thus the boundary excluded in Section 3.4 really has probability zero.
4. Concentration of type compositions
Conditional on the seating process, coalition membership is determined by departure positions independently of the uniformly random agent order. Each encountered coalition is therefore a uniform sample without replacement of its stated size. The same reasoning applies to the remaining coalition.
The Hoeffding bound is correctly scaled. For a coalition of size \(a>0\), the sampling inequality gives exponent \(-2\eta^2q^2/a\), which is at most \(-2\eta^2q\), because \(a\leq q\). Empty coalitions have no deviation. The required sampling inequality is stated explicitly in Proposition 1.2 of [Bardenet and Maillard, *Concentration inequalities for sampling without replacement*](https://arxiv.org/pdf/1309.4029).
The bound of \((q+1)^2\) encountered coalition occurrences is sufficient, and no independence between occurrences is needed for the union bound. With \(\eta=q^{-1/4}\), the failure probability tends to zero.
For each fixed constructed instance, the resulting mass errors and threshold-rounding errors vanish. This justifies the pattern-satisfaction assertions for coalitions separated from mass \(d\).
5. Uniform variation bound
The monotonicity argument is correct:
Thus the claimed numbers of upward and downward feasibility changes are valid upper bounds. Multiplication by the designated-pattern indicator introduces at most one additional change, giving the stated bound \(c(2B+2)\).
The sum of absolute payoff increments attributed to any particular type is bounded by this total variation. Since \(B\) and \(c\) are fixed while taking the replication limit, this is sufficient to discard events whose probabilities tend to zero. The later growth of \(c\) across reduction instances does not invalidate this argument.
6. Activation and the pivotal-order identity
On the activation branch, the condition \(Z_{B-1}>d/(1-d)\) correctly puts the critical departure fraction strictly before \(1-d\). Distinct ranked frequencies provide the stated separation around the distinguished table.
Inside the chosen interval, the \(B-1\) universal witnesses consist of the remaining coalition and the \(B-2\) larger outside coalitions. Matching feasibility is therefore equivalent to the distinguished table satisfying at least one block pattern. This is exactly the Boolean function \(h\) evaluated on its threshold indicators.
The uniform-order argument survives the conditioning used in the proof. Equal type populations and equal thresholds give permutation symmetry, and the concentration event involves every type symmetrically. The geometric conditions concern only the untyped process. Conditional on these events, relabeling types permutes the distinct crossing order, so all type orders have equal probability.
The payoff signs are correct. Activation increases the remaining coalition’s value from zero to \(c\), producing payoff \(-c\). The subsequent designated-type threshold loss decreases it from \(c\) to zero, producing payoff \(+c\) to type \(t\).
Minor issue — Section 3.2, transition from local activation to the entire payoff path. The write-up explicitly analyzes activation inside the interval and persistence afterward, but does not explicitly exclude an earlier activation before the interval. That exclusion is needed when identifying the entire type payoff with the two described changes.
Minimum clarification: state that the remaining coalition’s value is zero at every preceding stage on the same good event, and identify how the already established outside-edge monotonicity and witness count imply this. This is a routine consequence of the existing argument, not a missing mathematical lemma.
The nonactivation branch is otherwise valid. Before the designated threshold fails, concentration restricts the departure fraction to at most \(1-d+o(1)\). The strict inequality for \(Z_{B-1}\) then leaves at most \(B-2\) outside coalitions capable of satisfying any block. Including the remaining coalition still gives too few witnesses.
Together with the null boundary and the variation bound, these arguments support equations (4) and (5), including existence of the promised finite limits.
7. Lower bound on the activation probability
The dyadic choice satisfies all stated inequalities, including \(d<1/B\) and \(\rho<1/(2B)\). The count bound \(C_\rho\leq8B\) is valid.
The ordered-cycle enumeration is correct, including repeated specified lengths: the cycles are ordered and have disjoint supports. Dividing the summed ordered count by \(j!\) correctly gives the binomial factorial moment.
The Riemann-sum passage is justified. For fixed \(B\), the integration variables are bounded away from zero, and the domain boundary has measure zero. Frequency convergence, absence of threshold atoms, and bounded counts justify passage to expectations.
The box \([1/(2B),1/B]^j\) lies in the integration domain because \(j=B-1\). Its integral produces the stated \((\log 2)^j/j!\) lower bound. The remaining estimates give the conservative but sufficient bound \(p_{B,d}\geq2^{-(B^2+9B)}\). No constant or range error was found.
8. Encoding independent-set counts
The characterization of designated-type pivotality is correct: immediately before \(t\), no auxiliary type may have appeared, and the preceding vertex types must form an independent set.
The probability for a particular independent set of size \(k\) is correctly counted as \(k!(n+r-k)!/(n+r+1)!\). Padded types do not affect the induced uniform order on relevant types. Equation (10) follows with the claimed coefficients.
The construction also covers edgeless graphs and \(r=0\): the duplicate designated singleton ensures \(B\geq2\).
9. Calibration, amplification, and rounding
The calibration instance is valid because \(\tau\geq B\), so distinct singleton types are available. Its designated pivotal probability is \(1/B\). Matching the parameters \(B,d,\tau,c\) correctly preserves the unknown activation factor.
All error estimates check out:
Every denominator \((n+r+1)!\) in equation (10) divides \(D=(2n+1)!\). Hence \(D\phi_t(h_r)\) is integral, and the stated rounding recovers it uniquely. The estimates do not require coordinated oracle responses.
10. Linear recovery and complexity conclusion
The beta-integral expression for the matrix entries is correct. The kernel argument is valid over the reals: the test polynomials span all degrees through \(n\), so orthogonality implies zero squared integral, and then the coefficient argument establishes trivial kernel.
The rational arithmetic has polynomial bit complexity. There are polynomially many entries, each with polynomial binary length; exact elimination therefore remains polynomial time.
The reduction uses \(2(n+1)\) queries. The stated bounds on \(B,\tau,K\), pattern size, and rational encoding lengths are correct. The finite-limit promise is established for both encoding and calibration instances.
Recovering the independent-set counts decides Independent Set, whose required hardness follows from Clique by graph complementation. The cited foundational result establishes Clique’s completeness. [Karp, *Reducibility among Combinatorial Problems*](https://people.seas.harvard.edu/~madhusudan/courses/Fall2020/Lectures/L19-after.pdf).
The adjudicated conclusion is therefore hardness for the permitted weighted subclass, with only the minor clarification identified above.
⟨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.