| paper | d4-conf-atal-2022-0274 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; an exactly optimal rational weight representation can be computed. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
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 a distribution μ over τ voting-rights types. Each type receives a nonnegative weight \(a_t\), normalized by \(∑_t μ_t a_t^2=1\); its influence density is the limiting, √N-rescaled per-member Banzhaf value under independent random coalitions. The objective is to minimize mass-weighted ℓ2 error from the target densities.
The mirror covers the Banzhaf LBF approximation result in Theorem 7 for repeated voter classes; it leaves the general semivalue result, the other LBF results, and the experiments aside.
The strongest positive case is a Gaussian type-density inverse-Banzhaf problem for large membership organizations. Imagine a cooperative with \(N\) members divided into \(\tau\) voting-rights classes. Members in class \(t\) share the same desired influence target and receive the same voting weight; the class occupies fraction \(\mu_t\) of the membership. Here \(N\gg\tau\), and the society is represented by the rational type masses \(\mu_t\).
My anchor is Theorem 7, proved in this paper. It says that, given a realizable vector of target Banzhaf indices \(c\), the authors compute weights for a linear bounded function whose Banzhaf vector is within \(\ell_2\)-error \(\epsilon\) of \(c\), in time \(\tilde O(n^2/\epsilon^4)\). This is an algorithmic result about approximating the inverse Banzhaf problem; the LBF is the paper’s relaxation. The paper’s exact-hardness claim is cited to earlier work [11], rather than stated as a numbered result here, so I do not use it as an anchor.
Here is the continuous problem I would hand to a prover. Under the Banzhaf coalition distribution, each member’s vote is an independent uniform sign. For a large replica of the society, give each member of type \(t\) weight \(a_t/\sqrt N\), and set the threshold in the same normalized units as the aggregate vote fluctuation. The type-level fluctuations converge to independent \(Z_t\sim\mathcal N(0,\mu_t)\). Normalize the weights by \(\sum_t\mu_t a_t^2=1\), and define the type’s per-member influence density as
\[
\Phi_t(\mu,a,\eta)
=\frac{1}{\mu_t}\mathbb E\!\left[
Z_t\,\operatorname{sign}\!\left(\sum_s a_sZ_s-\eta\right)
\right],
\]
where \(\eta\) is the normalized threshold.
Gaussian Type-Density Inverse Banzhaf takes binary-rational masses \(\mu_t>0\) summing to \(1\), target densities \(c_t\), and threshold \(\eta\). It asks for nonnegative type weights \(a_t\), with \(\sum_t\mu_ta_t^2=1\), minimizing the mass-weighted target error
\[
\|\Phi-c\|_{2,\mu}
=\left(\sum_t\mu_t\bigl(\Phi_t(\mu,a,\eta)-c_t\bigr)^2\right)^{1/2}.
\]
A solution is an \(\epsilon\)-approximate minimizer: its error is at most \(\mathrm{OPT}+\epsilon\). When the targets are realizable, this asks for weights whose type influence densities are within \(\epsilon\) of the requested values.
This is recognizably the paper’s inverse-design question: choose weights to meet influence targets. In the Gaussian model, \(\Phi_t=2a_t\varphi(\eta)\), where \(\varphi\) is the standard normal density. So I expect this mirror to be Class A: the stated continuous problem has a direct solution. Its further research questions are whether the finite-\(N\) Banzhaf indices converge at a useful rate, how lattice effects change that limit, and whether compressed algorithms can handle those corrections in time polynomial in \(\tau\), the input bit length, and \(1/\epsilon\).
The mirror covers only the Banzhaf inverse-design result, not the paper’s general semivalue theorem or its experiments. Its weak point is substantial: it rescales individual power by \(\sqrt N\) and takes a Gaussian limit. Theorem 7 concerns a finite hypercube and an LBF relaxation; it does not prove that this limit preserves the hard or algorithmically interesting parts of finite inverse Banzhaf design. The positive case is that the limiting question retains the same weight-design objective while making the *population* a type distribution. Its plausibility depends on whether the authors and a referee regard that leading-order influence density as a meaningful high-multiplicity version of their problem.
The strongest anchor is Theorem 7, and there is a plausible high-multiplicity setting for it: a large membership organization with repeated voting-rights classes. I would not object that the paper lacks a computational result, that players must be unique, or that such a regime is inherently nonsensical.
The difficulty is that the proposed Gaussian limit removes the inverse-design structure Theorem 7 addresses. With \(Y=\sum_s a_sZ_s\sim\mathcal N(0,1)\), Gaussian integration by parts gives
\[
\Phi_t=\frac{1}{\mu_t}\mathbb E[Z_t\,\operatorname{sign}(Y-\eta)]
=2a_t\varphi(\eta).
\]
So the attainable target vectors lie on a single positive sphere: the coordinates are just the chosen weights times one common scalar. For a realizable target \(c\), recovering the weights is normalization; for the proposed approximate objective, the optimizer is the projection of \(c\) onto that sphere. The LBF version has the same collapse: its type influence is \(a_t\) times one common scalar. There is no longer a rich inverse problem in which the algorithm must fit interacting coordinates. The continuous model gives a useful asymptotic identity, but little of Theorem 7’s computational question remains.
That collapse follows from the population limit. In an atomless society, an individual has zero mass and zero pivotality. The proposed \(\sqrt N\) rescaling preserves a nonzero quantity by retaining second-order coalition fluctuations and taking their Gaussian limit. It is a sensible choice for diffuse, repeated classes, but it is an additional fluctuation model. Without the rescaling, the individual indices vanish; with the diffuse scaling, the Gaussian limit makes them proportional to the weights. If a few players retain substantial influence, they must be represented as atoms. A model with those atoms may be useful, but its interesting pivotal structure comes from the finite atomic component; growing that component to retain the original inverse-design complexity brings back the finite-player problem.
A stronger mirror would ask for finite-replica corrections: given type masses and a population size \(N\), approximate the finite Banzhaf targets and recover weights with a runtime bound in \(\tau\), \(N\), input precision, and error. That could be worthwhile, but the nontrivial part would be controlling finite-size and lattice effects. For diffuse classes, the Gaussian answer is already explicit. Retaining the difficult cases means keeping the exact replication counts, weights, and threshold arithmetic that the continuum limit smooths away. Those are high-multiplicity discrete instances, rather than a computational problem determined by the population measure alone.
So my case against this mirror is narrow: the Gaussian construction is a legitimate mirror of power density in one natural regime, but it appears too collapsed to be a strong continuous-complexity result. I cannot honestly turn that into a universal “no.” A rigorous finite-size transfer result could still justify the work, and a reader who regards the asymptotic identity itself as a worthwhile result may reasonably keep the anchor.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.