Answer: Polynomial-time solvable in \(m,\tau,L\); every valid rational-input instance admits a law with at most \(m+1\) supported bundles per type.
Theorem 6.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 2 is a strongly polynomial-time algo- rithm that gives an outcome that is ex-ante WEF, and ex-post WPROP1, ex-ante Pareto optimal, and ex-post Pareto optimal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T\) with masses \(\mu_t\), entitlements \(e_t\), additive values \(v_t(g)\), and supplies \(\sigma_g\) of indivisible item categories \(g\in G\), find a type-level configuration law \(\lambda_{t,B}\) over integral bundles \(B\in\mathbb{Z}_{\ge 0}^{G}\), with \(\sum_B\lambda_{t,B}=1\) and \(\sum_{t,B}\mu_t\lambda_{t,B}B_g=\sigma_g\), whose marginals \(x_{t,g}=\sum_B\lambda_{t,B}B_g\) maximize \(\sum_t\mu_te_t\log v_t(x_t)\), satisfy \(v_t(x_t)/e_t\ge v_t(x_u)/e_u\) for all positive-mass types \(t,u\), and induce a measurable integral assignment that is Pareto optimal and gives every supported bundle \(B\) weighted proportionality up to one item: \(v_t(B)\ge e_tV_t\) or \(v_t(B)+v_t(g)\ge e_tV_t\) for some available \(g\), where \(V_t=\sum_g\sigma_gv_t(g)\).
A society is an atomless probability space partitioned into types \(T\). Its input is the support list of the \(\tau=|T|\) positive-mass types, with binary-rational masses \(\mu_t>0\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\ge1\) item categories, binary-rational supplies \(\sigma_g>0\), entitlement densities \(e_t>0\) normalized by \(\sum_t\mu_te_t=1\), and nonnegative binary-rational additive values \(v_t(g)\), with \(V_t=\sum_g\sigma_gv_t(g)>0\). Let \(L\) be the total input bit length and \(v_t(z)=\sum_gv_t(g)z_g\).
Supplies measure aggregate masses of copies; individuals receive integral bundles \(B\in\mathbb Z_{\ge0}^{G}\), without individual capacity bounds. An outside copy of any positive-supply category may witness proportionality up to one item, including a category already represented in the bundle.
Seek a finitely supported rational configuration law \(\lambda_{t,B}\ge0\) satisfying \(\sum_B\lambda_{t,B}=1\), \(x_t=\sum_B\lambda_{t,B}B\), and \(\sum_t\mu_tx_{t,g}=\sigma_g\) for every \(g\).
Its marginals must maximize \(\sum_t\mu_te_t\log v_t(x_t)\) over all nonnegative fractional allocations satisfying those supply equalities, and satisfy weighted envy-freeness: \(v_t(x_t)/e_t\ge v_t(x_u)/e_u\) for all \(t,u\in T\).
Every supported bundle must satisfy weighted proportionality up to one item: \(v_t(B)\ge e_tV_t\), or \(v_t(B)+v_t(g)\ge e_tV_t\) for some \(g\in G\).
The law must admit a measurable integral realization assigning bundle \(B\) to mass \(\mu_t\lambda_{t,B}\) of type \(t\), which is Pareto optimal: no other measurable integral assignment with the same supplies weakly improves utility almost everywhere and strictly improves it on a set of positive mass.
Can such a law be computed, or its nonexistence determined, in time polynomial in \(m,\tau,L\), or is this computational problem NP-hard?
For finitely many agents and explicitly listed goods, a strongly polynomial algorithm computes weighted-Nash-maximizing marginals and a lottery satisfying ex-ante weighted envy-freeness and Pareto optimality, and ex-post weighted proportionality up to one item and Pareto optimality. [Discrete result](https://evi-micha.github.io/papers/wbobw.pdf)
Subsequent discrete work also obtains these guarantees in strongly polynomial time; neither verified source treats the atomless configuration problem above, and no result settling that exact problem was located. [Subsequent result](https://publications.rwth-aachen.de/record/988549/files/988549.pdf)
The problem is polynomial-time solvable, and every valid instance admits a law satisfying all the requirements. The law can be chosen to have at most \(m+1\) supported bundles per type.
I use the intended finite rational-input interpretation: the entitlement densities \(e_t\) are rational numbers whose encodings are included in \(L\).
The construction combines exact linear Fisher-market computation with an explicit rounding lemma. Pareto optimality holds for every measurable realization of the resulting law.
Let \(H\subseteq G\) contain the categories valued positively by at least one type. Construct a linear Fisher market with one buyer per type and one unit-supply good per category in \(H\). Define the budgets and utilities by
\(b_t=\mu_te_t,\qquad a_{t,g}=\sigma_gv_t(g).\)
Every budget is positive, every buyer values some retained good because \(V_t>0\), and every retained good is valued by some buyer.
We use the following known algorithmic result: a linear Fisher market with positive rational budgets, nonnegative rational utilities, unit supplies, and a positive utility in every row and column has an exactly computable rational equilibrium in polynomial bit time. Orlin gives a strongly polynomial algorithm for this market model. Its integer-input formulation applies here by clearing utility denominators and budget denominators separately; uniform utility scaling preserves demands, and uniform budget scaling merely rescales equilibrium prices. These transformations have polynomial encoding length. [Orlin, *Improved Algorithms for Computing Fisher’s Market Clearing Prices*](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf)
Let \(y_{t,g}\) be the equilibrium fractions and \(P_g>0\) the equilibrium prices. Thus
\(\sum_t y_{t,g}=1,\qquad \sum_{g\in H}P_gy_{t,g}=b_t.\)
For each buyer, put
\(\alpha_t=\max_{g\in H}\frac{a_{t,g}}{P_g}>0.\)
The equilibrium condition says
\(a_{t,g}\leq\alpha_tP_g,\)
with equality whenever \(y_{t,g}>0\).
For each category outside \(H\), assign its entire fractional supply to any fixed type. Define the per-copy prices and per-capita allocations by
\(p_g=P_g/\sigma_g,\qquad x_{t,g}=\sigma_gy_{t,g}/\mu_t\quad(g\in H),\)
and set \(p_g=0\) outside \(H\), using the chosen fractional allocation there.
These quantities satisfy
\(\sum_t\mu_tx_{t,g}=\sigma_g,\qquad p\cdot x_t=e_t,\)
and
\(v_t(g)\leq\alpha_tp_g,\)
with equality whenever \(x_{t,g}>0\). For categories outside \(H\), this equality follows because both sides are zero.
Consequently, writing \(U_t=v_t(x_t)\), we have
\(U_t=\alpha_t e_t>0,\qquad p\cdot\sigma=\sum_t\mu_te_t=1.\)
All these quantities are rational and computable with polynomial encoding length.
Let \(z\) be any feasible nonnegative fractional allocation. The price inequalities imply
\(\sum_t\mu_t\frac{e_t}{U_t}v_t(z_t) =\sum_t\mu_t\frac{v_t(z_t)}{\alpha_t} \leq\sum_t\mu_t p\cdot z_t =p\cdot\sigma=1.\)
If some \(v_t(z_t)=0\), its Nash objective is negative infinity, so it cannot improve upon \(x\). Otherwise, applying \(\log r\leq r-1\) for \(r>0\) gives
\(\sum_t\mu_te_t\log\frac{v_t(z_t)}{U_t} \leq\sum_t\mu_te_t\left(\frac{v_t(z_t)}{U_t}-1\right) \leq 1-\sum_t\mu_te_t=0.\)
Thus \(x\) maximizes exactly the required weighted Nash objective.
For every pair \(t,u\),
\(v_t(x_u)\leq\alpha_t p\cdot x_u=\alpha_te_u.\)
Since \(U_t/e_t=\alpha_t\), this proves
\(\frac{v_t(x_t)}{e_t}\geq\frac{v_t(x_u)}{e_u}.\)
For every type,
\(V_t=\sum_g\sigma_gv_t(g) \leq\alpha_t\sum_g\sigma_gp_g=\alpha_t.\)
Therefore,
\(U_t=\alpha_te_t\geq e_tV_t.\)
We prove a rounding lemma for a single type.
Order its categories so that their values satisfy
\(a_1\geq a_2\geq\cdots\geq a_m\geq0,\qquad a_1>0.\)
Let \(x_i\geq0\) denote its fractional quantities in that order, and define
\(S_0=0,\qquad S_k=\sum_{i=1}^k x_i.\)
For \(r\in[0,1)\), define the integral bundle
\(B_i(r)=\lfloor S_i+r\rfloor-\lfloor S_{i-1}+r\rfloor.\)
Because the prefix sums are nondecreasing, every \(B_i(r)\) is a nonnegative integer.
If \(r\) is uniform on \([0,1)\), then for every real \(s\),
\(\mathbb E[\lfloor s+r\rfloor]=s.\)
Indeed, writing \(s=n+f\) with \(n\) integral and \(f\in[0,1)\), the floor equals \(n+1\) on a set of length \(f\) and \(n\) otherwise. Hence
\(\mathbb E[B_i(r)]=S_i-S_{i-1}=x_i.\)
Define
\(D_k(r)=\lfloor S_k+r\rfloor-S_k.\)
Then \(D_k(r)>-1\). Set \(a_{m+1}=0\). Telescoping yields
\(\sum_{i=1}^m a_i(B_i(r)-x_i) =\sum_{k=1}^m(a_k-a_{k+1})D_k(r).\)
All coefficients on the right are nonnegative, and their sum is \(a_1>0\). Therefore,
\(\sum_{i=1}^m a_iB_i(r)>\sum_{i=1}^m a_ix_i-a_1.\)
Apply this construction to type \(t\), and let
\(M_t=\max_{g\in G}v_t(g)>0.\)
Every produced bundle satisfies
\(v_t(B)+M_t>U_t\geq e_tV_t.\)
A category attaining \(M_t\) has positive supply. Under the stipulated outside-copy convention, it is an admissible witness even when that category already appears in \(B\). Thus every produced bundle satisfies weighted proportionality up to one item.
The function \(r\mapsto B(r)\) changes only when some \(S_k+r\) crosses an integer. Its possible internal breakpoints are
\(1-\{S_k\}\quad\text{for those }k\text{ with }\{S_k\}>0,\)
where \(\{s\}=s-\lfloor s\rfloor\).
There are at most \(m\) distinct internal breakpoints. Together with \(0\) and \(1\), they partition the parameter interval into at most \(m+1\) intervals.
For each interval:
Merge repeated bundles if necessary. Since \(x\) is rational, all breakpoints and probabilities are rational. The resulting law has at most \(m+1\) supported bundles and preserves every coordinate of \(x\).
Doing this separately for all types produces \(\lambda_{t,B}\) with
\(\sum_B\lambda_{t,B}=1,\qquad \sum_B\lambda_{t,B}B=x_t.\)
In particular, all supply equalities remain exact.
Use the divisibility theorem for atomless finite measures: if \(A\) is measurable and \(c\in[0,\mu(A)]\), there exists a measurable subset of \(A\) of measure \(c\).
Each type set inherits atomlessness from the society. Repeated application of this theorem partitions type \(t\) into measurable pieces of measures
\(\mu_t\lambda_{t,B}.\)
Assign bundle \(B\) on its corresponding piece. This gives a measurable integral assignment \(A\), and its aggregate supplies are
\(\int A_g\,d\mu =\sum_t\mu_t\sum_B\lambda_{t,B}B_g =\sum_t\mu_tx_{t,g} =\sigma_g.\)
Define the positive type weights
\(c_t=\frac{1}{\alpha_t}=\frac{e_t}{U_t}.\)
The price inequalities imply, for every nonnegative integral bundle \(C\),
\(c_tv_t(C)\leq p\cdot C.\)
Consequently, every measurable integral assignment \(A'\) with the same supplies satisfies
\(\int c_{t(\omega)}v_{t(\omega)}(A'(\omega))\,d\mu(\omega) \leq\sum_gp_g\int A'_g\,d\mu =p\cdot\sigma=1.\)
For the constructed realization, equality holds:
\(\int c_{t(\omega)}v_{t(\omega)}(A(\omega))\,d\mu(\omega) =\sum_t\mu_tc_tU_t =\sum_t\mu_te_t=1.\)
Suppose \(A'\) weakly improves utility almost everywhere and strictly improves utility on a set of positive measure. Because every \(c_t>0\), the weighted utility difference is nonnegative almost everywhere and positive on a set of positive measure. It therefore has strictly positive integral.
The relevant utilities are integrable: supplies are finite, there are finitely many categories and types, and all values and weights are finite. Thus \(A'\) would have weighted utility integral strictly greater than \(1\), contradicting the preceding bound.
This proves Pareto optimality. The argument applies to every measurable realization of the law.
The Fisher-market transformation and exact equilibrium computation take polynomial time in \(m,\tau,L\).
For each type, rounding requires sorting the categories, forming prefix sums, sorting at most \(m\) breakpoints, and constructing at most \(m+1\) bundles. These are polynomially many exact rational operations on numbers of polynomial encoding length.
Large supplies do not require expanding copies. Indeed,
\(x_{t,g}\leq\sigma_g/\mu_t,\qquad B_g(r)\leq\lceil x_{t,g}\rceil\leq\lceil\sigma_g/\mu_t\rceil.\)
Hence bundle multiplicities have polynomial binary encoding length even when their numerical values are large.
The output has at most \(\tau(m+1)\) supported type-bundle pairs, each containing \(m\) binary-encoded multiplicities and one rational probability. Its total encoding length is polynomial.
The algorithm therefore computes the requested law in polynomial bit time; under the stated hypotheses, a nonexistence outcome never occurs.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time solvability and existence for every valid instance under the explicitly stated rational encoding of the entitlement densities. I found no false step, major gap, or required repair.
The prover explicitly assumes that the entitlement densities \(e_t\) are rational and included in \(L\). This is the natural finite-input interpretation of the task’s otherwise unspecified entitlement encoding. The complexity conclusion is properly understood under that interpretation.
The market transformation is correct:
The cited algorithmic result applies. Orlin’s paper specifies the positive-row and positive-column assumptions, computes an exact equilibrium consisting of prices and spending allocations, and supplies a strongly polynomial algorithm. Its basic-solution discussion also establishes rationality through rational linear systems. These support the prover’s stated exact polynomial-time computation claim. [Orlin’s paper, Sections 1.1, 2, and 4](https://drops.dagstuhl.de/storage/16dagstuhl-seminar-proceedings/dsp-vol10171/DagSemProc.10171.2/DagSemProc.10171.2.pdf)
Clearing utility and budget denominators separately is valid: the two uniform scalings have the stated effects, and their encoding lengths are polynomial in the input length.
The conversions
\(p_g=P_g/\sigma_g\) and \(x_{t,g}=\sigma_gy_{t,g}/\mu_t\)
correctly yield supply feasibility and \(p\cdot x_t=e_t\). The equilibrium inequalities convert correctly to
\(v_t(g)\leq\alpha_tp_g\), with equality on allocated coordinates. Universally unvalued categories can receive zero prices and be assigned to an arbitrary type without affecting these identities.
Consequently, both
\(U_t=\alpha_te_t>0\) and \(p\cdot\sigma=1\)
are justified.
Nash optimality. The price inequality gives exactly the stated weighted utility bound for every feasible fractional allocation. Applying \(\log r\leq r-1\) with weights \(\mu_te_t\) then proves the required objective inequality. Allocations giving any type zero utility are correctly excluded from improvement because every objective weight is positive and the constructed allocation has finite objective.
Weighted envy-freeness. The inequality
\(v_t(x_u)\leq\alpha_tp\cdot x_u=\alpha_te_u\)
uses the evaluating type’s price inequality correctly. Division by positive entitlements gives precisely the requested guarantee for every ordered pair of types.
Marginal proportionality. Summing the price inequalities against supplies gives \(V_t\leq\alpha_t\). Thus \(U_t\geq e_tV_t\). The normalization constant is correctly one throughout.
No gap occurs in this section.
The rounding construction is valid for arbitrary nonnegative fractional quantities, including quantities exceeding one.
Integrality and nonnegativity. Each coordinate is a difference of floors of nondecreasing prefix sums, so it is a nonnegative integer.
Marginal preservation. The identity
\(\mathbb E[\lfloor s+r\rfloor]=s\)
is correctly derived by separating the integer and fractional parts. Taking differences preserves every coordinate exactly.
Utility bound. The telescoping identity is correct. Its initial boundary term vanishes because
\(\lfloor S_0+r\rfloor-S_0=0\)
throughout the specified parameter interval. The other boundary is handled by \(a_{m+1}=0\).
Each \(D_k(r)>-1\), the coefficients \(a_k-a_{k+1}\) are nonnegative, and their sum is the strictly positive quantity \(a_1\). These facts justify the strict inequality
\(v_t(B)>U_t-M_t\).
Since all categories have positive supply, a category attaining \(M_t\) is an admissible outside-copy witness under the task’s explicit convention. Hence every produced bundle satisfies the required proportionality condition.
Finite law. The listed breakpoints exhaust all changes of the bundle function. There are at most \(m\) distinct internal breakpoints and therefore at most \(m+1\) intervals. Midpoint evaluation with interval-length probabilities preserves the uniform distribution’s expectations; endpoint values have measure zero. Rational prefix sums give rational breakpoints and probabilities.
Zero marginal coordinates and universally unvalued categories cause no failure. Tied values, integer prefix sums, and the case \(m=1\) are all covered by the formulas.
The atomless divisibility theorem is stated with the needed hypotheses. Restrictions of an atomless measure to measurable type sets remain atomless. Repeated subdivision therefore provides the finitely many prescribed piece masses.
The resulting assignment is measurable, and its aggregate supplies equal the required supplies by the displayed finite-sum calculation.
The task asks for the law to *admit* such a realization; it does not require an algorithmic encoding of measurable subsets of the underlying society. The existence argument therefore addresses the requirement.
The weights \(c_t=1/\alpha_t\) are strictly positive. The bundle inequality
\(c_tv_t(C)\leq p\cdot C\)
holds for every competing nonnegative integral bundle, without a capacity or support restriction.
Integrating it gives the upper bound one for every measurable competing assignment with the same supplies. The constructed assignment attains one because its typewise expected utilities are \(U_t\).
The integrability claim is correct: finitely many finite valuation coefficients and weights, together with finite coordinate supplies, bound all relevant integrals. A weak improvement almost everywhere with a strict improvement on a positive-measure set therefore produces a strictly larger weighted integral, contradicting the bound.
This also establishes the asserted guarantee for every measurable realization of the law.
The rounding stage performs polynomially many exact rational operations. Prefix sums, breakpoints, probabilities, and midpoint calculations retain polynomial encoding length.
The bound
\(B_g(r)\leq\lceil x_{t,g}\rceil\leq\lceil\sigma_g/\mu_t\rceil\)
is correct. Thus large numerical supplies do not force a large explicit expansion into copies.
The support bound and polynomial binary encoding of each multiplicity establish polynomial output size. The algorithm operates on the listed support of types, so its dependence is on \(\tau\), as required.
Feedback: No repair is required. The explicit rational-input interpretation of entitlements should remain attached to the complexity statement.
⟨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.