Answer: Polynomial-time solvable in \(m,\tau,L\), counting value-oracle calls at unit cost.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateEvery fair division instance, with matroid-rank valuations, admits a maximin share allocation, $\alloc$, that also maximizes social welfare. Furthermore, such an allocation $\mathcal{A}$ can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\) with rational masses \(\mu_\theta\), good classes \(G\) with rational per-capita supplies \(\rho_g\), and value-oracle matroid-rank valuations \(r_\theta\), compute a mass allocation \(x_{\theta,B}\) over integral bundles \(B\subseteq G\) satisfying \(\sum_B x_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B\ni g}x_{\theta,B}\le\rho_g\), and \(x_{\theta,B}>0\Rightarrow r_\theta(B)\ge\lambda_\theta(\rho)\), where \(\lambda_\theta(\rho)\) is the largest integer \(q\) supported by a distribution over integral bundles of rank at least \(q\) under the same capacities; maximize \(\sum_{\theta,B}x_{\theta,B}r_\theta(B)\) over all capacity-feasible allocations in time polynomial in the type and good dimensions and the input bit length.
A society is given by its support: a list \(\Theta\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) good classes \(G\), with nonnegative binary-rational per-capita supplies \(\rho_g\). Each type has a matroid-rank valuation \(r_\theta:2^G\to\mathbb Z_{\geq0}\), supplied by a value oracle. Bundles are subsets of \(G\), including the empty set, and contain at most one unit of each class.
Define \(\lambda_\theta(\rho)\) as the largest \(q\in\{0,\ldots,m\}\) for which there exist \(p_B\geq0\) satisfying \(\sum_{B\subseteq G}p_B=1\), \(\sum_{B\ni g}p_B\leq\rho_g\) for every \(g\), and \(p_B>0\Rightarrow r_\theta(B)\geq q\). This benchmark uses a unit-mass society consisting entirely of type \(\theta\).
A capacity-feasible allocation consists of masses \(x_{\theta,B}\geq0\) satisfying \(\sum_Bx_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B\ni g}x_{\theta,B}\leq\rho_g\). Unused supply is allowed. It is fair if \(x_{\theta,B}>0\Rightarrow r_\theta(B)\geq\lambda_\theta(\rho)\).
The allocation problem is to compute a fair allocation attaining the maximum of \(\sum_{\theta,B}x_{\theta,B}r_\theta(B)\) over all capacity-feasible allocations, or determine that no such allocation exists. Represent allocations by their nonzero bundle masses.
Is this allocation problem solvable in polynomial time in \(m,\tau,L\), counting value-oracle calls at unit cost, or is it NP-hard even for polynomial-time evaluable rank functions? Here \(L\) is the total bit length of the rational input.
For finitely many agents and indivisible goods, an exact maximin-share allocation attaining unrestricted maximum social welfare always exists and is computable in polynomial time with value-oracle access ([Barman–Verma](https://arxiv.org/abs/2012.12710)). No result settling this exact mass-and-capacity problem was identified in the literature search.
The allocation problem is solvable in polynomial time in \(m,\tau,L\), counting value-oracle calls at unit cost. The algorithm either returns a fair allocation attaining unrestricted maximum welfare or correctly determines that no such allocation exists. Its output has at most \(\tau(m+1)\) nonzero bundle masses, all rational and of polynomial encoding length.
The proof treats unrestricted welfare maximization exactly as requested: it computes both the unrestricted optimum and the optimum subject to fairness, then compares them exactly.
Let \(M_\theta\) denote the matroid whose rank function is \(r_\theta\). Write \(\mathcal I_\theta\) for its independent sets.
For every bundle \(B\subseteq G\), the definition of matroid rank guarantees an independent set \(I\subseteq B\) with
\(|I|=r_\theta(B)=r_\theta(I)\).
Replacing a mass of type \(\theta\) assigned \(B\) by the same mass assigned \(I\):
Unused supply is allowed, so this replacement preserves capacity feasibility. Consequently, both the benchmark distributions and the allocation optimization may be restricted to independent bundles without changing their relevant feasibility or optimum values.
Moreover, independence is testable with one value-oracle call:
\(I\in\mathcal I_\theta\iff r_\theta(I)=|I|\).
For an integer \(q\) with \(0\le q\le r_\theta(G)\), define
\(\mathcal I_{\theta,q}=\{I\in\mathcal I_\theta:|I|\ge q\}\),
and let
\(P_{\theta,q}=\operatorname{conv}\{\mathbf 1_I:I\in\mathcal I_{\theta,q}\}\subseteq\mathbb R^G\),
where \(\mathbf 1_I\) is the incidence vector of \(I\).
We first prove that linear optimization over \(P_{\theta,q}\) is polynomial-time computable, including for arbitrary signed rational objective coefficients.
Fix coefficients \(a_g\in\mathbb Q\). Order the goods as \(g_1,\ldots,g_m\) so that
\(a_{g_1}\ge\cdots\ge a_{g_m}\).
Run matroid greedy in this order, accepting a good whenever adding it preserves independence. For each \(k\in\{0,\ldots,r_\theta(G)\}\), let \(I_k\) consist of the first \(k\) accepted goods.
Claim. The set \(I_k\) maximizes \(\sum_{g\in I}a_g\) among independent sets of cardinality exactly \(k\).
Proof. Put \(A_j=\{g_1,\ldots,g_j\}\). After scanning \(A_j\), greedy has selected a maximal independent subset of \(A_j\): a rejected good cannot become addable after further insertions, because independence is hereditary. By the matroid augmentation axiom, every maximal independent subset of \(A_j\) has cardinality \(r_\theta(A_j)\). Therefore,
\(|I_k\cap A_j|=\min\{k,r_\theta(A_j)\}\).
For any independent set \(J\) of cardinality \(k\),
\(|J\cap A_j|\le\min\{k,r_\theta(A_j)\}=|I_k\cap A_j|\).
For every cardinality-\(k\) set \(J\), telescoping the ordered coefficients gives
\(\displaystyle \sum_{g\in J}a_g =k\,a_{g_m}+\sum_{j=1}^{m-1}(a_{g_j}-a_{g_{j+1}})|J\cap A_j|\).
Each coefficient difference is nonnegative. The prefix inequalities thus imply that the weight of \(I_k\) is at least the weight of \(J\). This proof allows negative coefficients, since the term \(k\,a_{g_m}\) is identical for both sets. \(\square\)
It follows that an optimum over \(P_{\theta,q}\) is obtained by choosing the highest-weight set among
\(I_q,I_{q+1},\ldots,I_{r_\theta(G)}\).
One greedy scan uses at most \(m\) independence tests. Sorting, computing the candidate weights, and selecting the best candidate take polynomial time. Thus we have an exact strong optimization oracle for \(P_{\theta,q}\).
If \(q>r_\theta(G)\), the family is empty, which is detected by querying \(r_\theta(G)\).
We use the following standard rational-polyhedral results. A polytope is *well described* when a bound is known on the encoding length of each inequality in some rational description; the number of inequalities need not be polynomial.
For such polytopes, exact linear optimization and strong separation are polynomially interconvertible. These algorithms handle lower-dimensional polytopes and detect emptiness. Given a rational point in a nonempty polytope and an optimization oracle, one can also compute its expression as a convex combination of at most one more than the ambient dimension many vertices, with rational coefficients. Finally, a rational polytope generated by vectors of encoding length at most \(v\) in dimension \(d\) has facet complexity at most \(3d^2v\). These are respectively Theorem 6.4.9, Theorem 6.5.11, and Lemma 6.2.4(b) of [Grötschel–Lovász–Schrijver, *Geometric Algorithms and Combinatorial Optimization*](https://link.springer.com/chapter/10.1007/978-3-642-78240-4_7).
Their hypotheses hold here:
Consequently, we can obtain strong separation oracles for these polytopes and perform exact rational optimization over their intersections with explicit rational constraints. We can also construct vertex decompositions of rational points in them.
This includes cases involving loops, zero supplies, or singleton polytopes: no full-dimensionality assumption is needed.
Fix a type \(\theta\) and an integer \(q\). By Section 1, \(q\) is feasible in the definition of \(\lambda_\theta(\rho)\) exactly when a distribution exists over \(\mathcal I_{\theta,q}\) whose consumption marginals satisfy the capacities.
Equivalently,
\(P_{\theta,q}\cap\{y\in\mathbb R^G:y_g\le\rho_g\text{ for every }g\in G\}\ne\varnothing\).
To verify both directions:
For \(q\le r_\theta(G)\), this intersection has a polynomial-time strong separation oracle: check the explicit capacity inequalities and then membership in \(P_{\theta,q}\). Its facet complexity remains polynomial in \(m,L\). Section 3 therefore provides an exact feasibility test.
Test all \(q\in\{0,\ldots,m\}\), immediately rejecting those exceeding \(r_\theta(G)\), and retain the largest feasible value. The value \(q=0\) is always feasible because the empty bundle consumes nothing.
Repeating this procedure for all supported types computes all \(\lambda_\theta(\rho)\) using polynomial time and polynomially many value-oracle calls.
Let \(\mathbf q=(q_\theta)_{\theta\in\Theta}\) be any integer threshold vector with
\(0\le q_\theta\le r_\theta(G)\).
For each type and good, introduce a variable \(z_{\theta,g}\), interpreted as the total mass of type \(\theta\) receiving good \(g\). Define
\(\displaystyle \mathcal F(\mathbf q)= \left\{z\in\mathbb R^{\Theta\times G}: z_\theta/\mu_\theta\in P_{\theta,q_\theta}\text{ for every }\theta,\quad \sum_{\theta\in\Theta}z_{\theta,g}\le\rho_g\text{ for every }g \right\}\).
Division by \(\mu_\theta\) is valid because every supported type has positive mass. Consider
\(\displaystyle W(\mathbf q)= \max_{z\in\mathcal F(\mathbf q)} \sum_{\theta\in\Theta}\sum_{g\in G}z_{\theta,g}\).
Claim. This is exactly the maximum welfare obtainable by capacity-feasible allocations satisfying the thresholds \(q_\theta\).
Proof. Start with such an allocation. Replace each bundle by an independent subset as in Section 1, preserving its welfare. Define
\(\displaystyle z_{\theta,g}=\sum_{I\ni g}x_{\theta,I}\).
Since \(\sum_Ix_{\theta,I}=\mu_\theta\), the numbers \(x_{\theta,I}/\mu_\theta\) form a probability distribution over \(\mathcal I_{\theta,q_\theta}\). Hence
\(\displaystyle z_\theta/\mu_\theta =\sum_I(x_{\theta,I}/\mu_\theta)\mathbf 1_I \in P_{\theta,q_\theta}\).
Capacity feasibility gives the remaining constraints. Because the allocated bundles are independent, their welfare equals
\(\displaystyle \sum_{\theta,I}x_{\theta,I}r_\theta(I) =\sum_{\theta,I}x_{\theta,I}|I| =\sum_{\theta,g}z_{\theta,g}\).
Conversely, given \(z\in\mathcal F(\mathbf q)\), choose for each type a convex representation
\(\displaystyle z_\theta/\mu_\theta=\sum_Ip_{\theta,I}\mathbf 1_I\)
using sets \(I\in\mathcal I_{\theta,q_\theta}\). Assign masses
\(x_{\theta,I}=\mu_\theta p_{\theta,I}\).
Their total mass is \(\mu_\theta\); their aggregate consumption is \(z\); every positive-mass bundle has rank at least \(q_\theta\); and their welfare is the displayed objective. This proves the claim. \(\square\)
The optimization is polynomial-time computable. Indeed, its dimension is \(m\tau\). To separate a candidate \(z\), check the capacity inequalities and query the separation oracle for each \(z_\theta/\mu_\theta\). A separating inequality \(a^\top y\le b\) for a type’s polytope becomes the valid inequality
\(a^\top z_\theta\le\mu_\theta b\).
Scaling by the rational masses and adding the explicit capacity inequalities preserve polynomial facet complexity in \(m,\tau,L\). Furthermore,
\(0\le z_{\theta,g}\le\mu_\theta\),
so the feasible set is bounded. Section 3 therefore yields an exact optimum rational point and value whenever the feasible set is nonempty.
For completeness, the fair feasible set is always nonempty. For each type, choose a benchmark marginal vector \(y^\theta\in P_{\theta,\lambda_\theta(\rho)}\) satisfying \(y^\theta_g\le\rho_g\). Set \(z_\theta=\mu_\theta y^\theta\). Then
\(\displaystyle \sum_\theta z_{\theta,g} \le\sum_\theta\mu_\theta\rho_g =\rho_g\).
This proves fairness feasibility; attaining unrestricted maximum welfare is handled separately below.
Compute the two exact rational optimum values
\(W_{\mathrm{all}}=W(\mathbf 0)\),
and
\(W_{\mathrm{fair}}=W((\lambda_\theta(\rho))_{\theta\in\Theta})\).
By Section 5, these are respectively the unrestricted optimum and the best welfare attainable subject to fairness. Since fairness restricts the feasible allocations,
\(W_{\mathrm{fair}}\le W_{\mathrm{all}}\).
There are two cases.
The comparison is exact, since the algorithms return rational optimum values.
In the equality case, let \(z^*\) be an optimum rational point of the fair formulation. For every type, construct a convex decomposition
\(\displaystyle z^*_\theta/\mu_\theta =\sum_{j=1}^{s_\theta}\alpha_{\theta,j}\mathbf 1_{I_{\theta,j}}\),
where
\(s_\theta\le m+1,\qquad \alpha_{\theta,j}>0,\qquad \sum_j\alpha_{\theta,j}=1\).
The constructive decomposition theorem in Section 3 computes this in polynomial time. Each returned vertex belongs to the finite generating family of \(P_{\theta,\lambda_\theta(\rho)}\), so its bundle \(I_{\theta,j}\) is independent and has cardinality at least \(\lambda_\theta(\rho)\).
Output
\(x_{\theta,I_{\theta,j}}=\mu_\theta\alpha_{\theta,j}\),
aggregating any duplicate bundles.
Section 5 proves that this allocation has the required type masses, respects capacities, is fair, and attains \(W_{\mathrm{all}}\). There are at most \(\tau(m+1)\) nonzero bundle masses.
All oracle transformations, feasibility tests, optimizations, and decompositions operate in polynomial dimension with polynomial encoding bounds. The returned rational points and coefficients have polynomial encoding length; division and multiplication by the positive input masses preserve that bound. No expansion into a finite population or into a common-denominator number of goods is required.
Thus the full computation, including explicit allocation output, is polynomial in \(m,\tau,L\) under the stated value-oracle model.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is established. The argument addresses the exact allocation problem, including unrestricted maximum welfare, rational capacities, value-oracle access, and explicit output. I found no major or minor mathematical issues.
For every bundle \(B\), the matroid rank definition supplies an independent subset \(I\subseteq B\) with \(|I|=r_\theta(B)\). Replacing \(B\) by \(I\) preserves allocated mass, welfare, and the applicable rank threshold while weakly decreasing each good’s consumption.
This works for both benchmark distributions and allocations because unused supply is allowed. Conversely, independent bundles are already permitted bundles. Thus the restriction preserves feasibility and optimum welfare in both directions.
The independence test \(r_\theta(I)=|I|\) is valid under the stated matroid-rank promise.
After scanning a prefix \(A_j\), the greedy set is maximal independent in that prefix. A previously rejected element cannot become addable after further insertions: otherwise heredity would imply it was addable when rejected. Matroid augmentation then gives the selected cardinality \(r_\theta(A_j)\).
Consequently, the first \(k\) accepted elements satisfy
\[
|I_k\cap A_j|=\min\{k,r_\theta(A_j)\}.
\]
Every independent cardinality-\(k\) competitor satisfies the corresponding upper bound.
The telescoping identity in the write-up is correct. All coefficient differences are nonnegative, and the possibly negative term \(k\,a_{g_m}\) is identical for both competitors. Therefore the fixed-cardinality optimization claim holds for arbitrary signed rational coefficients.
Selecting the best candidate among cardinalities from \(q\) through \(r_\theta(G)\) correctly optimizes over the entire eligible family. The scan uses at most \(m\) independence tests, and its remaining arithmetic has polynomial bit complexity.
The cited GLS results support the required operations: strong optimization and strong separation are polynomially interconvertible for well-described rational polyhedra; constructive decomposition produces affinely independent vertices and positive rational coefficients; and bounded vertex encoding yields polynomial facet complexity. These are exact rational results, rather than approximate optimization results. [GLS, Chapter 6](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf)
Here, each generating incidence vector has encoding length \(O(m)\), so the stated bound \(3m^2v\) is polynomial. Section 2 supplies the required exact optimization oracle and polynomial-size outputs. The decomposition is applied only to nonempty bounded polytopes and rational points belonging to them.
Lower-dimensional feasible sets do not invalidate these applications. The publisher’s description explicitly confirms that the rational-polyhedral framework removes full-dimensionality assumptions and permits exact optimal solutions. [Rational Polyhedra](https://link.springer.com/chapter/10.1007/978-3-642-78240-4_7)
A benchmark distribution over eligible independent bundles has a marginal vector in \(P_{\theta,q}\), and its capacity constraints are exactly \(y_g\le\rho_g\). Conversely, a convex representation of such a marginal vector provides the required distribution.
Crucially, the benchmark constraints use \(\rho_g\) directly, without scaling by \(\mu_\theta\). This matches the task’s unit-mass, single-type benchmark.
Combining the polytope’s separation oracle with the explicit capacity inequalities gives a valid separation oracle for the intersection. Adding these rational inequalities preserves a polynomial description bound, so exact feasibility testing is justified.
Testing all \(m+1\) candidate thresholds per supported type is polynomial. Thresholds exceeding the matroid rank are correctly rejected, and \(q=0\) is feasible through the empty bundle.
Positive supported masses justify division by \(\mu_\theta\). For an eligible allocation, the normalized bundle masses form a convex representation of \(z_\theta/\mu_\theta\). Its independent-bundle welfare equals \(\sum_{\theta,g}z_{\theta,g}\).
Conversely, each convex representation determines bundle masses \(\mu_\theta p_{\theta,I}\) with the prescribed total type mass, consumption marginals, and rank threshold. Thus the formulation neither introduces spurious allocations nor loses attainable welfare values.
The transformed separating inequality
\[
a^\top z_\theta\le\mu_\theta b
\]
is valid and separates the candidate whenever the original inequality separates \(z_\theta/\mu_\theta\). Rational scaling and embedding into dimension \(m\tau\) preserve polynomial encoding bounds. Membership also implies \(0\le z_{\theta,g}\le\mu_\theta\), establishing boundedness.
The benchmark marginal vectors exist because their thresholds were certified feasible. The proposed weighted combination satisfies
\[
\sum_\theta\mu_\theta y^\theta_g
\le\rho_g\sum_\theta\mu_\theta
=\rho_g.
\]
Hence fair feasibility is established.
The proof correctly treats attainment of unrestricted maximum welfare as a separate requirement. The two formulations compute precisely the unrestricted optimum and the fair optimum. Strict inequality certifies that no requested allocation exists; equality makes an optimal fair allocation a valid answer. Exact rational optimization justifies the exact comparison.
Constructive decomposition gives at most \(m+1\) vertices per type. Every vertex of a convex hull of a finite generating family belongs to that family, so every returned incidence vector represents an eligible independent bundle.
Multiplying the decomposition coefficients by the type masses yields the required allocation. Aggregating duplicates preserves all constraints and welfare. The support bound \(\tau(m+1)\) follows directly.
The cited algorithms return rational data of polynomial encoding length. Division and multiplication by positive input rationals preserve polynomial bit length. There are polynomially many threshold tests and oracle operations, all in polynomial dimension. No dependence on a numerical common denominator or an expanded population appears.
The proof also handles loops, zero supplies, rank-zero matroids, singleton polytopes, and supplies exceeding one without requiring additional assumptions. No repair or additional mathematical clarification is needed. It establishes a polynomial-time solution to the requested search-or-certify problem; it does not claim that a fair allocation attaining unrestricted optimum always exists.
⟨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.