Answer: Polynomial-time solvable: construction takes time \(\operatorname{poly}(m,\tau,R,L)\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a scale-invariant, PEF1 mechanism that always produces an EF1 allocation in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), additive utility vectors \(u_t\in\mathbb{Q}_{\ge 0}^m\), and rational per-capita supplies \(q_g\ge 0\), consider ordered profiles \(f:[0,1]\to T\) encoded as \(R\) rational rank intervals, with each type appearing on mass \(\mu_t\). Can one construct a scale-invariant polynomial-time rule, with running time measured in \(m,\tau,R,L\), that maps each \(f\) to a rank-indexed allocation \(B_f(r)\in\mathbb{Z}_{\ge 0}^m\), satisfies \(\int_0^1 B_{f,g}(r)\,dr=q_g\) for every good class \(g\), and gives EF1 for almost every pair of ranks? Require also PEF1 across every pair \(f,f'\) with the same type masses: for every type-preserving measure-preserving bijection \(\phi\) between their rank spaces, almost every rank \(r\) must satisfy the PEF1 comparison between \(B_f(r)\) and \(B_{f'}(\phi(r))\), using utility \(u_{f(r)}\) and removal of one good.
A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) good classes, additive utilities \(u_t\in\mathbb{Q}_{\geq0}^m\), and per-capita supplies \(q\in\mathbb{Q}_{\geq0}^m\). Zero utilities and zero supplies are allowed.
An ordered profile \(f:[0,1]\to T\) is constant on \(R\) rational intervals and satisfies \(\lambda(f^{-1}(t))=\mu_t\), where \(\lambda\) is Lebesgue measure. Let \(L\) be the total binary input length.
A deterministic rule observes the ordered utility function and supplies, without agent identities, and returns \(B_f:[0,1]\to\mathbb{Z}_{\geq0}^m\), encoded by finitely many rational intervals with binary integer bundle vectors. Equivalent interval encodings must yield the same allocation almost everywhere, and \(\int_0^1 B_{f,g}(r)\,dr=q_g\) for every class \(g\).
Write \(C_t(x,y)\) when either \(y=0\), or some \(g\) with \(y_g>0\) satisfies \(u_t\cdot x\geq u_t\cdot(y-e_g)\), where \(e_g\) removes exactly one copy of class \(g\).
Require EF1: \(C_{f(r)}(B_f(r),B_f(s))\) for almost every \((r,s)\) under product Lebesgue measure.
Require PEF1: for every ordered pair \(f,f'\) with the same utilities, supplies, and type masses, and every measurable measure-preserving bijection \(\phi\) modulo null sets satisfying \(f'\circ\phi=f\) almost everywhere, \(C_{f(r)}(B_f(r),B_{f'}(\phi(r)))\) holds for almost every \(r\).
Scale-invariance means that independently multiplying rank utilities by positive factors leaves the allocation unchanged almost everywhere whenever the rescaled ordered utility function has a finite rational interval encoding; type support may be refined accordingly.
Is constructing a scale-invariant rule satisfying these feasibility, EF1, and PEF1 requirements possible in time polynomial in \(m,\tau,R,L\), or is this construction problem NP-hard?
For finite societies with nonnegative additive utilities, a scale-invariant polynomial-time PEF1 mechanism producing EF1 allocations exists ([Mahara et al.](https://ojs.aaai.org/index.php/AAAI/article/download/38763/42725)).
For divisible cake and finitely many participants, simultaneous envy-freeness and meta-envy-freeness are known for two and three participants ([Manabe–Okamoto](https://www.jstage.jst.go.jp/article/ipsjjip/20/3/20_686/_pdf)); no result settling the precise continuum-of-ranks problem above was located.
The construction problem is polynomial-time solvable. There is a deterministic, scale-invariant rule satisfying feasibility, EF1, and the stated PEF1 requirement. Its allocation has \(O(R+\tau m^2)\) rational intervals, with polynomial binary encoding length.
The construction combines simultaneous consumption—the idea underlying [probabilistic serial](https://www.sciencedirect.com/science/article/pii/S0022053100927108)—with deterministic rounding within each preference class. The proof below is self-contained.
Fix the class order \(1,\ldots,m\), used to break utility ties.
Write \(Q=\sum_{g=1}^m q_g\). If \(Q=0\), return the zero bundle everywhere. This satisfies all requirements. Henceforth assume \(Q>0\), and put \(K=\lceil Q\rceil\).
Introduce a dummy class \(d=m+1\), with supply \(\widehat q_d=K-Q\) and utility zero for every type. For real classes, put \(\widehat q_g=q_g\). Thus
\(\sum_{g=1}^{m+1}\widehat q_g=K.\)
Extend each utility vector to \(\widehat u_t=(u_t,0)\). Sort classes by decreasing utility, breaking ties by increasing class index. This gives a strict ordering, called the rank’s preference signature. Classes earlier in this ordering always have weakly greater utility.
Let \(\Sigma\) be the set of signatures present in the ordered utility function. For an ordered profile \(f\), define
\(A_\sigma^f=\{r:\text{the utility at }r\text{ has signature }\sigma\},\qquad \nu_\sigma=\lambda(A_\sigma^f).\)
There are at most \(\tau\) signatures. Each set \(A_\sigma^f\) is a finite union of rational intervals.
These definitions use only the ordered utility function. They do not distinguish utility-identical types by their labels. Profiles with the same utilities and type masses have the same signature masses \(\nu_\sigma\).
Initially, let the remaining supplies be \(z_g=\widehat q_g\).
While some supply remains, every signature \(\sigma\) selects its first class \(c_\sigma\) with positive remaining supply. All ranks with that signature consume this class at unit speed per rank. Consequently, class \(g\) is consumed at aggregate speed
\(v_g=\sum_{\sigma:c_\sigma=g}\nu_\sigma.\)
Since every rank selects one available class,
\(\sum_g v_g=1.\)
Keep these choices fixed for duration
\(\Delta=\min_{g:v_g>0}\frac{z_g}{v_g},\)
and update every remaining supply by \(z_g\leftarrow z_g-\Delta v_g\).
The duration is positive. All updated supplies are nonnegative, and at least one positive supply becomes zero. Therefore the process has at most \(m+1\) phases.
It continues until every supply is zero. Because the total consumption speed is one and the initial total supply is \(K\), its ending time is exactly \(K\).
Write the phase boundaries as
\(0=a_0<a_1<\cdots<a_H=K,\qquad H\leq m+1.\)
During phase \(h\), signature \(\sigma\) consumes a fixed class \(c_{\sigma,h}\). All boundaries are rational.
Suppose signature \(\sigma\) consumes class \(h\) at a time \(a\) strictly before a time \(b\) when some signature consumes class \(g\), with both times inside phases.
Class \(g\) has positive remaining supply at time \(b\). Since remaining supplies never increase, it was also available at time \(a\). Signature \(\sigma\) chose its favorite available class at time \(a\). Hence, for every original utility vector having signature \(\sigma\),
\(\widehat u_t(h)\geq\widehat u_t(g).\)
This observation will prove both fairness requirements.
Conceptually divide the consumption horizon into the \(K\) unit rounds \([j,j+1)\), where \(j=0,\ldots,K-1\).
For each signature, round, and class, define
\(p_{\sigma,j,g}=\sum_{h:c_{\sigma,h}=g}\lambda\bigl([a_{h-1},a_h)\cap[j,j+1)\bigr).\)
These quantities are nonnegative rational numbers, and
\(\sum_g p_{\sigma,j,g}=1.\)
We will assign every rank exactly one augmented item in every round, realizing these proportions within each signature class.
For \(r\in A_\sigma^f\), define its cumulative coordinate within that class:
\(\theta_\sigma^f(r)=\frac{\lambda(A_\sigma^f\cap[0,r))}{\nu_\sigma}.\)
For any \(0\leq x<y\leq1\),
\(\lambda\{r\in A_\sigma^f:\theta_\sigma^f(r)\in[x,y)\}=\nu_\sigma(y-x).\)
To verify this identity, list the component intervals of \(A_\sigma^f\) in increasing order. On each component, the numerator increases linearly with slope one. Its images are consecutive intervals partitioning \([0,\nu_\sigma)\), up to endpoints.
Put
\(P_{\sigma,j,g}=\sum_{\ell=1}^g p_{\sigma,j,\ell}.\)
At rank \(r\in A_\sigma^f\), assign in round \(j\) the class
\(c_j^f(r)=\min\{g:\theta_\sigma^f(r)<P_{\sigma,j,g}\}.\)
This is defined almost everywhere; endpoint values can be fixed arbitrarily. The cumulative-coordinate identity gives
\(\lambda\{r\in A_\sigma^f:c_j^f(r)=g\}=\nu_\sigma p_{\sigma,j,g}.\)
In particular, every class assigned on a set of positive measure has positive consumption duration for that signature in that round.
Let \(\widehat e_g\) denote the unit vector of augmented class \(g\). Define
\(\widehat B_f(r)=\sum_{j=0}^{K-1}\widehat e_{c_j^f(r)},\)
and obtain \(B_f(r)\) by deleting its dummy coordinate. Thus \(B_f(r)\) is an integer bundle.
Section 6 shows how to compute this allocation without enumerating the possibly enormous number \(K\) of rounds.
For every augmented class \(g\), the rounding identity implies
\(\int_0^1\widehat B_{f,g}(r)\,dr =\sum_{j=0}^{K-1}\sum_{\sigma\in\Sigma}\nu_\sigma p_{\sigma,j,g}.\)
Summing the intersection lengths over the unit rounds reconstructs each phase length. Therefore the right-hand side equals
\(\sum_{h=1}^H(a_h-a_{h-1})\sum_{\sigma:c_{\sigma,h}=g}\nu_\sigma.\)
This is exactly the total amount of class \(g\) consumed by the process, namely \(\widehat q_g\).
Deleting the dummy coordinate consequently gives
\(\int_0^1 B_{f,g}(r)\,dr=q_g\)
for every real class \(g\).
First establish an inequality that works across different ordered profiles.
Let \(f,f'\) have the same utilities, supplies, and type masses. They induce the same consumption process, because that process depends only on supplies and signature masses.
Fix ranks \(r,s\) outside the exceptional null sets. Let \(t=f(r)\). For each \(j=0,\ldots,K-2\), the class \(c_j^f(r)\) is consumed by \(r\)’s signature during a positive-duration part of \([j,j+1)\). Likewise, \(c_{j+1}^{f'}(s)\) is consumed during a positive-duration part of \([j+1,j+2)\).
Choose an interior consumption time for each of these classes. The first time is strictly earlier than the second. The earlier-choice observation from Section 2 gives
\(\widehat u_t(c_j^f(r))\geq\widehat u_t(c_{j+1}^{f'}(s)).\)
Summing these inequalities and using nonnegativity of the utility of \(r\)’s last item yields
\(\widehat u_t\cdot\widehat B_f(r) \geq \widehat u_t\cdot\widehat B_{f'}(s)-\widehat u_t(c_0^{f'}(s)).\)
For \(K=1\), the same inequality follows directly from nonnegativity, with the intermediate sum empty.
There are three cases:
\(u_t\cdot B_f(r)\geq u_t\cdot(B_{f'}(s)-e_g)\).
\(u_t\cdot B_f(r)\geq u_t\cdot B_{f'}(s)\).
If the comparison bundle is nonempty, removing any one of its real items preserves the required inequality, because utilities are nonnegative.
Thus, across any two such profiles, almost every pair of ranks satisfies
\(C_{f(r)}(B_f(r),B_{f'}(s)).\)
EF1. Take \(f'=f\). The preceding statement gives EF1 under product Lebesgue measure.
PEF1. Fix any measurable measure-preserving bijection \(\phi\) modulo null sets satisfying \(f'\circ\phi=f\) almost everywhere. The preceding proof works for every \(r,s\) outside individual null sets for \(f,f'\). Since \(\phi\) is measure-preserving, the preimage of the exceptional null set for \(f'\) is null. Taking \(s=\phi(r)\) therefore gives
\(C_{f(r)}(B_f(r),B_{f'}(\phi(r)))\)
for almost every \(r\), as required.
This verifies the quantifier over every admissible bijection.
The conceptual construction has \(K\) rounds, but only a polynomial number require explicit rounding.
Define the exceptional-round set
\(\mathcal E=\{\lfloor a_h\rfloor:1\leq h<H,\ a_h\notin\mathbb Z\}.\)
A round belongs to \(\mathcal E\) exactly when it contains a phase boundary in its interior. Multiple boundaries may lie in the same round. In particular,
\(|\mathcal E|\leq H-1\leq m.\)
Every other round lies entirely within one phase, up to endpoints. In such a round, all ranks of signature \(\sigma\) receive the fixed class \(c_{\sigma,h}\).
The number of whole unit rounds contained in phase \(h\) is
\(N_h=\max\{0,\lfloor a_h\rfloor-\lceil a_{h-1}\rceil\}.\)
Hence the allocation can be computed directly as
\(\widehat B_f(r) =\sum_{h=1}^H N_h\widehat e_{c_{\sigma(r),h}} +\sum_{j\in\mathcal E}\widehat e_{c_j^f(r)}.\)
The first sum consists of binary integer counts. Only the at most \(m\) exceptional rounds require cumulative-coordinate cuts.
For one signature and one exceptional round, there are at most \(m\) nontrivial cumulative thresholds. Each threshold introduces at most one new cut inside the signature’s component intervals: the cumulative coordinate traverses \([0,1)\) once as those intervals are scanned in order.
Thus there are at most \(|\Sigma|\,|\mathcal E|\,m\leq\tau m^2\) new cuts. Together with the original profile boundaries, this gives
\(O(R+\tau m^2)\)
allocation intervals. Their endpoints are rational.
A bound on the number of phases alone would not suffice; intermediate rational lengths must also be controlled.
Let \(D_\mu\) be a common denominator for the signature masses, and \(D_q\) a common denominator for the augmented supplies. Products of the corresponding input denominators provide choices whose binary lengths are polynomial in \(L\).
Every consumption speed has the form
\(v_g=\frac{A_g}{D_\mu},\qquad 0\leq A_g\leq D_\mu,\)
with integer \(A_g\).
Suppose current residual supplies have common denominator \(B\), and a minimizing class has residual \(n/B\) and positive speed \(A/D_\mu\). Then
\(\Delta=\frac{nD_\mu}{BA}.\)
For another class with speed \(A_g/D_\mu\), its consumed amount is
\(\Delta v_g=\frac{nA_g}{BA}.\)
Consequently, multiplying the current common denominator by \(A\) suffices for all new residual supplies and the new phase boundary. After at most \(m+1\) phases, a common denominator is bounded by
\(D_qD_\mu^{\,m+1}.\)
Its binary length is polynomial in \(m,L\). Residual supplies and phase times are bounded by \(K\), whose binary length is polynomial in \(L\). Their numerators therefore also have polynomial binary length.
Exceptional-round probabilities are sums of phase intersection lengths and have polynomial binary length. A cumulative-coordinate cut inside an original interval is found by multiplying its threshold by \(\nu_\sigma\), subtracting preceding component lengths, and adding the interval’s left endpoint. These operations preserve polynomial binary length.
Finally, every bundle coordinate is at most \(K\), so its binary encoding is polynomial.
There are polynomially many preference comparisons, phase computations, exceptional-round calculations, cuts, and bundle additions. All use exact arithmetic on numbers of polynomial binary length. The complete algorithm therefore runs in time polynomial in \(m,\tau,R,L\).
Multiplying the utility vector at any rank by a positive factor preserves its preference signature, including the fixed resolution of ties. Thus independent rank scaling preserves, almost everywhere:
The resulting allocation is unchanged almost everywhere. This argument also applies when scaling requires refining the utility-type support.
Equivalent interval encodings describe the same ordered utility function almost everywhere. They therefore give the same signature sets modulo null sets. Their cumulative measures agree at every rank, because changing a set on a null set does not change any prefix measure. The entire construction consequently gives the same allocation almost everywhere.
The rule observes only supplies, utilities, and rank coordinates. It uses no agent identities. Zero utilities and zero supplies were allowed throughout the argument.
⟨structured verdict parsed — rendered above⟩
The construction resolves the stated problem. Its fairness argument establishes a stronger comparison than required, and its compression avoids enumerating the potentially enormous number of rounds. I found no major or minor issues.
The case \(Q=0\) is handled correctly: nonnegative supplies then vanish individually, and the zero allocation satisfies feasibility, EF1, PEF1, and scale-invariance.
For \(Q>0\), the integer \(K=\lceil Q\rceil\) is positive, and the dummy supply \(K-Q\) is nonnegative. The augmented supplies sum to \(K\).
The fixed tie-breaking order makes each signature uniquely determined by the utility vector. Vectors sharing a signature need not have equal cardinal utilities; the argument uses only the weak utility comparisons implied by that signature.
Each signature mass is positive, since signatures are drawn from the positive-mass support. Thus division by \(\nu_\sigma\) in the cumulative coordinate is legitimate. Grouping utility-identical types or distinct types with the same signature is consistent with the requirement that the rule observe utilities without agent identities.
Whenever positive supply remains, every signature selects exactly one available class. Consequently, the aggregate consumption speeds sum to one.
At least one selected class has positive aggregate speed, so the minimum defining \(\Delta\) is over a nonempty set of positive ratios. The update preserves nonnegative supplies and exhausts at least one class. Exhausted classes never become available again. Therefore there are at most \(m+1\) phases.
Because the aggregate speed is one throughout, consuming all augmented supply takes exactly \(K\) units of time.
The earlier-choice observation is valid. A class available at a later interior time was available at every earlier time, because its remaining supply never increases. The earlier consumer’s selected class therefore has weakly greater utility for every utility vector with that consumer’s signature. Neither ties nor zero utilities invalidate this comparison.
The phase intersections partition each unit round, up to endpoints, so the probabilities are nonnegative and sum to one.
The cumulative-coordinate identity is justified by the component-interval calculation given in the output. Within each component, the unnormalized prefix measure increases with slope one; across components, its images concatenate into the interval of total signature mass. Normalizing gives the stated measure identity.
The threshold rule realizes precisely the prescribed proportions. Zero-probability classes cannot be selected away from exceptional endpoints: their cumulative thresholds do not increase.
Every selected class, outside the exceptional null set, therefore has a positive-duration consumption segment in its assigned round. This fact is essential to the subsequent fairness argument and is established here.
The conceptual allocation assigns exactly \(K\) augmented items to each nonexceptional rank. Although \(K\) may be large, it is finite, so the conceptual sums and unions of endpoint exceptions are finite.
The integral calculation is correct. Summing each class’s phase-intersection lengths over all unit rounds recovers its full consumption duration for every signature.
Multiplying those durations by signature masses and summing yields exactly the amount consumed by the process. Thus augmented supplies are realized exactly.
Deleting the dummy coordinate preserves each real class’s integral. The resulting allocation meets the task’s exact feasibility requirement.
For each \(j\) from \(0\) through \(K-2\), the first selected class is consumed during a positive-duration part of round \(j\), and the comparison class during a positive-duration part of round \(j+1\). Interior times can therefore be chosen with the first strictly earlier than the second.
The earlier-choice observation applies even when the comparison rank has a different signature. It gives exactly the pairwise utility inequalities asserted in the output.
Summation compares the first bundle’s items from rounds \(0\) through \(K-2\) with the second bundle’s items from rounds \(1\) through \(K-1\). Nonnegativity permits adding the first bundle’s final item, yielding the displayed inequality after removal of the second bundle’s initial augmented item.
For \(K=1\), the comparison bundle minus its initial augmented item is empty, so the stated inequality follows from nonnegativity.
The three cases translating augmented fairness into real-item EF1 are exhaustive and valid:
Taking the same profile on both sides establishes EF1.
Profiles with the same utilities, supplies, and type masses have identical signature masses and hence identical consumption processes.
The proof establishes its comparison for every pair of ranks outside separate null sets belonging to the two profiles. This is stronger than merely establishing a product-almost-everywhere statement. That distinction matters: a product-null exceptional set alone would not justify restricting the comparison to the graph of an arbitrary bijection.
Here the stronger assertion is explicitly justified by the rankwise rounding properties. For any admissible measure-preserving bijection, the preimage of the second profile’s exceptional null set is null. The first profile’s exceptional set is also null. The comparison consequently holds almost everywhere after substituting \(s=\phi(r)\).
Thus the proof verifies the requirement for every admissible bijection, with the correct order of quantifiers.
The exceptional-round set identifies exactly the rounds containing a noninteger phase boundary in their interior. There are at most \(H-1\), hence at most \(m\), such rounds.
The formula for \(N_h\) correctly counts unit rounds wholly contained in phase \(h\), including phases with integer endpoints and phases containing no complete round.
Every round is accounted for either by one whole-phase count or by the exceptional-round sum. There is no omission or double counting.
With \(m+1\) augmented classes, each exceptional round contributes at most \(m\) internal cumulative thresholds per signature. Each threshold produces at most one new cut as the signature’s components are traversed in order. Together with the original boundaries, this gives the asserted allocation-interval bound.
The compressed formula produces the same bundle vectors as the conceptual construction, using binary counts for the whole rounds.
The proposed common denominators have polynomial binary length.
The denominator update is valid. With residual denominator \(B\) and selected speed numerator \(A\), all new residuals have denominator dividing \(BA\). The phase time is also controlled: elapsed time equals \(K\) minus total remaining augmented supply, so a common residual denominator controls the phase boundary as well.
Each selected numerator satisfies \(1\leq A\leq D_\mu\). Therefore, after at most \(m+1\) phases, the maintained denominator is bounded by \(D_qD_\mu^{m+1}\), whose binary length is polynomial.
Supplies, phase times, probabilities, thresholds, interval endpoints, and bundle coordinates all have polynomial binary length under the stated calculations. The number of required operations is polynomial, and the algorithm never enumerates all \(K\) rounds.
The claimed polynomial running time and polynomial output encoding length follow.
Positive rankwise scaling preserves utility comparisons and ties, including for zero vectors. Hence it preserves signatures, signature sets, their masses, the consumption process, cumulative coordinates, and rounded allocations almost everywhere.
Refinement of the type support does not affect this reasoning because the rule depends on signatures and their rank sets.
Equivalent interval encodings change those sets only on null sets. Their prefix measures consequently agree at every coordinate, and allocations agree almost everywhere. The construction therefore satisfies both encoding independence and the prohibition on using agent identities.
No external theorem is needed for the proof: the probabilistic-serial reference supplies context, while the operative claims are justified within the output.
No additional clarification, lemma, or correction is required.
⟨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.