Answer: Polynomial-time solvable in \(m,\tau,L,C\); every instance admits a complete, utilitarian-optimal, envy-free plan with subsidies in \(\{0,1\}\).
Theorem 3.20 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor matroidal valuations, there is a polynomial-time algorithm for computing an allocation with a subsidy that is complete, utilitarian optimal, and envy-free, with each agent receiving a subsidy of 0 or 1 and the total subsidy being at most 𝑛−1. We construct the allocation required in the theorem by extending an arbitrary clean Lorenz dominating allocation 𝐴= (𝐴1,𝐴2, . . . ,𝐴𝑛); that is, we initialize 𝐴 to be the one computed in Step 1 of the SE mechanism.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a support \(T\) of \(\tau\) worker types with rational shares \(\mu_t\), matroid rank valuations \(r_t\) on \(E\), and rational per-capita supplies \(\lambda_e\) of each item class, determine whether a polynomial-time algorithm can output a finite-support rational plan \(x_{t,k,p}\). Here \(k\in\mathbb{Z}_{\ge 0}^{E}\) is each worker's integral bundle of interchangeable copies, copies of a class are parallel in every type's matroid, and \(p\in\{0,1\}\) is the subsidy. Require \(\sum_{k,p}x_{t,k,p}=\mu_t\), \(\sum_{t,k,p}x_{t,k,p}k_e=\lambda_e\) for every \(e\), maximum utilitarian welfare among complete plans, and envy-freeness between every pair of positive-mass outcomes: \(r_t(\operatorname{supp}(k))+p\ge r_t(\operatorname{supp}(k'))+p'\). Measure running time in \(m=|E|\), \(\tau\), input bit length, and matroid representation cost.
A society is given by its support: a list \(T\) of \(\tau\ge1\) worker types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not all possible types.
There are \(m=|E|\ge1\) item classes with binary-rational per-capita supplies \(\lambda_e\ge0\). Type \(t\) has a matroid rank valuation \(r_t\) on \(E\), accessible through a rank oracle. Copies of each class are parallel: a bundle \(k\in\mathbb Z_{\ge0}^{E}\) has value \(r_t(S(k))\), where \(S(k)=\{e:k_e>0\}\).
A plan is a finitely supported family \(x_{t,k,p}\in\mathbb Q_{\ge0}\), with \(p\in\{0,1\}\), satisfying \(\sum_{k,p}x_{t,k,p}=\mu_t\) and \(\sum_{t,k,p}x_{t,k,p}k_e=\lambda_e\) for every \(e\). Workers may receive redundant copies; all supplies must be allocated.
Utilities are quasi-linear. Require \(r_t(S(k))+p\ge r_t(S(k'))+p'\) whenever \(x_{t,k,p}>0\) and \(x_{s,k',p'}>0\), including outcomes of the same type.
Require welfare \(\sum_{t,k,p}x_{t,k,p}r_t(S(k))\) to equal its maximum over all complete plans, without imposing envy-freeness in that comparison. The computational problem is to output such a plan, or report that none exists; output masses and bundle coordinates are encoded in binary.
Is this problem polynomial-time solvable in \(m,\tau,L,C\), or is it NP-hard? Here \(L\) is the input bit length and \(C\) the cost of a rank query; hardness is understood for explicit matroid representations with polynomial-time rank evaluation.
For finite societies, a polynomial-time algorithm produces a complete, utilitarian-optimal, envy-free allocation with subsidies in \(\{0,1\}\) and total subsidy at most \(n-1\), where \(n\) is the number of agents. [Goko et al.](https://arxiv.org/pdf/2105.01801v1)
For discrete dichotomous valuations more generally, envy-freeness with subsidies in \(\{0,1\}\) is efficiently achievable in the value-oracle model. [Barman et al.](https://arxiv.org/abs/2201.07419) No result settling this precise continuous problem was located.
The problem is polynomial-time solvable in \(m,\tau,L,C\). Every instance admits a required plan. The algorithm produces at most \(\tau+2m+1\) positive-mass outcomes, with polynomial binary encoding length.
The construction has two parts: compute a compressed optimal allocation that permits disposal, and then allocate surplus copies while preserving envy-freeness.
Let \(\mathcal I_t\) denote the independent sets of type \(t\)’s matroid. Consider the polytope
\(\displaystyle P=\left\{z\ge0: \sum_{I\in\mathcal I_t}z_{t,I}=\mu_t\ \text{for every }t,\quad \sum_{t}\sum_{\substack{I\in\mathcal I_t\\e\in I}}z_{t,I}\le\lambda_e\ \text{for every }e \right\}. \)
A configuration \((t,I)\) gives mass \(z_{t,I}\) of type \(t\) one copy of each class in \(I\). Thus \(P\) describes *clean partial plans*: bundles are independent, and disposal is permitted.
The polytope is nonempty, because every type can receive the empty bundle. It is bounded, because its coordinates are nonnegative and sum to \(1\). Define
\(\displaystyle W=\max_{z\in P}\sum_{t,I}|I|z_{t,I}.\)
Although \(P\) can have exponentially many coordinates, it is a finite rational polytope. Consequently, its optimum is attained by a rational point.
Claim. \(W\) is exactly the maximum welfare over complete plans.
Proof. Given any complete plan, replace each supported bundle \(k\) of type \(t\) by an independent set \(I\subseteq S(k)\) of size \(r_t(S(k))\). This preserves its value and weakly decreases every class’s consumption. Aggregating the resulting configurations gives a point of \(P\) with the same welfare. Therefore every complete plan has welfare at most \(W\).
Conversely, any rational clean partial plan can be completed. Suppose an outcome has positive mass \(q\), and class \(e\) has residual supply \(R_e\). Write
\(\displaystyle R_e=hq+\rho,\qquad h=\left\lfloor R_e/q\right\rfloor,\qquad 0\le\rho<q. \)
Give all \(q\) workers \(h\) additional copies of \(e\), and give a submass \(\rho\) one further copy. This consumes exactly \(R_e\), preserves type masses, and requires at most one split. Repeating for all classes gives a finite rational complete plan. Monotonicity ensures that completion cannot decrease welfare.
Completing a rational optimum of \(P\) therefore gives welfare at least \(W\), and the preceding upper bound forces equality. \(\square\)
In particular, \(W\) also bounds the welfare of every partial plan whose consumption is coordinatewise at most the supplies: extracting independent subsets again produces a point of \(P\).
First compute \(W\). Then solve
\(\displaystyle \min_{z\in P}\sum_{t,I}|I|^2z_{t,I} \quad\text{subject to}\quad \sum_{t,I}|I|z_{t,I}=W. \)
The objective is the average square of each worker’s rank, rather than the square of a type’s average rank.
Both LPs can be solved exactly in polynomial time through separation in their duals.
For welfare maximization, the dual is
\(\displaystyle \min\sum_t\mu_ta_t+\sum_e\lambda_e\gamma_e, \)
with \(\gamma_e\ge0\), \(a_t\) unrestricted, and constraints
\(\displaystyle a_t+\sum_{e\in I}\gamma_e\ge |I| \qquad(t,\ I\in\mathcal I_t). \)
For the square-minimization LP, the dual is
\(\displaystyle \max\sum_t\mu_t\alpha_t+W\beta-\sum_e\lambda_e\gamma_e, \)
with \(\gamma_e\ge0\), \(\alpha_t,\beta\) unrestricted, and constraints
\(\displaystyle \alpha_t+\beta|I|-\sum_{e\in I}\gamma_e\le |I|^2 \qquad(t,\ I\in\mathcal I_t). \)
For either dual, separation reduces, for each type and cardinality \(j\), to finding a minimum-weight independent set of size \(j\), with element weights \(\gamma_e\). Sort the elements by increasing weight and run matroid greedy. Its first \(j\) accepted elements form a minimum-weight independent set of size \(j\): they are a minimum-weight basis of the rank-\(j\) truncation. This handles every \(j\) from \(0\) through \(r_t(E)\), using polynomially many rank queries.
Thus the duals have polynomial dimension, polynomial coefficient encoding length, and exact polynomial-time separation oracles. The standard exact ellipsoid method with primal recovery solves these configuration LPs and returns polynomially many columns. This uses the primal-recovery form of the method, not an assumption that ordinary column generation terminates polynomially. [Burrell and Todd, *The Ellipsoid Method Generates Dual Variables*](https://pubsonline.informs.org/doi/10.1287/moor.10.4.688).
Take a basic optimal solution of the recovered square-minimization LP. After introducing supply slacks, there are \(\tau+m+1\) equality rows. Hence at most \(\tau+m+1\) configuration variables are positive.
Write these outcomes as
\(\displaystyle (t_i,q_i,k_i),\qquad i\in V,\)
where \(q_i>0\), \(k_i\) is the incidence vector of an independent set, and \(|V|\le\tau+m+1\).
We use the following finite matroid-rank facts:
Here Lorenz dominance means that, after sorting workers’ values increasingly, every initial partial sum is at least the corresponding sum for every other allocation. The first fact and the applicability of the subsidized egalitarian mechanism to an arbitrary clean Lorenz-dominating allocation are stated in [Goko et al., Section 2 and Theorem 3.1](https://arxiv.org/html/2105.01801v1).
We verify their applicability without constructing a large society.
Choose an integer \(N\) clearing the denominators of all \(\mu_t,\lambda_e,q_i\). Conceptually create \(N\mu_t\) workers of each type and \(N\lambda_e\) distinguishable copies of each class. A worker’s rank on these copies is
\(\displaystyle \widehat r_t(A)=r_t(\{\text{classes represented in }A\}).\)
This is a matroid rank function: it is the parallel expansion of the original matroid, restricted to the available copies.
Our clean plan becomes a finite clean allocation \(A\), with \(Nq_i\) workers receiving configuration \(i\). It has welfare \(NW\). Every finite allocation, after cleaning and dividing worker counts by \(N\), yields a feasible point of \(P\); therefore its welfare is at most \(NW\). Thus \(A\) is finite utilitarian-optimal.
Moreover, \(A\) minimizes the sum of squared values among finite clean utilitarian-optimal allocations. Otherwise, scaling a better finite allocation by \(1/N\) would contradict the square-minimization LP.
Let \(B\) be a finite clean Lorenz-dominating allocation. Its welfare is also \(NW\). Let \(a\) and \(b\) be the increasingly sorted value vectors of \(A\) and \(B\). Lorenz dominance gives
\(\displaystyle \sum_{\ell=1}^{j}b_\ell\ge\sum_{\ell=1}^{j}a_\ell \quad\text{for every }j, \qquad \sum_\ell b_\ell=\sum_\ell a_\ell. \)
The strict majorization inequality for the strictly convex function \(u\mapsto u^2\) gives
\(\displaystyle \sum_\ell b_\ell^2\le\sum_\ell a_\ell^2,\)
with equality only when the sorted vectors coincide. Square-minimality of \(A\) gives the reverse inequality. Hence \(a=b\), so \(A\) itself is Lorenz-dominating.
The finite subsidy theorem therefore applies to \(A\). Selecting one representative worker from each positive configuration proves that the compressed outcomes admit subsidies in \(\{0,1\}\).
These subsidies can be computed directly. Set
\(\displaystyle d_i=r_{t_i}(S(k_i)),\qquad w_{ij}=r_{t_i}(S(k_j))-d_i. \)
Existence of binary subsidies implies that every directed walk has weight at most \(1\), and every directed cycle has nonpositive weight. Define \(p_i\) as the maximum weight of a walk starting at \(i\), including the empty walk. Removing nonpositive cycles shows that this maximum is attained by a simple path. Thus \(p_i\in\{0,1\}\).
Concatenating an edge with a maximizing walk gives
\(\displaystyle p_i\ge w_{ij}+p_j,\)
which is exactly envy-freeness. Negating edge weights and computing shortest paths finds these subsidies in polynomial time.
The expanded society was used only to justify this property; the algorithm never constructs it.
We now prove the key lemma for compressed plans.
Lemma. Suppose a finite rational partial plan:
For any class with positive residual supply, that entire residual can be allocated while preserving welfare, subsidies, and envy-freeness, with at most one additional outcome.
Proof. Index the current outcomes by \(V\), with masses \(q_i>0\), types \(t_i\), bundles \(k_i\), and subsidies \(p_i\). Let \(R_e>0\) be the residual supply of class \(e\).
First, optimality implies
\(\displaystyle r_{t_i}(S(k_i)\cup\{e\})=r_{t_i}(S(k_i)) \quad\text{for every }i. \)
Indeed, a rank increase would let us give one copy of \(e\) to a positive rational submass at most \(\min(q_i,R_e)\), producing a feasible partial plan with welfare greater than \(W\). Section 1 rules this out.
Define the tight envy graph: there is an edge \(j\to i\) precisely when
\(\displaystyle d_j+p_j=r_{t_j}(S(k_i))+p_i, \qquad d_j=r_{t_j}(S(k_j)). \)
Choose a strongly connected component \(H\) with no entering tight edge from outside \(H\), and choose any host \(i\in H\). Such a component exists in every finite directed graph.
We claim that adding \(e\) to the host’s support preserves all envy comparisons.
For an observer \(j\), let
\(\displaystyle \Delta_j=r_{t_j}(S(k_i)\cup\{e\})-r_{t_j}(S(k_i)). \)
Matroid rank implies \(\Delta_j\in\{0,1\}\).
If \(j\to i\) is not tight, its envy inequality has integer slack at least \(1\). This absorbs the increase \(\Delta_j\).
If \(j\to i\) is tight, the choice of \(H\) implies \(j\in H\). For \(j=i\), the owner-rank equality above gives \(\Delta_j=0\).
For \(j\ne i\), take a simple tight directed path from \(i\) to \(j\). Together with \(j\to i\), it forms a directed cycle. Along every tight edge \(a\to b\),
\(\displaystyle r_{t_a}(S(k_b))-d_a=p_a-p_b. \)
Consequently, the total rank change from cyclically reassigning these bundles is zero.
If \(\Delta_j=1\), cyclically reassign a common positive rational submass of the bundles and additionally give class \(e\) to the submass of type \(t_j\) receiving \(k_i\). Choose this submass no larger than \(R_e\) and any participating outcome mass. Bundle permutation preserves all existing class consumption and all type masses; the extra copies remain within supply. Welfare increases by that submass, contradicting the upper bound \(W\).
Therefore \(\Delta_j=0\) for every tight incoming comparison.
All observers’ envy inequalities consequently survive adding \(e\) to the host’s support. The host’s own rank and subsidy remain unchanged, so its outgoing comparisons also survive.
Finally, write
\(\displaystyle R_e=hq_i+\rho,\qquad h=\lfloor R_e/q_i\rfloor,\qquad 0\le\rho<q_i. \)
Replace the host by outcomes of masses \(q_i-\rho\) and, when positive, \(\rho\), receiving respectively
\(\displaystyle k_i+h\mathbf 1_e \quad\text{and}\quad k_i+(h+1)\mathbf 1_e, \)
both with subsidy \(p_i\).
This consumes exactly \(R_e\). Every resulting support is either the original support or that support with \(e\) added. Parallel copies cause no further rank changes. Thus welfare and all envy inequalities are preserved, including comparisons between the two resulting outcomes. There is at most one split. \(\square\)
Apply this lemma once to every class with positive residual supply. The resulting plan is complete, has welfare \(W\), and retains subsidies in \(\{0,1\}\).
Initially there are at most \(\tau+m+1\) outcomes. Each class adds at most one, so the final number is at most
\(\displaystyle \tau+2m+1.\)
At each completion step, build the tight graph using rank queries on subsets of \(E\), compute its strongly connected components, and select a source component. These operations are polynomial in the current support size, \(m\), and \(C\). There are at most \(m\) steps.
It remains to bound the binary encoding length.
The initial basic LP solution has polynomial encoding length: its matrix entries are bounded integers, its dimension is at most \(\tau+m+1\), and its right-hand side has polynomial encoding length. Let \(D\) be a common denominator of the initial masses and all input masses and supplies. Since there are polynomially many such numbers, \(\log D\) is polynomially bounded.
Throughout completion, masses and residual supplies remain integer multiples of \(1/D\). Indeed, the only new mass is
\(\displaystyle \rho=R_e-hq_i.\)
Every positive mass is therefore at least \(1/D\). Hence
\(\displaystyle h\le D\lambda_e. \)
Each class is processed once, and its initial bundle coordinates are at most \(1\), so every final coordinate satisfies the sufficient bound
\(\displaystyle k_e\le D\lambda_e+2.\)
Thus all masses and bundle coordinates have polynomial binary encoding length. All arithmetic, rank queries, graph operations, and LP computations take polynomial time in \(m,\tau,L,C\).
The output satisfies exactly the requested comparisons between every pair of supported outcomes, including outcomes of the same type. Its welfare equals the unrestricted complete-plan optimum.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with minor gaps. The argument establishes the claimed polynomial-time algorithm and existence of a required plan for every instance. I found no false mathematical step or substantive gap. The remaining issue is the precision of the invocation of exact LP recovery.
The proof addresses the intended problem: rational, finitely supported plans; complete allocation of supplies; welfare optimality against unrestricted complete plans; and envy comparisons between every pair of supported outcomes, including outcomes of the same type.
The configuration model is correct. Independent sets suffice for the welfare comparison because every support contains an independent subset whose cardinality equals its rank. Replacing a bundle by such a subset preserves its owner’s value and decreases each class’s consumption. Aggregation preserves the prescribed type masses.
Feasibility, boundedness, and rational attainment are correct. Empty configurations establish feasibility. Nonnegative configuration masses sum to \(1\), establishing boundedness. The configuration family is finite, and all constraints are rational.
The completion calculation is correct. For a positive rational mass \(q\), the decomposition \(R_e=hq+\rho\), with \(0\leq\rho<q\), consumes exactly \(R_e\): the added consumption is \(hq+\rho\). The split masses remain rational and nonnegative. At most one additional outcome is necessary per processed class.
This completion need not initially preserve welfare exactly. The prover correctly uses monotonicity to obtain welfare at least \(W\), then uses the previously established upper bound for complete plans to force equality.
The extension of the upper bound to partial plans is valid. Extraction of independent subsets requires only coordinatewise consumption bounds and the prescribed type masses. Completeness and envy-freeness are unnecessary.
No issue arises here.
Both duals have the correct signs and domains.
The separation reduction is correct. For a fixed type and cardinality \(j\), both dual constraint families reduce to minimizing \(\sum_{e\in I}\gamma_e\) over independent sets of size \(j\). The coefficients involving \(j\) are constant within that cardinality.
The greedy claim is correctly stated and applicable. The rank-\(j\) truncation is a matroid, and its bases are precisely the original independent sets of size \(j\). Increasing-weight greedy therefore supplies a minimum-weight configuration for every feasible cardinality. The empty configuration and rank-zero matroids are included.
A complete separation oracle must also check the explicit restrictions \(\gamma_e\geq0\). That check is immediate; its omission from the implementation description does not invalidate the oracle.
Exact primal recovery is a valid standard tool here. It is essential that the separation oracle returns actual violated configuration constraints, as this oracle does. The recovery principle permits obtaining a polynomial collection of primal columns preserving the optimum; it is more than merely computing the dual optimum value. This principle is documented, for example, in [CMU’s treatment of large configuration LPs, Problem 2](https://www.cs.cmu.edu/~15850/hws/h4.pdf).
The support bound is correct. After supply slacks are introduced, there are \(\tau+m+1\) equality rows. A basic feasible solution has at most that many positive variables in total, hence at most that many positive configuration variables. Dependent rows can only reduce this bound.
Minor issue — theorem precision. The write-up invokes “the standard exact ellipsoid method with primal recovery” without stating the exact theorem and its hypotheses. This is an expositional gap: the required standard result applies, and the displayed LPs and oracle satisfy its substantive conditions.
Minimum clarification: state the exact recovery theorem being used, including its coefficient-encoding assumptions and its guarantee of an exact optimum supported on polynomially many recoverable columns. Explicitly connect the polynomial encoding length of \(W\) to the basic-solution encoding argument when introducing the second LP.
The cited finite result supports the required quantifier. Goko et al.’s mechanism chooses an arbitrary clean Lorenz-dominating allocation, and its envy-freeness guarantee therefore applies to the allocation \(A\) constructed here. The relevant support appears in the mechanism description and Lemma 3.12, rather than merely in the existential wording of Theorem 3.1. [Goko et al., Sections 2–3.2](https://arxiv.org/html/2105.01801v1)
The denominator-clearing construction is valid. Clearing the denominators makes worker counts, copy counts, and configuration multiplicities integral. Configuration feasibility ensures enough distinguishable copies exist to realize the bundles disjointly. The expanded valuations are matroid rank valuations obtained by parallel expansion and restriction.
The comparison with all finite allocations is valid. Cleaning any finite allocation and dividing its configuration counts by \(N\) gives a feasible point of \(P\). Consequently, its welfare cannot exceed \(NW\).
Square-minimality transfers correctly. Any finite clean utilitarian-optimal allocation with smaller squared-value sum would, after division by \(N\), contradict the second LP’s optimum.
The majorization argument has the correct direction. Lorenz dominance with equal total welfare implies that the squared-value sum of \(B\) is no greater than that of \(A\). Strict convexity gives equality only when the sorted vectors coincide. Square-minimality supplies the opposite inequality. Thus \(A\) has the same sorted value vector as \(B\), which suffices for \(A\) itself to Lorenz-dominate every allocation.
Representative selection is legitimate. Each positive configuration has at least one expanded worker. Restricting the finite envy inequalities to one representative per configuration supplies binary subsidies satisfying every compressed comparison. No uniform-subsidy assumption about all workers in a configuration is needed.
The subsidy computation is correct. Existing binary subsidies bound every walk’s weight by \(1\), by telescoping the edge inequalities. They also imply nonpositive cycle weights. Removing such cycles cannot decrease walk weight, so the maximum is attained by a simple path. Integer weights and inclusion of the empty walk imply \(p_i\in\{0,1\}\).
The concatenation inequality has the correct orientation: \(p_i\geq w_{ij}+p_j\). Negated weights have no negative cycles, so shortest-path computation is applicable.
No substantive issue arises here.
The owner-rank equality is justified for every supported outcome. If adding a residual class increased its owner’s rank, allocating one copy to a positive rational submass would create a feasible partial plan with welfare greater than \(W\). The contradiction does not require that modified plan to remain envy-free.
The source strongly connected component is chosen in the correct direction. With tight edges directed from observer to recipient, a component with no entering edges ensures every tight observer of the host lies inside the component.
Nontight comparisons are handled correctly. Ranks and subsidies are integers, so a nontight comparison has slack at least \(1\). A single new class increases an observer’s rank by at most \(1\).
The tight-cycle argument is valid.
Therefore every tight incoming observer has zero gain from the added class.
The split preserves all comparisons. Both resulting bundles have either the original support or its union with the processed class. The owner’s rank and subsidy remain unchanged, and all incoming comparisons have already been checked. Comparisons between the split outcomes are consequently valid as well.
The cases \(h=0\), \(\rho=0\), and an already-present class cause no failure. Parallel copies justify ignoring multiplicity beyond support.
No issue arises here.
The outcome count is correct: initially at most \(\tau+m+1\), followed by at most one additional outcome for each of \(m\) classes.
The completion operations are polynomial. The graph has polynomially many vertices; its edges use rank queries on subsets of \(E\). Strongly connected components and the required rational arithmetic are polynomial-time operations.
The denominator invariant is correct. Initial masses and supplies are integer multiples of \(1/D\). Consumption uses integer coordinates, and each new mass is \(\rho=R_e-hq_i\), so the invariant persists. Every positive mass is at least \(1/D\).
The numerical bounds are valid. Since \(R_e\leq\lambda_e\), the bound \(h\leq D\lambda_e\) follows. Each coordinate begins at most \(1\) and receives additions only when its class is processed, so \(k_e\leq D\lambda_e+2\) is sufficient.
These arguments bound binary encoding length, rather than numerical magnitudes, as the task requires. The conceptual expanded society is never constructed.
Zero supplies, all-loop matroids, a single listed type, and repeated types introduce no counterexample. The final plan meets all requested constraints.
State the exact LP primal-recovery theorem and explicitly identify its encoding hypotheses for both LPs. No new mathematical argument or change to the construction is needed. There are no blocking issues.
⟨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.