Answer: Polynomial-time solvable in \(m\), \(\tau\), and \(L\), including with \(m=2\) fixed.
Proposition 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateTake $S \notin \mathcal{W}$, then player $i$ is $g$-critical if $\left(\mathcal{W}_{\min} \setminus S \right)_i$ is non-empty with the rank given by the minimal cardinality of the sets in $\left(\mathcal{W}_{\min} \setminus S \right)_i$. Taking $S \in \mathcal{W}$, player $i$ is $g$-critical if $\left(\mathcal{B}_{\min} \setminus S^c \right)_i$ is non-empty with the rank given by the minimal cardinality of the sets in $\left(\mathcal{B}_{\min} \setminus S^c \right)_i$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu\), a rational two-chamber weight matrix \(A\), quotas \(q\), a baseline coalition \(s\), a target type \(t^\star\), and a required focal mass \(\delta>0\), find the infimum of \(\sum_t x_t\), report whether it is attained, and return a witness if it is. For an outside action, require \(As\not\ge q\), \(0\le x\le\mu-s\), \(x_{t^\star}\ge\delta\), \(A(s+x)\ge q\), and \(A(s+x-\delta e_{t^\star})\not\ge q\); for every \(t\) with \(x_t>0\), also require \(A(s+x-x_t e_t)\not\ge q\). For an inside action, require \(As\ge q\), \(0\le x\le s\), \(x_{t^\star}\ge\delta\), \(A(s-x)\not\ge q\), and \(A(s-x+\delta e_{t^\star})\ge q\); for every \(t\) with \(x_t>0\), also require \(A(s-x+x_t e_t)\ge q\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=2\) chambers. Input consists of \(A\in\mathbb{Q}_{\ge0}^{2\times\tau}\), quotas \(q\in\mathbb{Q}_{>0}^{2}\) satisfying \(A\mu\ge q\), a rational baseline \(0\le s\le\mu\), a focal type \(t^\star\in T\), a rational \(\delta>0\), and an action mode, outside or inside. Let \(L\) be the total binary input length.
A coalition mass vector \(y\in[0,\mu]\) wins exactly when \(Ay\ge q\). Vector inequalities are componentwise; \(z\not\ge q\) means \(z_j<q_j\) for at least one chamber \(j\). Let \(e_t\) be the coordinate unit vector for type \(t\).
An outside action is a real vector \(x\) satisfying \(As\not\ge q\), \(0\le x\le\mu-s\), \(x_{t^\star}\ge\delta\), \(A(s+x)\ge q\), and \(A(s+x-\delta e_{t^\star})\not\ge q\); additionally, every \(t\) with \(x_t>0\) must satisfy \(A(s+x-x_te_t)\not\ge q\).
An inside action is a real vector \(x\) satisfying \(As\ge q\), \(0\le x\le s\), \(x_{t^\star}\ge\delta\), \(A(s-x)\not\ge q\), and \(A(s-x+\delta e_{t^\star})\ge q\); additionally, every \(t\) with \(x_t>0\) must satisfy \(A(s-x+x_te_t)\ge q\).
For the specified mode, the computational problem is to determine exactly \(\inf_x\sum_{t\in T}x_t\), determine whether it is attained, and return a rational minimizing witness when attained. An empty feasible set has infimum \(+\infty\), which is not attained.
Is this exact infimum-and-attainment problem solvable in polynomial time in \(m\), \(\tau\), and \(L\), with \(m=2\) fixed, or is it NP-hard?
For finite societies, the discrete algorithm computes the minimum size of an essential critical group containing a focal player by scanning explicitly supplied minimal winning coalitions for outside actions, or minimal blocking coalitions for inside actions; its running time is polynomial in those lists’ encoded size. [Source](https://arxiv.org/html/2207.03565v5).
No result settling this exact mass problem was located.
The problem is solvable in polynomial time. In fact, the argument works for arbitrary \(m\), not just \(m=2\).
The key is that deleting an inessential nonfocal type preserves feasibility and decreases the objective. Consequently, essentiality does not change either the infimum or its attainment. After removing those conditions, the problem is a union of \(m\) linear systems, each containing one strict inequality.
Write \(f=t^\star\) and \(C(x)=\sum_{t\in T}x_t\). Let \(E\) denote the action set specified in the question, and let \(R\) denote the set obtained by dropping only the final essentiality requirement for every participating type.
First check the baseline condition. If \(As\ge q\) in outside mode, or \(As\not\ge q\) in inside mode, the action set is empty. Henceforth assume the appropriate baseline condition holds.
Because \(A\) has nonnegative entries, \(v\le w\) implies \(Av\le Aw\). We will repeatedly use the resulting monotonicity of winning and losing.
For an outside action in \(R\), \(x_f\ge\delta\) gives
\(s+x-x_fe_f\le s+x-\delta e_f\).
The right-hand vector loses, so the left-hand vector loses as well.
For an inside action in \(R\),
\(s-x+x_fe_f\ge s-x+\delta e_f\).
The right-hand vector wins, so the left-hand vector wins as well. Thus the focal type satisfies the full essentiality condition in either mode.
Suppose \(x\in R\) and some nonfocal type \(t\) with \(x_t>0\) fails its essentiality condition. Set
\(x'=x-x_te_t\).
The bounds on \(x\) and the inequality \(x_f\ge\delta\) remain satisfied.
In outside mode, failure of essentiality means
\(A(s+x-x_te_t)\ge q\).
Thus \(s+x'\) wins. Moreover,
\(s+x'-\delta e_f\le s+x-\delta e_f\),
so removing the focal mass \(\delta\) still produces a losing vector. Hence \(x'\in R\).
In inside mode, failure of essentiality means
\(A(s-x+x_te_t)\not\ge q\).
Thus \(s-x'\) loses. Also,
\(s-x'+\delta e_f\ge s-x+\delta e_f\),
so restoring the focal mass \(\delta\) still produces a winning vector. Again \(x'\in R\).
Each deletion reduces the number of positive coordinates and decreases \(C(x)\) by \(x_t>0\). Repeat whenever a nonfocal participant fails essentiality. After at most \(\tau-1\) deletions, all remaining participants are essential; the focal type is essential by Lemma 1. Therefore the resulting vector belongs to \(E\) and has objective at most \(C(x)\).
Since \(E\subseteq R\), while every member of \(R\) can be pruned to a member of \(E\), the two sets are empty simultaneously. When nonempty, Lemma 2 gives
\(\inf_{x\in E}C(x)=\inf_{x\in R}C(x)\).
Their attainment status also agrees. Indeed, if \(x\) minimizes \(C\) over \(R\) but is not essential, Lemma 2 supplies a feasible deletion with strictly smaller objective, a contradiction. Thus every minimizing vector in \(R\) already belongs to \(E\).
Conversely, an attained minimum in \(E\) also minimizes over \(R\), because their infima agree.
It therefore suffices to solve the relaxed problem exactly.
Let \(a_f=Ae_f\), the focal column of \(A\).
Define \(b=q-As\). The relaxed constraints are
\(0\le x\le\mu-s,\qquad x_f\ge\delta,\qquad Ax\ge b\),
together with
\((Ax)_j<b_j+\delta(a_f)_j\)
for at least one chamber \(j\).
For each \(j\in\{1,\ldots,m\}\), define the closed polytope
\(P_j=\{x:0\le x\le\mu-s,\ x_f\ge\delta,\ Ax\ge b,\ (Ax)_j\le b_j+\delta(a_f)_j\}\),
and the affine slack
\(g_j(x)=b_j+\delta(a_f)_j-(Ax)_j\).
Then
\(R=\bigcup_{j=1}^{m}\{x\in P_j:g_j(x)>0\}\).
Define \(d=As-q\). The relaxed constraints are
\(0\le x\le s,\qquad x_f\ge\delta,\qquad Ax\le d+\delta a_f\),
together with
\((Ax)_j>d_j\)
for at least one chamber \(j\).
For each chamber, define
\(P_j=\{x:0\le x\le s,\ x_f\ge\delta,\ Ax\le d+\delta a_f,\ (Ax)_j\ge d_j\}\),
and
\(g_j(x)=(Ax)_j-d_j\).
Again,
\(R=\bigcup_{j=1}^{m}\{x\in P_j:g_j(x)>0\}\).
In both modes, every \(P_j\) is a rational closed polytope contained in a bounded box, and \(g_j\ge0\) throughout \(P_j\).
The following observation handles both modes.
Let \(P\) be a nonempty bounded polytope, and let \(g\) be affine and nonnegative on \(P\). Put \(S=\{x\in P:g(x)>0\}\).
The set \(S\) is nonempty exactly when
\(\max_{x\in P}g(x)>0\).
Suppose this holds, and choose \(z\in S\). For any \(p\in P\) and \(0<\lambda\le1\), convexity gives
\(p_\lambda=(1-\lambda)p+\lambda z\in P\),
and affinity gives
\(g(p_\lambda)=(1-\lambda)g(p)+\lambda g(z)>0\).
Thus \(p_\lambda\in S\) and \(p_\lambda\to p\). Consequently,
\(\inf_{x\in S}C(x)=\min_{x\in P}C(x)\).
If this value is \(\alpha\), it is attained in \(S\) exactly when
\(\max\{g(x):x\in P,\ C(x)=\alpha\}>0\).
The last equivalence follows because the displayed maximization tests whether the optimal face contains a point of \(S\). The optimal face is nonempty and compact, so the maximum exists.
For each chamber \(j\):
\(\alpha_j=\min_{x\in P_j}C(x)\).
Call the remaining branches *active*. If there are none, return infimum \(+\infty\), not attained.
Otherwise return the finite infimum
\(\alpha=\min_{j\text{ active}}\alpha_j\).
Lemma 3 proves this formula for the relaxed problem; Section 1 proves it for the original problem.
To decide attainment, for each active branch with \(\alpha_j=\alpha\), solve
\(\max\{g_j(x):x\in P_j,\ C(x)=\alpha\}\).
If any such maximum is positive, return a rational maximizer as the minimizing witness. It belongs to \(R\), has the global minimum objective, and therefore satisfies every essentiality condition by Section 1.
If all these maxima are zero, the infimum is not attained. To verify exhaustiveness, suppose some \(x\in R\) attained \(\alpha\). It belongs to a strict active branch \(j\), and
\(\alpha\le\alpha_j\le C(x)=\alpha\).
Hence \(\alpha_j=\alpha\), and that branch’s optimal face contains a point with positive slack—contrary to the test result.
We use the standard polynomial-time theorem for rational linear programming: a linear program with rational coefficients can be solved in time polynomial in its encoded length, detecting infeasibility and returning an exact rational optimum and rational optimizer whenever the optimum exists.
Its hypotheses apply here:
All comparisons with zero and between objective values are exact rational comparisons. Consequently, the algorithm handles strictly feasible branches even when their available slack is very small.
The complete infimum-and-attainment problem is therefore polynomial-time solvable in \(m\), \(\tau\), and \(L\).
Here is a valid outside instance showing why the optimal-face test is necessary. Take
\(A=\begin{pmatrix}1&2&0\\0&2&1\end{pmatrix},\quad \mu=(1/4,1/4,1/2),\quad s=0,\quad q=(1/2,1/2),\quad f=1,\quad \delta=1/8.\)
The input promises hold: all masses are positive and normalized, and \(A\mu=(3/4,1)\ge q\).
Every feasible action satisfies \(x_1\ge1/8\) and \(2x_2+x_3\ge1/2\). Since \(x_3\ge0\),
\(2(x_2+x_3)\ge2x_2+x_3\ge1/2\),
so \(C(x)\ge3/8\).
Equality forces \(x_1=1/8\) and \(x_2+x_3=1/4\). Combining the latter equality with \(2x_2+x_3\ge1/2\) forces \(x_3=0\) and \(x_2=1/4\). Removing the focal mass then leaves chamber totals \((1/2,1/2)\), which win. Therefore equality is infeasible.
For every \(0<\varepsilon<1/16\), however, take
\(x^{(\varepsilon)}=(1/8,\ 1/4-\varepsilon,\ 2\varepsilon)\).
This lies within the coordinate bounds and has chamber totals
\(Ax^{(\varepsilon)}=(5/8-2\varepsilon,\ 1/2)\ge q\).
Removing the focal mass makes chamber one lose. Removing type two makes chamber one lose, and removing type three makes chamber two lose. Hence these are essential outside actions, with
\(C(x^{(\varepsilon)})=3/8+\varepsilon\).
Thus their infimum is exactly \(3/8\), and it is not attained.
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the exact infimum-and-attainment problem. The reduction preserves both the infimum and attainment, and the linear programs correctly handle the strict inequalities. No mathematical gaps or false statements were found.
The baseline checks match the definitions: outside actions require \(As\not\ge q\), and inside actions require \(As\ge q\). Failure of the corresponding condition makes the feasible set empty independently of \(x\).
The monotonicity assertion follows from the stipulated nonnegativity of \(A\). It applies to both winning and losing: decreasing a losing vector preserves at least one strict quota failure, while increasing a winning vector preserves all quota inequalities.
Both comparisons in Lemma 1 have the correct direction.
Thus the focal coordinate automatically satisfies the omitted essentiality requirement. The assumption \(\delta>0\) also ensures that the focal type participates.
Lemma 2 correctly identifies the negation of essentiality in each mode.
In outside mode, an inessential participating coordinate can be deleted while preserving winning. The focal-deletion vector decreases componentwise, so its losing condition persists.
In inside mode, deleting an inessential participating coordinate preserves losing. The focal-restoration vector increases componentwise, so its winning condition persists.
The deletion preserves the relevant coordinate bounds and leaves \(x_f\) unchanged because the deleted coordinate is nonfocal. Each deletion strictly reduces the objective and removes one positive coordinate. Rechecking essentiality after each deletion accounts for any changes to the other participants’ status. Therefore the stated termination bound of at most \(\tau-1\) deletions is valid.
The inclusion \(E\subseteq R\), together with the pruning property, establishes simultaneous emptiness and equality of infima.
The attainment argument is also valid. A relaxed minimizer with an inessential participant would admit a feasible deletion with strictly smaller objective, contradicting minimality. Thus every relaxed minimizer is already essential. Conversely, an essential action attaining the common infimum is a relaxed minimizer.
This justifies dropping essentiality for the entire requested optimization problem, including witness extraction.
The outside translation is exact: winning becomes \(Ax\ge b\), and losing after focal deletion becomes
\[
(Ax)_j<b_j+\delta(a_f)_j
\]
for at least one chamber.
The inside translation is exact: winning after focal restoration becomes \(Ax\le d+\delta a_f\), and losing after withdrawal becomes
\[
(Ax)_j>d_j
\]
for at least one chamber.
The definitions of \(P_j\) and \(g_j\) correctly replace each strict inequality with its weak version and a positive-slack requirement. In both modes, \(g_j\ge0\) on \(P_j\). The coordinate bounds make every nonempty \(P_j\) compact.
Zero focal coefficients and incompatible focal bounds are covered by these formulations: branches without positive slack are discarded, and inconsistent bounds yield infeasibility.
Lemma 3 is correct under its stated hypotheses. The convex combinations belong to \(P\), have positive slack, and approach the arbitrary point \(p\). Since \(C\) is linear and continuous, the claimed equality between the strict-branch infimum and the closed-polytope minimum follows.
The optimal-face test is exact. That face is nonempty and compact, and positive maximum slack is equivalent to the existence of a strict-feasible minimizer.
The algorithm correctly discards empty strict branches before comparing their closed-polytope minima. This matters because a closed branch without positive slack need not contribute any feasible action.
The global attainment test is exhaustive. Any relaxed action attaining the global infimum belongs to an active strict branch, whose closed-polytope minimum must equal that infimum. Its positive slack would therefore be detected on the corresponding optimal face.
A rational maximizer returned by a positive-slack test is a relaxed global minimizer. Section 1 correctly establishes that it satisfies all original essentiality conditions.
The stated rational linear-programming theorem is sufficiently precise for these applications. All feasible programs here are bounded, so finite optima are attained.
The complexity claims are valid:
No numerical tolerance or assumed lower bound on positive slack is needed. The argument consequently establishes polynomial time for arbitrary \(m\), and hence for the requested case \(m=2\).
The example satisfies all input promises. The computed total society weights \(A\mu=(3/4,1)\) are correct.
The lower bound \(C(x)\ge3/8\) follows from the focal bound and the second chamber’s winning condition. Equality forces the specified vector \((1/8,1/4,0)\), whose focal-deletion vector wins in both chambers. Thus equality is infeasible.
For every \(0<\varepsilon<1/16\), the displayed family satisfies the coordinate bounds, wins, and loses after deleting the prescribed focal mass. Deleting type two makes chamber one lose; deleting type three makes chamber two lose. All participating types are therefore essential.
Its objective is \(3/8+\varepsilon\), confirming the claimed finite, unattained infimum.
No repair or additional clarification is needed. The proof establishes the claimed polynomial-time classification and supplies a correct procedure for exact values, attainment decisions, and rational minimizing witnesses.
⟨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.