Answer: \(\text{Polynomial-time solvable}\)
MRFpolytime — class: algorithmic
Given finite agent types \(T\) with rational masses \(\mu_t\), succinct reported matroid rank functions \(r_t\) on \(m\) item categories, and rational per-capita supplies \(b_j\), compute masses \(x_{t,S}\) assigned to integral independent bundles \(S\subseteq M\), satisfying \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S\ni j}x_{t,S}\le b_j\), whose induced utility distribution Lorenz-dominates every feasible assignment; a priority refinement may select among equivalent allocations.
Given a finite item set \(M\), types \(T\), rational masses \(\mu_t\), rational supplies \(b_j\), and succinct matroid rank functions \(r_t\), an allocation is nonnegative rational masses \(x_{t,S}\) for independent \(S\subseteq M\), with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S\ni j}x_{t,S}\le b_j\).
Its utility distribution assigns mass \(x_{t,S}\) to utility \(r_t(S)=|S|\). It Lorenz-dominates another allocation if, for every \(q\in[0,\sum_t\mu_t]\), the total utility of its least-well-off mass \(q\) is at least that of the other allocation.
Is computing a feasible allocation whose utility distribution Lorenz-dominates every feasible allocation solvable in polynomial time, or is it NP-hard?
For finitely many individual agents with succinct matroid-rank valuations and indivisible items, a priority-refined non-redundant Lorenz-dominating allocation is computable in polynomial time.
No result for the stated mass-distribution formulation is assumed here.
The problem is polynomial-time solvable, under the standard interpretation that the succinct matroid representations permit polynomial-time rank evaluation. More generally, the algorithm uses polynomially many rank-oracle calls and polynomial additional time.
It outputs an allocation with at most \(|T|+|M|\) positive masses, each of polynomial encoding length. The finite-agent theorem supplied in the question is used to prove existence; the algorithm does not expand rational masses into individual agents.
Write \(n=|M|\), \(H=\sum_t\mu_t\), and let \(\mathcal I_t\) denote the independent sets of type \(t\). Masses and supplies are assumed nonnegative. If \(H=0\) or \(n=0\), the allocation assigning everyone the empty set solves the problem. Henceforth assume both are positive.
For an allocation \(x\), define its mass at utility \(h\) by
\(p_h(x)=\sum_t\sum_{S\in\mathcal I_t:\,|S|=h}x_{t,S}\), for \(h\in\{0,\ldots,n\}\).
For each integer \(k\in\{0,\ldots,n\}\), define the deficit
\(D_k(x)=\sum_{h=0}^n (k-h)_+p_h(x)\),
where \((a)_+=\max\{a,0\}\). In particular, \(D_0(x)=0\).
Let \(L_x(q)\) be the total utility of the least-well-off mass \(q\). Equivalently,
\(L_x(q)=\min\left\{\sum_{h=0}^n hz_h:\ 0\le z_h\le p_h(x),\ \sum_{h=0}^n z_h=q\right\}\).
We will use the identities
\(L_x(q)=\max_{k\in\{0,\ldots,n\}}\bigl(kq-D_k(x)\bigr)\),
and
\(D_k(x)=\max_{0\le q\le H}\bigl(kq-L_x(q)\bigr)\).
Proof. For any admissible vector \(z\) and any \(k\),
\(kq-\sum_h hz_h=\sum_h(k-h)z_h\le\sum_h(k-h)_+p_h(x)=D_k(x)\).
Consequently, \(L_x(q)\ge kq-D_k(x)\).
For a fixed \(q\), select all mass strictly below a utility threshold \(k\), an appropriate amount at utility \(k\), and none above it. An integer threshold exists because utilities are integers. For this selection, the preceding inequality is equality. This proves the first identity.
Conversely, the inequality already proved gives \(kq-L_x(q)\le D_k(x)\). Taking \(q=\sum_{h<k}p_h(x)\) gives equality and proves the second identity.
It follows that
\(L_x(q)\ge L_y(q)\ \text{for every }q\in[0,H]\quad\Longleftrightarrow\quad D_k(x)\le D_k(y)\ \text{for every }k\in\{1,\ldots,n\}\).
Thus our task is to find a feasible allocation simultaneously minimizing all the deficits.
For this existence argument, temporarily allow real allocation masses. The feasible region is a nonempty, bounded rational polytope: it has finitely many coordinates, the empty-set allocation is feasible, and every coordinate satisfies \(0\le x_{t,S}\le\mu_t\).
For each \(k\in\{1,\ldots,n\}\), choose a rational minimizer \(x^{(k)}\) of \(D_k\). Such a minimizer exists because a linear objective over a nonempty bounded rational polytope has a rational optimal vertex.
Choose a positive integer \(d\) clearing the denominators of:
Construct the following finite-agent instance.
There are \(d\mu_t\) individual agents of type \(t\). For each original item \(j\), create \(db_j\) distinct copies. Let \(M'\) be the resulting item set, and let \(\pi\) map each copy to its original item.
For a type-\(t\) agent, define independence on \(M'\) by
\(A\in\mathcal I'_t\quad\Longleftrightarrow\quad |A|=|\pi(A)|\ \text{and}\ \pi(A)\in\mathcal I_t\).
This is a matroid. Heredity follows immediately. For augmentation, if \(A,B\in\mathcal I'_t\) and \(|A|<|B|\), augmentation in the original matroid supplies an item \(j\in\pi(B)\setminus\pi(A)\) such that \(\pi(A)\cup\{j\}\) is independent. Adding the copy of \(j\) contained in \(B\) augments \(A\).
Its rank function is
\(r'_t(A)=r_t(\pi(A))\).
Indeed, an independent subset of \(\pi(A)\) can be lifted by choosing one available copy of each item, and every independent subset of \(A\) projects injectively to an independent set. Thus rank evaluation is available in polynomial time in the expanded instance size.
Each allocation \(x^{(k)}\) can be realized in this finite instance: assign \(dx^{(k)}_{t,S}\) type-\(t\) agents the projected bundle \(S\), using a distinct copy for each occurrence of an item. There are enough copies because
\(\sum_{t,S\ni j}dx^{(k)}_{t,S}\le db_j\).
Apply the finite-agent theorem given in the question. It yields a non-redundant allocation \(A^\star\) whose utility vector Lorenz-dominates every feasible finite-agent allocation, including each realization just constructed.
Project its bundles back to \(M\), and give each individual mass \(1/d\). Denote the resulting mass allocation by \(x^\star\). Non-redundancy ensures that each projected bundle is independent and has the same cardinality as its copied bundle. The agent counts give the required type masses, and the copy counts give the supply inequalities. Hence \(x^\star\) is feasible and rational.
To check the Lorenz comparison after rescaling, let \(L_{A^\star}\) denote the Lorenz curve of the finite-agent utility vector, interpolated linearly between integer arguments. Then
\(L_{x^\star}(q)=d^{-1}L_{A^\star}(dq)\).
The corresponding identity holds for every realized \(x^{(k)}\). Finite-agent Lorenz inequalities at integer arguments imply inequalities throughout each unit interval by linear interpolation. Therefore \(x^\star\) Lorenz-dominates every \(x^{(k)}\).
By Section 1,
\(D_k(x^\star)\le D_k(x^{(k)})=\min_xD_k(x)\).
Since \(x^\star\) is itself feasible, equality holds for every \(k\). A rational simultaneous deficit minimizer therefore exists.
The integer \(d\) and the copied instance can be very large. They serve only in this existence proof.
Define
\(C(x)=\sum_{k=1}^nD_k(x)\).
Section 2 shows that the individual minimum values can all be attained together. Consequently, every minimizer of \(C\) minimizes every \(D_k\): each deficit is at least its individual minimum, and equality in their summed lower bound forces equality term by term.
For a bundle of cardinality \(h\), its coefficient in \(C\) is
\(c_h=\sum_{k=1}^n(k-h)_+=\sum_{\ell=1}^{n-h}\ell=\frac{(n-h)(n-h+1)}2\).
It therefore suffices to solve the linear program
\(\min\ \sum_t\sum_{S\in\mathcal I_t}c_{|S|}x_{t,S}\),
subject to
\(\sum_{S\in\mathcal I_t}x_{t,S}=\mu_t\quad\text{for every }t\),
\(\sum_t\sum_{S\in\mathcal I_t:\,j\in S}x_{t,S}\le b_j\quad\text{for every }j\),
and \(x_{t,S}\ge0\).
This program has potentially exponentially many variables. Its dual admits polynomial-time separation.
Introduce unrestricted dual variables \(\alpha_t\) for the type equalities and nonnegative variables \(\beta_j\) for the supply constraints. The dual is
\(\max\ \sum_t\mu_t\alpha_t-\sum_jb_j\beta_j\),
subject to \(\beta_j\ge0\) and
\(\alpha_t-\sum_{j\in S}\beta_j\le c_{|S|}\quad\text{for every }t,\ S\in\mathcal I_t\).
Given a rational candidate \((\alpha,\beta)\), first check nonnegativity of \(\beta\). For each type, the remaining separation problem is to compute
\(\min_{S\in\mathcal I_t}\left(c_{|S|}+\sum_{j\in S}\beta_j\right)\).
For each attainable cardinality \(h\), a minimum-weight independent set of size \(h\) is obtainable by matroid greedy: process items in nondecreasing order of \(\beta_j\), accepting an item whenever independence is preserved.
For completeness, every prefix of the accepted sequence has minimum weight among independent sets of its cardinality. To see this, let \(g_\ell\) be the position in the sorted item order of the \(\ell\)-th accepted item. For any independent set of size \(h\), let its sorted positions be \(a_1<\cdots<a_h\). The prefix ending at \(a_\ell\) has rank at least \(\ell\). Greedy selects a maximal independent set within every processed prefix, and hence selects exactly that prefix’s rank. Therefore \(g_\ell\le a_\ell\), implying \(\beta_{g_\ell}\le\beta_{a_\ell}\). Summing proves the assertion.
Independence can be tested by checking \(r_t(S)=|S|\). Thus one greedy run computes minimum weights \(w_{t,h}\) for every \(h\in\{0,\ldots,r_t(M)\}\), using polynomially many rank evaluations.
The required minimum is exactly
\(\min_{0\le h\le r_t(M)}(c_h+w_{t,h})\).
If it is smaller than \(\alpha_t\), the corresponding greedy prefix supplies a violated dual constraint. Otherwise all constraints for that type hold. This is an exact polynomial-time separation oracle.
We use the standard rational linear-programming theorem with primal recovery: a feasible, bounded-value LP with polynomially many rows, uniformly bounded coefficient encoding lengths, and polynomial-time separation for its dual can be optimized in polynomial time, returning an optimal primal solution supported on polynomially many columns. The constructive ellipsoid method collects sufficient dual constraints and solves the corresponding restricted primal LP; see the [primal-recovery explanation in Section 8.3.2, footnote 9](https://www.nowpublishers.com/article/DownloadSummary/TCS-085).
All hypotheses hold here:
After primal recovery, take an optimal basic feasible solution of the polynomial-size restricted primal. Adding supply slack variables gives \(|T|+n\) equality rows, so this solution has at most \(|T|+n\) positive allocation coordinates. Its rational coordinates have polynomial encoding length by the usual determinant bounds for basic solutions with rational input data.
Thus the algorithm outputs a polynomial-size list of triples \((t,S,x_{t,S})\).
By Section 3, the returned allocation minimizes every deficit. By Section 1, its utility distribution Lorenz-dominates that of every feasible allocation. This completes the proof.
⟨structured verdict parsed — rendered above⟩
The proof is correct under its stated assumption that the matroid representations support polynomial-time rank evaluation. It establishes both existence of a universally Lorenz-dominating allocation and a polynomial-time algorithm producing one. I found no major or minor mathematical gaps.
Nonnegative masses and supplies are the natural domain of the stated allocation problem, and the prover explicitly adopts it. The empty-set allocation establishes feasibility. The cases \(H=0\) and \(n=0\) are correctly handled.
The complexity claim is explicitly conditional on efficient rank evaluation. The proof also establishes a polynomial rank-oracle bound; it does not claim polynomial running time for arbitrary encodings in which evaluating the represented rank function might itself be intractable.
The expression defining \(L_x(q)\) correctly permits taking a fraction of the mass at a utility level.
The inequality relating \(L_x(q)\) and \(kq-D_k(x)\) is valid: positive coefficients are bounded using \(z_h\le p_h(x)\), and negative coefficients using \(z_h\ge0\).
The threshold construction attains equality. Integer thresholds suffice because all utility levels are integers. It also covers the endpoints \(q=0\) and \(q=H\), with thresholds \(0\) and \(n\), respectively.
For the reverse identity, the stated choice \(q=\sum_{h<k}p_h(x)\) attains equality. Consequently, both directions of the claimed equivalence between Lorenz dominance and coordinatewise deficit comparison follow. No equal-total-utility assumption is needed.
The real feasible region is a finite-dimensional, nonempty, bounded rational polytope. Each deficit therefore has a rational optimal vertex. A common denominator for the finitely many selected optimizers and input quantities exists.
The copied-item independence system is a matroid. The augmentation argument correctly uses injectivity of projection on each independent set. The asserted rank formula follows from the two lifting and projection observations supplied in the proof.
Each selected optimizer can be realized in the copied instance: integrality gives integer agent counts, the type equalities account for every agent, and the supply inequalities provide enough distinct copies. The different optimizers are realized as separate comparison allocations; they need not coexist.
The finite-agent theorem applies to the constructed matroid-rank valuations. Its non-redundancy guarantee ensures that projecting the resulting bundles preserves independence and utility.
The rescaling identity for Lorenz curves is correct. Both finite-agent curves are linear on every common interval between consecutive integer arguments, so dominance at integers extends throughout those intervals.
Finally, comparison with the optimizer selected for each deficit proves simultaneous optimality. The potentially enormous copied instance is used only for existence, so its size does not compromise the algorithmic claim.
Once simultaneous attainment has been established, every minimizer of the sum must attain every individual minimum. This reasoning is valid and does not implicitly substitute lexicographic optimization for simultaneous minimization.
The coefficient calculation
\(c_h=(n-h)(n-h+1)/2\)
is correct for every attainable cardinality, including \(h=0\) and \(h=n\). The resulting primal LP exactly represents the allocation constraints and objective.
The dual signs are correct: the supply multipliers enter the objective negatively and the bundle constraints as subtracted nonnegative prices. The type multipliers are unrestricted.
The greedy argument establishes minimum weight separately for every attainable cardinality. In particular, the comparison between the positions of greedy selections and those of an arbitrary independent set is justified by the rank of each processed prefix. Ties in weights do not affect the argument.
Independence testing through rank equality is valid. The empty prefix handles cardinality zero, including rank-zero matroids. Checking all greedy prefixes therefore computes the exact separation minimum and returns an explicitly represented violated constraint when one exists.
The invoked rational LP theorem with primal recovery is applicable: the number of rows is polynomial, coefficient and right-hand-side encoding lengths are controlled, the primal is feasible with finite optimum, and separation returns actual bundle constraints.
The cited Section 8.3.2, footnote 9, does describe recovering a polynomial-size restricted primal from constraints generated while solving the dual. The reference supports the recovery step attributed to it. [Roughgarden, *The Barbados Lectures*](https://www.nowpublishers.com/article/DownloadSummary/TCS-085)
Taking an optimal basic feasible solution of that restricted primal gives the claimed support bound. Adding supply slacks yields at most \(|T|+n\) independent equality rows; degeneracy or redundant rows can only decrease the bound.
Polynomial encoding length follows from the stated rational-data determinant bounds. Explicitly listing the supported bundles also requires only polynomial space.
The returned allocation minimizes the summed objective, hence every deficit, hence Lorenz-dominates every feasible allocation. This completes the assigned task under the expressly stated computational interpretation.
No repair is required. The rank-evaluation qualification should remain attached to the polynomial-time conclusion.
⟨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.