Answer: \(\mathrm{NP}\)-complete, even for \(k=3\) and utilities in \(\{0,1,2\}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe AssignTEF1 problem is NP-complete, even with only 3 types.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational profile masses \(\mu_{p,\theta}\) for protected group \(p\) and complete utility profile \(\theta\), rational per-capita supplies \(\sigma_j\) of flat classes \(j\), utilities \(u_{\theta j}\), and threshold \(U\), decide whether there are bundle masses \(b_{pj}\) and flows \(x_{p,\theta,j}\ge0\) satisfying \(\sum_j x_{p,\theta,j}\le\mu_{p,\theta}\), \(\sum_\theta x_{p,\theta,j}\le b_{pj}\), \(\sum_p b_{pj}\le\sigma_j\), with each flow maximizing \(v_p(b_p)=\max_x\sum_{\theta,j}u_{\theta j}x_{p,\theta,j}\), such that \(\sum_p v_p(b_p)\ge U\) and \(v_p(b_p)\ge v_p(b_q)\) for every \(p,q\).
There are \(k\ge1\) protected groups and \(m\ge1\) flat classes. A society is given by its support: the list of \(\tau\) types \((p,\theta)\) with positive mass \(\mu_{p,\theta}\), each mass a binary rational. Here \(\tau\) is the support size, not the number of possible profiles; \(\theta=(u_{\theta1},\ldots,u_{\theta m})\) is a complete vector of nonnegative rational utilities.
Normalize \(\sum_{p,\theta}\mu_{p,\theta}=1\), require every group to have positive mass, and give positive rational per-capita supplies \(\sigma_j\) and a nonnegative rational threshold \(U\). At least one supported profile has positive utility for some flat class. Let \(L\) be the total binary input length.
For any bundle \(b\in\mathbb R_{\ge0}^m\), define \(v_p(b)=\max\{\sum_{\theta,j}u_{\theta j}x_{\theta j}:x_{\theta j}\ge0,\ \sum_jx_{\theta j}\le\mu_{p,\theta},\ \sum_\theta x_{\theta j}\le b_j\}\), summing over profiles supported in group \(p\).
An allocation consists of nonnegative real bundle masses \(b_{pj}\) with \(\sum_pb_{pj}\le\sigma_j\), together with a maximizing flow for each \(v_p(b_p)\). Supplies may be withheld and bundle mass may remain unmatched. Values are total utilities, without division by group mass; ties between maximizing flows are unrestricted.
The decision problem asks whether such an allocation satisfies \(\sum_pv_p(b_p)\ge U\) and exact group envy-freeness \(v_p(b_p)\ge v_p(b_q)\) for every \(p,q\); evaluating another group's bundle uses the evaluating group's own profile masses.
Is this continuous welfare-threshold decision problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,k,L\).
The discrete welfare-threshold problem with maximum-weight matching group valuations and group envy-freeness up to one item is NP-complete even for three groups. [Benabbou et al.](https://www.ijcai.org/proceedings/2019/0014.pdf)
For divisible items, approximation guarantees for class envy-freeness are known in online matching with binary utilities; these concern a different problem. [Hosseini et al.](https://arxiv.org/abs/2203.03751) No result settling the exact continuous decision problem above was located.
The decision problem is \(\mathrm{NP}\)-complete, even with \(k=3\) and every utility in \(\{0,1,2\}\). Consequently, a running time polynomial in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction below applies directly to the stated continuous model, including withholding, unmatched bundle mass, and unrestricted maximizing-flow ties.
An instance of PARTITION consists of positive integers \(a_1,\ldots,a_n\), encoded in binary. Writing \(S=\sum_{i=1}^n a_i\), the question is whether some subset \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=S/2\). This problem is \(\mathrm{NP}\)-complete. [MIT lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf)
Choose the smallest power of two \(D\) strictly greater than \(7S\). Thus \(7S<D\le14S\).
We construct three groups, denoted \(A,B,C\), and \(n+1\) flat classes. Classes \(1,\ldots,n\) encode the integers; class \(0\) is private to group \(C\).
The supported types are as follows. All utilities not explicitly specified are zero.
| Group | Profile mass | Positive utilities |
|---|---:|---|
| \(A\) | \(2S/D\) | Utility \(2\) for every class \(i\in\{1,\ldots,n\}\) |
| \(B\) | \(2S/D\) | Utility \(2\) for every class \(i\in\{1,\ldots,n\}\) |
| \(C\), one profile for each \(i\) | \(2a_i/D\) | Utility \(1\) for class \(i\) |
| \(C\), private profile | \(S/D\) | Utility \(1\) for class \(0\) |
| \(C\), dummy profile | \((D-7S)/D\) | None |
The total mass is
\(\displaystyle \frac{2S+2S+2S+S+(D-7S)}{D}=1.\)
Every supported mass is positive, and every group has positive mass. Moreover, all masses are dyadic rationals, so the construction satisfies even the restrictive interpretation of “binary rational.”
Set the supplies and threshold to
\(\displaystyle \sigma_i=\frac{4a_i}{D}\quad(1\le i\le n),\qquad \sigma_0=\frac{S}{D},\qquad U=\frac{9S}{D}.\)
For any bundle \(b\), the resulting valuations are
\(\displaystyle v_A(b)=v_B(b)=2\min\left\{\sum_{i=1}^n b_i,\frac{2S}{D}\right\},\)
and
\(\displaystyle v_C(b)=\min\left\{b_0,\frac{S}{D}\right\}+\sum_{i=1}^n\min\left\{b_i,\frac{2a_i}{D}\right\}.\)
The first formula follows because each of \(A,B\) has one profile, with utility \(2\) for every variable class and total matching capacity \(2S/D\). The second follows because each positive-utility profile of \(C\) values a different single class, so their matching problems are independent.
Consider any allocation, together with its maximizing flows. Define:
Zero-utility matches contribute nothing. Therefore welfare is exactly
\(\displaystyle W=2h+d+z.\)
Supply feasibility gives
\(\displaystyle h+d\le\frac{4S}{D},\qquad z\le\frac{S}{D}.\)
Consequently,
\(\displaystyle W\le2\left(\frac{4S}{D}-d\right)+d+\frac{S}{D}=\frac{9S}{D}-d\le U.\)
If \(W\ge U\), every inequality above must be tight. Hence
\(\displaystyle d=0,\qquad h=\frac{4S}{D},\qquad z=\frac{S}{D}.\)
Each positive-utility profile in \(A,B\) has capacity \(2S/D\). Thus each group matches exactly \(2S/D\) variable-class mass.
These equalities also determine the relevant bundle masses. Indeed, the variable-class supply totals \(4S/D\), and all of it is matched in \(A,B\). For each variable class, matched mass is bounded by the corresponding bundle mass, whose sum is bounded by supply. Since the sums of these inequalities are equalities, every classwise inequality is an equality. Thus
\(\displaystyle b_{Ci}=0,\qquad b_{Ai}+b_{Bi}=\frac{4a_i}{D}\quad(1\le i\le n),\)
and
\(\displaystyle \sum_{i=1}^n b_{Ai}=\sum_{i=1}^n b_{Bi}=\frac{2S}{D}.\)
Similarly, \(z=S/D\) exhausts the private supply, giving
\(\displaystyle b_{C0}=\frac{S}{D},\qquad b_{A0}=b_{B0}=0.\)
In particular, \(v_C(b_C)=S/D\). Withholding or unmatched bundle mass cannot evade these conclusions.
For any positive \(c\) and any \(x\in[0,2c]\),
\(\displaystyle \min\{x,c\}\ge\frac{x}{2},\)
with equality exactly when \(x=0\) or \(x=2c\). To verify this, if \(x\le c\), equality requires \(x=x/2\), hence \(x=0\); if \(x\ge c\), equality requires \(c=x/2\), hence \(x=2c\).
Apply this inequality with \(x=b_{Ai}\) and \(c=2a_i/D\). The supply bound ensures \(0\le b_{Ai}\le4a_i/D=2c\). Therefore
\(\displaystyle v_C(b_A)=\sum_{i=1}^n\min\left\{b_{Ai},\frac{2a_i}{D}\right\}\ge\frac12\sum_{i=1}^n b_{Ai}=\frac{S}{D}.\)
Envy-freeness of \(C\) toward \(A\) requires the reverse inequality, because \(v_C(b_C)=S/D\). Equality must therefore hold in every summand: each summand’s difference from \(b_{Ai}/2\) is nonnegative, and their sum is zero.
It follows that
\(\displaystyle b_{Ai}\in\left\{0,\frac{4a_i}{D}\right\}\quad\text{for every }i.\)
Let \(I=\{i:b_{Ai}=4a_i/D\}\). The bundle total now gives
\(\displaystyle \frac4D\sum_{i\in I}a_i=\frac{2S}{D},\)
so \(\sum_{i\in I}a_i=S/2\). Thus any envy-free allocation meeting the threshold yields a PARTITION solution.
Conversely, suppose \(\sum_{i\in I}a_i=S/2\). Give the entire supply of class \(i\) to \(A\) when \(i\in I\), and to \(B\) otherwise. Give the entire private supply to \(C\).
Each of \(A,B\) receives variable-class mass \(2S/D\), attaining its maximum possible value \(4S/D\). Hence neither envies any group.
Group \(C\) receives value \(S/D\), and evaluates the other bundles as
\(\displaystyle v_C(b_A)=\frac2D\sum_{i\in I}a_i=\frac{S}{D},\qquad v_C(b_B)=\frac2D\sum_{i\notin I}a_i=\frac{S}{D}.\)
Thus all envy constraints hold. Matching all allocated variable mass to the respective receiver profile, and the private mass to \(C\)'s private profile, gives maximizing flows. Welfare is
\(\displaystyle \frac{4S}{D}+\frac{4S}{D}+\frac{S}{D}=U.\)
This proves both directions of the reduction.
The construction has \(k=3\), \(m=n+1\), and \(\tau=n+4\). Since \(\log D=O(\log S)\), its explicitly listed utility vectors and rational quantities have total length \(O(n^2+n\log S)\), and can be constructed in polynomial time.
Therefore the problem is \(\mathrm{NP}\)-hard already for three groups. This reduction establishes ordinary hardness; it does not establish strong hardness for three groups.
We next prove membership in \(\mathrm{NP}\), including for allocations initially allowed to use arbitrary real numbers.
Let \(T_p\) denote the supported profiles in group \(p\), and put \(t_p=|T_p|\). Thus \(\sum_p t_p=\tau\).
The dual of the flow program defining \(v_p(b)\) is
\(\displaystyle v_p(b)=\min_{(\alpha,\beta)\in\mathcal D_p}\left(\sum_{\theta\in T_p}\mu_{p,\theta}\alpha_\theta+\sum_{j=1}^m b_j\beta_j\right),\)
where
\(\displaystyle \mathcal D_p=\left\{(\alpha,\beta)\ge0:\alpha_\theta+\beta_j\ge u_{\theta j}\ \text{for every }\theta\in T_p,\ j\right\}.\)
The primal is feasible at zero and bounded because every profile has finite mass. The dual is feasible, for example by setting every \(\alpha_\theta\) to the largest utility and every \(\beta_j\) to zero. Linear-programming strong duality therefore applies.
The dual polyhedron lies in a nonnegative orthant and contains no line. The fundamental theorem of linear programming consequently gives an optimal dual vertex for every nonnegative bundle \(b\).
Its dimension is \(d_p=t_p+m\), and it is described by
\(\displaystyle N_p=mt_p+t_p+m\)
inequalities. Every vertex is determined by \(d_p\) linearly independent tight constraints. Their coefficients and right-hand sides have polynomial encoding length. Cramer’s rule, after clearing denominators, therefore shows that every dual vertex has polynomial encoding length in \(m,\tau,L\).
Now choose a dual vertex \((\alpha^{pq},\beta^{pq})\) for each ordered pair \(p\ne q\). With these vertices fixed, introduce bundle variables \(b_{pj}\) and feasible own-flow variables \(x_{p,\theta j}\). Write
\(\displaystyle w_p=\sum_{\theta\in T_p,j}u_{\theta j}x_{p,\theta j}.\)
Impose supply feasibility, own-flow feasibility, and the following linear inequalities:
\(\displaystyle \sum_p w_p\ge U,\)
\(\displaystyle w_p\ge\sum_{\theta\in T_p}\mu_{p,\theta}\alpha^{pq}_\theta+\sum_j b_{qj}\beta^{pq}_j\quad(p\ne q).\)
This formulation is equivalent to the original decision problem after allowing the vertex choices:
\(\displaystyle v_p(b_p)\ge w_p\ge v_p(b_q)\),
and \(\sum_p v_p(b_p)\ge\sum_p w_p\ge U\). Maximizing own flows exist and can replace the certificate flows.
For fixed vertex choices, this is a rational linear system of polynomial size. Its bundle and flow variables are bounded by supplies and profile masses. If feasible, it therefore has a rational vertex of polynomial encoding length, again by Cramer’s rule.
Thus every yes-instance has a polynomial-size certificate consisting of the selected dual vertices and rational bundle/flow variables. All certificate conditions are checked by exact rational arithmetic in polynomial time. The problem belongs to \(\mathrm{NP}\).
Together with the reduction, this proves \(\mathrm{NP}\)-completeness.
For a prescribed rational bundle, valuation is a linear program with \(t_pm\) variables and \(t_p+m\) capacity constraints, and is computable in \(\operatorname{poly}(m,\tau,L)\) time. A prescribed rational allocation can be checked using \(k^2\) such evaluations, in \(\operatorname{poly}(m,\tau,k,L+B)\) time, where \(B\) is its encoding length.
An explicit exact decision algorithm enumerates dual vertices and solves the linear systems above. Each \(\mathcal D_p\) has at most
\(\displaystyle \binom{N_p}{d_p}\le N_p^{d_p}\)
vertices, enumerable by testing sets of tight constraints. Since \(N_p\le(m+1)(\tau+1)\), for \(k\ge2\) the resulting running time is bounded by
\(\displaystyle \bigl((m+1)(\tau+1)\bigr)^{(k-1)(\tau+km)}\operatorname{poly}(m,\tau,k,L).\)
For \(k=1\), envy constraints are automatic, and one flow linear program decides the problem in \(\operatorname{poly}(m,\tau,L)\) time.
The three-group hardness rules out a general polynomial running time unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof establishes the claimed \(\mathrm{NP}\)-completeness, even for \(k=3\) and utilities in \(\{0,1,2\}\). The reduction and polynomial-certificate argument are sound. I found one minor omission in the running-time statement for evaluating an externally supplied rational bundle. No issue blocks the complexity classification.
The source problem is correctly specified as binary-encoded PARTITION with positive integers. Its \(\mathrm{NP}\)-completeness is supported by the cited [MIT lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/f2829e57caade7e7f21d765b8e7b9058_MIT6_046JS15_lec16.pdf).
The construction satisfies the target’s hypotheses:
The use of ordinary rather than strong hardness is stated appropriately.
Both valuation formulas follow from the specified flow programs.
For \(A\) and \(B\), all variable classes have utility \(2\) for their sole profile, and their matching capacity is \(2S/D\). Class \(0\) contributes zero. Thus their value depends only on total variable-class bundle mass, capped by that capacity.
For \(C\), each positive-utility profile values exactly one distinct class. The corresponding positive-utility matches therefore have independent caps. Zero-utility matches, including those involving the dummy profile, cannot increase the objective or invalidate the displayed maximum.
These formulas use the evaluating group’s own masses, as required by USER_TASK.
The definitions of \(h,d,z\) correctly give \(W=2h+d+z\), regardless of zero-utility matches or ties.
The supply bounds imply
\(W\le9S/D-d\le U\).
Therefore \(W\ge U\) forces \(d=0\). Equality in the preceding bound then forces both \(h+d=4S/D\) and \(z=S/D\). Consequently, \(h=4S/D\).
The capacity conclusion is also correct: the two groups \(A,B\) each have capacity \(2S/D\), so their combined matched mass can reach \(4S/D\) only if both capacities are exhausted.
The subsequent bundle conclusions are justified. Positive-utility matches in \(A,B\) already consume the entire aggregate variable supply. Because every classwise supply and matching slack is nonnegative, equality in their sum forces equality class by class. This rules out variable-class mass assigned to \(C\), withholding, and unmatched variable bundle mass. The private-class conclusion follows by the same exhaustion argument.
Thus the proof legitimately obtains all the displayed bundle equalities and \(v_C(b_C)=S/D\). Unrestricted maximizing-flow ties do not create an exception.
The scalar inequality is correct throughout its stated domain:
\(\min\{x,c\}\ge x/2\) for \(c>0\) and \(0\le x\le2c\).
Its equality cases are exactly \(x=0\) and \(x=2c\), including the boundary cases.
For each application, \(c=2a_i/D>0\), and supply feasibility gives the required upper bound on \(b_{Ai}\).
The lower bound \(v_C(b_A)\ge S/D\), combined with \(C\)’s envy constraint, forces equality. Since each summand’s slack is nonnegative, the conclusion that every summand attains equality is valid. Hence every variable class is assigned wholly to either \(A\) or \(B\).
The resulting equation
\((4/D)\sum_{i\in I}a_i=2S/D\)
correctly yields a partition. The argument does not assume that \(S\) is even; when it is odd, the resulting integer equality is impossible, as required.
The allocation constructed from a partition respects every supply.
Both \(A\) and \(B\) attain their global maximum value \(4S/D\), so neither can envy any bundle. Group \(C\)’s evaluations of both other bundles equal its own value \(S/D\). This checks all ordered envy comparisons.
The stated own flows are feasible and attain the displayed valuations, so they are maximizing flows. Their welfare is exactly \(U\).
Both directions of the reduction are therefore established.
The dual has the correct variables, signs, constraints, and objective.
For every finite nonnegative bundle, the primal is feasible and bounded. The proposed dual feasible point is valid. Strong duality therefore applies with attained finite optimal values.
The dual polyhedron is nonempty and pointed because it lies in the nonnegative orthant. The invoked optimal-vertex property applies even when some bundle coordinates are zero or the optimal face is unbounded. Thus choosing optimal dual vertices for cross-bundle evaluations is justified.
The dimension \(d_p=t_p+m\) and inequality count \(N_p=mt_p+t_p+m\) are correct.
A vertex is determined by \(d_p\) independent active constraints. Their rational data have polynomial encoding length, and the stated Cramer’s-rule argument gives polynomial encoding length for the vertex coordinates. No bound on the magnitude or encoding length of an original real allocation is needed for this step.
Both directions are correct.
From an original solution, maximizing own flows and optimal cross-evaluation dual vertices satisfy the proposed system.
Conversely, a feasible own flow supplies a lower bound on own value, while a feasible dual point supplies an upper bound on the evaluated other bundle. The inequality directions therefore give precisely
\(v_p(b_p)\ge w_p\ge v_p(b_q)\).
The welfare inequality follows in the same direction.
The certificate flows need not themselves maximize: replacing them with maximizing flows preserves the bundle allocation and can only increase own utility. This correctly handles the allocation definition in USER_TASK.
After fixing the dual vertices, the system is linear with polynomially many variables and constraints and polynomial-length rational coefficients.
Nonnegative bundle variables are bounded by supplies, and nonnegative flow variables are bounded by profile masses. Hence a feasible system has a bounded feasible polyhedron and a rational vertex of polynomial encoding length.
There are only \(k(k-1)\) selected dual points, so the total certificate length remains polynomial. Exact rational verification is polynomial-time. Membership in \(\mathrm{NP}\) is established, including for instances whose initially postulated solution uses arbitrary reals.
The decision-algorithm bound is valid.
The active-constraint enumeration bound for each dual polyhedron is correct. Each group’s chosen vertex is selected independently for its \(k-1\) outgoing cross-evaluations. The exponent is therefore correctly computed using
\(\sum_p(t_p+m)=\tau+km\).
The enumeration and polynomial-time linear-program feasibility checks fit within the stated bound
\(\bigl((m+1)(\tau+1)\bigr)^{(k-1)(\tau+km)}\operatorname{poly}(m,\tau,k,L)\).
For \(k=1\), envy is automatic, and the single flow linear program suffices.
Minor issue — encoding length of a prescribed bundle. Section 3’s first sentence claims valuation time polynomial in \(m,\tau,L\), but \(L\) denotes the original instance length. An externally supplied rational bundle can have arbitrarily large encoding length. That length must be included or explicitly bounded. The next sentence already makes the corresponding allowance for a prescribed allocation.
Minimum clarification: State whether the prescribed bundle’s encoding length is included in the valuation input-length parameter, or restrict that sentence to bundles whose encoding length is polynomial in the original instance length. This is an encoding qualification; it does not affect the reduction, certificates, or decision-algorithm bound.
⟨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.