Answer: Polynomial-time solvable in \(\operatorname{poly}(\tau(Q_1+Q_2),L)\) time, including an exact minimum and an attaining rational division.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe (ϵ1, ϵ2)-core of G is non-empty if and only if ϵ1 + ϵ2 ≥ϵ∗, where ϵ∗is max{ν1(S) + ν2(N \ S) | ∅⊆S ⊆N} −T. (7) Moreover, we can compute ϵ∗in polynomial time in |N|.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), a total utility \(T\), and two coalition-value functions \(\nu_i(q)=\max_{j\in[Q_i]}(b_{ij}+\sum_t a_{ijt}q_t)\) on \(D(\mu)=\prod_t[0,\mu_t]\), compute the minimum \(\epsilon_1+\epsilon_2\) and a type-symmetric per-unit division \(x\) attaining it, subject to \(\sum_t\mu_t x_t=T\), \(\epsilon_i\ge 0\), and \(\sum_t q_t x_t\ge\nu_i(q)-\epsilon_i\) for every \(q\in D(\mu)\) and \(i\in\{1,2\}\).
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
A coalition is any mass vector \(q\in D(\mu)=\prod_{t=1}^{\tau}[0,\mu_t]\), including the empty and grand coalitions.
The input includes \(T\in\mathbb Q_{\ge0}\) and two explicitly listed functions \(\nu_i(q)=\max_{1\le j\le Q_i}(b_{ij}+\sum_{t=1}^{\tau}a_{ijt}q_t)\), with \(Q_i\ge1\) and signed rational coefficients.
Promise that each \(\nu_i\) is nonnegative on \(D(\mu)\), satisfies \(\nu_i(0)=0\) and \(\nu_i(\mu)\le T\), and is lattice-supermodular: \(\nu_i(q)+\nu_i(r)\le\nu_i(q\wedge r)+\nu_i(q\vee r)\), where meet and join are coordinatewise minimum and maximum.
A type-symmetric per-unit division is \(x\in\mathbb R^{\tau}\), with no sign restriction, satisfying \(\sum_t\mu_t x_t=T\).
Compute the minimum \(\epsilon_1+\epsilon_2\) and an attaining division, subject to \(\epsilon_i\ge0\) and \(\sum_tq_tx_t\ge\nu_i(q)-\epsilon_i\) for every \(q\in D(\mu)\) and \(i\in\{1,2\}\).
Let \(L\) be the total binary input length; state running times in \(\tau,Q_1,Q_2,L\). There is no separate \(m\) parameter.
Is computing this minimum and an attaining division in polynomial time, or is it NP-hard?
For finite supermodular two-scenario games, the minimum total nonnegative slack is computable in polynomial time, and an attaining division can also be computed in polynomial time ([Hatano and Yoshida, 2018](https://www.ijcai.org/proceedings/2018/0043.pdf)).
No published complexity result for exactly the stated mass problem was located.
Result. The minimum and an attaining division are computable in \( \operatorname{poly}(\tau(Q_1+Q_2),L) \) time. The explicit max-affine representation suffices; supermodularity is not needed for this algorithm.
1. Exact reduction of the coalition constraints
Write \( Q=Q_1+Q_2 \). Introduce total payments \( y_t=\mu_t x_t \) and coefficients \( c_{ijt}=\mu_t a_{ijt} \). Since each \( \mu_t>0 \), this change of variables is invertible, and the budget becomes \( \sum_{t=1}^{\tau}y_t=T \).
Fix a scenario \( i \) and an affine piece \( j \). For every division \( x \),
\( \displaystyle \max_{q\in D(\mu)} \left(b_{ij}+\sum_{t=1}^{\tau}(a_{ijt}-x_t)q_t\right) = b_{ij}+\sum_{t=1}^{\tau}\mu_t\max\{a_{ijt}-x_t,0\} = b_{ij}+\sum_{t=1}^{\tau}\max\{c_{ijt}-y_t,0\}. \)
Indeed, the box constraints allow each coordinate to be chosen independently: choose \( q_t=\mu_t \) when \( a_{ijt}-x_t>0 \), and \( q_t=0 \) when it is negative; either endpoint works when it is zero.
Furthermore, a number dominates a maximum of finitely many affine pieces exactly when it dominates every piece. Consequently, the original constraints for scenario \( i \) are equivalent to
\( \displaystyle \epsilon_i\ge b_{ij}+\sum_{t=1}^{\tau}\max\{c_{ijt}-y_t,0\} \qquad (1\le j\le Q_i). \)
This equivalence includes all coalitions, including the empty and grand coalitions.
2. A polynomial-size linear program
For every triple \( (i,j,t) \), introduce an auxiliary variable \( u_{ijt} \). Solve the following rational linear program:
\( \displaystyle \begin{aligned} \text{minimize}\quad &\epsilon_1+\epsilon_2\\ \text{subject to}\quad &\sum_{t=1}^{\tau}y_t=T,\\ &\epsilon_i\ge0 &&(i\in\{1,2\}),\\ &u_{ijt}\ge0 &&(i\in\{1,2\},\ 1\le j\le Q_i,\ 1\le t\le\tau),\\ &u_{ijt}\ge c_{ijt}-y_t &&(i\in\{1,2\},\ 1\le j\le Q_i,\ 1\le t\le\tau),\\ &\epsilon_i\ge b_{ij}+\sum_{t=1}^{\tau}u_{ijt} &&(i\in\{1,2\},\ 1\le j\le Q_i). \end{aligned} \)
The variables \( y_t \) have no sign restriction.
To verify exactness in both directions:
The objectives agree under both transformations. Therefore the two problems have exactly the same attainable objective values.
3. Feasibility, attainment, and exact output
The LP is feasible. Explicitly, take
\( \displaystyle y_t^0=\mu_t T,\qquad u_{ijt}^0=\max\{c_{ijt}-y_t^0,0\},\qquad \epsilon_i^0= \max\left\{0,\max_{1\le j\le Q_i} \left(b_{ij}+\sum_{t=1}^{\tau}u_{ijt}^0\right)\right\}. \)
The budget holds because \( \sum_t\mu_t=1 \), and the remaining constraints hold by construction. All these quantities are finite rationals.
The objective is bounded below by zero because both slacks are nonnegative. The standard rational linear-programming theorem therefore applies: a nonempty rational LP with an objective bounded below has an attained rational optimum, and an optimal solution can be computed in polynomial time in its explicit binary encoding length.
If \( (y^\ast,\epsilon^\ast,u^\ast) \) is an optimal solution, output
\( \displaystyle \epsilon_1^\ast+\epsilon_2^\ast \quad\text{and}\quad x_t^\ast=\frac{y_t^\ast}{\mu_t}\quad(1\le t\le\tau). \)
The equivalence already proved establishes that this division attains the original minimum.
4. Running time
The LP has \( \tau+2+\tau Q \) variables, \( 2\tau Q+Q+2 \) inequalities, and one equality.
Constructing it requires \( O(\tau Q) \) rational multiplications and \( O(\tau Q) \) coefficient entries. Each product \( c_{ijt}=\mu_t a_{ijt} \) has \( O(L) \) bits, so the entire explicit LP encoding has length
\( \displaystyle O\!\left(\tau Q\bigl(L+\log(\tau Q+2)\bigr)\right). \)
Polynomial-time rational LP optimization and the subsequent divisions by the positive input masses therefore take \( \operatorname{poly}(\tau(Q_1+Q_2),L) \) bit operations and produce outputs of polynomial binary length. No additional population-size parameter is involved.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument correctly establishes a polynomial-time algorithm for the exact minimum and an attaining rational division. No major or minor mathematical issues were found.
The substitution \(y_t=\mu_t x_t\) is invertible because every input mass is strictly positive. It correctly transforms the budget into \(\sum_t y_t=T\) and preserves the absence of sign restrictions on the division.
For a fixed affine piece, the displayed maximization formula is correct. Each coordinate contributes independently over \([0,\mu_t]\), with maximum contribution \(\mu_t\max\{a_{ijt}-x_t,0\}\). The second equality follows from \(\mu_t>0\) and \(c_{ijt}=\mu_t a_{ijt}\).
The passage from the max-affine function to constraints for every piece is exact: for each coalition, domination of the finite maximum is equivalent to domination of every affine piece. Maximizing each piece’s excess over the box therefore gives precisely the stated inequalities.
There is no omission of boundary coalitions. The coordinate maximization includes both endpoints, and hence includes the empty and grand coalitions. Signed coefficients and negative intercepts do not invalidate the calculation.
The auxiliary constraints correctly impose
\(u_{ijt}\ge\max\{c_{ijt}-y_t,0\}\).
Both directions of the feasibility correspondence are valid:
The use of lower bounds on the auxiliary variables causes no relaxation error: their larger possible values only strengthen the corresponding slack requirement.
The objective is unchanged in both directions. Consequently, the claim that the two formulations have exactly the same attainable objective values is justified.
The proposed feasible point is valid. Its budget follows from \(\sum_t\mu_t=1\), its auxiliary variables satisfy their defining inequalities, and the chosen slacks dominate every affine-piece bound while remaining nonnegative. All quantities are finite rationals.
The objective is bounded below by zero. The invoked rational linear-programming theorem is stated sufficiently precisely for this application: a feasible rational LP with a bounded-below linear objective attains a rational optimum and admits polynomial-time exact optimization in its encoding length. Its hypotheses are satisfied here; boundedness of the feasible region is not required.
Dividing the optimal payments by the strictly positive masses gives a well-defined rational division. The established feasibility correspondence and objective equality justify attainment of the original minimum.
The stated counts are correct: \(\tau+2+\tau Q\) variables, \(2\tau Q+Q+2\) inequalities, and one equality.
The construction uses \(O(\tau Q)\) rational products. Each product has \(O(L)\) binary length. The coefficient-entry count and encoding bound are valid using a sparse explicit LP representation; indices contribute the stated logarithmic overhead.
Polynomial-time rational LP optimization consequently gives the claimed \(\operatorname{poly}(\tau(Q_1+Q_2),L)\) bit complexity. Exact division by the input masses preserves polynomial output length and takes polynomial time.
The argument resolves both requested outputs: the minimum total nonnegative slack and an attaining division. It applies to every promised input and does not require supermodularity or the other value-function promises. Establishing the algorithm under weaker assumptions is consistent with the task.
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.