Answer: Exactly solvable in time polynomial in \(m,\tau,g,K,L\) by rational linear programming.
Theorem 2.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe $\cProblemU$ problem is NP-hard when groups have a non-laminar structure. In fact, it cannot be approximated to any positive multiplicative factor.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite platform set \(P\), a finite support \(T\) of item types with rational masses \(\mu_t>0\) summing to \(1\), and for each type \(t\) an allowed-platform set \(A_t\), utilities \(u_{tp}\), and group-membership set \(J_t\), along with a rational utility threshold \(\ell\) and rational convex piecewise-linear cost functions \(\Phi_p,\Psi_{pj}:[0,1]\to\mathbb{Q}\), choose masses \(y_{tp}\geq 0\) to minimize \(\sum_{p\in P}(\Phi_p(\sum_t y_{tp})+\sum_j\Psi_{pj}(\sum_{t:j\in J_t}y_{tp}))\), subject to \(\sum_{p\in A_t}y_{tp}\leq\mu_t\) for each \(t\) and \(\sum_{t,p}u_{tp}y_{tp}\geq\ell\); report infeasibility if no such assignment exists.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) platforms \(P\) and \(g\geq1\) groups. Each type has an allowed set \(A_t\subseteq P\), utilities \(u_{tp}\in\mathbb{Q}_{\geq0}\) for \(p\in A_t\), and a nonempty membership set \(J_t\subseteq\{1,\ldots,g\}\). Groups may overlap arbitrarily; every group contains at least one supported type.
The input includes \(\ell\in\mathbb{Q}_{\geq0}\) and finite continuous convex piecewise-linear functions \(\Phi_p,\Psi_{pj}:[0,1]\to\mathbb{R}\), encoded explicitly by binary-rational breakpoints and values, including both endpoints. Values and slopes may have either sign, and values at zero need not vanish.
Choose divisible masses \(y_{tp}\in\mathbb{R}_{\geq0}\), with \(y_{tp}=0\) whenever \(p\notin A_t\), subject to \(\sum_{p\in A_t}y_{tp}\leq\mu_t\) for every \(t\) and \(\sum_{t\in T}\sum_{p\in A_t}u_{tp}y_{tp}\geq\ell\). Unassigned mass is permitted.
Define \(\sigma_p=\sum_{t\in T}y_{tp}\) and \(\nu_{pj}=\sum_{t:j\in J_t}y_{tp}\). Compute an exact minimum of \(\sum_{p\in P}(\Phi_p(\sigma_p)+\sum_{j=1}^{g}\Psi_{pj}(\nu_{pj}))\), or report infeasibility. Let \(K\) be the total number of linear pieces and \(L\) the total binary input length.
Is this continuous optimization problem solvable in time polynomial in \(m,\tau,g,K,L\), or is it NP-hard?
For indivisible items with arbitrarily overlapping groups, exact optimization is NP-hard and no finite multiplicative approximation is possible; with disjoint or laminar groups and uniform utilities, exact optimization is polynomial-time. [Verified discrete results](https://ojs.aaai.org/index.php/AAAI/article/view/38768/42730).
The problem is solvable exactly in time polynomial in \(m,\tau,g,K,L\), including arbitrary group overlaps and arbitrary rational utilities satisfying the stated hypotheses.
The proof gives a polynomial-size rational linear program whose optimal allocations and objective value coincide with those of the original problem.
Let \(E=\{(t,p):t\in T,\ p\in A_t\}\), and introduce allocation variables only for pairs in \(E\). All other allocations are zero.
For every allocation satisfying the mass constraints,
\(\displaystyle \sum_{(t,p)\in E}y_{tp} \leq \sum_{t\in T}\mu_t=1.\)
Consequently, for every platform and group,
\(\displaystyle 0\leq \nu_{pj}\leq \sigma_p\leq 1.\)
The first inequality between aggregates holds because the sum defining \(\nu_{pj}\) uses a subset of the nonnegative terms defining \(\sigma_p\). It holds irrespective of group overlaps. Thus every cost is evaluated within its domain.
Consider any one of the input cost functions \(f\). Write its breakpoints and values as
\(\displaystyle 0=b_0<b_1<\cdots<b_k=1,\qquad v_i=f(b_i).\)
For each piece \(r\in\{1,\ldots,k\}\), define
\(\displaystyle a_r=\frac{v_r-v_{r-1}}{b_r-b_{r-1}},\qquad c_r=v_{r-1}-a_rb_{r-1}.\)
The function equals \(a_rx+c_r\) on \([b_{r-1},b_r]\).
Claim. For every \(x\in[0,1]\),
\(\displaystyle f(x)=\max_{1\leq r\leq k}(a_rx+c_r).\)
Proof. Convexity at any interior breakpoint gives
\(\displaystyle v_r\leq \frac{b_{r+1}-b_r}{b_{r+1}-b_{r-1}}v_{r-1} + \frac{b_r-b_{r-1}}{b_{r+1}-b_{r-1}}v_{r+1}. \)
Rearranging yields \(a_r\leq a_{r+1}\). Hence the piece slopes are nondecreasing.
Fix a piece \(r\). If \(x\geq b_r\), partition \([b_r,x]\) at its breakpoints. Every traversed piece has slope at least \(a_r\), so
\(\displaystyle f(x)-v_r\geq a_r(x-b_r).\)
Since \(v_r=a_rb_r+c_r\), this implies \(f(x)\geq a_rx+c_r\).
If \(x\leq b_{r-1}\), every piece traversed from \(x\) to \(b_{r-1}\) has slope at most \(a_r\). Therefore
\(\displaystyle v_{r-1}-f(x)\leq a_r(b_{r-1}-x),\)
again giving \(f(x)\geq a_rx+c_r\). Within the piece interval there is equality.
Thus every affine piece extension lies below \(f\) everywhere, and at every point at least one extension equals \(f\). This proves the claim. \(\square\)
No positivity assumption on slopes or values was used. The intercepts \(c_r\) retain all constants, including nonzero values at zero.
Apply this construction to write
\(\displaystyle \Phi_p(x)=\max_r(a^\Phi_{pr}x+c^\Phi_{pr}),\qquad \Psi_{pj}(x)=\max_r(a^\Psi_{pjr}x+c^\Psi_{pjr}). \)
Each maximum ranges over the pieces of its particular function.
Introduce the allocation variables \(y_{tp}\), aggregate variables \(\sigma_p,\nu_{pj}\), and cost variables \(z_p,w_{pj}\). The cost variables are real variables with no nonnegativity restriction.
Minimize
\(\displaystyle \sum_{p\in P}z_p+\sum_{p\in P}\sum_{j=1}^g w_{pj}\)
subject to the following linear constraints:
\(\displaystyle y_{tp}\geq0\quad ((t,p)\in E),\)
\(\displaystyle \sum_{p\in A_t}y_{tp}\leq\mu_t\quad(t\in T),\)
\(\displaystyle \sum_{(t,p)\in E}u_{tp}y_{tp}\geq\ell.\)
\(\displaystyle \sigma_p=\sum_{t:(t,p)\in E}y_{tp}\quad(p\in P),\)
\(\displaystyle \nu_{pj}=\sum_{\substack{t:(t,p)\in E\\j\in J_t}}y_{tp} \quad(p\in P,\ 1\leq j\leq g),\)
\(\displaystyle 0\leq\sigma_p\leq1,\qquad 0\leq\nu_{pj}\leq1.\)
\(\displaystyle z_p\geq a^\Phi_{pr}\sigma_p+c^\Phi_{pr},\)
\(\displaystyle w_{pj}\geq a^\Psi_{pjr}\nu_{pj}+c^\Psi_{pjr}.\)
Let \(F(y)\) denote the original objective.
Every original feasible allocation can be extended to an LP-feasible point by using its prescribed aggregates and setting
\(\displaystyle z_p=\Phi_p(\sigma_p),\qquad w_{pj}=\Psi_{pj}(\nu_{pj}).\)
The affine representation proves all cost inequalities, and the LP objective then equals \(F(y)\).
Conversely, every LP-feasible point projects to an original feasible allocation. Its cost inequalities imply
\(\displaystyle z_p\geq\Phi_p(\sigma_p),\qquad w_{pj}\geq\Psi_{pj}(\nu_{pj}).\)
Therefore its LP objective is at least \(F(y)\).
These two directions establish equivalence of feasibility and equality of optimal values. Moreover, an optimal LP point projects to an optimal original allocation: otherwise lifting a strictly better original allocation would contradict LP optimality.
For completeness, whenever feasible, the original problem attains its minimum. Its feasible set is closed and bounded, since \(0\leq y_{tp}\leq\mu_t\), and its objective is continuous. Thus the equivalent LP also has an attained finite optimum.
Let \(n=|E|\leq m\tau\). The LP has
\(\displaystyle n+2m(g+1)\)
variables and
\(\displaystyle O(n+\tau+m(g+1)+K)\)
constraints, counting equalities as pairs of inequalities if necessary.
Arbitrary overlaps only determine which allocation variables appear in each aggregate equation. These incidences can be constructed directly from the supported types and their membership sets; no enumeration of unsupported types or possible membership patterns is needed.
All coefficients are rational. Each new slope and intercept requires a constant number of rational arithmetic operations on input numbers. Their binary lengths are therefore \(O(L)\), even when a breakpoint interval is very short. The complete LP encoding has length polynomial in \(m,\tau,g,K,L\).
We now apply the standard exact rational linear-programming theorem: an explicitly encoded rational LP can be solved in polynomial time in its binary encoding length, detecting infeasibility or unboundedness, or returning an exact rational optimal solution when a finite optimum exists. This is an exact bit-complexity result, rather than merely an approximation guarantee; see [*Linear Programming using Limited-Precision Oracles*, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
Here the LP is explicitly encoded, rational, and of polynomial encoding length. Whenever feasible, it has an attained finite optimum, as proved above. Hence the theorem returns an exact optimal allocation and value in the required polynomial time.
Define
\(\displaystyle v_t=\max\bigl(\{0\}\cup\{u_{tp}:p\in A_t\}\bigr),\qquad U_{\max}=\sum_{t\in T}\mu_tv_t.\)
For every feasible allocation,
\(\displaystyle \sum_{(t,p)\in E}u_{tp}y_{tp} \leq\sum_{t\in T}v_t\sum_{p\in A_t}y_{tp} \leq U_{\max}. \)
This bound is attained by assigning each type with \(v_t>0\) entirely to an allowed platform attaining \(v_t\), and leaving types with \(v_t=0\) unassigned. This also handles empty allowed sets.
Thus the problem is feasible exactly when \(\ell\leq U_{\max}\), a condition checkable by polynomial-time rational arithmetic.
The [cited discrete results](https://ojs.aaai.org/index.php/AAAI/article/view/38768/42730) concern indivisible allocations. Here allocations are real variables, and the formulation above has no integrality constraints. Arbitrary overlap therefore poses no obstacle to solving this continuous problem by linear programming.
The classification proved here is exact polynomial-time solvability in the binary input model; no claim of strongly polynomial running time is needed.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The continuous problem is exactly solvable in polynomial time in \(m,\tau,g,K,L\). The write-up establishes an exact rational LP formulation, proves its equivalence to the original optimization problem, and verifies the hypotheses needed for polynomial-time exact LP solution.
No major or minor mathematical issues were found.
The mass constraints imply
\[
\sum_{(t,p)\in E}y_{tp}\leq\sum_{t\in T}\mu_t=1.
\]
Since all allocation variables are nonnegative and each group aggregate sums a subset of the corresponding platform aggregate, the stated bounds
\[
0\leq\nu_{pj}\leq\sigma_p\leq1
\]
are correct.
Overlapping groups do not invalidate this argument: each individual group aggregate is a subset sum, even though different group aggregates can count the same mass. All cost arguments therefore lie in their specified domains.
The slope and intercept formulas are correct. Strictly increasing breakpoints ensure that every denominator is positive.
The convexity inequality at an interior breakpoint rearranges to \(a_r\leq a_{r+1}\). The subsequent comparisons of slopes correctly show that every affine piece extension lies below the function on both sides of its own interval. Equality holds on that interval, establishing
\[
f(x)=\max_{1\leq r\leq k}(a_rx+c_r)
\]
throughout the domain.
The argument also covers a single linear piece, endpoints, repeated slopes, negative slopes, negative values, and nonzero values at zero. No unstated monotonicity or normalization assumption is used.
The allocation constraints reproduce the original feasibility conditions exactly. Introducing variables only for allowed pairs correctly enforces zero allocation elsewhere. The aggregate equations also match the task, including arbitrary group memberships.
The cost inequalities are precisely the epigraph constraints furnished by the affine representation. Allowing unrestricted real cost variables is necessary because costs may be negative; the prover explicitly handles this.
Both equivalence directions are valid:
These statements establish feasibility equivalence and equality of optimal values. The contradiction argument showing that an optimal LP allocation is optimal for the original problem is also correct.
The original feasible set is closed and bounded in finitely many allocation variables. Its objective is continuous. Consequently, whenever feasible, it has an attained finite minimum.
This reasoning also covers \(E=\varnothing\): the allocation space then has dimension zero, and feasibility is governed by the utility constraint. Lifting an original minimizer establishes attainment for the LP, despite its cost variables being unbounded above.
The variable count \(n+2m(g+1)\), with \(n=|E|\leq m\tau\), is correct. The stated constraint bound accounts for nonnegativity, mass constraints, the utility constraint, aggregate definitions, domain bounds, and all \(K\) cost inequalities.
Group overlap can increase the number of aggregate incidences, but there are at most \(ng\) group incidences. Thus it does not create an exponentially large representation or require enumeration of unsupported types.
Each slope and intercept uses a constant number of rational arithmetic operations on input rationals. Their encoding lengths remain \(O(L)\), including when breakpoint differences are small. Together with the polynomial numbers of rows, columns, and incidences, this establishes polynomial total LP encoding length.
The prover states the theorem with the relevant guarantees: polynomial time in binary encoding length, infeasibility detection, and exact rational optimal output when a finite optimum exists.
The cited Section 1.3 explicitly discusses exact polynomial-time algorithms for rational LPs and distinguishes exact optimization from approximate optimization. The citation supports the theorem being invoked. [*Linear Programming using Limited-Precision Oracles*, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf)
All applicable hypotheses are verified in the write-up: the LP is explicitly encoded, rational, polynomial in size, and has an attained finite optimum whenever feasible. Computing the exact objective value from the returned rational solution also requires only polynomial-time rational arithmetic.
The definition of \(v_t\) handles empty allowed sets. The utility upper bound is valid because \(0\leq u_{tp}\leq v_t\) for every allowed pair.
The described allocation attains \(U_{\max}\): every type with positive maximum utility has an allowed maximizing platform, and no platform capacity prevents assigning its entire mass there. Types with zero maximum utility can remain unassigned.
Therefore feasibility is exactly equivalent to \(\ell\leq U_{\max}\). The criterion includes zero utilities, empty allowed sets, \(\ell=0\), and equality at the maximum.
The cited paper concerns item matchings, and its discrete hardness does not imply hardness for this continuous formulation. The prover correctly identifies the absence of integrality constraints as the relevant distinction. [*Group Fair Matchings Using Convex Cost Functions*](https://ojs.aaai.org/index.php/AAAI/article/view/38768/42730)
The conclusion establishes polynomial bit complexity without claiming a strongly polynomial algorithm.
No additional lemma, clarification, or correction is needed to make the argument verifiable.
⟨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.