Answer: Exact polynomial-time solvable in \(m,\tau,L\), returning rational \(\epsilon^\ast\) and an optimal rational payoff-rate vector \(p^\ast\).
Theorem 3.2 — class: algorithmic
Given rational type masses \(\mu\) with \(\sum_t\mu_t=1\) and an explicitly represented rational piecewise-affine coalition-value function \(v(q)\) over feasible submass vectors \(q\in[0,\mu]\), compute the minimum \(\epsilon\) and nonnegative payoff rates \(p_t\) satisfying \(p^\top\mu=v(\mu)\) and \(p^\top q\ge v(q)-\epsilon\lVert q\rVert_1\) for every feasible deviation \(q\); return an exact optimum or certificate.
A society is given by its support: the list of the \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input specifies \(v:[0,\mu]\to\mathbb R\) by \(m\) closed rational polyhedra covering \([0,\mu]\), each given by linear inequalities and a rational affine value formula; formulas agree on overlaps. Assume \(v(0)=0\), \(v(\mu)\ge0\), and \(v(q+r)\ge v(q)+v(r)\) whenever \(q,r\ge0\) and \(q+r\le\mu\). Values elsewhere may be negative. Let \(L\) be the total binary input length.
A payoff rate \(p_t\ge0\) assigns payoff \(p_tq_t\) to a deviating mass \(q_t\) of type \(t\). Define the continuous weak least-core problem as minimizing \(\epsilon\in\mathbb R\) over rates \(p\ge0\) satisfying \(p^\top\mu=v(\mu)\) and \(p^\top q\ge v(q)-\epsilon\lVert q\rVert_1\) for every real vector \(q\in[0,\mu]\), including \(q=\mu\).
Is this exact continuous weak least-core optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For discrete superadditive games, explicitly listed synergy coalitions suffice to compute a nonnegative weak least-core allocation by an LP, in polynomial time in that representation and the supplied grand-coalition value; a synergy coalition is a singleton or a coalition worth strictly more than every proper partition. [Riley et al.](https://cgi.csc.liv.ac.uk/~katie/aamas16.pdf)
No result settling the exact continuous problem with the input representation above was located.
The exact continuous weak least-core problem is solvable in polynomial time in \(m,\tau,L\). Both the optimal value and an optimal payoff-rate vector can be returned as exact rational numbers.
The proof constructs a polynomial-size rational linear program. Superadditivity is not needed for this construction.
Write the supplied pieces and their value formulas as
\(P_i=\{q\in\mathbb R^\tau:D_iq\le d_i\},\qquad v(q)=a_i^\top q+c_i\quad\text{on }P_i\cap[0,\mu].\)
Intersect every piece with the domain:
\(Q_i=P_i\cap[0,\mu]=\{q\in\mathbb R^\tau:A_iq\le b_i\}.\)
Here \(A_iq\le b_i\) includes the inequalities \(q\le\mu\) and \(-q\le0\). Test each \(Q_i\) for emptiness by rational LP feasibility and discard empty pieces. Let \(I\) index the remaining pieces, and let \(s_i\) be the number of rows of \(A_i\).
Every retained \(Q_i\) is nonempty and compact, and together they cover \([0,\mu]\). This preprocessing adds at most \(2m\tau\) inequalities and has polynomial encoding size.
Set \(V=v(\mu)\). We can compute \(V\) exactly by finding a piece containing \(\mu\) and evaluating its affine formula. The overlap agreement ensures that the result is independent of the chosen piece.
Let \(\mathbf1\in\mathbb R^\tau\) denote the all-ones vector. Since \(q\ge0\), we have \(\lVert q\rVert_1=\mathbf1^\top q\). Thus, on \(Q_i\), the deviation constraints are equivalent to
\((a_i-p-\epsilon\mathbf1)^\top q+c_i\le0\qquad\text{for every }q\in Q_i.\)
Fix \(p,\epsilon\), and a retained piece \(i\). Consider the LP
\(\max\{(a_i-p-\epsilon\mathbf1)^\top q:A_iq\le b_i,\ q\in\mathbb R^\tau\}.\)
The variable \(q\) is unrestricted in this LP notation because its box constraints have already been included in \(A_iq\le b_i\).
Its feasible set is nonempty and compact, so its maximum is finite and attained. Its dual is
\(\min\{b_i^\top\lambda_i:A_i^\top\lambda_i=a_i-p-\epsilon\mathbf1,\ \lambda_i\ge0\}.\)
By LP strong duality, the dual also attains the same finite optimum. This theorem applies to general LPs, including those whose feasible sets have lower dimension. See the [LP duality theorem and unrestricted-variable formulation](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture05.pdf).
Consequently, all deviation constraints on \(Q_i\) hold if and only if there exists \(\lambda_i\in\mathbb R^{s_i}\) satisfying
\(\lambda_i\ge0,\qquad A_i^\top\lambda_i=a_i-p-\epsilon\mathbf1,\qquad b_i^\top\lambda_i+c_i\le0.\)
For completeness, sufficiency follows directly: for any \(q\in Q_i\),
\((a_i-p-\epsilon\mathbf1)^\top q+c_i =\lambda_i^\top A_iq+c_i \le\lambda_i^\top b_i+c_i \le0.\)
For necessity, if every deviation constraint holds, the primal optimum is at most \(-c_i\). An attained optimal dual solution therefore satisfies \(b_i^\top\lambda_i+c_i\le0\).
The original problem is exactly the following rational LP, with variables \(p,\epsilon\), and \(\lambda_i\) for \(i\in I\):
Minimize \(\epsilon\), subject to
The added constraint \(\epsilon\ge0\) does not change the problem. Indeed, the required deviation constraint at \(q=\mu\), together with efficiency and \(\mathbf1^\top\mu=1\), gives
\(V=p^\top\mu\ge v(\mu)-\epsilon\lVert\mu\rVert_1=V-\epsilon,\)
and hence \(\epsilon\ge0\).
Section 2 proves that the projection of this LP’s feasible set onto \((p,\epsilon)\) is precisely the original feasible set. Coverage of the domain ensures that every real deviation is included, including boundary points and deviations arbitrarily close to zero.
We next prove that the optimization has a finite, attained optimum.
Define the nonnegative rational number
\(C=\max\bigl(\{0\}\cup\{a_{it}:i\in I,\ 1\le t\le\tau\}\bigr).\)
We claim that
\(v(q)\le C\mathbf1^\top q\qquad\text{for every }q\in[0,\mu].\)
For \(q=0\), this follows from \(v(0)=0\). Fix any other \(q\). For each piece, the set
\(T_i=\{t\in[0,1]:tq\in Q_i\}\)
is either empty or a closed interval, possibly a singleton, because \(Q_i\) is closed and convex. These finitely many intervals cover \([0,1]\).
Partition \([0,1]\) at all their endpoints, obtaining
\(0=t_0<t_1<\cdots<t_k=1.\)
Each segment \([t_{j-1},t_j]\) lies in some \(T_{i_j}\): choose an interior point and an interval containing it; that interval cannot start or end inside the segment, and its closedness includes the segment’s endpoints.
The affine formula therefore gives
\(v(t_jq)-v(t_{j-1}q)=(t_j-t_{j-1})a_{i_j}^\top q.\)
Since every coordinate of \(q\) is nonnegative and every coefficient \(a_{i_jt}\le C\),
\(a_{i_j}^\top q\le C\mathbf1^\top q.\)
Summing the increments and using \(v(0)=0\) proves the claim.
Now choose \(p=V\mathbf1\) and \(\epsilon=C\). Because \(V\ge0\) and \(\mathbf1^\top\mu=1\), these rates are nonnegative and efficient. Furthermore,
\(p^\top q+\epsilon\lVert q\rVert_1=(V+C)\mathbf1^\top q\ge C\mathbf1^\top q\ge v(q).\)
Thus the original problem, and hence the equivalent LP, is feasible. Its objective is bounded below by zero. A feasible LP with a bounded objective attains its optimum; with rational coefficients, it has a rational optimal solution.
The constructed LP has
\(\tau+1+\sum_{i\in I}s_i\)
variables and \(O(\tau+\sum_{i\in I}s_i+m\tau)\) scalar constraints.
All coefficients come from the input, box inequalities, the rational value \(V\), or constants. Their total binary encoding length is polynomial in \(m,\tau,L\). In particular, computing \(V\) by rational dot-product arithmetic takes polynomial time and produces a number of polynomial bit length.
The standard exact rational LP theorem supplies a polynomial-time algorithm that detects infeasibility or unboundedness, or returns an exact rational optimum and optimizer. Exactness here is in the binary bit model; see [Gleixner and Steffy, Section 1.3](https://arxiv.org/html/1912.12820v1#S1.SS3). Our LP is feasible and bounded in objective by Section 4, so it returns an optimal \(\epsilon^\ast\) and \(p^\ast\).
Therefore the stated continuous optimization problem is polynomial-time solvable. The proof accommodates negative values, lower-dimensional pieces, and arbitrarily small deviations. It holds under all the given promises and, in fact, does not require superadditivity.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The proposed LP is exactly equivalent to the continuous optimization problem, is feasible with a finite attained optimum, and has polynomial binary encoding length. No major or minor mathematical issues were found.
The output addresses the specified representation: explicitly supplied rational polyhedra with rational affine formulas, in dimension equal to the support size \(\tau\).
Intersecting each piece with \([0,\mu]\) is valid. Every retained \(Q_i\) is nonempty, closed, and bounded, hence compact. Discarding empty intersections preserves coverage. Adding the box inequalities introduces at most \(2m\tau\) rows, with polynomial encoding length.
The computation of \(V=v(\mu)\) is justified: coverage supplies a piece containing \(\mu\), membership can be checked using rational arithmetic, and overlap agreement makes the evaluated value unambiguous.
The identity \(\lVert q\rVert_1=\mathbf1^\top q\) holds throughout the domain because all coordinates are nonnegative. Consequently, the rewritten piecewise deviation inequalities have the correct signs.
Finding: Correct, with no missing domain assumption.
For fixed \(p,\epsilon\), the primal objective on piece \(i\) has coefficient vector \(a_i-p-\epsilon\mathbf1\). Its feasible set is nonempty and compact, so its optimum exists and is finite.
Because the primal variable is unrestricted and all inequalities—including its box bounds—are in \(A_iq\le b_i\), the displayed dual correctly has:
The strong-duality assertion used here is valid: a feasible LP with finite optimum has an attained dual optimum of equal value. The cited notes explicitly cover unrestricted variables and state the requisite existence and equality theorem. No full-dimensionality hypothesis is needed. [LP duality notes](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture05.pdf)
Both implications of the certificate equivalence are correctly established. Sufficiency uses \(A_iq\le b_i\) and \(\lambda_i\ge0\). Necessity uses an optimal dual solution whose objective is at most \(-c_i\).
The quantifiers are also correct: for each fixed \(p,\epsilon\), universal validity on a piece is equivalent to the existence of its own multiplier vector. Collecting these vectors into one LP preserves that equivalence.
Finding: Correct, including for lower-dimensional pieces.
Rearranging the dual equality gives precisely
\(A_i^\top\lambda_i+p+\epsilon\mathbf1=a_i\).
All displayed constraints are linear in the optimization variables.
The additional restriction \(\epsilon\ge0\) follows from the original constraints at \(q=\mu\), since efficiency gives \(p^\top\mu=V\) and normalization gives \(\lVert\mu\rVert_1=1\). The resulting inequality \(V\ge V-\epsilon\) implies the claimed sign.
Coverage then makes the projection onto \(p,\epsilon\) exactly the original feasible set. There is no excluded boundary or positive lower bound on coalition size.
At \(q=0\), the deviation constraint is satisfied because \(v(0)=0\). The certificate equivalence includes this point wherever it belongs to a piece.
Finding: Exact equivalence is established.
The proof of \(v(q)\le C\mathbf1^\top q\) is valid.
For each fixed nonzero \(q\), the inverse image \(T_i\) of \(Q_i\) along \(t\mapsto tq\), restricted to \([0,1]\), is closed and convex. Thus it is empty or a closed interval, including the singleton case. These sets cover \([0,1]\).
Partitioning at their finitely many distinct endpoints gives strictly positive-length consecutive segments. An interval containing an interior point of such a segment cannot have an endpoint strictly inside it; closedness therefore ensures that it contains the whole segment.
The affine formula applies at both endpoints of every chosen segment. Subtraction correctly cancels its constant term. Overlap agreement ensures that these endpoint values are the specified values of \(v\), even when adjacent segments use different formulas.
Finally, \(a_{i_jt}\le C\) and \(q_t\ge0\) justify the slope bound. Summing the increments telescopes from \(v(0)=0\) to \(v(q)\).
The separate treatment of \(q=0\) is correct. Negative coefficients, negative function values, singleton intersections, and lower-dimensional pieces do not invalidate any step.
Finding: The uniform bound is proved, including for arbitrarily small deviations.
The proposed feasible pair \(p=V\mathbf1,\epsilon=C\) satisfies nonnegativity and efficiency because \(V\ge0\) and \(\mathbf1^\top\mu=1\).
The deviation calculation is correct:
\((V+C)\mathbf1^\top q\ge C\mathbf1^\top q\ge v(q)\).
Section 2 therefore also supplies feasible multipliers for the constructed LP. Its objective is bounded below by zero.
The invoked LP facts are applicable: a nonempty polyhedron with a linear objective bounded below has an attained minimum, and rational LP data permit a rational optimal solution. Compactness of the entire extended feasible set is not required.
Finding: A finite attained rational optimum is justified.
The variable count \(\tau+1+\sum_{i\in I}s_i\) is correct. The stated constraint bound accounts for multiplier nonnegativity, the \(\tau\) dual equalities per piece, the piecewise scalar inequalities, and the allocation constraints.
All matrix coefficients are input rationals, box coefficients, constants, or the computed rational \(V\). Repetition in the extended LP may enlarge the representation, but only polynomially.
Computing \(V\) involves a rational dot product and an affine constant. Its arithmetic cost and resulting bit length are polynomial in the input length. The proof does not confuse polynomial bit complexity with polynomial dependence on numerical magnitudes.
The exact rational LP theorem used in Section 5 has the required scope: explicit binary-encoded rational LPs admit polynomial-time exact optimization. The cited Section 1.3 expressly discusses exact polynomial-time rational LP algorithms. [Gleixner and Steffy, Section 1.3](https://arxiv.org/html/1912.12820v1#S1.SS3)
The conclusion concerns exact optimization, including an optimizer, rather than approximation or feasibility alone. The proof legitimately avoids using superadditivity: it establishes the claim under weaker assumptions, which include all promised inputs.
Finding: The polynomial-time classification and exact rational output claim both follow.
No repair or additional mathematical clarification 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.