Answer: Polynomial-time solvable; an exactly optimal rational weight representation can be computed.
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a vector of desired Banhzaf indices 𝑐, we can efficiently compute a weight vector 𝑤 such that the LBF 𝑓𝑤,0 has e𝑓𝑤,0 parameters that approximate 𝑐 within ℓ2 error 𝜖. The algorithm runs in time ˜𝑂𝑛2/𝜖4, where the ˜𝑂() hides logarithmic factors in its argument.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given binary-rational type masses μ_t>0 summing to \(1\), target influence densities \(c_t\), and threshold η, choose nonnegative weights \(a_t\) satisfying \(∑_t μ_t a_t^2=1\) to minimize \(√{∑_t μ_t(Φ_t(μ,a,η)-c_t)^2}\), where \(Z_t\sim\mathcal{N}(0,μ_t)\) independently and \(Φ_t=(1/μ_t)ℕ[Z_t\,\operatorname{sign}(\sum_s a_s Z_s-η)]\).
A society is given by its support: the list of its \(\tau\geq 1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Inputs also include target densities \(c_t\in\mathbb Q\), a fixed threshold \(\eta\in\mathbb Q\), and accuracy \(\varepsilon\in\mathbb Q\cap(0,1)\). Let \(L\) be the total binary input length. There is no separate candidate parameter \(m\) in this model.
Feasible weights satisfy \(a_t\geq0\) and \(\sum_t\mu_ta_t^2=1\). Independently draw \(Z_t\sim\mathcal N(0,\mu_t)\), and define \(\Phi_t(\mu,a,\eta)=\mu_t^{-1}\mathbb E[Z_t\operatorname{sign}(\sum_s a_sZ_s-\eta)]\), with \(\operatorname{sign}(0)=1\).
Set \(D(a)=(\sum_t\mu_t(\Phi_t(\mu,a,\eta)-c_t)^2)^{1/2}\) and \(\mathrm{OPT}=\min_aD(a)\). No exact realizability of the targets is promised. A finite weight representation is a nonzero vector \(b\in\mathbb Q_{\geq0}^{\tau}\), denoting \(a_t=b_t/(\sum_s\mu_sb_s^2)^{1/2}\).
Can weights with \(D(a)\leq\mathrm{OPT}+\varepsilon\) be computed in time \(\operatorname{poly}(\tau,L,1/\varepsilon)\), or is achieving this additive approximation NP-hard for inverse-polynomial \(\varepsilon\)?
For realizable discrete Banzhaf targets, a polynomial-time algorithm finds a linear bounded function with zero threshold and \(\ell_2\) error at most \(\varepsilon\), in time \(\widetilde O(n^2/\varepsilon^4)\), where \(n\) is the number of players. [Source](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p354.pdf)
No result settling the precisely specified Gaussian approximation problem was located.
The problem is polynomial-time solvable, in the stronger sense that an exactly optimal weight representation \(b\in\mathbb Q_{\geq0}^{\tau}\setminus\{0\}\) can be computed in time \(\operatorname{poly}(\tau,L)\). No realizability promise is needed.
The algorithm is:
We prove both optimality and the complexity bound.
Fix any feasible \(a\), and set \(S=\sum_s a_sZ_s\). Independence and feasibility give
\(S\sim\mathcal N(0,1)\), since \(\operatorname{Var}(S)=\sum_s\mu_sa_s^2=1\).
For each \(t\), define \(R_t=Z_t-\mu_ta_tS\). The pair \((R_t,S)\) is jointly Gaussian, possibly degenerate, and
\(\operatorname{Cov}(R_t,S)=\operatorname{Cov}(Z_t,S)-\mu_ta_t\operatorname{Var}(S)=\mu_ta_t-\mu_ta_t=0\).
Uncorrelated jointly Gaussian variables are independent. Since \(\mathbb E[R_t]=0\), it follows that
\(\mathbb E[Z_t\operatorname{sign}(S-\eta)]=\mu_ta_t\,\mathbb E[S\operatorname{sign}(S-\eta)]\).
Let \(\varphi(s)=(2\pi)^{-1/2}\exp(-s^2/2)\). Because \(S\) has a continuous distribution, the convention at zero does not affect this expectation. Using \(\mathbb E[S]=0\) and \(\varphi'(s)=-s\varphi(s)\), we obtain
\(\mathbb E[S\operatorname{sign}(S-\eta)]=2\int_\eta^\infty s\varphi(s)\,ds=2\varphi(\eta)\).
Consequently, with the strictly positive constant \(\kappa=2\varphi(\eta)=\sqrt{2/\pi}\exp(-\eta^2/2)\), we have the exact identity
\(\Phi_t(\mu,a,\eta)=\kappa a_t\).
This holds for every feasible \(a\) and every input threshold \(\eta\).
Write \(C^2=\sum_t\mu_tc_t^2\). Expanding the squared objective and using feasibility gives
\(D(a)^2=\sum_t\mu_t(\kappa a_t-c_t)^2=\kappa^2+C^2-2\kappa\sum_t\mu_ta_tc_t\).
Since \(\kappa>0\), minimizing \(D(a)^2\), and hence \(D(a)\), is equivalent to maximizing \(\sum_t\mu_ta_tc_t\).
Introduce \(x_t=\sqrt{\mu_t}\,a_t\) and \(d_t=\sqrt{\mu_t}\,c_t\). Because every mass is positive, this is a bijection between feasible weights and vectors satisfying \(x_t\geq0\) and \(\sum_tx_t^2=1\). The quantity to maximize becomes \(d\cdot x\).
We now solve this maximization in all cases.
Suppose some \(c_t>0\). Define \(d_t^+=\max\{d_t,0\}\) and \(r=\|d^+\|_2>0\).
For every feasible \(x\), nonnegativity and the Cauchy–Schwarz inequality give
\(d\cdot x\leq d^+\cdot x\leq\|d^+\|_2\|x\|_2=r\).
The vector \(x^*=d^+/r\) is feasible. Its coordinates vanish wherever \(d_t\leq0\), so
\(d\cdot x^*=\sum_{t:d_t>0}d_t^2/r=r\).
Thus \(x^*\) is globally optimal. Translating back to weights gives
\(a_t^*=\max\{c_t,0\}/\bigl(\sum_s\mu_s\max\{c_s,0\}^2\bigr)^{1/2}\).
This is exactly the weight vector denoted by the rational representation \(b_t=\max\{c_t,0\}\). The representation is nonzero because at least one target is positive.
Suppose \(c_t\leq0\) for every \(t\), so also \(d_t\leq0\). Let \(M=\max_td_t\leq0\).
For every feasible \(x\), we have \(\sum_tx_t\geq1\): indeed,
\(\bigl(\sum_tx_t\bigr)^2=\sum_tx_t^2+2\sum_{s<t}x_sx_t\geq1\).
Therefore,
\(d\cdot x\leq M\sum_tx_t\leq M\),
where the last inequality uses \(M\leq0\). If \(j\) satisfies \(d_j=M\), then \(x=e_j\) attains this bound.
Such a coordinate can be found using rational comparisons alone. Since all targets are nonpositive,
\(d_t=\sqrt{\mu_t}\,c_t=-\sqrt{\mu_tc_t^2}\).
Hence maximizing \(d_t\) is equivalent to minimizing the rational number \(\mu_tc_t^2\). Choose any minimizing index \(j\), and output \(b=e_j\). Its represented weights satisfy \(a_j=1/\sqrt{\mu_j}\) and \(a_t=0\) for \(t\neq j\), giving precisely \(x=e_j\).
This also covers zero targets and ties.
Testing the signs of the rational targets and copying their positive parts takes polynomial time in the input length.
In the second case, each product \(\mu_tc_t^2\) has binary encoding length \(O(L)\). Exact comparisons use cross multiplication of positive denominators, involving integers of \(O(L)\) bits. Finding a minimum among \(\tau\) such products therefore takes \(\operatorname{poly}(\tau,L)\) bit operations.
The output has polynomial encoding length: it consists either of the input targets with negative entries replaced by zero, or of a coordinate vector. Neither square roots nor the transcendental constant \(\kappa\) need to be evaluated.
In both cases the represented weights attain \(D(a)=\mathrm{OPT}\). Thus they satisfy \(D(a)\leq\mathrm{OPT}+\varepsilon\) for every allowed \(\varepsilon\), with running time \(\operatorname{poly}(\tau,L)\), and therefore also \(\operatorname{poly}(\tau,L,1/\varepsilon)\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed polynomial-time result. Both branches return an exactly optimal rational weight representation under the representation specified in USER_TASK. No substantive gaps, false statements, or missing hypotheses were found.
Feasibility gives \(\operatorname{Var}(S)=\sum_s\mu_sa_s^2=1\). Since \(S\) is a linear combination of independent centered Gaussian variables, the assertion \(S\sim\mathcal N(0,1)\) is correct.
The residual \(R_t=Z_t-\mu_ta_tS\) and \(S\) are jointly Gaussian because both are linear combinations of the Gaussian input vector. The displayed covariance calculation is correct.
The theorem invoked—uncorrelated jointly Gaussian variables are independent—applies here, including when the joint distribution is degenerate. The prover explicitly acknowledges that possibility. Since \(R_t\) is centered and independent of \(S\), its contribution to the expectation involving \(\operatorname{sign}(S-\eta)\) vanishes. All expectations exist because the sign function is bounded and Gaussian variables are integrable.
The integral computation
\[
\mathbb E[S\operatorname{sign}(S-\eta)]
=2\int_\eta^\infty s\varphi(s)\,ds
=2\varphi(\eta)
\]
is correct for every finite real \(\eta\), including negative thresholds. The boundary term at infinity vanishes. Also, \(\mathbb P(S=\eta)=0\), so the convention \(\operatorname{sign}(0)=1\) has no effect.
Thus \(\Phi_t(\mu,a,\eta)=\kappa a_t\), with \(\kappa>0\), is established for every feasible weight vector.
The expansion
\[
D(a)^2=\kappa^2+C^2-2\kappa\sum_t\mu_ta_tc_t
\]
correctly uses the normalization \(\sum_t\mu_ta_t^2=1\).
Since \(D(a)\geq0\) and \(\kappa>0\), maximizing the displayed linear functional is equivalent to minimizing both \(D(a)^2\) and \(D(a)\).
The transformation \(x_t=\sqrt{\mu_t}\,a_t\) is invertible because every listed mass is strictly positive. It maps the feasible set exactly onto the nonnegative unit sphere, and the transformed functional is correctly identified as \(d\cdot x\).
A positive target implies \(\|d^+\|_2>0\), so the proposed normalization is well-defined.
Both inequalities
\[
d\cdot x\leq d^+\cdot x\leq\|d^+\|_2\|x\|_2
\]
have their hypotheses satisfied: the first uses coordinatewise nonnegativity of \(x\), and the second is Cauchy–Schwarz.
The proposed vector \(x^*=d^+/\|d^+\|_2\) is feasible and attains the bound. The calculation establishing equality is correct, including when some other targets are zero or negative.
Translating back yields exactly the normalized vector represented by \(b_t=\max\{c_t,0\}\). This representation is rational, nonnegative, and nonzero.
Here every \(d_t\leq0\), so \(M=\max_td_t\leq0\). The prover correctly establishes \(\sum_tx_t\geq1\) for every nonnegative unit vector.
The bound
\[
d\cdot x\leq M\sum_tx_t\leq M
\]
has the correct inequality directions. In particular, the second inequality correctly accounts for the nonpositive sign of \(M\).
A coordinate vector at a maximizing index attains the bound. The identity
\[
d_t=-\sqrt{\mu_tc_t^2}
\]
is valid precisely because this branch assumes \(c_t\leq0\). Consequently, minimizing \(\mu_tc_t^2\) correctly selects a maximizing coordinate without evaluating square roots.
The output \(b=e_j\) represents the claimed feasible weights and maps to \(x=e_j\). Zero targets, ties, the all-zero target vector, and support size \(\tau=1\) are covered.
The complexity claim is valid under the explicitly allowed normalized rational representation. The algorithm need not output the generally irrational normalized weights themselves.
Sign tests, copying positive rational targets, and constructing a coordinate vector require polynomial time and output length.
Each product \(\mu_tc_t^2\) has encoding length \(O(L)\). Comparing such products by cross multiplication uses integers of \(O(L)\) bits; scanning the support for a minimum therefore takes polynomially many bit operations.
Neither branch requires evaluating \(\kappa\), the threshold-dependent exponential, or any square root. Thus even large encoded thresholds introduce no numerical precision requirement.
The proof establishes exact optimality, which implies the requested additive approximation for every allowed \(\varepsilon\). It uses no realizability promise and introduces no separate candidate parameter.
No additional clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.