Answer: Polynomial-time solvable; an allocation of value \(\mathrm{OPT}\) can be computed exactly, with only binary-length dependence on \(k\).
Theorem 4 — class: hardness
Given a finite set \(T\) of reviewer types with rational masses \(\mu_t\) summing to \(1\), \(q\) interchangeable paper classes with rational per-capita supplies \(\beta_r\) summing to \(k\), and utilities \(u_t(r)\in\{\upsilon_1,\upsilon_2,\upsilon_3\}\), where \(0\le\upsilon_1<\upsilon_2<\upsilon_3\), what is the maximum \(\lambda\) for which there are nonnegative masses \(x_{t,z}\) assigned to integral bundle patterns \(z\in\mathbb Z_{\ge0}^q\), \(\sum_r z_r=k\), such that \(\sum_z x_{t,z}=\mu_t\), \(\sum_{t,z}z_r x_{t,z}\le\beta_r\) for every class \(r\), and \(x_{t,z}>0\) only if \(\sum_r z_r u_t(r)\ge\lambda\)? Determine the problem's complexity in the number of types, classes, and the input bit length.
A society is given by its support: a nonempty list \(T\) of \(\tau\) reviewer 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=q\ge1\) paper classes with nonnegative binary rational supplies \(\beta_r\), summing to \(k\), where \(k\ge2\) is a binary encoded integer. All classes are available to every type; papers within each class are interchangeable.
The input specifies common binary rational values \(0\le\upsilon_1<\upsilon_2<\upsilon_3\) and utilities \(u_t(r)\in\{\upsilon_1,\upsilon_2,\upsilon_3\}\). Let \(L\) be the total input bit length.
Let \(Z_k=\{z\in\mathbb Z_{\ge0}^{m}:\sum_r z_r=k\}\). An allocation consists of real masses \(x_{t,z}\ge0\) satisfying \(\sum_{z\in Z_k}x_{t,z}=\mu_t\) and \(\sum_{t,z}z_r x_{t,z}\le\beta_r\) for every class.
Its value is \(\min\{\sum_r z_r u_t(r):x_{t,z}>0\}\); let \(\mathrm{OPT}\) be the maximum such value. Thus every positive mass receives an integral bundle, and types may split among bundles.
Set \(\rho=\frac{\upsilon_2+(k-1)\upsilon_1}{\min\{2\upsilon_2,\upsilon_1+\upsilon_3\}+(k-2)\upsilon_1}\).
For each fixed rational \(\varepsilon>0\), on instances with \(\rho+\varepsilon\le1\), can an allocation of value at least \((\rho+\varepsilon)\mathrm{OPT}\) be computed in time polynomial in \(m,\tau,L\) (including only binary length dependence on \(k\)), or is achieving this guarantee NP-hard?
For finite agents and individual goods, achieving the same ratio is NP-hard for every fixed \(k\ge2\) and fixed utility triple, even when every good is available to every agent. [Source](https://aamas.csc.liv.ac.uk/AAMAS/aamas2014/proceedings/aamas/p997.pdf)
No result settling this approximation question for the precise mass formulation above was located in the literature search.
The mass formulation is polynomial-time solvable, even exactly. An allocation of value \(\mathrm{OPT}\), represented by at most \(m+\tau\) positive rational masses, can be computed in time polynomial in \(m,\tau,L\). In particular, the dependence on \(k\) is through its binary encoding length.
The proof uses the configuration linear program and an exact separation oracle obtained from integer programming in three variables.
Write the three utility values as rationals and let \(D\) be the product of their denominators. Define \(a_j=D\upsilon_j\) for \(j\in\{1,2,3\}\). These are nonnegative integers, and their binary encoding lengths, together with that of \(D\), are polynomial in \(L\).
Every scaled bundle utility is an integer between \(ka_1\) and \(ka_3\). For an integer threshold \(h\), define
\[ C_t(h)=\left\{z\in\mathbb Z_{\ge0}^{m}:\sum_r z_r=k,\quad D\sum_r u_t(r)z_r\ge h\right\}. \]
Thus an allocation has value at least \(h/D\) precisely when all its positive variables use bundles in \(C_t(h)\).
Classes with \(\beta_r=0\) can be deleted. Indeed, their supply constraint forces \(z_r=0\) for every bundle receiving positive mass. At least one class remains because the supplies sum to \(k>0\). Below, \(R\) denotes the remaining classes, so every \(\beta_r\), \(r\in R\), is positive.
Threshold \(ka_1\) is feasible. To see this directly, let \(e_r\) be the unit vector for class \(r\), and set
\[ x_{t,ke_r}=\mu_t\frac{\beta_r}{k}. \]
The type masses sum correctly, and class \(r\) receives total consumption \(\beta_r\). Every bundle has scaled utility at least \(ka_1\).
For a fixed \(h\), consider the following linear program, whose variables are indexed by \(t\in T\) and \(z\in C_t(h)\):
\[ F(h)=\max \sum_{t\in T}\sum_{z\in C_t(h)}x_{t,z}, \]
subject to
\[ x_{t,z}\ge0,\qquad \sum_{z\in C_t(h)}x_{t,z}\le\mu_t \quad(t\in T), \]
and
\[ \sum_{t\in T}\sum_{z\in C_t(h)}z_r x_{t,z}\le\beta_r \quad(r\in R). \]
This is a finite linear program: each bundle coordinate lies between \(0\) and \(k\). Its feasible region is nonempty and bounded, and \(F(h)\le\sum_t\mu_t=1\).
Claim. Threshold \(h/D\) is feasible if and only if \(F(h)=1\).
Proof. Any allocation attaining the threshold is feasible for this linear program and has objective value \(1\). Conversely, suppose a feasible solution has objective value \(1\). The nonnegative deficits
\[ \mu_t-\sum_{z\in C_t(h)}x_{t,z} \]
sum to zero, so every deficit is zero. Consequently, every type receives exactly its required mass, and every positive variable uses a bundle meeting the threshold. This is an allocation of value at least \(h/D\). \(\square\)
Its dual is
\[ \min_{\alpha,p}\left(\sum_{t\in T}\mu_t\alpha_t+ \sum_{r\in R}\beta_rp_r\right), \]
subject to
\[ \alpha_t\ge0,\qquad p_r\ge0, \]
and
\[ \alpha_t+\sum_{r\in R}p_rz_r\ge1 \quad(t\in T,\ z\in C_t(h)). \]
There are only \(\tau+|R|\) dual variables. The remaining task is to separate its implicitly specified bundle inequalities in polynomial time.
Fix a rational candidate \((\alpha,p)\). Negative coordinates immediately yield violated nonnegativity constraints, so assume all coordinates are nonnegative.
For a type \(t\), partition the remaining classes according to its utilities:
\[ R_{t,j}=\{r\in R:u_t(r)=\upsilon_j\}, \qquad j\in\{1,2,3\}. \]
For each nonempty group, choose a class \(r_{t,j}\) minimizing \(p_r\), and write \(c_{t,j}=p_{r_{t,j}}\). For an empty group, set \(c_{t,j}=0\) and impose \(n_j=0\) below.
Consider integer counts \(n_1,n_2,n_3\) satisfying
\[ n_j\ge0,\qquad n_1+n_2+n_3=k,\qquad a_1n_1+a_2n_2+a_3n_3\ge h, \]
with \(n_j=0\) whenever \(R_{t,j}\) is empty.
For these counts, the cheapest bundle puts all \(n_j\) papers from utility group \(j\) in class \(r_{t,j}\). Its price is \(\sum_j c_{t,j}n_j\). This assertion uses exactly the stated bundle model: a class may occur repeatedly, and supply restrictions constrain aggregate consumption rather than each individual bundle.
It follows that type \(t\) has a violated dual bundle inequality if and only if such integer counts exist with
\[ \sum_{j=1}^{3}c_{t,j}n_j<1-\alpha_t. \]
Here are both directions explicitly:
The strict inequality can be encoded exactly as an integer linear constraint. Let \(Q\) be the product of the denominators of \(\alpha_t,c_{t,1},c_{t,2},c_{t,3}\). Then it is equivalent to
\[ \sum_{j=1}^{3}(Qc_{t,j})n_j \le Q(1-\alpha_t)-1. \]
All coefficients in this inequality are integers.
We have therefore reduced separation for one type to integer linear feasibility in three variables, with a constant number of constraints. Lenstra’s fixed-dimensional integer-programming theorem solves this in time polynomial in the binary length of the coefficients. Its dimension hypothesis is satisfied independently of \(m,\tau,k\). [Lenstra, *Integer Programming with a Fixed Number of Variables*](https://pub.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf).
A feasible integer witness can also be recovered in polynomial time. Even using only a feasibility routine, one can determine each coordinate by binary search over \(\{0,\ldots,k\}\), successively fixing the recovered coordinates. This requires only a polynomial number of calls.
Scanning the classes to obtain the cheapest representatives and applying this procedure to each listed type gives an exact polynomial-time separation oracle for the dual. Its running time is polynomial in \(m,\tau,L\) and the encoding length of the query.
We use the constructive separation–optimization theorem for rational linear programming: with polynomially many variables, a known polynomial bound on individual constraint encoding lengths, and a polynomial-time exact separation oracle returning original violated inequalities, one can compute the exact optimum and recover an optimal solution of the dual linear program using polynomially many inequalities. Equivalently, for an LP with implicitly specified columns, one can recover an optimal solution supported on polynomially many columns. This includes exact rational computation and does not require full-dimensional feasible regions. [Grötschel–Lovász–Schrijver, *Geometric Algorithms and Combinatorial Optimization*](https://link.springer.com/book/10.1007/978-3-642-78240-4).
The hypotheses hold here:
The dual point \(\alpha_t=1\), \(p_r=0\) is feasible and has objective value \(1\). Because every objective coefficient is positive, any nonnegative point with objective at most \(1\) satisfies
\[ \alpha_t\le\frac1{\mu_t},\qquad p_r\le\frac1{\beta_r}. \]
Thus these rational coordinate bounds retain an optimal dual solution and have polynomial encoding length.
For completeness, these bounds also permit constructive recovery without changing the relevant restricted LP values. Retain the polynomial collection of bundle inequalities produced by the constructive ellipsoid procedure. Any dual restricted to those inequalities still admits \(\alpha_t=1,p_r=0\). Its minimum is attained: its nonnegative objective sublevel set at value \(1\) is compact because all objective coefficients are positive. Every minimizer lies within the same coordinate bounds. Consequently, removing those computational bounds leaves the restricted dual optimum unchanged.
The corresponding restricted primal keeps only the bundle variables associated with these retained inequalities. Strong duality gives it the same optimum \(F(h)\), and it can now be solved as an explicitly described polynomial-size LP. This standard primal-recovery procedure is also described in the proof of Theorem 3.5 of [Roughgarden–Kearns, *Marginals-to-Models Reducibility*](https://timroughgarden.org/papers/marg.pdf).
Choosing an optimal basic feasible solution yields at most \(\tau+|R|\le\tau+m\) positive bundle variables: after introducing slack variables, there are only \(\tau+|R|\) equations.
All returned masses have polynomial binary encoding length. Indeed, a basis matrix has dimension at most \(d=\tau+m\) and integer entries of absolute value at most \(k\). Hadamard’s determinant bound and Cramer’s rule, after clearing the rational right-hand-side denominators, bound the solution encoding lengths polynomially in \(d,L,\log k\). Each bundle also has polynomial encoding length because its coordinates are at most \(k\).
Therefore \(F(h)\) can be computed exactly, and whenever \(F(h)=1\), an explicit sparse allocation meeting the threshold can be returned.
Threshold feasibility is monotone: \(C_t(h+1)\subseteq C_t(h)\).
Binary search over the integer interval from \(ka_1\) to \(ka_3\), using the exact test \(F(h)=1\), finds the largest feasible integer threshold \(h^\star\). The number of iterations is at most
\[ O\!\left(\log\bigl(k(a_3-a_1)+1\bigr)\right), \]
which is polynomial in \(L\).
Every allocation’s scaled value is an integer, since it is the minimum of finitely many integer bundle utilities. Feasible allocations exist by Section 1, and there are finitely many possible values. Hence the largest feasible threshold satisfies
\[ h^\star=D\,\mathrm{OPT}. \]
Recovering the primal solution at \(h^\star\) therefore produces an allocation of value exactly \(\mathrm{OPT}\).
The exact algorithm applies to every instance described in the question. On instances satisfying \(\rho+\varepsilon\le1\), nonnegativity of utilities gives
\[ \mathrm{OPT}\ge(\rho+\varepsilon)\mathrm{OPT}. \]
Thus the requested guarantee is achievable in polynomial time.
This does not contradict the cited finite-agent hardness result. In that model, each agent must receive a single bundle of individual goods. In the present model, a type may split its mass among bundles, and feasibility is exactly linear in those masses. No integrality condition forces a type to choose one bundle. The cited result concerns the former formulation. [Ferraioli–Gourvès–Monnot, *On Regular and Approximately Fair Allocations of Indivisible Goods*](https://aamas.csc.liv.ac.uk/AAMAS/aamas2014/proceedings/aamas/p997.pdf).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes an exact polynomial-time algorithm for the stated mass formulation, including polynomial dependence on the binary encoding length of \(k\). I found no major or minor mathematical issues requiring repair.
The product \(D\) of the three positive rational denominators makes every \(a_j=D\upsilon_j\) an integer. Its bit length, and those of the scaled utilities, are polynomial in \(L\); numerical magnitude is not being confused with encoding length.
Every bundle contains exactly \(k\) papers, so its scaled utility lies between \(ka_1\) and \(ka_3\). The definition of \(C_t(h)\) therefore captures the threshold condition exactly.
Deleting zero-supply classes is valid: all terms in their consumption constraints are nonnegative, so a bundle with positive mass cannot contain such a class. The total supply ensures that at least one class remains.
For each type, the proposed masses satisfy
\(\sum_r x_{t,ke_r}=\mu_t\sum_r\beta_r/k=\mu_t\).
Class \(r\)'s total consumption is
\(\sum_t kx_{t,ke_r}=\beta_r\sum_t\mu_t=\beta_r\).
Each used bundle has scaled utility at least \(ka_1\). This construction works with fractional supplies and arbitrarily large binary-encoded \(k\); it uses no unstated divisibility assumption.
The configuration set is finite. Each variable is bounded by its type's mass, and the zero vector is feasible, so the primal maximum exists.
The equivalence between threshold feasibility and \(F(h)=1\) is rigorous. When the objective equals \(1\), the nonnegative type deficits sum to zero, forcing every type constraint to hold with equality. Thus the LP cannot falsely certify feasibility by leaving some types underserved.
The displayed dual has the correct objective, signs, and bundle inequalities. Strong duality applies to this finite, feasible, bounded primal, including thresholds for which some or all configuration sets are empty.
For fixed utility-group counts, concentrating each group's papers in a cheapest representative minimizes its price while preserving its utility and cardinality. This operation is permitted by the task: repetitions within a class are allowed, and supplies constrain aggregate consumption rather than individual bundles.
Both directions of the violation equivalence are established. Empty utility groups are handled correctly by imposing \(n_j=0\), so the oracle cannot construct papers from an unavailable group.
The denominator-clearing calculation is also correct. Both \(\sum_j(Qc_{t,j})n_j\) and \(Q(1-\alpha_t)\) are integers. Consequently, the strict inequality is exactly equivalent to the displayed weak inequality with the right-hand side decreased by one. There is no rounding error.
The invoked theorem decides integer linear feasibility in polynomial time in the binary input length when the number of integer variables is fixed. The cited paper establishes this result and also permits witness recovery. Here the dimension is three, all coefficients are integral after scaling, and equalities can be represented by pairs of inequalities. Lower-dimensional feasible sets do not invalidate the theorem. [Lenstra, *Integer Programming with a Fixed Number of Variables*](https://pub.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf).
The coefficients have polynomial bit length in the instance and query lengths. In particular, the product \(Q\) involves only four denominators.
The optional coordinate-recovery procedure is valid: coordinate bounds permit successive binary searches using feasibility queries. Its number of calls depends logarithmically on \(k\). Scanning only the listed types correctly uses the support size \(\tau\).
The output explicitly invokes the constructive rational separation–optimization theorem, including recovery from polynomially many original inequalities. This is stronger than merely computing a dual optimum and is the appropriate theorem for the claimed allocation output.
Its application has the necessary dimension and encoding bounds. The feasible dual point with all \(\alpha_t=1\) and all \(p_r=0\) supplies an objective upper bound. After zero-supply classes are removed, every objective coefficient is strictly positive, so the stated coordinate bounds contain an optimal solution and have polynomial encoding length.
The restricted-LP argument also handles the computational bounds correctly. Every restricted dual still has that feasible point, and its nonnegative objective sublevel set is compact. Removing the coordinate bounds therefore preserves its optimum. Strong duality then transfers the retained dual inequalities to the corresponding restricted primal columns.
The cited proof of Theorem 3.5 describes this constructive recovery mechanism, rather than supplying only an existence claim. [Roughgarden–Kearns, *Marginals-to-Models Reducibility*](https://timroughgarden.org/papers/marg.pdf).
Introducing slack variables gives \(\tau+|R|\) equations. A basic feasible solution has at most that many positive variables in total, hence at most \(\tau+|R|\le\tau+m\) positive bundle masses.
The basis matrix has integer entries bounded in absolute value by \(k\), including its slack columns. Clearing the rational right-hand-side denominators costs only polynomial bit length. Hadamard's bound and Cramer's rule therefore justify polynomial encoding lengths for the returned masses. Each explicitly listed bundle also has polynomial encoding length.
Threshold feasibility is monotone, the lower endpoint is feasible, and the upper endpoint bounds every possible bundle utility. The stated logarithmic iteration bound is polynomial in \(L\).
Every allocation has a nonempty finite positive support, so its scaled value is an integer. There are finitely many possible values and at least one feasible allocation. Thus the optimum is attained, and the largest feasible integer threshold equals \(D\,\mathrm{OPT}\).
Nonnegative utilities imply \(\mathrm{OPT}\ge0\). On the specified instances, \(\rho+\varepsilon\le1\), so an exact optimum meets the requested guarantee, including when \(\mathrm{OPT}=0\).
The algorithm is uniform in the input utility triple and binary-encoded \(k\). The explanation of why finite-agent hardness does not transfer is consistent with the task: the mass formulation permits splitting among integral bundles.
Feedback: No repair or additional mathematical clarification is required. The output resolves the assigned question and supports its stronger exact-solvability claim.
⟨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.