Answer: polynomial-time solvable
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLorenz Improvement is NP-complete for the XOR-language. 6I’m indebted to Harry Buhrman, Bruno Loffand Leen Torenvliet for the main insight at the heart of this result; see also their work on approximations of knapsack problems [7].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite good catalogue \(G\), type masses \(\mu_t\) summing to \(1\), an XOR utility \(u_t\), a current bundle \(A_t^0\), a required subset \(P_t\) for each type \(t\), and per-capita supplies \(b_g\), decide whether there are assignments \(y_{t,B}\ge 0\) to integral bundles \(B\subseteq G\) such that \(\sum_{B\supseteq P_t}y_{t,B}=\mu_t\) and \(\sum_{t,B:\,g\in B}y_{t,B}\le b_g\), with \(\mathcal L_y(q)\ge\mathcal L_x(q)\) for every \(q\in[0,1]\) and strict inequality for some \(q\). Here \(\mathcal L_y(q)\) is the total utility of the poorest \(q\)-fraction under \(y\), and \(\mathcal L_x\) is the corresponding curve for the current bundles.
Let \(G\) be a finite catalogue of \(m\) goods. A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has an explicitly listed XOR bid \(\{(S_{tj},w_{tj})\}_j\), where \(\varnothing\ne S_{tj}\subseteq G\) and \(w_{tj}\in\mathbb Q_{\ge0}\), defining \(u_t(B)=\max(\{0\}\cup\{w_{tj}:S_{tj}\subseteq B\})\). All weights are binary rationals.
The input also gives current bundles \(A_t^0\subseteq G\), required subsets \(P_t\subseteq G\), and binary-rational per-capita supplies \(b_g\in[0,1]\). Require \(\sum_{t:g\in A_t^0}\mu_t=b_g\) and \(\sum_{t:g\in P_t}\mu_t\le b_g\) for every \(g\); no inclusion between \(P_t\) and \(A_t^0\) is required.
An assignment splits type masses among integral bundles: \(y_{t,B}\in\mathbb R_{\ge0}\), with \(y_{t,B}=0\) unless \(B\supseteq P_t\), \(\sum_{B\subseteq G}y_{t,B}=\mu_t\), and \(\sum_{t,B:g\in B}y_{t,B}=b_g\). Thus all supplies are allocated, without transfers of utility.
For any assignment \(z\), its utility distribution places mass \(z_{t,B}\) at \(u_t(B)\). Define \(\mathcal L_z(q)=\int_0^q Q_z(s)\,ds\), where \(Q_z\) is its increasing utility quantile; masses at tied utilities may be split. This curve is not divided by mean utility. The current assignment is \(x_{t,B}=\mu_t\mathbf1_{\{B=A_t^0\}}\).
Continuous Lorenz Improvement asks whether a feasible \(y\) satisfies \(\mathcal L_y(q)\ge\mathcal L_x(q)\) for every \(q\in[0,1]\), with strict inequality for some \(q\). Running times are measured in \(m\), \(\tau\), the total number \(K\) of listed atomic bids, and total input bit length \(L\).
Is Continuous Lorenz Improvement solvable in polynomial time in \(m,\tau,K,L\), or is it NP-hard?
For finitely many agents receiving disjoint bundles that partition the goods, deciding whether a current allocation admits a strict Lorenz improvement extending a required partial allocation is NP-complete for XOR utilities. [Endriss, 2013](https://www.ifaamas.org/Proceedings/aamas2013/docs/p175.pdf)
No result settling this exact mass-splitting problem was located in the literature search.
Continuous Lorenz Improvement is solvable in polynomial time in \(m,\tau,K,L\). A rational linear program with \(\tau+K\) variables suffices.
The proof uses two properties of the stated model: an XOR utility can be witnessed by one atomic bid, and unused supplies can be allocated by splitting masses without decreasing anyone’s utility.
Let \(V=\{0\}\cup\{w_{tj}:t,j\}\), with duplicates removed, and let \(M=\max V\). Every attainable utility, including every current utility, belongs to \(V\).
For a utility distribution \(z\) of total mass \(1\), define its shortfall function by
\[ H_z(a)=\sum_{t,B}z_{t,B}(a-u_t(B))_+, \qquad (r)_+=\max\{r,0\}. \]
Equivalently, \(H_z(a)=\int_0^1(a-Q_z(s))_+\,ds\). We establish the identities
\[ H_z(a)=\max_{q\in[0,1]}\{aq-\mathcal L_z(q)\}, \qquad \mathcal L_z(q)=\max_{a\in V}\{aq-H_z(a)\}. \]
For the first identity, observe that
\[ aq-\mathcal L_z(q)=\int_0^q(a-Q_z(s))\,ds. \]
Because \(Q_z\) is increasing, this expression is maximized by including all quantile mass with utility below \(a\), any desired portion with utility equal to \(a\), and no mass with utility above \(a\). Its maximum is exactly \(H_z(a)\).
Consequently, \(aq-H_z(a)\le\mathcal L_z(q)\) for every \(a,q\). To prove equality for a suitable \(a\in V\), first suppose \(0<q<1\). Choose a utility value \(a\) for which
\[ p_<:=\Pr_z(U<a)\le q\le\Pr_z(U\le a). \]
Such a value exists because the distribution has finite support. Writing \(I_<=\int_0^{p_<}Q_z(s)\,ds\), we have
\[ H_z(a)=ap_<-I_<, \qquad \mathcal L_z(q)=I_<+a(q-p_<)=aq-H_z(a). \]
At \(q=0\), choose \(a=0\); at \(q=1\), choose \(a=M\), using \(H_z(M)=M-\mathcal L_z(1)\). This proves the second identity, including the case \(M=0\).
It follows that, for distributions supported on \(V\),
\[ \mathcal L_z(q)\ge\mathcal L_x(q)\text{ for every }q \quad\Longleftrightarrow\quad H_z(a)\le H_x(a)\text{ for every }a\in V. \]
Indeed, the forward implication follows from the first identity, and the reverse implication from the second.
Moreover, under these weak inequalities, strict Lorenz improvement is equivalent to strict shortfall inequality at some \(a\in V\). If every shortfall value on \(V\) is equal, the second identity gives equality of the Lorenz curves. Conversely, equality of the Lorenz curves implies equality of all shortfall values by the first identity.
Thus finitely many linear inequalities, together with one positive slack, characterize the desired improvement.
Let \(k_t\) be the number of atomic bids of type \(t\). Define
\[ D_{t0}=P_t, \qquad D_{tj}=P_t\cup S_{tj}\quad(1\le j\le k_t), \qquad v_{tj}=u_t(D_{tj}). \]
All these bundles and their actual utilities can be computed from the explicitly listed bids in polynomial time.
We claim that every allowed bundle \(B\supseteq P_t\) has a utility-preserving reduction to one of these bundles.
If \(u_t(B)=0\), choose \(D_{t0}\). Since \(D_{t0}\subseteq B\) and utilities are nonnegative and monotone, \(u_t(D_{t0})=0\).
If \(u_t(B)>0\), some listed bid attains the maximum defining its utility: \(S_{tj}\subseteq B\) and \(w_{tj}=u_t(B)\). Then \(D_{tj}\subseteq B\), and
\[ u_t(B)=w_{tj}\le u_t(D_{tj})\le u_t(B). \]
Hence \(u_t(D_{tj})=u_t(B)\).
Applying this reduction separately to each positive-mass cell of an assignment preserves its utility distribution and type masses, preserves all required subsets, and can only decrease consumption of each good. The number of candidate bundles is
\[ N=\sum_t(k_t+1)=K+\tau. \]
Suppose an assignment \(z\) satisfies the type-mass and required-subset constraints, but only satisfies the supply upper bounds. Let its consumption of good \(g\) be \(c_g\le b_g\).
The mass of cells whose bundles lack \(g\) is \(1-c_g\). The amount still to allocate is \(\delta_g=b_g-c_g\), and the premise \(b_g\le1\) gives
\[ 0\le\delta_g\le1-c_g. \]
Choose mass \(\delta_g\) among those cells, splitting a cell if necessary, and add \(g\) to their bundles. This makes consumption of \(g\) exactly \(b_g\). It changes no other good’s consumption, no type total, and no required-subset inclusion.
Process every good in this way. The resulting assignment \(y\) meets all supply equalities.
Each descendant cell has a superset of its original bundle, so its utility cannot decrease. Therefore, for every threshold \(a\),
\[ H_y(a)\le H_z(a). \]
In particular, any strict Lorenz improvement achieved before filling remains strict afterward.
This construction also has polynomial output size: processing one good requires at most one cell split if cells are handled sequentially. Starting with at most \(N\) cells, the completed assignment has at most \(N+m\) cells.
Compute the current utilities \(u_t^0=u_t(A_t^0)\) and the constants
\[ h_a=H_x(a)=\sum_t\mu_t(a-u_t^0)_+ \quad(a\in V). \]
Introduce a nonnegative variable \(\alpha_{tj}\) for the mass assigned to candidate bundle \(D_{tj}\), for \(0\le j\le k_t\).
Impose the type-mass constraints
\[ \sum_{j=0}^{k_t}\alpha_{tj}=\mu_t \quad\text{for every }t, \]
the supply upper bounds
\[ \sum_{t,j:g\in D_{tj}}\alpha_{tj}\le b_g \quad\text{for every }g, \]
and the shortfall inequalities
\[ \sum_{t,j}\alpha_{tj}(a-v_{tj})_+\le h_a \quad\text{for every }a\in V. \]
Maximize the total slack
\[ \Phi(\alpha)= \sum_{a\in V} \left( h_a-\sum_{t,j}\alpha_{tj}(a-v_{tj})_+ \right). \]
The decision rule is:
All objective summands are nonnegative on the feasible region, so positive total slack is equivalent to strict inequality at some threshold.
If a strict Lorenz improvement exists, the program has positive optimum.
Let \(y\) be such an assignment. Apply the utility-preserving reductions of Section 2 and aggregate the resulting masses into \(\alpha_{tj}\). The type constraints hold, and supply consumption has only decreased. Its utility distribution is exactly that of \(y\).
By Section 1, all shortfall inequalities hold, with at least one strict inequality. Thus \(\alpha\) is feasible and \(\Phi(\alpha)>0\).
If the program has positive optimum, a strict Lorenz improvement exists.
Take a feasible \(\alpha\) with positive objective. Assign its masses to the bundles \(D_{tj}\), obtaining an assignment \(z\) that respects required subsets and supply upper bounds. Its actual utilities are \(v_{tj}\), so the linear inequalities and positive objective imply that \(z\) strictly Lorenz dominates \(x\).
Complete its supplies using Section 3. The resulting feasible assignment \(y\) satisfies \(H_y(a)\le H_z(a)\) for every \(a\). Hence all dominance inequalities remain valid, and any strict one remains strict. Section 1 therefore gives the required strict Lorenz improvement.
Neither direction assumes \(P_t\subseteq A_t^0\).
The program has \(K+\tau\) variables and, apart from nonnegativity, at most \(\tau+m+K+1\) constraints.
Candidate bundles, their utilities, and current utilities are computable by subset tests against the explicitly listed bids. Every coefficient is rational, and all differences, products, and sums used to construct the program have polynomial encoding length in \(m,\tau,K,L\).
If feasible, the program is bounded because \(0\le\alpha_{tj}\le\mu_t\). The standard polynomial-time theorem for rational linear programming therefore permits exact optimization and exact comparison of its optimum with zero. No numerical tolerance or presumed minimum improvement is needed.
This settles the stated mass-splitting problem. The NP-completeness result for allocations to indivisible agents concerns a different feasible set; see [Endriss, Proposition 7](https://www.ifaamas.org/Proceedings/aamas2013/docs/p175.pdf).
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct. The argument resolves the stated mass-splitting problem, including strict improvement, exact supply allocation, and binary-rational input complexity. No major or minor mathematical issues were found.
Every bundle utility belongs to \(V\): the maximum defining an XOR utility is either zero or one of the explicitly listed weights. Consequently, both current and proposed utility distributions have finite support contained in \(V\).
The first identity,
\[
H_z(a)=\max_{q\in[0,1]}\{aq-\mathcal L_z(q)\},
\]
is justified correctly. Since the quantile is increasing, the integrand \(a-Q_z(s)\) is positive before utility \(a\), zero at utility \(a\), and negative afterward. The maximization therefore gives exactly the total shortfall. Ties cause no difficulty because their contribution is zero.
The second identity,
\[
\mathcal L_z(q)=\max_{a\in V}\{aq-H_z(a)\},
\]
is also established correctly. For interior \(q\), the chosen support value \(a\) satisfies the required quantile-mass inequalities. The two displayed expressions involving \(p_<\) and \(I_<\) then give equality. The endpoint choices are valid: utilities are nonnegative, so \(H_z(0)=0\); utilities are at most \(M\), so \(H_z(M)=M-\mathcal L_z(1)\).
The directions of the dominance inequalities are correct. Larger Lorenz curves give smaller shortfall functions, and the second identity supplies the converse from thresholds in \(V\).
The strictness argument is valid under weak dominance. Equality of all shortfall values on \(V\) is equivalent to equality of the Lorenz curves. Thus failure of equality on either side supplies a strict inequality with the stated direction. This does not require the strict Lorenz inequality and strict shortfall inequality to occur at corresponding arguments.
The candidate reduction is correct for every allowed bundle.
Using the candidates’ actual utilities \(v_{tj}\) is essential and is handled correctly: adjoining \(P_t\) can activate additional bids.
Reducing cells preserves their masses, types, required subsets, and utilities while weakly decreasing each good’s consumption. Duplicate candidate bundles do not invalidate the construction or the LP; their masses can be aggregated when interpreting an assignment.
The count \(N=K+\tau\) is correct, including types with no bids.
The filling argument is valid for the stated feasible set.
For any good \(g\), total mass lacking that good is \(1-c_g\). The supply assumption \(b_g\le1\) gives exactly the necessary bound
\[
0\le b_g-c_g\le1-c_g.
\]
Mass splitting therefore permits the prescribed amount to receive \(g\).
Adding \(g\) changes no other good’s consumption. It also preserves type masses and required-subset inclusion. Accordingly, processing subsequent goods cannot undo an earlier supply equality.
Monotonicity ensures that each descendant cell has utility at least that of its ancestor. Hence the claimed shortfall inequality holds at every threshold. Any strict shortfall inequality relative to the current assignment remains strict after filling.
The output-size claim is correct: allocating a single good sequentially across cells requires at most one partial-cell split. Starting from at most \(N\) cells therefore leaves at most \(N+m\) cells after all goods are processed.
All LP constraints represent their intended quantities correctly:
The objective is a sum of nonnegative slacks on the feasible region. Its positivity is therefore equivalent to strict inequality at some threshold in \(V\).
The feasible region is closed and bounded: nonnegativity and each type equality imply \(0\le\alpha_{tj}\le\mu_t\). Thus, whenever feasible, the optimum is attained. The decision rule correctly distinguishes infeasibility, zero optimum, and positive optimum.
The forward direction preserves an improving assignment’s utility distribution exactly while reducing consumption. It consequently produces an LP-feasible vector with positive objective.
The reverse direction interprets a positive-objective vector as a candidate assignment, applies the established Lorenz characterization, and fills supplies while preserving strict improvement. The resulting assignment satisfies all original equalities.
Neither direction requires \(P_t\subseteq A_t^0\). The current allocation is used only to compute the comparison distribution, which is appropriate even when it fails the required-subset restrictions.
The stated dimensions are correct: \(K+\tau\) variables and at most \(\tau+m+K+1\) constraints apart from nonnegativity.
Subset tests and utility evaluations are polynomial in the explicit input size. The rational differences, products, and sums defining the coefficients have polynomial encoding length. No operation enumerates all bundles.
The invoked rational-LP theorem applies: the program has rational coefficients of polynomial encoding length and, when feasible, a bounded feasible region. Polynomial-time exact optimization supports exact comparison with zero; strict improvement requires no numerical tolerance.
The zero-utility case is handled explicitly by \(M=0\). Empty bid lists and zero supplies also introduce no failure in the reduction, filling argument, or LP.
The contextual citation is accurate: [Endriss, Proposition 7](https://www.ifaamas.org/Proceedings/aamas2013/docs/p175.pdf) concerns XOR Lorenz improvement for discrete agents. It is not used as a premise of the continuous algorithm.
No repair or additional clarification 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.