Answer: NP-hard for every fixed \(k\in\{1,\ldots,6\}\), already with \(\tau=2\).
Proposition 7 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (V, A, LP, B, R) satisfying (SMon), a set C ✓V of controllable agents, and a formula '. If the basic strategy σ' for G given C is not successful for ' then no control strategy for G given C is successful for '. An interesting issue now is to know whether there are BRGs satisfying (SMon). We provide a positive answer to this question in the next section.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational distribution over initial belief types, a target formula φ, a controllable portion of the mass, and a common policy \(R^k_{Δ_{d_D,Σ}}\) for some \(k\in\{1,\ldots,6\}\), does there exist a mass transfer from controllable types \((B,e)\) to bases \(B'\) with \(B'\preceq_\varphi B\) such that, under complete interaction and mass-weighted merging, every resulting positive-mass cohort's cycle outcome entails φ?
Let there be \(m\geq1\) propositional variables. Initial bases and the target \(\varphi\) are satisfiable propositional formulas, encoded succinctly; bases are identified up to logical equivalence.
A society is given by its support: the list of \(\tau\) types \((B,e)\) with positive mass, each mass a binary rational, summing to \(1\); \(e\in\{0,1\}\) indicates controllability. Here \(\tau\) is the support size, not the number of possible types, and \(L\) is the total input bit length.
A control divides each controllable type's mass among finitely many satisfiable bases \(B'\), using nonnegative real masses that conserve its mass; each destination must satisfy \(B'\preceq_\varphi B\), meaning \(B\wedge\varphi\models B'\models B\vee\varphi\). Uncontrollable mass stays at its initial base; retaining controllable mass unchanged is allowed. There is no additional budget or cost.
For a weighted profile \(Q\), define \(\Delta_\mu(Q)\) by retaining all interpretations satisfying \(\mu\) that maximize \(\sum_{(D,w)\in Q}w\mathbf{1}_{\omega\models D}\); write \(\Delta(Q)=\Delta_\top(Q)\). Ties retain every maximizer.
The population is atomless and interaction complete: every individual sees the entire current population profile \(Q\), including the rest of its own cohort. Singleton profiles explicitly inserted below have weight \(1\), and \(\uplus\) adds profile weights.
Fix a common policy index \(k\in\{1,\ldots,6\}\). With \(M=\Delta(Q)\), the six updates of a current base \(B\) are \(R^1(B,Q)=M\), \(R^2(B,Q)=\Delta_M(\{(B,1)\})\), \(R^3(B,Q)=\Delta(Q\uplus\{(B,1)\})\), \(R^4(B,Q)=\Delta(\{(B,1),(M,1)\})\), \(R^5(B,Q)=\Delta_B(\{(M,1)\})\), and \(R^6(B,Q)=\Delta_B(Q)\).
After the initial control, updates are synchronous and cohort masses remain fixed. A cohort's outcome is the disjunction of its bases on the eventual cycle, considered up to logical equivalence.
Target. For each fixed \(k\in\{1,\ldots,6\}\), is deciding whether a control makes every positive-mass cohort's outcome entail \(\varphi\) solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), and \(L\).
Nearest known results. In finite societies where successful unanimous acceptance survives every initial promotion, replacing every controllable base by \(\varphi\) succeeds whenever any control succeeds; this is a structural result, not a complexity classification.
Finite complete societies with a common one of these six drastic-distance sum policies satisfy that preservation property. [Source](https://www.cril.univ-artois.fr/~marquis/ijcai16-long.pdf). No result settling precisely the mass model defined above was located.
For every fixed \(k\in\{1,\ldots,6\}\), the decision problem is NP-hard, under polynomial-time many-one reductions. This holds already with:
Thus a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The following deterministic upper bounds also hold. They are not claimed to be optimal.
| Fixed policy \(k\) | Classification | Decision running time |
|---|---|---|
| \(1,2,4\) | NP-hard | \(2^m(\tau+1)\operatorname{poly}(L)\) |
| \(5\) | NP-hard | \(2^m(\tau+1)\operatorname{poly}(L)\) |
| \(3,6\) | NP-hard | \(2^{O(m4^m)}\operatorname{poly}(\tau,L)\) |
The algorithms allow arbitrary finite splitting into real masses and retain every tied maximizer. In particular, all six problems are polynomial-time solvable when \(m\) is fixed.
Let \(\Omega=\{0,1\}^m\), let \(N=|\Omega|=2^m\), and identify each base with its nonempty model set. Write \(G=\operatorname{Mod}(\varphi)\).
Consider any finite profile with positive cohort masses \(w_i\), summing to \(1\), and current model sets \(D_i\). Define
\[ s(\omega)=\sum_i w_i\mathbf{1}_{\omega\in D_i}, \qquad S=\max_{\omega\in\Omega}s(\omega), \qquad M=\{\omega:s(\omega)=S\}. \]
Here and below, these displayed expressions use the usual mathematical interpretation. Because some satisfiable base has positive mass, \(S>0\).
For cohort \(i\), policy \(3\) maximizes \(s(\omega)+\mathbf{1}_{\omega\in D_i}\).
If \(\omega\in D_i\), then \(s(\omega)\geq w_i>0\), so its augmented score exceeds \(1\). If \(\omega\notin D_i\), its augmented score is at most \(1\). Therefore every maximizer belongs to \(D_i\), and within \(D_i\) the added score is constant.
Consequently,
\[ R^3(D_i,Q)=R^6(D_i,Q) =\operatorname*{arg\,max}_{\omega\in D_i}s(\omega). \]
This uses both normalization of the population mass and positive cohort mass.
Their updates are:
| Policy | If \(D_i\cap M\neq\varnothing\) | If \(D_i\cap M=\varnothing\) |
|---|---|---|
| \(1\) | \(M\) | \(M\) |
| \(2\) | \(D_i\cap M\) | \(M\) |
| \(4\) | \(D_i\cap M\) | \(D_i\cup M\) |
| \(5\) | \(D_i\cap M\) | \(D_i\) |
For policy \(4\), this follows because the two singleton bases give score \(2\) on their intersection, or, when disjoint, score \(1\) on their union.
Let \(a\) be the total mass of cohorts whose initial bases miss \(M\).
Under policy \(2\), after one update every base is contained in \(M\), and every \(\omega\in M\) has score \(S+a\): its original supporters retain it, and all cohorts missing \(M\) acquire it. Thus the new maximizing set is exactly \(M\), and the profile is fixed.
Under policy \(4\), after one update every \(\omega\in M\) again has score \(S+a\). Every interpretation outside \(M\) has score at most its original score, which is strictly below \(S\). The maximizing set therefore remains \(M\). At the second update, bases previously missing \(M\) become \(M\); all other bases remain their intersections with \(M\). This profile is fixed.
Policy \(1\) plainly reaches the unanimous base \(M\) after one update.
In all three cases the union of final bases is \(M\). Indeed, every \(\omega\in M\) originally had a positive-mass supporter, which retains it. Therefore:
For policies \(1,2,4\), a given controlled profile succeeds exactly when \(M\subseteq G\).
For policy \(5\), every interpretation in \(M\) retains exactly its original supporters, so its score remains \(S\). Scores outside \(M\) cannot increase and remain strictly below \(S\). Thus \(M\) remains unchanged, and the profile is fixed after one update.
It follows that:
For policy \(5\), a given controlled profile succeeds exactly when \(M\subseteq G\) and every initial cohort whose base contains a model outside \(G\) intersects \(M\).
Necessity of \(M\subseteq G\) follows because each interpretation in \(M\) has a positive-mass supporter and survives in that supporter’s final base.
Both policies contract every current base to its score-maximizing models. We prove the uniform bound, independently of the number of cohorts and their masses.
Initially regard all cohorts as active. Among their supported interpretations, take the set \(A\) of interpretations having maximal active score.
Every active cohort meeting \(A\) contracts to its intersection with \(A\). Every interpretation in \(A\) retains all its active supporters, so its score remains unchanged. Every interpretation outside \(A\) had strictly smaller active score, and contraction cannot increase that score. Consequently, the cohorts meeting \(A\) have reached fixed bases.
Their resulting bases are contained in \(A\). The remaining active cohorts have bases disjoint from \(A\), and contraction preserves this disjointness. Hence the fixed cohorts no longer contribute to scores on active bases.
Repeat this argument on the remaining active profile. Each round fixes some cohorts and uses a nonempty set of interpretations disjoint from all sets used previously. There can be at most \(N\) such rounds.
Thus every cohort is fixed after at most \(N\) updates. In particular, eventual outcomes are fixed bases; nontrivial eventual cycles do not occur.
Let \(F\) be an arbitrary propositional SAT instance on variables \(x_1,\ldots,x_n\). Introduce a fresh variable \(p\), set \(\varphi=p\), and construct two types:
| Initial base | Controllable? | Mass |
|---|---|---|
| \(B=\neg p\vee(p\wedge F)\) | No | \(3/4\) |
| \(C=\neg p\) | Yes | \(1/4\) |
Both initial bases and the target are satisfiable, regardless of whether \(F\) is satisfiable. The construction has \(m=n+1\), \(\tau=2\), and size linear in the SAT input size.
The controllable type is genuinely changeable. Indeed, \(C\wedge p\) is unsatisfiable and \(C\vee p\) is a tautology, so every satisfiable destination base is admissible.
Replace the entire controllable mass by \(p\). The score is:
\[ s(\omega)= \begin{cases} 1,&\omega\models p\wedge F,\\ 1/4,&\omega\models p\wedge\neg F,\\ 3/4,&\omega\models\neg p. \end{cases} \]
Hence \(M=\operatorname{Mod}(p\wedge F)\), which is nonempty.
Both current bases contain \(M\). Policies \(1,2,4,5\) therefore update both cohorts to \(M\). Policy \(6\) also does so, because \(M\) is precisely the set of maximum-score models within either base. Policy \(3\) coincides with policy \(6\).
Once both cohorts hold \(M\), that profile is fixed under every policy. Every outcome entails \(p\).
Now the uncontrollable base is equivalent to \(\neg p\).
Under any admissible splitting of the controllable mass:
Thus the initial maximizing set is nonempty and contained in \(\operatorname{Mod}(\neg p)\).
For policies \(1,2,4\), Section 2.2 implies failure.
For policies \(5,6\), every update contracts the uncontrollable cohort’s current base. Its base therefore remains a nonempty subset of \(\operatorname{Mod}(\neg p)\) forever. Its outcome cannot entail \(p\). Policy \(3\) again coincides with policy \(6\).
We have proved, for each fixed policy, that the constructed instance admits a successful control if and only if \(F\) is satisfiable. This establishes all six NP-hardness claims.
Write \(w_i\) for the input type masses. Define:
\[ c=\sum_{i:e_i=1}w_i, \qquad u(\omega)=\sum_{i:e_i=0}w_i\mathbf{1}_{\omega\models B_i}. \]
Thus \(c\) is the total controllable mass and \(u\) is the contribution of uncontrollable types.
Enumerating all interpretations evaluates all input formulas and computes these quantities in \(2^m(\tau+1)\operatorname{poly}(L)\) bit operations. Every rational sum and comparison has bit length polynomial in \(L\).
Replacing every controllable type by \(\varphi\) gives score \(u(\omega)+c\) on \(G\), and \(u(\omega)\) outside \(G\).
Under any control, a good interpretation’s score is at most \(u(\omega)+c\), while a bad interpretation’s score is at least \(u(\omega)\). Therefore a successful control exists exactly when:
\[ \max_{\omega\in G}\bigl(u(\omega)+c\bigr) > \max_{\omega\notin G}u(\omega). \]
To justify necessity, a successful controlled profile must have only good global maximizers. Its maximum good score strictly exceeds every bad score, and the preceding bounds imply the displayed inequality. Sufficiency follows by replacing all controllable mass by \(\varphi\).
If \(G=\Omega\), the answer is immediately yes.
This proves the stated running time for these three policies.
Define the forced controllable contribution on good interpretations:
\[ f(\omega)= \sum_{i:e_i=1}w_i\mathbf{1}_{\omega\models B_i}, \qquad \omega\in G. \]
Promotion requires every destination of type \(i\) to contain \(\operatorname{Mod}(B_i)\cap G\). Hence every control gives a good interpretation score at least \(u(\omega)+f(\omega)\).
Let \(J\) consist of the uncontrollable types whose bases contain at least one bad interpretation.
If \(J=\varnothing\), the answer is yes: replace all controllable mass by \(\varphi\).
If some \(i\in J\) has no good model, the answer is no, since policy \(5\) always contracts that uncontrollable base.
Otherwise define:
\[ A=\max_{\omega\in G}\bigl(u(\omega)+f(\omega)\bigr), \qquad D=\max_{\omega\notin G}u(\omega), \]
and
\[ H= \min_{i\in J} \max_{\omega\in G\cap\operatorname{Mod}(B_i)} \bigl(u(\omega)+c\bigr). \]
The exact decision criterion is \(H\geq A\) and \(H>D\).
Suppose a successful control exists. Its initial maximizing set \(M\) is contained in \(G\).
Every positive-mass controlled destination must contain a good model: otherwise contraction could never make that cohort accept \(\varphi\). Remove all bad models from every controlled destination. This preserves satisfiability and admissibility. Good scores remain unchanged and bad scores decrease, so \(M\) remains exactly unchanged. Uncontrollable cohorts consequently have the same updates, while controlled cohorts now already entail \(\varphi\).
Let \(T\) be the maximum score of this modified profile. Forced good contributions imply \(T\geq A\). Since all bad scores now equal \(u(\omega)\), and no bad interpretation maximizes, \(T>D\).
Every type \(i\in J\) must meet \(M\). For such a meeting interpretation \(\omega\),
\[ T=s(\omega)\leq u(\omega)+c. \]
Thus \(T\leq H\), proving \(H\geq A\) and \(H>D\).
Assume these inequalities. We construct a finite control with good scores
\[ s(\omega)=\min\{u(\omega)+c,H\}, \qquad \omega\in G, \]
and bad scores \(s(\omega)=u(\omega)\).
The desired total controllable contribution at each good interpretation lies between \(f(\omega)\) and \(c\). Therefore it can be divided among controllable types, respecting the forced inclusion of every model in \(\operatorname{Mod}(B_i)\cap G\).
Moreover, there is a good interpretation \(z\) with \(u(z)+c=H\): choose a type attaining the minimum defining \(H\), then an interpretation attaining its inner maximum. At \(z\), the desired contribution is \(c\), so every controllable type includes \(z\) with its entire mass.
For each controllable type, realize the chosen inclusion fractions by independently including its optional good interpretations. Always include its forced good interpretations and \(z\). This is a distribution over finitely many bases. Every destination is nonempty, is contained in \(G\), and contains the required intersection with \(G\); hence every destination is admissible.
The resulting maximizing set is exactly:
\[ M=\{\omega\in G:u(\omega)+c\geq H\}. \]
Bad scores are strictly below \(H\), because \(H>D\). Every type in \(J\) meets \(M\), by the definition of \(H\). All controlled destinations and all other uncontrollable bases already entail \(\varphi\). Section 2.2 therefore proves success.
All quantities in this criterion require only enumeration of interpretations and rational sums and comparisons. This establishes the singly exponential bound for policy \(5\).
Here arbitrary real splitting is handled through rational linear programming, without assuming rational controls in advance.
A weak order is an ordered partition of \(\Omega\), representing equal-score blocks in decreasing score order. There are at most \(N^N\) weak orders: assign each interpretation its block rank in \(\{1,\ldots,N\}\).
Enumerate sequences of \(N\) weak orders, one for each update round. Their number is at most \(N^{N^2}\).
For a fixed sequence and any nonempty initial model set \(E\), its hypothetical trajectory is determined: at each round, retain the elements of its current set in the highest score block that it meets.
For each controllable input type \(i\), enumerate every admissible nonempty destination \(E\), namely every set satisfying:
\[ \operatorname{Mod}(B_i)\cap G \subseteq E \subseteq \operatorname{Mod}(B_i)\cup G. \]
Introduce its mass variable \(x_{i,E}\geq0\), with conservation constraint:
\[ \sum_E x_{i,E}=w_i. \]
Uncontrollable types retain fixed initial masses. There are at most \(\tau 2^N\) variables.
At each round, each interpretation’s score is a rational linear expression in these variables: the coefficient of a destination variable is \(1\) exactly when its hypothetical current base contains that interpretation.
Require equal scores within each proposed weak-order block and strictly decreasing scores between consecutive blocks. Also require \(x_{i,E}=0\) whenever the hypothetical base after \(N\) updates contains a bad interpretation. Reject the sequence if an uncontrollable cohort’s hypothetical final base contains a bad interpretation.
To handle strict inequalities, introduce \(0\leq\delta\leq1\), replace each required strict score difference by a difference at least \(\delta\), and maximize \(\delta\). Accept the sequence exactly when the linear program is feasible with optimum strictly positive.
This transformation is exact: finitely many strict inequalities have a common positive margin whenever they all hold. If there are no strict inequalities, feasible mass assignments allow \(\delta=1\).
If the linear program accepts, its score constraints ensure, by induction on rounds, that every positive-mass cohort follows its hypothetical trajectory. Section 2.3 guarantees stabilization by round \(N\), and the final-base constraints guarantee success.
Conversely, any successful real-mass control determines a sequence of actual weak score orders. Its masses satisfy the associated linear constraints, with a positive common margin for all strict inequalities. Therefore that sequence is accepted.
The programs have rational coefficients, explicitly encoded polynomial size in \(\tau 2^N,N,L\). Rational linear programming is solvable in polynomial time in this encoded size; allowing real control masses introduces no additional feasibility issue.
The total running time is bounded by:
\[ N^{N^2}\operatorname{poly}(\tau 2^N,N,L) = 2^{O(m4^m)}\operatorname{poly}(\tau,L). \]
Policy \(3\) has the same algorithm because it coincides with policy \(6\).
The cited [finite-society preservation result](https://www.cril.univ-artois.fr/~marquis/ijcai16-long.pdf) is not used in these proofs. Under the specified mass updates, the replacement shortcut fails for policies \(3,5,6\).
The following examples use distinct interpretations \(a,b,c,d\) with \(m=2\), and target model set \(G=\{a,c\}\). Every listed model set is expressible by a satisfiable propositional formula.
Take uncontrollable bases \(\{a,b\}\) and \(\{c\}\), with masses \(1/4\) and \(1/2\), and controllable base \(\{a,b\}\), with mass \(1/4\).
Replacing the controllable base by \(\{a\}\) is admissible. Scores are \(s(a)=s(c)=1/2\) and \(s(b)=1/4\). The maximizing set is \(\{a,c\}\), and every cohort’s update entails the target.
Replacing it instead by \(G\) gives \(s(c)=3/4\), \(s(a)=1/2\), and \(s(b)=1/4\). Now \(M=\{c\}\). The uncontrollable base \(\{a,b\}\) misses \(M\), remains unchanged, and fails.
Take uncontrollable bases \(\{a\}\), \(\{a,b\}\), and \(\{c,b\}\), with masses \(1/2,1/8,1/4\), and controllable base \(\{b\}\), with mass \(1/8\).
Replacing the controllable base by \(\{c\}\) is admissible. Initially:
\[ s(a)=5/8,\qquad s(c)=s(b)=3/8. \]
The base \(\{a,b\}\) first contracts to \(\{a\}\), while \(\{c,b\}\) retains both models. The next scores satisfy \(s(c)=3/8>s(b)=1/4\), so \(\{c,b\}\) contracts to \(\{c\}\). Every final base entails the target.
Replacing the controllable base by \(G\) instead gives initial scores \(s(a)=3/4\) and \(s(c)=s(b)=3/8\). After one update, the controllable cohort holds \(\{a\}\), and the scores of \(c,b\) both become \(1/4\). The base \(\{c,b\}\) remains tied and fixed, so unanimity fails.
These examples also show why the upper-bound arguments must respect the exact interaction and tie conventions in the question.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output establishes NP-hardness for every fixed policy \(k\in\{1,\ldots,6\}\), with the stated deterministic upper bounds. I found no mathematical errors or gaps requiring repair.
1. Model conventions and policy equivalence
Identifying bases with nonempty model sets respects logical equivalence and satisfiability. Finite splitting produces a finite profile, and zero-mass destinations can be discarded.
Section 2.1 correctly proves \(R^3=R^6\) for every positive-mass cohort. An interpretation inside its current base has augmented score at least \(1+w_i>1\), whereas an interpretation outside has augmented score at most \(1\). Consequently, policy \(3\) retains precisely the score maximizers within the current base.
Both necessary hypotheses are present: population mass remains normalized to \(1\), and every cohort under consideration has positive mass. In Section 5, hypothetical trajectories for zero-mass destinations cause no problem because correctness is asserted only for positive-mass cohorts.
2. Dynamics for policies \(1,2,4,5\)
The update table follows correctly from the definitions, including the disjoint-base cases and retention of all ties.
For policy \(2\), the first update places every base inside \(M\). Each interpretation in \(M\) receives its original supporting mass \(S\), plus exactly the mass \(a\) of cohorts initially missing \(M\). Outside scores become zero. Since \(S>0\), the maximizing set remains exactly \(M\), and the resulting profile is fixed.
For policy \(4\), interpretations in \(M\) similarly obtain score \(S+a\). Outside \(M\), support cannot increase, so scores remain strictly below \(S\). The second update removes the remaining outside models from initially disjoint bases. The resulting profile is fixed.
Policy \(1\) immediately produces unanimous base \(M\). For all three policies, every interpretation in \(M\) survives in at least one positive-mass cohort. Thus the union of final bases is exactly \(M\), validating the stated success criterion.
For policy \(5\), maximizers retain all their original supporters, and outside scores cannot increase. Hence \(M\) remains unchanged and the first updated profile is fixed. A base containing bad models succeeds precisely when it meets \(M\), provided \(M\subseteq G\). Both directions of the criterion in Section 2.2 are justified.
3. Stabilization for policies \(3,6\)
The active-cohort argument is sound.
At each stage, every active cohort meeting the maximal active-score set \(A\) contracts to its intersection with \(A\). Every interpretation in \(A\) retains all its active supporters. Interpretations outside \(A\) cannot gain support, so these cohorts remain fixed thereafter.
The remaining active bases are disjoint from \(A\). Previously fixed cohorts therefore contribute nothing on those bases, permitting the same argument at the next synchronous update.
Each stage fixes at least one positive-mass cohort and identifies a nonempty interpretation set disjoint from all previously selected sets. There are at most \(N\) stages. The bound is independent of the number of destinations and their real masses.
This establishes actual stabilization, so the eventual-cycle definition introduces no additional success condition.
4. NP-hardness reduction
The reduction meets every input restriction:
When \(F\) is satisfiable, the three stated scores are correct. The maximizing set is exactly \(\operatorname{Mod}(p\wedge F)\), and both current bases contain it. Every policy consequently sends both cohorts to that set, which is fixed.
When \(F\) is unsatisfiable, every bad interpretation has score at least \(3/4\), while every good interpretation has score at most \(1/4\), under every allowed finite splitting. Policies \(1,2,4\) fail by their established criterion. For policies \(5,6\), the uncontrollable base contracts while remaining nonempty and contained in \(\operatorname{Mod}(\neg p)\). Its outcome therefore cannot entail \(p\). Policy \(3\) follows from its equivalence with policy \(6\).
The reduction establishes the required equivalence for arbitrary controls, not merely unsplit or rational controls. All six NP-hardness conclusions follow.
5. Algorithms for policies \(1,2,4\)
Replacing a controllable base by \(\varphi\) is always admissible.
The pointwise bounds used in Section 4.1 hold under every control: a good score is at most \(u(\omega)+c\), and a bad score is at least \(u(\omega)\). Combined with the success criterion, they give the displayed strict inequality as a necessary condition. Replacing all controllable mass by \(\varphi\) makes it sufficient.
Strict inequality is essential because tied bad maximizers are retained. The separate treatment of \(G=\Omega\) correctly avoids a maximum over an empty set.
Truth-table enumeration and exact rational arithmetic support the stated bound \(2^m(\tau+1)\operatorname{poly}(L)\).
6. Policy \(5\) criterion and splitting construction
The preliminary cases are correct. If \(J\) is empty, target replacement leaves every cohort with a good base. If an uncontrollable bad-containing base has no good model, contraction makes success impossible.
For necessity, removing bad models from successful controlled destinations preserves nonemptiness and admissibility. Good scores remain unchanged, and bad scores decrease, so the maximizing set stays exactly the same. The resulting maximum \(T\) satisfies \(T\geq A\), \(T>D\), and \(T\leq H\), establishing both required inequalities.
For sufficiency, the desired controllable contribution is indeed within the claimed interval. The hypotheses give \(H\geq u(\omega)+f(\omega)\), while \(c\geq f(\omega)\). Consequently,
\[
f(\omega)\leq \min\{u(\omega)+c,H\}-u(\omega)\leq c.
\]
The coordinatewise allocation among controllable types respects their forced inclusions. Optional memberships impose no cross-interpretation restrictions under the stated promotion relation.
The chosen interpretation \(z\) exists because the relevant finite sets are nonempty and both extrema are attained. Its desired controllable contribution is \(c\), ensuring that every positive-mass controlled destination contains \(z\). Independent inclusion of optional interpretations then gives a finite distribution over nonempty admissible bases with the requested marginals.
The maximizing set and the intersections with every type in \(J\) follow as written. The decision algorithm only computes the criterion; it need not explicitly output the potentially large splitting distribution. The running-time claim is therefore justified.
7. Linear-programming algorithm for policies \(3,6\)
The weak-order enumeration bound is valid: canonical block ranks inject weak orders into maps from \(N\) interpretations to \(N\) ranks. Enumerating \(N\) rounds therefore requires at most \(N^{N^2}\) sequences.
Enumerating all admissible model sets covers every allowed control. Multiple cohorts from the same type with identical destinations can be represented by their combined mass, since their updates and subsequent trajectories coincide.
For a fixed order sequence, hypothetical trajectories determine the score expressions. Equalities within blocks and strict inequalities between consecutive blocks enforce the entire proposed order. The final-base constraints correctly apply success requirements to positive-mass destinations.
The common-margin transformation is exact because there are finitely many strict inequalities. The linear programs have rational coefficients. Conservation bounds every mass variable, and \(\delta\) is explicitly bounded, so a feasible program has an attained optimum. Exact rational linear programming can distinguish a positive optimum from zero in polynomial time in the explicit encoding length.
Both directions of the correctness argument follow. The program size and sequence count yield \(2^{O(m4^m)}\operatorname{poly}(\tau,L)\), as claimed. Fixing \(m\) makes all stated bounds polynomial in the remaining input parameters.
8. Examples and external dependence
Both examples in Section 6 have admissible destinations, correctly computed scores, and the claimed fixed outcomes. They establish failure of target replacement for the specified mass model.
The hardness reduction and algorithms do not rely on transferring the cited [finite-society preservation theorem](https://www.cril.univ-artois.fr/~marquis/ijcai16-long.pdf) to this model. No unverified application of that theorem enters the argument.
Required clarification: none. The output resolves the assigned classification and provides justified running times.
⟨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.