Answer: \(\mathrm{NP}\)-complete, even with \(\tau=K=1\) and an initially equilibrium target.
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateELIMINATION and FEASIBLE ELIMINATION are both NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many module types \(T\) with rational masses \(\mu_t\), Boolean action spaces \(A_t\) encoded by private local variables, goal formulas \(\gamma_t\), action costs \(c_t\), and initial endowments \(e_t^0\), together with a rational target action-mass profile \(x_{t,a}\) satisfying \(\sum_{a\in A_t}x_{t,a}=\mu_t\) and \(c_t(a)\le e_t^0\) whenever \(x_{t,a}>0\), let \(E=\sum_t\mu_t e_t^0\). Does there exist a measurable redistribution \(b\) over the unit-mass population, with \(\int b=E\), that keeps the assigned target action affordable almost everywhere and lets a positive mass of agents whose target action falsifies \(\gamma_t\) afford some action \(a'\in A_t\) satisfying \(\gamma_t\)? Each agent has private module variables, so a unilateral change does not affect another agent’s goal.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a finite private variable set \(\Phi_t\), implicitly represented actions \(A_t=\{0,1\}^{\Phi_t}\), a propositional goal \(\gamma_t\) over those variables, binary-encoded costs \(k_t(p,v)\in\mathbb Z_{\ge0}\), and a binary-rational initial endowment \(e_t^0\ge0\). Define \(c_t(a)=\sum_{p\in\Phi_t}k_t(p,a(p))\). Each agent has its own copy of its type's variables; goals depend only on that agent's assignment. Agents strictly prefer goal satisfaction and are otherwise indifferent, regardless of cost.
The target profile is an explicit list of positive binary-rational entries \(x_{t,a}\), with unlisted entries zero, \(\sum_{a\in A_t}x_{t,a}=\mu_t\), and \(c_t(a)\le e_t^0\) for every listed entry. No initial equilibrium promise is imposed.
Represent the population by \([0,1]\) with Lebesgue measure \(\lambda\), partitioned into measurable cells \(S_{t,a}\) of measure \(x_{t,a}\), each assigned target action \(a\). Let \(E=\sum_t\mu_t e_t^0\).
A successful redistribution is a measurable \(b:[0,1]\to\mathbb R_{\ge0}\) with \(\int_0^1 b\,d\lambda=E\), satisfying \(b(s)\ge c_t(a)\) almost everywhere on each \(S_{t,a}\), and
\(\lambda\bigl(\bigcup_{t,a}\{s\in S_{t,a}:a\not\models\gamma_t,\ \exists a'\in A_t\text{ with }a'\models\gamma_t\text{ and }c_t(a')\le b(s)\}\bigr)>0\).
Is deciding whether a successful redistribution exists solvable in polynomial time, or is it \(\mathrm{NP}\)-hard? State running times in \(m=\sum_t|\Phi_t|\), \(\tau\), the number \(K\) of listed target entries, and the total input bit length \(L\).
For finite electric Boolean games, elimination and feasible elimination of a given initially feasible outcome are \(\mathrm{NP}\)-complete, with nonnegative additive costs and goal-based preferences. [Source](https://spiral.imperial.ac.uk/server/api/core/bitstreams/f1de22dc-b547-4880-a78c-5968edf5280f/content)
No published complexity result for this exact atomless, private-variable, positive-mass formulation was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau=K=1\), all costs belong to \(\{0,1\}\), and the target is an equilibrium under the initial endowment. Consequently, a polynomial-time algorithm exists if and only if \(\mathrm{P}=\mathrm{NP}\).
The proof below gives an exact characterization of successful redistribution and explicit running-time bounds.
Let \(J\) be the set of listed target entries. Define
\(C=\sum_{(t,a)\in J}x_{t,a}c_t(a)\), and \(D=E-C\).
Initial feasibility implies
\(C\le\sum_{(t,a)\in J}x_{t,a}e_t^0=\sum_t\mu_t e_t^0=E\),
so \(D\ge0\).
Define the measurable baseline budget \(d\) by \(d(s)=c_t(a)\) on each listed cell \(S_{t,a}\), and set it to zero on the remaining null set. Thus \(\int_0^1d\,d\lambda=C\).
Every redistribution preserving target feasibility satisfies \(b\ge d\) almost everywhere. Its available surplus is therefore
\(\int_0^1(b-d)\,d\lambda=D\).
Proposition. A successful redistribution exists if and only if there are a listed entry \((t,a)\in J\) and an assignment \(a'\in A_t\) such that
\(a\not\models\gamma_t,\qquad a'\models\gamma_t,\qquad \bigl(D>0\ \text{or}\ c_t(a')\le c_t(a)\bigr).\)
In particular, when \(D>0\), the magnitude of a satisfying action’s cost imposes no additional restriction.
Suppose a successful redistribution \(b\) exists. Its successful-deviation set has positive measure. Since there are finitely many listed cells, some listed cell with \(a\not\models\gamma_t\) contains a positive-measure set of agents who can afford a satisfying assignment. Hence \(\gamma_t\) is satisfiable.
If \(D>0\), this already gives the required witness.
If \(D=0\), then \(b-d\ge0\) almost everywhere and its integral is zero. Therefore \(b=d\) almost everywhere: otherwise, some set \(\{b-d\ge1/j\}\), with positive integer \(j\), would have positive measure and force a positive integral.
Choose a successful agent in the selected cell outside this null exceptional set. That agent can afford some satisfying assignment \(a'\), and
\(c_t(a')\le b(s)=d(s)=c_t(a)\).
This proves necessity.
Suppose the stated witness exists and \(D=0\). Set \(b=d\). This preserves target feasibility and has integral \(C=E\).
Every agent in \(S_{t,a}\) can afford \(a'\), because \(c_t(a')\le c_t(a)\). The entire cell therefore admits a strictly preferred deviation. Its measure \(x_{t,a}\) is positive, so the redistribution is successful.
Suppose \(D>0\) and the stated witness exists. Write
\(x=x_{t,a},\qquad h=\max\{0,c_t(a')-c_t(a)\}\),
and choose
\(\delta=\min\{x/2,\ D/[2(h+1)]\}>0\).
There is a measurable subset \(B\subseteq S_{t,a}\) with \(\lambda(B)=\delta\). To verify this directly, the function
\(f(u)=\lambda(S_{t,a}\cap[0,u])\)
is continuous, since \(|f(u)-f(v)|\le|u-v|\), and has endpoint values \(0\) and \(x\). The intermediate value theorem supplies the desired subset.
Let \(r=D-\delta h\). Our choice gives \(\delta h\le D/2\), so \(r\ge D/2>0\). Define
\(b(s)=d(s)+h\mathbf{1}_B(s)+r\).
This function is measurable, nonnegative, and at least \(d\). Since the population has measure one,
\(\int_0^1 b\,d\lambda=C+\delta h+r=C+D=E\).
For every agent in \(B\),
\(b(s)\ge c_t(a)+h\ge c_t(a')\).
Thus a set of measure \(\delta>0\) admits a strictly preferred deviation. This completes the characterization.
A certificate consists of one listed entry \((t,a)\) and one assignment \(a'\in\{0,1\}^{\Phi_t}\). Its length is \(O(m+\log K)\).
The verifier computes \(C,E,D\), checks that the listed action fails its goal, evaluates the goal on \(a'\), and checks the condition in the proposition. Formula evaluation, additive-cost computation, and exact rational arithmetic all take polynomial time in \(L\).
The proposition proves that the certificate exists exactly for successful instances. No representation of a measurable redistribution is needed. Hence the problem belongs to \(\mathrm{NP}\).
We reduce from propositional satisfiability, using its standard \(\mathrm{NP}\)-completeness theorem.
Let \(F\) be an input formula over variables \(y_1,\ldots,y_n\). Introduce a fresh variable \(q\), and construct one type with:
The construction has polynomial size, with \(m=n+1\) and \(\tau=K=1\). The target costs zero and is initially feasible. It fails its goal because \(q=0\). Moreover,
\(C=0,\qquad E=D=1/2>0\).
If \(F\) is satisfiable, extend a satisfying assignment by setting \(q=1\). The resulting satisfying action costs one. Giving budget one to half the population and zero to the other half preserves the target’s feasibility, uses total budget \(1/2\), and permits a strictly preferred deviation on a set of measure \(1/2\).
Conversely, if a successful redistribution exists, some agent can afford an assignment satisfying \(q\land F\). Its restriction to the original variables satisfies \(F\).
Thus the constructed instance is successful if and only if \(F\) is satisfiable.
This reduction also avoids relying on an initially unstable target: every initially affordable action has \(q=0\), since setting \(q=1\) costs one and the initial endowment is \(1/2\). Consequently, no initially affordable action satisfies the goal, and the target is initially an equilibrium.
The problem is therefore \(\mathrm{NP}\)-hard under all the restrictions stated above. Together with membership, this proves \(\mathrm{NP}\)-completeness.
Let \(n_t=|\Phi_t|\), and let \(U\) contain those types having at least one listed target action that fails its goal. For each \(t\in U\), compute
\(B_t=\max\{c_t(a):(t,a)\in J,\ a\not\models\gamma_t\}\).
The characterization gives a deterministic algorithm:
Using schoolbook exact arithmetic, a conservative preprocessing and certificate-verification bound is
\(O((K+\tau+m)L^2)\)
bit operations. The rational sums can be maintained with \(O(L)\)-bit numerators and denominators: products of input denominators have bit length bounded by their total encoded length, and summed action costs also have \(O(L)\) bits. Each enumerated assignment can likewise be checked in \(O(L^2)\) bit operations.
The deterministic algorithm therefore runs in
\(O\left(\left(K+\tau+m+\sum_{t\in U}2^{n_t}\right)L^2\right)\).
A bound expressed only through the requested parameters is
\(O((K+\tau+m+2^m)L^2)\).
Indeed, for nonnegative integers \(u,v\),
\(2^u+2^v\le2^{u+v}+1\),
because \((2^u-1)(2^v-1)\ge0\). Repeated application yields \(\sum_{t\in U}2^{n_t}\le2^m+|U|-1\) when \(U\) is nonempty; the empty case is immediate.
Thus the problem is fixed-parameter tractable in \(m\), while fixing only \(\tau\) and \(K\) does not remove its \(\mathrm{NP}\)-hardness.
Proposition 7 of the cited [*Electric Boolean Games* paper](https://spiral.imperial.ac.uk/server/api/core/bitstreams/f1de22dc-b547-4880-a78c-5968edf5280f/content) establishes \(\mathrm{NP}\)-completeness for finite-game elimination and feasible elimination. The proof here is independent and addresses the specified atomless, private-variable formulation directly.
Atomlessness changes the budget condition: any positive surplus can fund an arbitrarily costly satisfying action on a sufficiently small positive-measure group. It does not remove the computational difficulty of determining whether that satisfying action exists.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes \(\mathrm{NP}\)-completeness for the specified atomless problem, including the restriction \(\tau=K=1\). The characterization, certificate argument, reduction, and running-time bounds are valid. No major or minor mathematical issues were found.
The definitions of \(C\) and \(D\) are valid finite sums of rational numbers. Initial feasibility gives \(c_t(a)\le e_t^0\) for every listed entry. Multiplying by the positive masses and summing correctly yields \(C\le E\), hence \(D\ge0\).
The baseline function \(d\) is measurable because it is constant on finitely many measurable listed cells. Those cells cover the population up to a null set: their measures sum to one. Consequently, its integral is \(C\).
Every admissible redistribution satisfies \(b\ge d\) almost everywhere. Since both functions have finite integrals, the asserted identity
\[
\int_0^1(b-d)\,d\lambda=D
\]
is correct.
The successful-deviation set is measurable: within each cell, affordability of a satisfying action is a finite union of measurable budget threshold sets. Unlisted cells collectively have measure zero, so positive success measure must occur in a listed cell. Finiteness of the listed cells justifies selecting one with positive success measure.
For \(D>0\), existence of an affordable satisfying assignment in that cell supplies exactly the witness required by the proposition.
For \(D=0\), the argument that \(b=d\) almost everywhere is correct. The difference is nonnegative almost everywhere and has integral zero. The countable threshold-set argument correctly excludes a positive-measure set on which the difference is strictly positive.
Removing the exceptional null set from the positive-measure successful subset leaves a nonempty set. Choosing an agent there gives a satisfying assignment with \(c_t(a')\le c_t(a)\). There is no unjustified interchange of quantifiers: the proposition requires only one cell and one satisfying assignment.
For \(D=0\), setting \(b=d\) preserves target feasibility and exhausts the available budget. The witness assignment is affordable throughout its positive-measure cell, whose target action fails the goal. Thus the required strictly preferred deviation exists on positive measure.
For \(D>0\), both arguments of the minimum defining \(\delta\) are positive. Also, \(\delta\le x/2<x\), so the proposed subset size is admissible.
The subset construction is rigorous. The displayed Lipschitz estimate makes \(f\) continuous, and its endpoint values are zero and \(x\). These satisfy the hypotheses of the intermediate value theorem.
The numerical bounds are correct:
\[
\delta h\le \frac{Dh}{2(h+1)}\le \frac D2,
\qquad
r=D-\delta h\ge \frac D2>0.
\]
Adding the constant \(r\) over a population of measure one contributes exactly \(r\) to the integral. Therefore the constructed budget is measurable, nonnegative, target-feasible, and has total integral \(E\).
On \(B\), the baseline plus \(h\) already covers the satisfying action’s cost. The additional \(r\) cannot impair affordability. Success occurs on measure \(\delta>0\).
The certificate contains a listed-entry index and one assignment for its type. Its stated length is polynomial in the input size.
Every verification condition is computable in polynomial time: target-goal failure, witness-goal satisfaction, additive costs, and the exact rational comparison involving \(D\). The characterization proves completeness and soundness of this certificate scheme.
In particular, the proof correctly avoids requiring a finite encoding of the measurable redistribution itself.
The reduction from propositional satisfiability satisfies every input restriction:
The computations \(C=0\) and \(E=D=1/2\) are correct.
If \(F\) is satisfiable, the proposed redistribution funds a satisfying action of cost one on half the population and preserves the zero-cost target everywhere. Conversely, successful redistribution entails an assignment satisfying \(q\land F\), whose restriction satisfies \(F\).
The additional initial-equilibrium claim is also correct: every initially affordable assignment has \(q=0\), and therefore none satisfies the goal. With the specified preferences, no agent initially has a strictly preferred affordable deviation.
The construction has polynomial size. Together with membership, it establishes the claimed restricted \(\mathrm{NP}\)-completeness.
For each type in \(U\), taking the maximum baseline cost over its failing listed actions correctly implements the existential choice of a target cell when \(D=0\). When \(D>0\), the characterization requires only satisfiability.
The rational-arithmetic bounds are valid. Input denominator products have bit length bounded by the aggregate input encoding length; cost sums and intermediate numerators likewise have \(O(L)\) bits. The stated schoolbook-arithmetic bounds are conservative.
The enumeration time
\[
O\!\left(\left(K+\tau+m+\sum_{t\in U}2^{n_t}\right)L^2\right)
\]
is justified. The inequality used to derive the bound in the requested parameters is correct, including when some types have no variables. The empty-\(U\) case is explicitly handled.
Thus the bound \(O((K+\tau+m+2^m)L^2)\) and the fixed-parameter tractability claim in \(m\) follow. Hardness with fixed \(\tau\) and \(K\) follows directly from the reduction.
The attribution to Proposition 7 is accurate: the cited paper states \(\mathrm{NP}\)-completeness of elimination and feasible elimination for feasible finite-game outcomes. [*Electric Boolean Games*, Proposition 7](https://spiral.imperial.ac.uk/server/api/core/bitstreams/f1de22dc-b547-4880-a78c-5968edf5280f/content).
The continuous-problem proof is independent of that result. No additional clarification or mathematical repair is needed.
⟨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.