Answer: Polynomial-time solvable in \(m,\tau,L,\varepsilon^{-1}\).
Proposition 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe number of envied subsets problem is #P- complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses for a group \(P\) of mass \(\alpha\) and a group \(Q\) of mass \(1\), \(0<\alpha<1\), along with \(P\)’s current bundle and \(Q\)’s joint masses by preference type and assigned item class, compute the large-deviation rate \(I=\lim_{N\to\infty}-N^{-1}\log d_N\). Here \(d_N\) is the fraction of size-\(\alpha N\) subgroups of \(Q\) whose received bundle gives \(P\) strictly greater optimal utilitarian matching value than its current bundle; item-class supplies scale with population, and the finite populations realize the rational masses. Return an additive-\(\varepsilon\) approximation to \(I\), or report that envy is impossible. For selected masses \(x_{sj}\), the proposed rate is \(H(\alpha)-\sup \sum_{s,j}a_{sj}H(x_{sj}/a_{sj})\), subject to \(0\le x_{sj}\le a_{sj}\), \(\sum_{s,j}x_{sj}=\alpha\), and the strict envy condition, with the closure used only when strict envy is feasible.
A society is given by its support: the list of the \(\tau\) preference types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) item classes with interchangeable copies, and each type \(s\) has nonnegative binary-rational utilities \(u_{sj}\).
Group \(P\) has type masses \(p_s\) summing to \(\alpha\), where \(0<\alpha<1\), and current item-class masses \(c_j\geq0\) with \(\sum_jc_j\leq\alpha\). Group \(Q\) has mass \(1\); its prescribed joint masses \(a_{sj}\geq0\) sum to \(1\), where \(j=0\) denotes receiving no item and \(u_{s0}=0\). The prescribed assignment within \(Q\) maximizes its utilitarian welfare for its bundle; any optimal assignment is allowed, and its joint masses are fixed input.
For a bundle \(b\) of total mass at most \(\alpha\), define \(V_p(b)=\max\{\sum_{s,j\geq1}u_{sj}y_{sj}:y_{sj}\geq0,\ \sum_{j\geq1}y_{sj}\leq p_s,\ \sum_sy_{sj}=b_j\}\). Thus each agent receives at most one item, and every supplied item is assigned. Copies allocated to the two groups are distinct even when their classes coincide.
A selected subgroup has joint masses \(0\leq x_{sj}\leq a_{sj}\), \(\sum_{s,j}x_{sj}=\alpha\), and bundle \(b_j=\sum_sx_{sj}\) for \(j\geq1\). Strict envy means \(V_p(b)>V_p(c)\); envy is impossible when no such selection exists.
For every positive integer \(N\) divisible by a common denominator of all input masses, realize exactly \(Np_s\) agents in \(P\), \(Na_{sj}\) agents in each assigned category of \(Q\), and \(Nc_j\) copies in the current bundle. Let \(d_N\) be the fraction of all uniformly chosen \(\alpha N\)-agent subsets of \(Q\) whose received items have strictly greater optimal utilitarian matching value for \(P\) than its current bundle. Using natural logarithms, set \(I=\lim_{N\to\infty}-N^{-1}\log d_N\) along these integers, with \(-\log0=+\infty\).
Given binary-rational \(0<\varepsilon<1\), the computational problem is to approximate finite \(I\) within additive \(\varepsilon\), or report that envy is impossible. Let \(L\) be the total binary input length.
Does this rate-approximation problem admit an algorithm polynomial in \(m,\tau,L,\varepsilon^{-1}\), or is it NP-hard?
Exact counting of strictly envied equal-size subgroups in finite societies is \(\#\mathrm{P}\)-complete; a fully polynomial randomized approximation scheme is established when utilities are identical within each group. [Source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA230362)
No result settling this exact continuous rate-approximation problem was located in the literature search.
Result. The problem admits a deterministic algorithm polynomial in \(m,\tau,L,\varepsilon^{-1}\). Strict envy can be decided exactly, and whenever it is possible, the limit defining \(I\) exists and can be approximated within additive \(\varepsilon\).
The proof has two main ingredients: an exact entropy formula for the rate, and a rational linear-programming approximation of that formula.
1. Aggregating the assignment in \(Q\).
For \(j\in\{0,\ldots,m\}\), define \(q_j=\sum_s a_{sj}\). Thus \(q_j\geq0\) and \(\sum_{j=0}^m q_j=1\). Let
\[ \mathcal K=\left\{z\in\mathbb R^{m+1}:0\leq z_j\leq q_j,\ \sum_{j=0}^m z_j=\alpha\right\}. \]
Here \(z_j\) is the selected mass receiving class \(j\), including the no-item class \(0\).
The possible aggregate selections are exactly \(\mathcal K\). Indeed, any admissible joint selection gives \(z_j=\sum_s x_{sj}\in\mathcal K\). Conversely, for \(z\in\mathcal K\), set \(x_{sj}=a_{sj}z_j/q_j\) whenever \(q_j>0\), and set \(x_{sj}=0\) when \(q_j=0\). These joint masses satisfy all selection constraints.
Write \(b(z)=(z_1,\ldots,z_m)\), and put \(v=V_p(c)\). Define the strict and weak envy sets by
\[ \mathcal E=\{z\in\mathcal K:V_p(b(z))>v\}, \qquad \mathcal F=\{z\in\mathcal K:V_p(b(z))\geq v\}. \]
The proof applies to every fixed assignment in \(Q\), so it applies in particular to the promised optimal assignments.
2. Concavity, continuity, and the finite matching interpretation.
Every bundle with total mass at most \(\alpha\) is feasible for \(P\). For example, \(y_{sj}=p_s b_j/\alpha\) satisfies the column equalities and row inequalities.
The function \(V_p\) is concave. To see this, let \(y\) and \(y'\) be optimal assignments for bundles \(b\) and \(b'\). For \(t\in[0,1]\), the assignment \((1-t)y+ty'\) is feasible for \((1-t)b+tb'\). Consequently,
\[ V_p((1-t)b+tb')\geq(1-t)V_p(b)+tV_p(b'). \]
We also need continuity, including at boundary bundles. Introduce the dummy column \(b_0=\alpha-\sum_{j=1}^m b_j\), with utility zero, and replace the row inequalities by row equalities after adding this column. Let \(U=\max_{s,j\geq1}u_{sj}\).
Given bundles \(b,b'\), remove assignment mass from columns whose totals exceed the corresponding totals of \(b'\), and redistribute that mass within the same rows to deficit columns. The total mass moved is
\[ \Delta=\frac12\sum_{j=0}^m|b_j-b'_j|. \]
The redistribution preserves every row total and produces the required column totals. Removing this mass loses at most \(U\Delta\) welfare, while adding it loses none because utilities are nonnegative. Applying the argument in both directions gives
\[ |V_p(b)-V_p(b')| \leq U\Delta \leq U\sum_{j=1}^m|b_j-b'_j|. \]
Thus \(V_p\) is continuous. It follows that \(\mathcal F\) is compact and convex.
For every admissible \(N\), the finite optimal matching value of a lattice bundle \(b\) is exactly \(NV_p(b)\). Here is an integrality justification. After adding the dummy column, the scaled assignment problem is a transportation linear program with integer row and column totals. At a vertex, its positive-support bipartite graph contains no cycle: an alternating perturbation around a positive cycle would express the point as the midpoint of two distinct feasible points. Its support is therefore a forest. Repeated leaf elimination shows that every positive entry is integral, since a leaf edge equals its integer residual margin. A linear objective attains its optimum at a vertex, so an integral optimum exists.
Such an integral transportation assignment is realizable by assigning distinct agents and copies. This argument applies both to a selected subgroup’s bundle and to the current bundle.
3. Exact detection of impossible envy.
Compute \(v\) by its defining rational linear program. Next compute \(M\), the maximum of \(\sum_{s,j\geq1}u_{sj}y_{sj}\), subject to
\[ z\in\mathcal K,\qquad y_{sj}\geq0,\qquad \sum_{j=1}^m y_{sj}\leq p_s,\qquad \sum_s y_{sj}=z_j\quad(j\geq1). \]
For each fixed \(z\), optimizing over \(y\) gives \(V_p(b(z))\). Therefore
\[ M=\max_{z\in\mathcal K}V_p(b(z)), \qquad \mathcal E\neq\varnothing\ \Longleftrightarrow\ M>v. \]
Both linear programs are feasible, bounded, and have rational coefficients. Exact rational linear programming computes their optimal values in polynomial bit complexity, allowing an exact comparison of \(M\) and \(v\). This is the standard exact LP theorem; see the discussion in [Gleixner and Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
If \(M\leq v\), every finite selection also fails strict envy, by the finite matching interpretation above. The algorithm then reports that envy is impossible.
Henceforth assume \(M>v\).
4. The exact rate formula.
Define the binary entropy in natural logarithms by
\[ h(t)=-t\log t-(1-t)\log(1-t), \]
with \(h(0)=h(1)=0\). For \(z\in\mathcal K\), put
\[ H(z)=\sum_{j:q_j>0}q_jh(z_j/q_j), \qquad J(z)=h(\alpha)-H(z). \]
We will prove
\[ I=\min_{z\in\mathcal F}J(z) =h(\alpha)-\max_{z\in\mathcal F}H(z). \]
First consider the finite selection probabilities. If \(k_j\) selected agents receive class \(j\), then the probability of this count vector is
\[ \frac{\prod_{j=0}^m\binom{Nq_j}{k_j}}{\binom N{\alpha N}}. \]
The admissible vectors satisfy \(0\leq k_j\leq Nq_j\) and \(\sum_j k_j=\alpha N\). Such a vector is strictly envied precisely when \(k/N\in\mathcal E\).
For integers \(0\leq k\leq n\),
\[ \frac{e^{nh(k/n)}}{n+1} \leq\binom nk \leq e^{nh(k/n)}. \]
For \(0<k<n\), these bounds follow by considering a binomial distribution with success probability \(k/n\). Its probability at \(k\) is \(\binom nk e^{-nh(k/n)}\); this probability is at most one and, since \(k\) is a mode, at least \(1/(n+1)\). The endpoint cases hold directly.
Let \(r=|\{j:q_j>0\}|\). Whenever the finite strict-envy set is nonempty, define
\[ J_N=\min\{J(k/N):k/N\in\mathcal E,\ k\text{ an admissible integer vector}\}. \]
There are at most \((N+1)^r\) admissible count vectors. Applying the binomial bounds to each summand yields
\[ J_N-\frac{(r+1)\log(N+1)}N \leq-\frac1N\log d_N \leq J_N+\frac{r\log(N+1)}N. \]
It remains to identify the limit of \(J_N\).
Fix any \(z\in\mathcal E\). For every admissible \(N\), start with \(k_j=\lfloor Nz_j\rfloor\). The deficit \(\alpha N-\sum_j k_j\) is an integer equal to the sum of the fractional parts. Add one to that many coordinates having positive fractional parts. This produces an admissible vector: since each \(Nq_j\) is integral, a coordinate with positive fractional part can be rounded upward without exceeding its capacity. Moreover, \(|k_j/N-z_j|\leq1/N\).
Continuity of \(V_p\) implies that these rounded vectors lie in \(\mathcal E\) for all sufficiently large admissible \(N\). Continuity of \(J\) gives \(J(k/N)\to J(z)\). Thus the finite strict-envy set is eventually nonempty, and
\[ \lim_{N\to\infty}J_N=\inf_{z\in\mathcal E}J(z). \]
Indeed, every \(J_N\) is at least this infimum, while rounding any fixed \(z\in\mathcal E\) bounds the limiting upper value by \(J(z)\).
Finally, we can replace strict envy by weak envy in this infimum. Choose \(z^\star\in\mathcal E\). For any \(z\in\mathcal F\) and \(t\in(0,1]\), concavity gives
\[ V_p(b((1-t)z+tz^\star)) \geq(1-t)V_p(b(z))+tV_p(b(z^\star)) >v. \]
Thus every point of \(\mathcal F\) is a limit of points of \(\mathcal E\). Since \(J\) is continuous and \(\mathcal F\) is compact,
\[ \inf_{z\in\mathcal E}J(z)=\min_{z\in\mathcal F}J(z). \]
This proves the rate formula and the existence of the limit. It also proves that envy being possible is equivalent to \(I\) being finite.
For later use, Jensen’s inequality and \(\sum_j z_j=\alpha\) give \(H(z)\leq h(\alpha)\). Therefore \(0\leq I\leq h(\alpha)\).
5. A polynomial-size rational LP approximates the entropy optimum.
The weak-envy constraint has an exact linear formulation: use the constraints from Section 3 and add
\[ \sum_{s,j\geq1}u_{sj}y_{sj}\geq v. \]
Its projection onto \(z\) is exactly \(\mathcal F\). We approximate only the entropy objective, leaving all these feasibility constraints exact.
We first establish a uniform entropy bound. For \(0<\delta\leq1\) and \(|s-t|\leq\delta\), integration of \(h'(x)=\log((1-x)/x)\) gives
\[ |h(s)-h(t)|\leq2\delta(1-\log\delta)\leq4\sqrt\delta. \]
For the first inequality, bound \(|h'(x)|\) by \(-\log x-\log(1-x)\). Each term has integral at most \(\delta(1-\log\delta)\) over an interval of length at most \(\delta\). The second inequality follows from \(\log(1/\delta)\leq\delta^{-1/2}\) and \(\delta\leq\sqrt\delta\).
Set \(K=\lceil256\varepsilon^{-2}\rceil\), \(t_i=i/K\) for \(i\in\{0,\ldots,K\}\), and \(\eta=\varepsilon/8\). Compute rational numbers \(r_i\) satisfying \(|r_i-h(t_i)|\leq\eta\).
For each positive \(q_j\), introduce continuous variables \(\lambda_{ji}\geq0\), subject to
\[ \sum_{i=0}^K\lambda_{ji}=1, \qquad z_j=q_j\sum_{i=0}^K t_i\lambda_{ji}. \]
Together with the exact weak-envy constraints, maximize the rational linear objective
\[ \widetilde H =\sum_{j:q_j>0}q_j\sum_{i=0}^K r_i\lambda_{ji}. \]
Let its optimum be \(\widetilde H^\star\), and let \(H^\star=\max_{z\in\mathcal F}H(z)\).
For any feasible \(\lambda\), concavity of \(h\) gives
\[ \sum_i r_i\lambda_{ji} \leq\sum_i h(t_i)\lambda_{ji}+\eta \leq h(z_j/q_j)+\eta. \]
Since the positive \(q_j\) sum to one, \(\widetilde H^\star\leq H^\star+\eta\).
For the reverse bound, fix a maximizer \(z\) of \(H\). Represent each \(z_j/q_j\) as a convex combination of its two neighboring grid points. Both grid points are at distance at most \(1/K\), so the entropy bound implies
\[ \sum_i r_i\lambda_{ji} \geq h(z_j/q_j)-4K^{-1/2}-\eta. \]
Consequently,
\[ H^\star-4K^{-1/2}-\eta \leq\widetilde H^\star \leq H^\star+\eta. \]
Now compute a rational \(\widehat h_\alpha\) satisfying \(|\widehat h_\alpha-h(\alpha)|\leq\eta\), and return
\[ \widehat I=\max\{0,\widehat h_\alpha-\widetilde H^\star\}. \]
Before truncation at zero, the absolute error is at most \(4K^{-1/2}+2\eta\leq\varepsilon/2\). Truncation cannot increase the error because \(I\geq0\). Thus \(|\widehat I-I|\leq\varepsilon\).
All \(\lambda\)-variables are continuous; this construction is a linear program.
6. Bit complexity and conclusion.
The exact envy test uses polynomially many variables and constraints in \(m,\tau\), with rational coefficients of polynomial encoding length. The exact optimal value \(v\) also has polynomial encoding length.
The entropy-approximation LP has
\[ O(\tau m+(m+1)K) =O(\tau m+(m+1)\varepsilon^{-2}) \]
variables and constraints. Aggregating the rational input masses and forming its coefficients require polynomial bit complexity.
For completeness, the entropy samples can be computed with the asserted precision in polynomial time. For a positive rational \(x\), write \(x=2^k w\), where \(1\leq w<2\). The integer \(|k|\) is bounded by the encoding length of \(x\). Using
\[ \log w =2\sum_{\ell=0}^{\infty} \frac{((w-1)/(w+1))^{2\ell+1}}{2\ell+1}, \]
the series argument has absolute value at most \(1/3\), so the tail decreases geometrically. The same expansion computes \(\log2\). Computing \(\log w\) and \(\log2\) with errors at most \(\rho/(2(|k|+1))\) gives \(\log x=k\log2+\log w\) with error at most \(\rho\). Polynomially many rational arithmetic operations, on numbers of polynomial encoding length, suffice. Applying this to the positive arguments in \(h(t_i)\) and \(h(\alpha)\) supplies the required rational approximations; endpoint entropy values are zero.
Therefore the algorithm:
Its running time is polynomial in \(m,\tau,L,\varepsilon^{-1}\), and its correctness includes the strict boundary cases. Only the listed support types are used.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time result is established. I found no mathematical errors, substantive gaps, or required expositional repairs. The proof addresses the specified support encoding, exact detection of impossible envy, existence of the rate limit, and deterministic additive approximation.
The aggregation is valid.
Thus replacing the joint selection variables by aggregate counts loses neither possible bundles nor relevant probability information. The proof’s independence from the optimality promise for \(Q\)’s assignment is legitimate: proving the result for every fixed assignment covers the promised inputs.
Issues: None.
The proposed assignment \(y_{sj}=p_sb_j/\alpha\) is feasible because \(\alpha>0\), its column totals equal \(b_j\), and its row totals are at most \(p_s\).
The concavity argument correctly combines feasible optimal assignments. The objectives are linear, so the displayed concavity inequality follows with the stated direction.
The continuity argument also works at boundary bundles. Adding the dummy column converts the constraints to fixed row totals. Removing mass from surplus columns and reallocating it within the same rows preserves those totals and supplies the deficit columns. The moved mass is precisely the stated \(\Delta\). Nonnegative utilities ensure that adding mass cannot decrease welfare, while removing it costs at most \(U\Delta\). Reversing the roles of the bundles gives the absolute-value bound. The final inequality correctly accounts for the change in the dummy column.
Consequently, the weak-envy set is closed and convex within the compact selection polytope.
The finite matching interpretation is justified by the transportation integrality argument:
The integral solution is realizable using distinct agents and copies, and its objective equals the scaled continuous optimum. This applies to both bundles being compared.
Issues: None.
The LP defining \(M\) correctly represents optimization over all selectable bundles and all feasible assignments to \(P\). Thus its optimum is the maximum of \(V_p(b(z))\) over \(\mathcal K\).
The equivalence between possible strict envy and \(M>v\) is exact. Both LPs are feasible and bounded, and their data are rational. The cited exact-LP result applies: rational linear programs can be solved exactly in polynomial bit complexity, permitting an exact comparison of their rational optimal values. The cited discussion does support this use. [Gleixner and Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf)
When \(M\leq v\), the finite matching interpretation rules out strict envy for every admissible finite realization.
Issues: None.
The count-vector probability is the correct multivariate hypergeometric probability. Every admissible integer count vector is realizable because the assigned categories contain exactly their prescribed integer numbers of agents.
The binomial bounds are valid, including the endpoint cases. For an interior count, that count is a mode of the binomial distribution with the specified success probability, giving the lower probability bound used in the proof.
The resulting bounds on \(-N^{-1}\log d_N\) have the correct signs and polynomial factors. The numerator contributes at most \(r\) binomial factors, the denominator contributes one, and the number of admissible count vectors is bounded as stated.
The lattice approximation respects all constraints:
For each fixed strictly envied point, continuity therefore guarantees strict envy after rounding for every sufficiently large admissible \(N\). The lower bound by the continuous infimum and the upper bound obtained from each fixed strict point establish the asserted limit of \(J_N\). Eventual nonemptiness handles the possibility that some earlier finite realizations have no envied subset.
Replacing strict envy by weak envy is justified. Mixing any weakly envied point with a fixed strictly envied point remains feasible and becomes strictly envied by concavity. Hence every weakly envied point is approximable by strictly envied points. Continuity and compactness then give the stated equality of extrema.
Jensen’s inequality applies with weights \(q_j\), which sum to one, and weighted mean \(\alpha\). It establishes the claimed nonnegativity and finiteness bounds.
Issues: None.
The lifted weak-envy constraints project exactly onto \(\mathcal F\). Existence of a feasible assignment attaining at least \(v\) is equivalent to the optimal assignment value being at least \(v\).
The entropy modulus is valid, including intervals touching the endpoints. The two logarithmic integrals have the asserted bounds, and the subsequent square-root estimate holds throughout the stated range.
The approximation LP requires no discrete variables. Its two objective estimates are correct:
Weighting by the positive \(q_j\) introduces no dimension-dependent error because those weights sum to one.
The constants also check out: the chosen grid gives \(4K^{-1/2}\leq\varepsilon/4\), and the two additional entropy-approximation errors total \(\varepsilon/4\). Thus the error before truncation is at most \(\varepsilon/2\). Truncation at zero cannot increase the error relative to the nonnegative true rate.
Issues: None.
The LP sizes are polynomial in the listed support size and number of item classes. No enumeration of unlisted preference types is used.
Aggregated masses, the exact value \(v\), grid coefficients, and rational entropy samples have polynomial encoding length. The logarithm computation is adequate: scaling a positive rational to the specified interval yields a geometrically convergent series, and the stated precision allocation controls multiplication by the scaling exponent. Endpoint entropy values are handled separately.
The grid size is polynomial in \(\varepsilon^{-1}\). Consequently, the rational arithmetic and exact LP solves give the claimed deterministic polynomial running time.
Zero type masses in \(P\), zero category capacities, zero utilities, boundary bundles, and equality in the envy comparison are covered by the argument.
Required feedback: None. The write-up resolves the assigned problem as stated.
⟨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.