Answer: —
Theorem 3.1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet (N, v, C) be a TU game with coalition structure. Assume there is a stationary subgame perfect equilibrium in which all the proposals ³ a (S, i)γ i∈S,γ∈ΓS,i ´ S⊂N are accepted. Then, a (S) = ζS for all S ⊂N, where ¡ ζS¢ S⊂N is inductively defined as follows: ζ{i} i = ri for all i ∈N. Assume we know ζT ∈RT for all T à S. Then, ζS i = 1 |S| v (S) + X j∈C0q\i |S| ¯¯C0q ¯¯ ³ ζS\j i −ζS\i j ´ + X C0r∈CS\C0q |C0 r| ¯¯C0q ¯¯ X j∈C0q ζS\C0r j − X j∈C0r ζ S\C0q j for all i ∈C0 q ∈CS.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational population shares \(\mu_t\), a rational multilinear worth function \(W\), and two rationally specified coalition structures \(C^0,C^1\), form replica societies of size \(n\) along common denominator multiples, with \(v_n(S)=nW((|S_t|/n)_{t\in T})\), where \(S_t\) counts active members of type \(t\). Assuming each replica has an all-proposals-accepted stationary SPE, do the per-member type payoffs \(\zeta^{(n,C)}\) from Theorem 3.1 converge, and what is the complexity of computing their limits and deciding whether the specified merger raises its members’ payoffs?
A society is given by its support: \(T\), the list of \(\tau\) 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. The worth function \(W\) is a multilinear polynomial given by \(m\) explicitly listed monomials with signed rational coefficients, with \(W(0)=0\); \(L\) is the total input bit length.
Coalition structures \(C^0,C^1\) are specified by rational type–block masses \(\alpha^h_{tq}\geq0\), with \(\sum_q\alpha^h_{tq}=\mu_t\) and every block having positive total mass. Let \(p\) be the number of blocks of \(C^0\). Two designated blocks \(a,b\) merge to form \(C^1\), leaving all other memberships unchanged.
For every positive integer \(n\) divisible by a common denominator of all masses, form \(N_n\) with \(n\alpha^h_{tq}\) members in each type–block cell and \(v_n(S)=nW((|S_t|/n)_{t\in T})\). Write \(r_i=v_n(\{i\})\), and require \(v_n(S)+\sum_{i\in N_n\setminus S}r_i\leq v_n(N_n)\) for every \(S\subseteq N_n\).
Fix rational \(\rho\in[0,1)\). At an active set \(S\), independently choose a uniform proposer in each nonempty restricted block; each proposes a TU-feasible allocation, voted on sequentially by its other block members. Rejection restarts with \(S\) with probability \(\rho\), otherwise removes the proposer, who receives \(r_i\). If all blocks approve, select a block’s proposal with probability proportional to its active size; all outsiders vote on it. Rejection restarts with \(S\) with probability \(\rho\), otherwise removes the entire proposing block, whose members receive their singleton worths. Acceptance ends bargaining. Promise that every replica under both structures has a stationary SPE accepting every proposal in every active-set subgame.
Define the associated payoff recursively: \(\zeta_i^{\{i\}}=r_i\). For \(|S|>1\), let \(\mathcal B_S\) be the nonempty intersections of structure blocks with \(S\); for \(i\in B\in\mathcal B_S\),
\(\displaystyle \zeta_i^S=\frac1{|S|}\left[v_n(S)+\frac{|S|}{|B|}\sum_{j\in B\setminus\{i\}}(\zeta_i^{S\setminus\{j\}}-\zeta_j^{S\setminus\{i\}})+\sum_{D\in\mathcal B_S\setminus\{B\}}\left(\frac{|D|}{|B|}\sum_{j\in B}\zeta_j^{S\setminus D}-\sum_{j\in D}\zeta_j^{S\setminus B}\right)\right].\)
Let \(z^h_{tq}(n)\) be the average full-society payoff in a positive type–block cell, and \(z^h_t(n)=\mu_t^{-1}\sum_q\alpha^h_{tq}z^h_{tq}(n)\). If cell limits \(\ell^h_{tq}\) exist, strict merger gain means \(\sum_t(\alpha^0_{ta}+\alpha^0_{tb})\ell^1_{t,a\cup b}>\sum_t(\alpha^0_{ta}\ell^0_{ta}+\alpha^0_{tb}\ell^0_{tb})\).
Do all cell and type payoff sequences converge on every promised input?
If they converge, is computing their limits to additive error \(2^{-k}\) polynomial-time in \(m,\tau,p,L,k\), or NP-hard?
Is deciding strict merger gain in \(\mathrm P\), or NP-hard?
For finite societies, all-acceptance stationary SPE payoffs equal the displayed recursion; this is a characterization, not a complexity bound. [Vidal-Puga](https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/0501/0501005.pdf).
The finite value is joint-monotonic in convex games, meaning mergers weakly increase aggregate member payoffs. [Vidal-Puga](https://vidalpuga.webs.uvigo.es/papers/harsanyi.pdf). Calvo gives a finite-type continuum extension and computation formula for the Owen value, a different allocation rule; no result settling this replica-limit problem was located. [Calvo](https://www.uv.es/ecalvo/Emilio%20Calvo_archivos/Research/Research%20in%20Game%20theory_archivos/ContOwen.pdf).
All cell and type payoff sequences converge.
Computing their limits to the requested additive accuracy is $\mathrm{NP}$-hard. In fact, a single limit approximation with fixed accuracy $2^{-3}$ suffices to recover a SAT count in the reduction below. Every replica used in that reduction is a convex game, so the equilibrium promise is satisfied.
The general complexity of strict merger gain remains unresolved here. I prove that it is an exact rational comparison, independent of replica size, and give a polynomial-time decision criterion when all monomial coefficients are nonnegative.
Let $S$ be a nonempty finite active set, partitioned into its nonempty restricted blocks $\mathcal B_S$. Independently give each block $D$ an exponential clock of rate $|D|$.
For $B\in\mathcal B_S$, let $R_B$ be the union of the blocks whose clocks ring after $B$’s clock, and define
$$ Q_B(S)=\mathbb E\bigl[v(B\cup R_B)-v(R_B)\bigr]. $$
We assume $v(\varnothing)=0$, as holds for every replica in the task.
For each realized ordering of the blocks, their marginal contributions telescope. Consequently,
$$ \sum_{B\in\mathcal B_S}Q_B(S)=v(S). $$
Write $s=|S|$ and $b=|B|$. The first clock belongs to $D$ with probability $|D|/s$. Exponential memorylessness therefore gives
$$ Q_B(S)= \frac b s\bigl[v(S)-v(S\setminus B)\bigr] +\sum_{D\ne B}\frac{|D|}{s}Q_B(S\setminus D). $$
For $A\subseteq B$, define the reduced game
$$ g_B^S(A)=Q_A\bigl(A\cup(S\setminus B)\bigr), \qquad g_B^S(\varnothing)=0. $$
Here a nonempty $A$ is treated as one block of rate $|A|$, while the outside blocks retain their memberships.
Lemma. For $i\in B$, the payoff in the displayed recursion is the ordinary Shapley payoff of $i$ in $g_B^S$.
Proof. Denote that Shapley payoff by $\xi_i^S$. Shapley efficiency gives
$$ \sum_{i\in B}\xi_i^S=g_B^S(B)=Q_B(S). $$
We also need balanced contributions. For a game $g$ on a set $B$ of size $b$, define
$$ P_B(g)= \sum_{\varnothing\ne A\subseteq B} \frac{(|A|-1)!(b-|A|)!}{b!}\,g(A), \qquad P_\varnothing=0. $$
Comparing coefficients with the Shapley formula gives
$$ \phi_i(g)= P_B(g)-P_{B\setminus\{i\}}(g|_{B\setminus\{i\}}). $$
Subtracting these identities, for distinct $i,j\in B$, proves
$$ \phi_i(g)-\phi_j(g) = \phi_i(g|_{B\setminus\{j\}}) -\phi_j(g|_{B\setminus\{i\}}). $$
Deleting a member of $B$ restricts the same reduced game, because all outside blocks remain unchanged. Thus
$$ \xi_i^S-\xi_j^S = \xi_i^{S\setminus\{j\}}-\xi_j^{S\setminus\{i\}}, \qquad i\ne j. $$
Summing over $j\in B\setminus\{i\}$ yields
$$ \sum_{j\in B\setminus\{i\}} \bigl(\xi_i^{S\setminus\{j\}}-\xi_j^{S\setminus\{i\}}\bigr) =b\xi_i^S-Q_B(S). $$
Block efficiency also gives
$$ \sum_{j\in B}\xi_j^{S\setminus D}=Q_B(S\setminus D) $$
for $D\ne B$, and
$$ \sum_{D\ne B}\sum_{j\in D}\xi_j^{S\setminus B} =v(S\setminus B). $$
Substituting these identities into the supplied recursion produces
$$ \xi_i^S+ \frac{v(S)-v(S\setminus B)}s -\frac{Q_B(S)}b +\frac1{sb}\sum_{D\ne B}|D|Q_B(S\setminus D). $$
The last three terms vanish by the clock recurrence. The singleton case gives $v(\{i\})=r_i$. Induction on $|S|$ proves the lemma. $\square$
Fix one of the two structures and suppress its superscript. For each block $q$, write
$$ \alpha_q=(\alpha_{tq})_{t\in T}, \qquad \beta_q=\sum_t\alpha_{tq}>0. $$
Hold all outside blocks fixed and vary block $q$’s type-mass vector $x$. Put $s(x)=\sum_t x_t$. On the block indices, define
$$ V_x(J)= W\left( \mathbf 1_{\{q\in J\}}x+ \sum_{D\in J\setminus\{q\}}\alpha_D \right). $$
Its unanimity coefficients are
$$ d_H(x)= \sum_{J\subseteq H}(-1)^{|H|-|J|}V_x(J). $$
Inclusion–exclusion gives
$$ V_x(J)=\sum_{\varnothing\ne H\subseteq J}d_H(x). $$
For a unanimity game supported on $H$, a required block contributes precisely when its clock is first among the clocks in $H$. Its expected share is its rate divided by the sum of those rates. Accordingly, define
$$ F_q(x)=W(x)+ \sum_{\substack{H\ni q\\H\ne\{q\}}} \frac{s(x)} {s(x)+\sum_{D\in H\setminus\{q\}}\beta_D}\,d_H(x). $$
Every denominator in the sum has a strictly positive constant outside-block contribution. Hence $F_q$ is smooth on a neighborhood of the compact box
$$ K_q=\prod_{t\in T}[0,\alpha_{tq}]. $$
Moreover, $F_q(0)=0$: at $x=0$, the presence of block $q$ does not change any coalition worth, so every unanimity coefficient involving $q$ vanishes.
For an admissible replica size $n$ and a subset $A$ of block $q$, the reduced game satisfies the exact identity
$$ g_{q,n}(A)= nF_q\left((|A_t|/n)_{t\in T}\right). $$
Indeed, the worths scale by $n$, and all relevant clock rates scale by the same factor $n$, preserving their ordering distribution.
Theorem. For every positive cell $(t,q)$,
$$ \ell_{tq}=\lim_{n\to\infty}z_{tq}(n) = \int_0^1\partial_tF_q(u\alpha_q)\,du. $$
The limit is along admissible replica sizes.
Proof. Relabeling members within a type–block cell preserves both the game and the recursion. All members of that cell therefore have the same payoff.
Fix a type-$t$ member $i$ of block $q$. Generate a uniform random ordering of the block using independent uniform priorities. Conditional on $i$’s priority being $u$, each other member precedes $i$ independently with probability $u$.
Let $X_n(u)$ be the vector of preceding type counts divided by $n$. The finite representation lemma and the random-order Shapley formula give
$$ z_{tq}(n)= \int_0^1 \mathbb E\left[ n\bigl(F_q(X_n(u)+e_t/n)-F_q(X_n(u))\bigr) \right]du. $$
The mean and summed coordinate variances satisfy
$$ \mathbb E X_n(u)=u\alpha_q-\frac u n e_t, $$
$$ \mathbb E\|X_n(u)-u\alpha_q\|_2^2 \leq \frac{\beta_q}{4n}+\frac1{n^2}. $$
The variance bound follows by summing the variances of at most $n\beta_q$ independent Bernoulli indicators, each divided by $n$.
Since $F_q$ is smooth near $K_q$, its derivative $\partial_tF_q$ is Lipschitz on $K_q$, with some finite constant $M$. The fundamental theorem of calculus gives
$$ n\bigl(F_q(X+e_t/n)-F_q(X)\bigr) = \int_0^1\partial_tF_q(X+\theta e_t/n)\,d\theta. $$
All these segments lie in $K_q$. By Cauchy–Schwarz, the difference between the expected integrand and $\partial_tF_q(u\alpha_q)$ is at most
$$ M\left( \sqrt{\frac{\beta_q}{4n}+\frac1{n^2}}+\frac1n \right). $$
This bound is uniform in $u$ and tends to zero. Integration proves the claimed limit. $\square$
Applying the theorem to both structures settles convergence on every promised input. The proof itself requires no coefficient-sign or equilibrium assumption.
The type limits are the corresponding finite weighted sums:
$$ \ell_t^h= \frac1{\mu_t} \sum_{\substack{q\\\alpha_{tq}^h>0}} \alpha_{tq}^h\ell_{tq}^h. $$
Throughout, zero-mass cells are omitted from payoff sums.
Reduced-game efficiency gives, for every admissible $n$,
$$ \sum_{\substack{t\\\alpha_{tq}>0}} \alpha_{tq}z_{tq}(n)=F_q(\alpha_q). $$
Thus normalized block aggregates are exactly independent of replica size. Passing to the limits gives
$$ \sum_{\substack{t\\\alpha_{tq}>0}} \alpha_{tq}\ell_{tq}=F_q(\alpha_q). $$
Consequently, strict merger gain is precisely
$$ G= F^1_{a\cup b}(\alpha_a^0+\alpha_b^0) -F_a^0(\alpha_a^0)-F_b^0(\alpha_b^0)>0. $$
Every term here is rational by the definition of $F_q$. In particular, strict merger gain does not require comparing transcendental cell limits.
A useful alternative formula follows directly from multilinearity. For a monomial
$$ c_M\prod_{t\in M}x_t, $$
assign each type occurrence to a block by a function $f:M\to\{1,\ldots,p\}$. Let
$$ H_f=f(M), \qquad A_f=c_M\prod_{t\in M}\alpha_{t,f(t)}. $$
The monomial’s block-coalition game is the sum of unanimity games supported on $H_f$, with coefficients $A_f$. Hence
$$ F_q(\alpha_q)= \sum_M \sum_{\substack{f:M\to\{1,\ldots,p\}\\q\in H_f}} A_f\frac{\beta_q}{\sum_{D\in H_f}\beta_D}. $$
This supplies an exact finite algorithm. Its unrestricted enumeration can be exponential, which by itself establishes no hardness result.
I give a polynomial-size construction whose single distinguished-cell limit determines a SAT count.
The promise check uses the following known result: for the weighted proposer protocol in the question, a convex finite TU game admits a stationary SPE constructed with all proposals accepted in every active-set subgame, for every partition and every $\rho\in[0,1)$. This is the existence construction in Proposition 6.7 and its supporting proposal construction in [Vidal-Puga’s paper](https://vidalpuga.webs.uvigo.es/papers/harsanyi.pdf). Strict convexity is used for stronger uniqueness conclusions; the existence statement is for convex games.
Below, I verify convexity for every replica and every active-set restriction.
I use Valiant’s precise reduction: from a CNF formula $\Phi$, one can construct in polynomial time a matrix $A$ with entries in $\{-1,0,1,2,3\}$ such that
$$ \operatorname{perm}(A)=4^{t(\Phi)}\,\#\operatorname{SAT}(\Phi), $$
where $t(\Phi)$ is explicitly computable and polynomially bounded. For a formula with three literals per clause, it is nonnegative. This is Lemma 3.1 of [Valiant’s original paper](https://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/Valiant_permanent.pdf).
Pad $A$ by an identity block if necessary so that its dimension $d$ satisfies $d\geq2$. Padding preserves its permanent.
If $A$ has a zero row, its permanent is zero, and the displayed identity already establishes that $\Phi$ is unsatisfiable. This detectable case can use a fixed zero-encoding instance. We therefore describe the construction for matrices with no zero row.
Let $A(z)$ replace every entry $-1$ by $z$, leaving all other entries unchanged. Then $\operatorname{perm}(A(z))$ has degree at most $d$, and $A(-1)=A$.
For $h=1,\ldots,d+1$, define the Lagrange coefficients
$$ \lambda_h= \prod_{\substack{g=1\\g\ne h}}^{d+1} \frac{-1-g}{h-g}. $$
Polynomial interpolation gives
$$ \operatorname{perm}(A) = \sum_{h=1}^{d+1}\lambda_h\operatorname{perm}(A(h)). $$
Each $A(h)$ is nonnegative, and the $\lambda_h$ have polynomial bit length.
Choose rational numbers $\theta_0,\ldots,\theta_{d-1}$ satisfying
$$ \sum_{r=0}^{d-1}\frac{\theta_r}{1+j+r} = \begin{cases} 0,&1\leq j<d,\\ 1,&j=d. \end{cases} $$
These numbers exist uniquely. Reindexing $j=i+1$, the coefficient matrix has entries
$$ H_{ri}=\frac1{r+i+2}, \qquad 0\leq r,i<d. $$
For every nonzero real vector $y$,
$$ y^\mathsf T H y = \int_0^1 u\left(\sum_{r=0}^{d-1}y_ru^r\right)^2du>0. $$
The strict inequality holds because a nonzero polynomial cannot vanish throughout $(0,1)$. Thus $H$ is nonsingular.
The $\theta_r$ are computable exactly in polynomial time and have polynomial bit length. To see the size bound explicitly, clear denominators using the product of the $d^2$ entry denominators. That product has $O(d^2\log d)$ bits. Determinants and minors of the resulting integer matrix have polynomial bit length by the determinant expansion bound, and exact linear algebra computes the solution in polynomial time.
Choose a dyadic rational $\beta$ such that
$$ 0<2d\beta\leq\frac12. $$
The blocks of $C^0$ are:
Designate $q$ and $R$ for merger to form $C^1$.
Block $q$ contains only one type, denoted $t_*$. Its mass is $\beta$.
For every $h\in\{1,\ldots,d+1\}$ and row $i\in\{1,\ldots,d\}$, introduce a distinct type $u_{hi}$. Choose a dyadic rational $\delta>0$ such that
$$ \delta d(d+1)\max(3,d+1)<\frac{\beta}{2}. $$
Assign its masses by
$$ \alpha_{u_{hi},D_j}=\delta A(h)_{ij}. $$
Every such type has positive total mass because $A$ has no zero row. The total assigned mass in each column block is less than $\beta/2$. Fill its remaining mass with a separate filler type confined to that block.
Each $E_\ell$ contains one distinct marker type $e_\ell$ of mass $\beta$. The residual block contains one further filler type.
All masses are dyadic rationals of polynomial bit length, every listed type has positive mass, every block has positive mass, and the total mass is one. The support size and number of blocks are polynomial in $d$.
Define
$$ V(x)= \sum_{h=1}^{d+1}\sum_{r=0}^{d-1} c_{hr}\, x_{t_*} \left(\prod_{i=1}^d x_{u_{hi}}\right) \left(\prod_{\ell=1}^r x_{e_\ell}\right), $$
where an empty marker product equals one and
$$ c_{hr}= \frac{\lambda_h\theta_r}{\beta\,\delta^d\,\beta^r}. $$
This is a multilinear polynomial with $d(d+1)$ explicitly listed monomials and polynomial-size rational coefficients.
For a fixed $h$, let
$$ C_j(h)= \sum_{\substack{f:\{1,\ldots,d\}\to\{1,\ldots,d\}\\ |\operatorname{im}f|=j}} \prod_{i=1}^d A(h)_{i,f(i)}. $$
For the monomial indexed by $(h,r)$, an assignment of the row types uses $j$ column blocks and exactly $r$ marker blocks. Together with $q$, its required blocks all have mass $\beta$. Its contribution to $q$’s normalized aggregate is therefore
$$ c_{hr}\,\beta\delta^d\beta^r \sum_{j=1}^d\frac{C_j(h)}{1+j+r}. $$
Summing and using the defining equations for $\theta_r$ gives
$$ F_q^{V}(\alpha_q) = \sum_{h=1}^{d+1}\lambda_h C_d(h). $$
An assignment of $d$ rows that uses all $d$ columns is a bijection. Hence
$$ C_d(h)=\operatorname{perm}(A(h)). $$
We conclude that
$$ F_q^{V}(\alpha_q)=\operatorname{perm}(A). $$
This calculation is an identity; the exponentially many assignments are used only to prove it, not to construct the input.
The polynomial $V$ can have negative coefficients. Define
$$ K=1+\sum_{h,r}|c_{hr}| $$
and use the worth polynomial
$$ W(x)=K\sum_{\{s,t\}\subseteq T}x_sx_t+V(x). $$
All coefficients and the complete explicit monomial list still have polynomial total bit length.
For distinct types $s,t$ and $0\leq x_u\leq\mu_u$, every product occurring in $\partial_s\partial_tV(x)$ lies in $[0,1]$. Thus
$$ \partial_s\partial_tW(x) \geq K-\sum_{h,r}|c_{hr}|=1. $$
All monomials have degree at least two, so every replica singleton worth is zero.
Now fix any admissible replica and two distinct players $i,j$ outside a coalition $S$.
If they have the same type, multilinearity makes the discrete second difference zero. If their types are distinct, say $s,t$, then
$$ v_n(S\cup\{i,j\})-v_n(S\cup\{i\}) -v_n(S\cup\{j\})+v_n(S) = \frac1n\partial_s\partial_tW(x)\geq0, $$
where $x=(|S_u|/n)_{u\in T}$. The equality follows by taking the two increments of size $1/n$ in the multilinear polynomial.
Nonnegative discrete second differences imply increasing marginal contributions: add the players of a larger coalition one at a time. Therefore every replica game is convex. Its active-set restrictions remain convex.
Since singleton worths are zero, convexity also implies
$$ v_n(S\cup\{i\})-v_n(S)\geq v_n(\{i\})-v_n(\varnothing)=0. $$
Thus $v_n(S)\leq v_n(N_n)$, which verifies the required singleton-worth inequality.
The finite convex-game existence result consequently verifies the all-acceptance promise for every replica under both $C^0$ and $C^1$, for the fixed $\rho$ in the task.
The quadratic term’s contribution to $q$’s normalized aggregate is explicitly computable:
$$ B_0= K\beta^2 \sum_{D\ne q}\frac{\beta_D}{\beta+\beta_D}. $$
Indeed, only pairs involving $t_*$ contribute to $q$. For an outside type mass in block $D$, the relevant unanimity component has block support $\{q,D\}$; summing those masses gives the displayed formula.
Therefore
$$ F_q^W(\alpha_q)=B_0+\operatorname{perm}(A). $$
Because $q$ contains only type $t_*$, all its players have equal payoffs. Exact block efficiency gives, for every admissible $n$,
$$ z_{t_*,q}^0(n)= \frac{B_0+\operatorname{perm}(A)}{\beta}. $$
This distinguished sequence is already constant. Its type-average payoff is the same, because the type occurs only in $q$.
Given an approximation $\widehat\ell$ with error at most $2^{-3}$,
$$ \left| \beta\widehat\ell-B_0-\operatorname{perm}(A) \right| \leq\frac{\beta}{8}<\frac12. $$
Rounding $\beta\widehat\ell-B_0$ to the nearest integer recovers $\operatorname{perm}(A)$ exactly. Dividing by the known factor $4^{t(\Phi)}$ recovers $\#\operatorname{SAT}(\Phi)$.
Every construction parameter and every exact postprocessing operation has polynomial bit complexity. Thus a single limit-approximation call at fixed accuracy recovers a SAT count. Computing either all cell limits or all type limits is therefore $\mathrm{NP}$-hard, and cannot have the requested polynomial-time algorithm unless $\mathrm P=\mathrm{NP}$.
Assume now that every listed monomial coefficient is nonnegative.
Expand a monomial into its original-block assignments $f$ as in Section 3. After the merger, replace the labels $a,b$ by their merged label. This represents the merged polynomial expansion because its masses are the sums of the original masses.
Let $H=H_f$ and let $A_f$ be the assignment coefficient.
If $H$ contains both designated blocks, their combined share is unchanged:
$$ \frac{\beta_a+\beta_b}{\sum_{D\in H}\beta_D}. $$
If $H$ contains neither, their share is zero before and after.
If $H$ contains exactly one designated block $q$, let $r$ be the other designated block and put
$$ \gamma=\sum_{D\in H\setminus\{q\}}\beta_D. $$
The assignment’s gain factor is
$$ \frac{\beta_q+\beta_r}{\beta_q+\beta_r+\gamma} -\frac{\beta_q}{\beta_q+\gamma} = \frac{\beta_r\gamma} {(\beta_q+\gamma)(\beta_q+\beta_r+\gamma)}. $$
It is positive exactly when an outsider block occurs. All assignment coefficients are nonnegative, so cancellation is impossible.
Define each type’s original block support by
$$ S_t=\{q:\alpha_{tq}^0>0\}. $$
A positive-coefficient monomial $M$ admits a positive-weight assignment using $a$, avoiding $b$, and using an outsider if and only if:
Necessity follows from such an assignment. For sufficiency, assign $t$ to $a$, assign $u$ to an outsider, and assign every remaining type to any available block other than $b$.
Check these conditions and their symmetric counterparts with $a,b$ exchanged. Scanning the explicit monomials and supports takes polynomial time. This proves that strict merger gain is in $\mathrm P$ for nonnegative coefficients, without a degree bound. The zero polynomial has zero gain.
For unrestricted signed coefficients, strict merger gain is the rational sign test from Section 3. Neither a polynomial-time algorithm nor a promised-input hardness reduction for that sign test is established here.
The approximation hardness proof does not settle this remaining question. Its convexifying quadratic term has a computable contribution to block payoffs, which can be subtracted when processing a numerical approximation. It also contributes to merger gain, so the sign of the constructed merger gain does not directly reveal the encoded SAT count.
⟨structured verdict parsed — rendered above⟩
The output is partial, with substantial correct results. The convergence argument and approximation hardness reduction are sound. The polynomial-time criterion for nonnegative coefficients also checks out. The requested complexity classification of strict merger gain for unrestricted signed coefficients remains unanswered, as the prover explicitly acknowledges.
I found no false central step or substantive mathematical gap in the results actually proved.
Verified.
$$
\phi_i(g)=P_B(g)-P_{B\setminus\{i\}}(g|_{B\setminus\{i\}})
$$
has the correct coefficients. Subtracting the identities for two distinct players yields the displayed balanced-contributions identity.
$$ \sum_{j\in B\setminus\{i\}} \bigl(\xi_i^{S\setminus\{j\}}-\xi_j^{S\setminus\{i\}}\bigr) =|B|\xi_i^S-Q_B(S). $$
The induction therefore establishes the representation for every nonempty active set. Cases with a singleton restricted block or no outside blocks are covered by empty sums; no undefined payoff on an empty active set is needed.
Verified.
$$
\frac{s(x)}{s(x)+\sum_{D\in H\setminus\{q\}}\beta_D}.
$$
Components not containing $q$ contribute nothing to its marginal contribution.
$$
g_{q,n}(A)=nF_q\left((|A_t|/n)_{t\in T}\right)
$$
is correct for nonempty $A$: worths scale by $n$, and every clock rate scales by the same factor. For empty $A$, both sides are zero.
$$ \mathbb E X_n(u)=u\alpha_q-\frac{u}{n}e_t. $$
Thus
$$
\ell_{tq}=\int_0^1\partial_tF_q(u\alpha_q)\,du
$$
is established along all admissible replica sizes. Finite weighted sums establish convergence of the type payoffs under both structures.
The proof does not require convexity, coefficient restrictions, or the equilibrium promise. It makes no unsupported claim that its convergence estimate yields a polynomial-time algorithm.
Verified.
Shapley efficiency and the scaling identity give
$$
\sum_t\alpha_{tq}z_{tq}(n)=F_q(\alpha_q)
$$
for every admissible replica size. The normalization is correct: cell counts are $n\alpha_{tq}$, while the reduced-game total is $nF_q(\alpha_q)$.
Passing to the limits yields the claimed formula for the merger gain $G$. Each evaluated $F_q(\alpha_q)$ is rational because all masses, coefficients, and positive denominators are rational.
The monomial-assignment expansion is also correct. Expanding each type coordinate over blocks produces one term for each assignment $f$, and that term induces a unanimity game supported on $H_f$. Its block share is the stated rate fraction.
This proves an exact finite comparison procedure. It does not prove a polynomial-time procedure, and the prover correctly avoids that inference.
Verified, including the promised-input requirements.
The stated permanent reduction agrees with Lemma 3.1 of [Valiant’s paper](https://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/Valiant_permanent.pdf). The source specifies
$$
t(\Phi)=2\,(\text{number of literal occurrences})-(\text{number of clauses}),
$$
so its computability and polynomial magnitude hold. Restricting to formulas with three literals per clause ensures the nonnegative exponent used in count recovery.
Proposition 6.7 and the supporting proposal construction in [Vidal-Puga’s paper](https://vidalpuga.webs.uvigo.es/papers/harsanyi.pdf) support the convex-game stationary-equilibrium existence claim. The construction supplies accepted proposals recursively over active sets; the prover appropriately distinguishes existence for convex games from stronger conclusions requiring strict convexity.
For each assignment, the required blocks consist of the distinguished block, $j$ used column blocks, and $r$ marker blocks, all of mass $\beta$. The resulting share denominator is therefore $1+j+r$.
The defining equations for $\theta_r$ cancel every contribution with $j<d$ and retain precisely $C_d(h)$. Assignments using all $d$ columns are bijections, so $C_d(h)=\operatorname{perm}(A(h))$. Interpolation then proves
$$
F_q^V(\alpha_q)=\operatorname{perm}(A).
$$
The bound
$$
\partial_s\partial_tW(x)\geq1
$$
is valid for distinct types throughout the feasible mass box: every remaining monomial product lies in $[0,1]$.
For different-type players, the discrete second difference is exactly the mixed derivative divided by $n$. For same-type players it is zero by multilinearity. These inequalities establish convexity for every replica and every active-set restriction.
All singleton worths vanish. Increasing marginal contributions therefore imply nonnegative marginal contributions and the required singleton-worth inequality. The cited existence result applies under both partitions and for the prescribed $\rho$.
The quadratic contribution $B_0$ has the correct normalization and is explicitly computable with polynomial bit complexity. Since the distinguished block contains one type only, efficiency gives the constant sequence
$$
z_{t_*,q}^0(n)=\frac{B_0+\operatorname{perm}(A)}{\beta}.
$$
The approximation error after multiplication by $\beta$ is less than $1/2$, so nearest-integer rounding recovers the permanent exactly. The known scaling factor then recovers the satisfying-assignment count.
This establishes the claimed approximation hardness for both cell and type limits. The reduction uses one approximation call at fixed accuracy, with polynomial-time exact postprocessing.
Verified.
The assignment cases exhaust all possibilities:
Because both designated block masses are positive, the last factor is positive exactly when an outsider occurs. With nonnegative assignment coefficients, cancellation cannot occur.
The support conditions correctly require distinct type occurrences to supply the designated block and an outsider. Necessity and sufficiency are both established, including the requirement that every remaining type has an available block avoiding the other designated block.
Scanning the explicit monomials and supports takes polynomial time. Degree-one monomials cannot satisfy the distinct-type condition; zero coefficients and the zero polynomial cause no difficulty.
Major incompleteness — Sections 3 and 6: unrestricted strict merger gain.
The task asks whether strict merger gain is in $\mathrm P$ or is $\mathrm{NP}$-hard on the full promised domain. The output supplies neither classification for signed coefficients.
Rationality and finite enumeration establish decidability, not polynomial complexity. Approximation hardness does not transfer automatically to the sign of $G$, and the prover correctly identifies the convexifying term as an obstacle to such a transfer.
Required follow-up: establish either a polynomial-time algorithm for the signed-coefficient comparison, with bit-complexity bounds, or a hardness reduction whose outputs satisfy every promise. This requires additional mathematics, not merely clarification.
The partial designation reflects this openly acknowledged missing task component. It does not invalidate the convergence, approximation hardness, or restricted strict-gain results.
⟨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.