Answer: Polynomial-time solvable, with polynomially many rank-oracle queries.
Theorem 4.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateUnder matroid-rank valuations, for any concave function $f$, Algorithm \ref{alg:therule} computes an \ruletie{} allocation in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T=\{t_1,\ldots,t_\tau\}\), masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), entitlement weights \(w_t>0\), a finite set of indivisible good classes \(G\) with per-capita supplies \(q_g\), and a matroid \(M_t=(G,\mathcal{I}_t)\) for each type, compute masses \(x_{t,B}\ge 0\) of type \(t\) receiving each integral independent bundle \(B\in\mathcal{I}_t\), subject to \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}\le q_g\), maximizing \(\sum_{t,B}x_{t,B}w_tf(r_t(B))\). When \(f(0)=-\infty\), first maximize positive mass, then apply a fixed type-order refinement; otherwise apply the refinement after weighted-welfare maximization.
A society is given by its support: an ordered list \(T=(t_1,\ldots,t_\tau)\) of types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\) good classes \(G\), nonnegative binary-rational per-capita supplies \(q_g\), and positive binary-rational entitlement weights \(w_t\). Each type has a matroid \(M_t=(G,\mathcal I_t)\), accessible through a unit-cost rank oracle \(r_t\); a bundle contains at most one good of each class.
The common welfare function is a strictly increasing, discretely concave table \(f(0),\ldots,f(m)\). Its finite entries are binary rationals of either sign; only \(f(0)\) may equal \(-\infty\). Let \(L\) be the total bit length of the numerical input.
An allocation assigns nonnegative masses \(x_{t,B}\) to independent bundles \(B\in\mathcal I_t\), subject to \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}\le q_g\). Supplies may remain unused. Compute an exact allocation represented by its nonzero bundle masses.
Write \(u_t=\sum_Bx_{t,B}r_t(B)\) and \(p_t=\sum_{B\ne\emptyset}x_{t,B}\). If \(f(0)\) is finite, maximize \(W=\sum_{t,B}x_{t,B}w_tf(r_t(B))\), then lexicographically maximize \((u_{t_1},\ldots,u_{t_\tau})\).
If \(f(0)=-\infty\), successively maximize \(\sum_tp_t\), lexicographically maximize \((p_{t_1},\ldots,p_{t_\tau})\), maximize \(W_+=\sum_{t,B\ne\emptyset}x_{t,B}w_tf(r_t(B))\), and lexicographically maximize \((u_{t_1},\ldots,u_{t_\tau})\). Every stage preserves all preceding optima; remaining ties are arbitrary.
Is computing this refined mass allocation solvable in polynomial time in \(m,\tau,L\), with polynomially many rank-oracle queries, or is it NP-hard?
For finitely many individual agents, the corresponding concave weighted-welfare rule, including positive-agent priority, utility tie-breaking, and nonredundancy, is computable in polynomial time with valuation-oracle access ([discrete result](https://arxiv.org/html/2303.14454v2)).
No result settling this exact mass problem was located in the literature search.
The refined mass allocation is computable exactly in polynomial time in \(m,\tau,L\), with polynomially many rank-oracle queries. The algorithm outputs at most \(\tau(2m+2)\) nonzero bundle masses.
The proof uses a polynomial-dimensional polytope that records both good-use marginals and bundle-size distributions. In fact, concavity and monotonicity of the finite welfare entries are unnecessary for this algorithm.
If \(m=0\), the unique allocation gives every type the empty bundle. Hence assume \(m\geq 1\).
For \(B\subseteq G\), let \(\chi_B\in\{0,1\}^m\) be its incidence vector. For \(k\in\{0,\ldots,m\}\), let \(e_k\in\{0,1\}^{m+1}\) be the corresponding unit vector. Define
\(P_t=\operatorname{conv}\{(\chi_B,e_{|B|}):B\in\mathcal I_t\}\subseteq\mathbb R^{2m+1}.\)
Write a point of \(P_t\) as \((y_t,z_t)\). Its intended interpretation is:
This interpretation is exact: membership in \(P_t\) means precisely that these quantities arise from a probability distribution over independent bundles.
Every generating point \((\chi_B,e_{|B|})\) is a vertex. Indeed, if it is a convex combination of generating points, each coordinate of \(\chi_B\), being either zero or one, forces every bundle with positive coefficient to have exactly the same incidence vector. Thus all contributing bundles equal \(B\). Conversely, every vertex of a finite convex hull belongs to its generating set.
We first construct an exact linear-optimization oracle for \(P_t\).
Given arbitrary rational coefficients \(a_g\) and \(b_k\), optimization reduces to finding an independent bundle maximizing
\(\displaystyle \sum_{g\in B}a_g+b_{|B|}.\)
Order the goods as \(g_1,\ldots,g_m\), with \(a_{g_1}\geq\cdots\geq a_{g_m}\). Scan this order, accepting a good whenever adding it preserves independence. Independence is tested by
\(r_t(I\cup\{g\})=|I|+1.\)
Let \(R=r_t(G)\), and let \(I_k\) consist of the first \(k\) accepted goods, for \(0\leq k\leq R\), with \(I_0=\emptyset\).
Claim. For each such \(k\), \(I_k\) maximizes \(\sum_{g\in B}a_g\) among independent bundles of size \(k\).
Proof. Put \(H_j=\{g_1,\ldots,g_j\}\). Greedy stopped after \(k\) acceptances satisfies
\(|I_k\cap H_j|=\min\{k,r_t(H_j)\}.\)
To justify this, if greedy has accepted \(k\) goods within \(H_j\), the equality follows immediately. Otherwise, its accepted set is maximal independent in \(H_j\): a previously rejected good cannot augment the final accepted set, since independence of that augmentation would, by heredity, imply independence when the good was processed. A maximal independent set in a matroid has cardinality equal to the rank, by the augmentation axiom.
Every independent bundle \(B\) of size \(k\) satisfies
\(|B\cap H_j|\leq\min\{k,r_t(H_j)\}.\)
The identity
\(\displaystyle \sum_{g\in B}a_g=a_{g_m}k+\sum_{j=1}^{m-1}(a_{g_j}-a_{g_{j+1}})|B\cap H_j|\)
therefore proves the claim: all coefficients in the latter sum are nonnegative, and \(I_k\) attains every prefix bound. This argument permits negative weights. \(\square\)
Consequently, evaluate
\(\displaystyle b_k+\sum_{g\in I_k}a_g\)
for every \(0\leq k\leq R\), and return a maximizing \(I_k\). No independent bundle has size greater than \(R\), so this solves the optimization problem exactly.
One greedy scan supplies all these candidates. It uses at most \(m\) independence tests, plus a rank query for \(R\). Sorting, evaluation, and all rational arithmetic take polynomial time in \(m\) and the coefficient encoding length. The returned optimizer is a vertex of \(P_t\).
We use the following standard results for well-described rational polytopes:
The running times and oracle-call counts are polynomial in the dimension, a bound on inequality encoding lengths, and the relevant input encoding lengths. These results accommodate lower-dimensional polytopes. See [Grötschel–Lovász–Schrijver, Chapter 6, including Theorem 6.5.11](https://link.springer.com/book/10.1007/978-3-642-78240-4).
Here the required encoding bound is polynomial and known independently of the matroids. To verify this, consider any convex hull of zero-one vectors in \(\mathbb R^d\). If its affine dimension is \(h\), select \(h\) coordinate positions whose projection is injective on its affine hull. Its projection is a full-dimensional zero-one polytope in \(\mathbb R^h\). Each facet hyperplane can be determined from \(h\) affinely independent zero-one vertices; determinant formulas give integer coefficients bounded in magnitude by \(h!\). The affine hull in the original coordinates likewise has equations obtained by elimination on zero-one vertices, with polynomial encoding length. Lifting the projected facet inequalities supplies a description of polynomial encoding length.
Thus each \(P_t\) has a known inequality-encoding bound polynomial in \(m\). Together with Section 2, the oracle equivalence supplies a polynomial-time strong separation oracle for \(P_t\), using polynomially many rank queries. Constructive decomposition is also available for \(P_t\).
Define the global feasible polytope
\(\displaystyle Q=\left\{((y_t,z_t))_{t\in T}:(y_t,z_t)\in P_t\text{ for every }t,\quad \sum_t\mu_t y_{t,g}\leq q_g\text{ for every }g\right\}.\)
Its ambient dimension is \(d=\tau(2m+1)\). It is bounded because every coordinate lies in \([0,1]\), and it is nonempty because every type can receive the empty bundle.
There is an exact correspondence between feasible allocations and points of \(Q\).
Given an allocation, define
\(\displaystyle y_{t,g}=\frac{1}{\mu_t}\sum_{B:g\in B}x_{t,B},\qquad z_{t,k}=\frac{1}{\mu_t}\sum_{B:|B|=k}x_{t,B}.\)
The positivity of \(\mu_t\) makes these expressions well-defined. Since \(\sum_Bx_{t,B}=\mu_t\), they form a convex combination of the generating points of \(P_t\). The supply constraints give membership in \(Q\).
Conversely, for a point of \(Q\), choose a convex decomposition
\(\displaystyle (y_t,z_t)=\sum_j\lambda_{t,j}(\chi_{B_{t,j}},e_{|B_{t,j}|}),\qquad \lambda_{t,j}\geq0,\quad \sum_j\lambda_{t,j}=1.\)
Set \(x_{t,B_{t,j}}=\mu_t\lambda_{t,j}\), combining repetitions if necessary. These masses satisfy the type totals, and their usage of class \(g\) is exactly \(\sum_t\mu_t y_{t,g}\). Every assigned bundle is independent.
A separation oracle for \(Q\) first checks its explicit supply inequalities and then calls the separation oracle for each \(P_t\). A separating inequality for a type block is also valid for \(Q\).
The inequality encoding lengths for \(Q\) are polynomial in \(m,\tau,L\): the type-block bounds were established above, and the supply coefficients are input rationals. Hence exact rational optimization over \(Q\) is polynomial-time.
Because every allowed bundle is independent, \(r_t(B)=|B|\). The relevant statistics are therefore linear functions on \(Q\):
\(\displaystyle u_t=\mu_t\sum_{k=0}^{m}kz_{t,k},\qquad p_t=\mu_t\sum_{k=1}^{m}z_{t,k}.\)
When \(f(0)\) is finite,
\(\displaystyle W=\sum_t\mu_tw_t\sum_{k=0}^{m}f(k)z_{t,k}.\)
When \(f(0)=-\infty\), the finite welfare stage is instead
\(\displaystyle W_+=\sum_t\mu_tw_t\sum_{k=1}^{m}f(k)z_{t,k}.\)
Thus no infinite coefficient enters a linear program.
For finite \(f(0)\), successively maximize the ordered list
\(W,\ u_{t_1},\ldots,u_{t_\tau}.\)
For \(f(0)=-\infty\), successively maximize
\(\displaystyle \sum_tp_t,\ p_{t_1},\ldots,p_{t_\tau},\ W_+,\ u_{t_1},\ldots,u_{t_\tau}.\)
After each maximization, add an equality fixing that objective to its exact optimum before proceeding. This preserves all preceding optima and implements precisely the prescribed lexicographic priorities. There are respectively \(\tau+1\) and \(2\tau+2\) stages.
We must also bound the encoding lengths of these successive optimum values. Every stage restricts the preceding feasible polytope to an optimal face. Consequently, each resulting polytope is a face of the original \(Q\), and its vertices are vertices of \(Q\).
By Cramer’s rule, vertices of a rational polytope in polynomial dimension, with polynomial inequality encoding lengths, have polynomial encoding length. Each stage objective also has polynomial encoding length. Its optimum is attained at a vertex of the current face, hence at a vertex of \(Q\), so every optimum value has a uniform polynomial encoding bound. This prevents cumulative growth of the equalities beyond polynomial size.
Separation for each successive face consists of checking the added equalities and then separating over \(Q\). The exact optimization theorem therefore applies at every stage, including when the optimal face has lower dimension.
Let \(((y_t^*,z_t^*))_t\) be an exact optimal point after the final stage.
For each type, apply constructive Carathéodory decomposition to \((y_t^*,z_t^*)\in P_t\). Since \(P_t\subseteq\mathbb R^{2m+1}\), this returns at most \(2m+2\) vertices:
\(\displaystyle (y_t^*,z_t^*)=\sum_{j=1}^{s_t}\lambda_{t,j}(\chi_{B_{t,j}},e_{|B_{t,j}|}),\qquad s_t\leq2m+2.\)
Section 1 ensures that these vertices identify independent bundles. Output the positive masses
\(x_{t,B_{t,j}}=\mu_t\lambda_{t,j},\)
combining any repetitions.
This preserves the optimized marginals and size distributions exactly. Section 4 then gives feasibility, while Section 5 shows that every objective in the refinement sequence retains its optimum.
All decomposition coefficients have polynomial encoding length, and decomposition uses polynomially many calls to the separation oracles already constructed. The total output contains at most \(\tau(2m+2)\) nonzero masses, each attached to a bundle representable by \(m\) bits.
This completes the polynomial-time algorithm and the proof of exact recovery.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time exact computation of the requested refined mass allocation, with polynomially many rank-oracle queries and polynomial output size. I found no major or minor mathematical issue requiring repair.
The coordinates of \(P_t\) simultaneously record good-use marginals and bundle-size probabilities. Because its generating points correspond precisely to independent bundles, membership is equivalent to the existence of a distribution over those bundles.
The vertex argument is correct: a convex combination equal to a generating point cannot mix different incidence vectors, since every incidence coordinate is either zero or one. Conversely, every vertex of a finite convex hull belongs to its generating set. Thus vertices returned during decomposition identify actual independent bundles.
The case \(m=0\) is correctly handled. Only the empty bundle exists, so the allocation is unique under either refinement rule.
The rank test correctly determines whether adding a good preserves independence, because the current accepted set is independent.
For every prefix \(H_j\), the claimed equality
\[
|I_k\cap H_j|=\min\{k,r_t(H_j)\}
\]
is justified. If the scan reaches \(k\) acceptances within the prefix, both sides equal \(k\). Otherwise, its accepted set is maximal independent in the prefix: heredity rules out a previously rejected good becoming addable later. Matroid augmentation then makes its cardinality equal to the prefix rank.
The displayed summation identity is correct. For a bundle of fixed size \(k\), the term involving the smallest coefficient is constant, while every successive coefficient difference is nonnegative. Attaining all prefix bounds therefore establishes optimality for that cardinality, even when the coefficients themselves are negative.
Comparing the candidates for all \(0\leq k\leq R\) consequently optimizes the full linear objective over \(P_t\). The empty candidate covers rank-zero matroids. One scan and the stated rank query use at most \(m+1\) rank-oracle calls; sorting and exact rational evaluations have polynomial bit complexity.
The cited strong optimization–separation equivalence is valid for well-described rational polyhedra. Exact optimization and vertex recovery also apply to bounded polytopes without a full-dimensionality assumption. The cited constructive Carathéodory theorem provides an exact rational decomposition into affinely independent vertices using a strong optimization oracle. These are supported by GLS Theorem 6.4.9, Corollary 6.5.9, and Theorem 6.5.11, respectively. [GLS, Chapter 6](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf)
The required description-complexity argument is sound. An injective coordinate projection of the affine hull produces a full-dimensional zero-one polytope in its affine dimension. Facet equations determined by affinely independent vertices admit the stated determinant bounds. The affine-hull equations likewise have polynomial encoding length. Lifting the projected inequalities therefore supplies a polynomial bound on individual inequality encoding lengths.
This argument establishes a known bound without requiring enumeration of the vertices, facets, or independent bundles. The potentially exponential number of inequalities does not invalidate the oracle algorithms.
Each \(P_t\) is nonempty, bounded, rational, and has the established encoding bound. Section 2 supplies its exact optimization oracle. The hypotheses needed for separation and constructive decomposition are therefore satisfied.
Normalization by \(\mu_t\) is legitimate because every support mass is positive. The type-total constraint makes the resulting coordinates a convex combination of generating points of \(P_t\).
Conversely, multiplying a per-type decomposition by \(\mu_t\) restores exactly that type’s required mass. The good-use marginals recover the supply usage exactly, so every supply inequality is preserved. Combining repeated bundles does not change these quantities.
This is an exact correspondence in the sense required for optimization and recovery; it need not be a one-to-one correspondence between allocations and marginal points.
The separation procedure for \(Q\) is valid. A violated supply inequality separates directly. A violated type-block inequality remains valid when embedded in the global coordinate space. If neither occurs, the point belongs to \(Q\).
The global dimension and inequality encoding lengths are polynomial in the specified parameters. Boundedness and nonemptiness are correctly established, including when supplies vanish or some matroids have only the empty independent set.
Since all allowed bundles are independent, \(r_t(B)=|B|\). The formulas for \(u_t\), \(p_t\), finite welfare, and positive-bundle welfare consequently match the task’s definitions.
The finite-welfare sequence has precisely the required order. The sequence for \(f(0)=-\infty\) likewise correctly prioritizes total positive mass, ordered per-type positive masses, finite positive-bundle welfare, and ordered utilities. Excluding the empty-bundle entry from \(W_+\) avoids undefined arithmetic with infinity. Negative finite welfare entries present no difficulty.
Fixing each objective to its exact optimum preserves all previous optima. The stated stage counts, \(\tau+1\) and \(2\tau+2\), are correct.
The bit-complexity justification also checks out. Each restriction is an optimal face of the preceding polytope and hence a face of \(Q\). Its vertices remain vertices of \(Q\). The rational vertex encoding bound therefore supplies a uniform polynomial bound on every successive optimum value. Adding polynomially many exact equalities does not cause uncontrolled encoding growth.
Separation over the successive faces is correctly obtained by checking the equalities and then invoking separation over \(Q\). Lower-dimensional faces remain within the cited algorithms’ scope.
Constructive decomposition applies to each rational optimal block. In ambient dimension \(2m+1\), the bound of \(2m+2\) vertices per type is valid.
The recovered vertices identify independent bundles, and multiplication by the support masses yields exact rational allocation masses. Their encoding lengths are polynomial. Dropping zero coefficients and combining repetitions preserves feasibility and every optimized objective.
The total bound of \(\tau(2m+2)\) nonzero bundle masses follows. Each bundle has a representation using \(m\) incidence bits. The polynomially many stages, type blocks, oracle reductions, and decompositions together retain polynomial running time and polynomial rank-query complexity.
The claim that concavity and monotonicity are unnecessary for this algorithm is also justified: the construction only uses finite size-dependent welfare coefficients and the explicitly prescribed refinement objectives.
Actionable feedback: No mathematical repair is needed.
⟨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.