Answer: —
Theorem 1 — class: algorithmic
Given a number-equivalent population scale \(N\), \(d\) good categories with \(Nq_g\) integral copies of category \(g\), a rational type distribution \(\mu\) over \(\tau\) complete valuation types, and monotone subadditive valuations \(v_t(b)\) on integral bundles \(b\), characterize the worst-case ratio between unrestricted maximum welfare and maximum EF1 welfare, and determine the complexity of computing a maximum-welfare EF1 allocation. In the mass model, variables \(x_{t,b}\ge 0\) satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\); EF1 must hold between every pair of positive-mass type-bundle configurations. Give the price and algorithmic bounds in \(N,d,\tau\), and input bit length \(L\), for scaled and unscaled valuations.
Inputs are integers \(N\geq1\), \(d\geq1\), positive rational supplies \(q_g\) with integral \(C_g=Nq_g\), and \(m=\sum_g C_g\) total copies; copies within a category are interchangeable. Bundles belong to \(B=\prod_{g=1}^d\{0,\ldots,C_g\}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\sum_t\mu_t=1\), and \(\tau\) is the support size, not the number of possible types; no integrality of \(N\mu_t\) is required.
Each type has a complete table of binary rational values \(v_t:B\to\mathbb{Q}_{\geq0}\), with \(v_t(0)=0\), inducing a monotone subadditive valuation on the copies. Scaled means \(v_t(C)=1\) for every type; unscaled imposes no common scale. Let \(L\) be the total input bit length, including these tables.
An allocation consists of real masses \(x_{t,b}\geq0\) satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\) for every category. It is EF1 if, for every pair \((t,b),(s,c)\) with positive mass and \(c\neq0\), some category \(g\) with \(c_g>0\) satisfies \(v_t(b)\geq v_t(c-e_g)\), where \(e_g\) is the unit vector.
Define \(W(x)=\sum_{t,b}x_{t,b}v_t(b)\), and let \(U\) and \(F\) be its unrestricted and EF1 maxima. The EF1 price is the supremum of \(U/F\) over instances with \(U>0\), taken separately for scaled and unscaled valuations; set the ratio to \(+\infty\) if no positive-welfare EF1 allocation exists.
What are the tight worst-case EF1 prices and the best polynomial-time factors \(\alpha\) for computing an EF1 allocation with \(W(x)\geq U/\alpha\), for scaled and unscaled valuations? State bounds and running times in \(N,m,d,\tau,L\).
For finite societies of \(n\) agents, the EF1 prices are \(\Theta(\sqrt n)\) when scaled and \(\Theta(n)\) when unscaled, even with additive lower bounds; polynomial-time algorithms attain the corresponding welfare guarantees with demand-oracle access to subadditive valuations. [Source](https://www.cs.toronto.edu/~nisarg/papers/price-of-fairness.pdf)
No result settling this precise mass model was located.
The full question remains unresolved for arbitrary dimension. However, the gap identified in the notes can be closed for all instances with $d\leq2$, including nonintegral supplies and arbitrary rational type masses.
Write
$$
E=\min\{N,m\}.
$$
The following bounds are proved below.
| Regime | Scaled price | Unscaled price | Polynomial-time welfare factors |
|---|---:|---:|---|
| $m\leq N$, arbitrary $d$ | $\Theta(\sqrt m)$ | $\Theta(m)$ | $\sqrt m$ and $m$ |
| $d\leq2$, arbitrary supplies | $\Theta(\sqrt E)$ | $\Theta(E)$ | $O(\sqrt E)$ and $E$ |
| Arbitrary $d$ satisfying either rounding condition below | Upper bound proved below | $\Theta(E)$ over this family | Explicit scaled factor below; unscaled factor $E$ |
| Every $q_g$ integral | Tight scaled order still open in unbounded dimension | Exact supremum $N$ | $\min\{N,1+\sqrt{dN}\}$ and $N$ |
The lower bounds in the first two rows use two types. All the displayed approximation algorithms run in $\operatorname{poly}(L)$ bit time. Their allocation LPs have $O(\tau d)$ variables.
There is also an exact algorithm for arbitrary instances taking
$$
|B|^\tau\operatorname{poly}(L)
$$
time. It determines EF1 feasibility and, when feasible, computes $F$.
The two rounding conditions are
$$
R:=\sum_g\bigl(q_g-\lfloor q_g\rfloor\bigr)\leq1
$$
and
$$
H:=\sum_g\bigl(\lceil q_g\rceil-q_g\bigr)\leq1.
$$
The second condition supplies the new construction needed to cover all two-category instances.
If the supremum in the question is taken over unrestricted values of all parameters, both global prices are infinite. The results here address the intended parameter-dependent question.
For a bundle $b$, write
$$
|b|=\sum_g b_g.
$$
Subadditivity on copies implies, whenever $b+c\leq C$ coordinatewise,
$$
v_t(b+c)\leq v_t(b)+v_t(c).
$$
In particular,
$$
v_t(b)\leq\sum_g b_gv_t(e_g).
$$
For scaled valuations, monotonicity also gives
$$
0\leq v_t(b)\leq1.
$$
An unrestricted feasible allocation always exists: give each type a fraction $1/N$ of its mass bundle $C$, and the remaining mass bundle $0$. When $N=1$, feasibility forces every supported bundle to equal $C$, because its average equals the coordinatewise upper bound. Thus both prices equal $1$ when $N=1$.
We subsequently allow arbitrary positive rational masses $\mu_t$. No argument requires $N\mu_t$ to be integral.
Let
$$
K=|B|=\prod_g(C_g+1).
$$
For each type, define
$$
r_t(0)=0,\qquad
r_t(c)=\min_{g:c_g>0}v_t(c-e_g)
\quad\text{for }c\neq0.
$$
The EF1 requirement is equivalent to
$$
v_t(b)\geq r_t(c)
$$
for every supported own bundle $(t,b)$ and every supported comparison bundle $c$.
Let
$$
V_t=\{v_t(b):b\in B\}.
$$
For each vector $a\in\prod_t V_t$, consider the allocation LP that permits a variable $x_{s,c}$ only when
$$
v_s(c)\geq a_s
\quad\text{and}\quad
r_t(c)\leq a_t\quad\text{for every }t.
$$
Its remaining constraints are the type-mass and supply equalities from the question.
Claim. The EF1 feasible set is exactly the union of these LP feasible sets.
Proof. Every allocation in a threshold LP is EF1, since a supported own bundle has value at least $a_t$, whereas every supported comparison bundle has removal value at most $a_t$.
Conversely, suppose $x$ is EF1. Positive type masses ensure that every type has nonempty support. Set
$$
a_t=\min_{b:x_{t,b}>0}v_t(b).
$$
This minimum belongs to $V_t$. Every supported own bundle satisfies the first restriction, and EF1 gives the second restriction for every supported comparison bundle. Hence $x$ belongs to this threshold LP. $\square$
Each LP feasible set is a compact rational polytope: every variable lies between $0$ and its type mass. Therefore the EF1 feasible set is compact, and $F$ is attained whenever it is feasible.
An optimal basic solution of an optimal threshold LP has at most $\tau+d$ positive variables, since there are $\tau+d$ equality constraints. Its rational encoding length is polynomial in $L$, by the determinant bounds for rational linear systems.
Precomputing all $r_t(c)$ requires $O(\tau Kd)$ table accesses. There are at most $K^\tau$ threshold vectors. Thus exact optimization takes
$$
K^\tau\operatorname{poly}(L)
$$
time. The complete-table representation ensures $\tau K=O(L)$. In particular, this algorithm is polynomial-time for fixed $\tau$.
The unrestricted optimum $U$ is computable by one rational allocation LP in $\operatorname{poly}(L)$ time.
Define
$$
r_g=\lfloor q_g\rfloor,\qquad
f_g=q_g-r_g,\qquad
R=\sum_g f_g.
$$
Assume $R\leq1$.
Restrict allocations to bundles
$$
r,\qquad r+e_g\quad\text{for }f_g>0.
$$
Let $y_{t,g}$ denote type-$t$ mass receiving $r+e_g$. The allocation LP is
$$
\sum_t y_{t,g}=f_g,\qquad
\sum_g y_{t,g}\leq\mu_t,\qquad
y_{t,g}\geq0,
$$
with remaining type mass receiving $r$. Maximize the actual welfare of this allocation. Denote its optimum by $W_\downarrow$.
The LP is feasible because $y_{t,g}=\mu_t f_g$ satisfies its constraints.
Every allowed bundle contains $r$. If the comparison bundle is $r+e_g$, deleting its extra copy leaves $r$, whose value is no greater than the recipient’s own value. If the comparison bundle is $r$, monotonicity gives the same conclusion after deleting any available copy. Thus every feasible solution of this LP is EF1.
Furthermore,
$$
Nf_g=C_g-Nr_g
$$
is an integer, and
$$
\sum_g Nf_g=NR\leq N.
$$
Consequently, $C$ can be partitioned into $N$ bundles, each equal to $r$ or to $r+e_g$: begin with $N$ copies of $r$ and distribute the remaining copies into distinct bundles.
For each type, subadditivity applied to this partition gives
$$
v_t(C)\leq
N\left((1-R)v_t(r)+\sum_g f_gv_t(r+e_g)\right).
$$
The expression in parentheses is exactly that type’s expected value under the feasible independent assignment $y_{t,g}=\mu_t f_g$. Hence
$$
W_\downarrow\geq\frac1N\sum_t\mu_t v_t(C).
$$
Since
$$
U\leq\sum_t\mu_t v_t(C),
$$
we obtain
$$
W_\downarrow\geq U/N.
$$
In the scaled case, this also proves
$$
W_\downarrow\geq1/N.
$$
The partition into $N$ bundles is only a proof device; the algorithm does not enumerate these bundles.
Define
$$
G_+=\{g:r_g\geq1\},\qquad
G_0=\{g:r_g=0\},
$$
and
$$
m_0=\sum_{g\in G_0}C_g,\qquad
D_\downarrow=\sum_{g\in G_+}\frac{q_g}{r_g}.
$$
An empty sum is zero.
Set
$$
a_t=v_t(r),\qquad A=\sum_t\mu_ta_t.
$$
Every allowed bundle contains $r$, so
$$
W_\downarrow\geq A.
$$
Split an unrestricted bundle $b$ into its $G_+$ and $G_0$ parts, denoted $b^+$ and $b^0$.
For $b^+$, put
$$
z(b)=\max_{g\in G_+}\frac{b_g}{r_g},
$$
with $z(b)=0$ if $G_+$ is empty. Partitioning $b^+$ into at most $\lceil z(b)\rceil$ bundles bounded coordinatewise by $r$ gives
$$
v_t(b^+)\leq(1+z(b))a_t.
$$
Together with $v_t(b^+)\leq1$, this implies
$$
v_t(b^+)
\leq a_t+\min\{1,z(b)a_t\}
\leq a_t+\sqrt{z(b)a_t}.
$$
For an unrestricted optimum $x$, the supply equalities give
$$
\sum_{t,b}x_{t,b}z(b)
\leq\sum_{g\in G_+}\frac{q_g}{r_g}
=D_\downarrow.
$$
Weighted Cauchy–Schwarz therefore yields
$$
U_+:=\sum_{t,b}x_{t,b}v_t(b^+)
\leq A+\sqrt{D_\downarrow A}.
$$
We next bound
$$
U_0:=\sum_{t,b}x_{t,b}v_t(b^0).
$$
Let $S_0$ be the optimal singleton welfare using just the supplies in $G_0$, with type capacities $\mu_t$. These supplies have total mass
$$
\sum_{g\in G_0}q_g=m_0/N\leq R\leq1.
$$
For every nonempty $b^0$, distribute mass $x_{t,b}$ among its singleton categories in proportions $b_g/|b^0|$. Subadditivity shows that the resulting singleton welfare is at least
$$
J_0:=\sum_{t,b:b^0\neq0}
x_{t,b}\frac{v_t(b^0)}{|b^0|}.
$$
This assignment respects type capacities and does not exceed any category supply. It can be completed to a full singleton assignment: its remaining supply mass is no greater than its remaining type capacity, because the total singleton supply is at most $1$.
Weighted Cauchy–Schwarz gives
$$
U_0^2
\leq J_0
\sum_{t,b}x_{t,b}v_t(b^0)|b^0|
\leq J_0\,m_0/N.
$$
Thus, when $m_0>0$,
$$
S_0\geq NU_0^2/m_0.
$$
When $m_0=0$, simply $U_0=0$.
Any feasible $G_0$ singleton assignment can be extended to the downward-rounding LP by assigning the remaining extra-copy supplies within the remaining type capacities. The total extra-copy supply is at most $1$. Moreover,
$$
v_t(r+e_g)\geq v_t(e_g).
$$
Consequently,
$$
W_\downarrow\geq S_0,
\qquad
U_0\leq\sqrt{(m_0/N)W_\downarrow}.
$$
Subadditivity gives $U\leq U_++U_0$. Combining the bounds,
$$
U\leq
W_\downarrow+
\left(\sqrt{D_\downarrow}+\sqrt{m_0/N}\right)
\sqrt{W_\downarrow}.
$$
Using $W_\downarrow\geq1/N$, we obtain the factor
$$
\boxed{
\alpha_\downarrow
=
\min\left\{
N,\,
1+\sqrt{ND_\downarrow}+\sqrt{m_0}
\right\}.
}
$$
For reference,
$$
ND_\downarrow
=\sum_{g\in G_+}\frac{C_g}{r_g}
\leq m-m_0,
$$
and $D_\downarrow\leq2|G_+|$. Therefore
$$
\alpha_\downarrow
\leq
\min\{N,\ 1+\sqrt{2m},\
1+\sqrt{2N|G_+|}+\sqrt N\}.
$$
Define
$$
s_g=\lceil q_g\rceil,\qquad
h_g=s_g-q_g,\qquad
H=\sum_g h_g.
$$
Assume $H\leq1$.
Restrict allocations to
$$
s,\qquad s-e_g\quad\text{for }h_g>0.
$$
These are valid bundles: $1\leq s_g\leq C_g$.
Let $y_{t,g}$ be type-$t$ mass receiving $s-e_g$. Use the LP
$$
\sum_t y_{t,g}=h_g,\qquad
\sum_g y_{t,g}\leq\mu_t,\qquad
y_{t,g}\geq0,
$$
with the remaining mass receiving $s$. Maximize its welfare and call the optimum $W_\uparrow$. The independent assignment $y_{t,g}=\mu_t h_g$ proves feasibility.
Consider own bundle $s-e_g$ and comparison bundle $s-e_j$.
If $g\neq j$, deleting a copy of category $g$ from the comparison bundle leaves
$$
s-e_j-e_g\leq s-e_g.
$$
If $g=j$, the bundles are equal. Comparing $s-e_g$ with $s$ is resolved by deleting category $g$. An own bundle $s$ weakly dominates every other allowed bundle. Monotonicity therefore proves EF1 for every feasible LP solution.
Also,
$$
Nh_g=Ns_g-C_g
$$
is integral, and $\sum_g Nh_g\leq N$. Starting with $N$ copies of $s$, omit the required copies from distinct bundles. The resulting $N$ bundles partition $C$.
Subadditivity, exactly as in the downward construction, proves
$$
W_\uparrow
\geq\frac1N\sum_t\mu_t v_t(C)
\geq U/N.
$$
For scaled valuations,
$$
W_\uparrow\geq1/N.
$$
There is at most one category satisfying
$$
s_g=1,\qquad q_g<1/2,
$$
because such a category has $h_g>1/2$, whereas $H\leq1$. Call this category exceptional if it exists.
First suppose there is no exceptional category. We prove that the independent assignment gives each type expected value at least $v_t(s)/2$.
Fix a type and write
$$
V=v_t(s),\qquad a_g=v_t(s-e_g).
$$
For distinct categories $g,j$, subadditivity and monotonicity imply
$$
V\leq a_g+a_j,
$$
because $(s-e_g)+e_g=s$ and $e_g\leq s-e_j$.
Furthermore, if $s_g\geq2$, then $e_g\leq s-e_g$, so
$$
V\leq a_g+v_t(e_g)\leq2a_g.
$$
If every omitted-bundle value is at least $V/2$, the independent expected value is at least
$$
(1-H)V+HV/2\geq V/2.
$$
Otherwise choose a minimum-value omission $j$ with $a_j<V/2$. The preceding inequality forces $s_j=1$. Absence of an exceptional category then gives $h_j\leq1/2$.
For every other omission, $a_g\geq V-a_j$. Hence the independent expected value is at least
$$
(1-h_j)V+(2h_j-H)a_j.
$$
If $2h_j-H\geq0$, this is at least $(1-h_j)V\geq V/2$. If $2h_j-H<0$, using $a_j<V/2$ bounds it below by
$$
(1-H/2)V\geq V/2.
$$
This proves the claim.
Consequently, in this case, with
$$
u=s,\qquad A=\sum_t\mu_t v_t(u),
$$
we have
$$
W_\uparrow\geq A/2.
$$
If an exceptional category $g_*$ exists, instead set
$$
u=s-e_{g_*},\qquad
A=\sum_t\mu_t v_t(u).
$$
The independent assignment gives bundle $u$ with probability $h_{g_*}>1/2$, so again
$$
W_\uparrow\geq A/2.
$$
If no exceptional category exists, let
$$
D_\uparrow=\sum_g q_g/s_g,\qquad m_0=0.
$$
If an exceptional category exists, let
$$
D_\uparrow=\sum_{g\neq g_*}q_g/s_g,\qquad
m_0=C_{g_*}.
$$
On the coordinates present in $u$, the partition and Cauchy–Schwarz argument from Section 3 gives
$$
U_+\leq A+\sqrt{D_\uparrow A}
\leq2W_\uparrow+\sqrt{2D_\uparrow W_\uparrow}.
$$
It remains to justify the exceptional-coordinate bound when $g_*$ exists. Put $q_*=q_{g_*}<1/2$. Any singleton assignment of this category has type masses $z_t$ satisfying
$$
0\leq z_t\leq\mu_t,\qquad \sum_tz_t=q_*.
$$
It can be realized inside the upward-rounding construction:
This is possible because
$$
\sum_{g\neq g_*}h_g
=H-h_{g_*}
\leq1-h_{g_*}
=q_*.
$$
Every bundle allocated to the masses $z_t$ contains one copy of $g_*$. Therefore the optimized upward-rounding welfare is at least the optimal singleton welfare of this category.
The singleton extraction calculation from Section 3 now gives
$$
U_0\leq\sqrt{(m_0/N)W_\uparrow}.
$$
In the nonexceptional case, $U_0=0$.
Combining these estimates and using $W_\uparrow\geq1/N$ proves
$$
\boxed{
\alpha_\uparrow
=
\min\left\{
N,\,
2+\sqrt{2ND_\uparrow}+\sqrt{m_0}
\right\}.
}
$$
Here $D_\uparrow\leq d$, and $ND_\uparrow\leq m-m_0$. Thus
$$
\alpha_\uparrow
\leq
\min\{N,\ 2+\sqrt{3m},\
2+\sqrt{2dN}+\sqrt N\}.
$$
Let $k$ be the number of nonintegral supplies. Then
$$
R+H=k.
$$
If $d\leq2$, we have $k\leq2$, so at least one of $R\leq1$ and $H\leq1$ holds.
Therefore every two-category instance admits an EF1 allocation, and the constructions give
$$
W\geq U/N
$$
for unscaled valuations.
For scaled valuations, the bounds above give the simple uniform factor
$$
\min\{N,\ 2+3\sqrt N\}.
$$
When $m\leq N$, the stronger singleton bounds proved next apply. Combining regimes yields factors
$$
O(\sqrt E)\quad\text{and}\quad E
$$
for scaled and unscaled valuations, respectively.
If every supply is integral, the downward construction has only the bundle $q$. Its unscaled guarantee is $N$. In its scaled bound,
$$
m_0=0,\qquad D_\downarrow=d,
$$
giving
$$
\min\{N,1+\sqrt{dN}\}.
$$
The unscaled supremum for any fixed positive integral supply vector is exactly $N$. To prove the lower bound, use valuations depending only on the first category:
$$
v_H(b)=Mb_1,\qquad v_L(b)=b_1,
$$
with masses $1/N$ and $1-1/N$, where $N\geq2$.
The unrestricted optimum is $Mq_1$. Strict increase in the first-coordinate count forces all supported first-coordinate counts in an EF1 allocation to differ by at most one. Since their average $q_1$ is integral, they must all equal $q_1$. Thus
$$
F=q_1\left(M/N+1-1/N\right),
$$
and
$$
\frac UF
=\frac{M}{M/N+1-1/N}\longrightarrow N.
$$
Other categories can be allocated at their common integral supplies and contribute zero value.
An allocation supported on empty bundles and singletons is automatically EF1. Its optimal welfare $S$ is given by
$$
\max\sum_{t,g}y_{t,g}v_t(e_g)
$$
subject to
$$
\sum_g y_{t,g}\leq\mu_t,\qquad
\sum_t y_{t,g}=q_g,\qquad
y_{t,g}\geq0.
$$
It is feasible because $y_{t,g}=\mu_tq_g$ and $\sum_gq_g=m/N\leq1$.
Given an unrestricted optimum, extract singleton masses from every nonempty bundle in proportions $b_g/|b|$. The resulting welfare is at least
$$
J=\sum_{t,b\neq0}x_{t,b}\frac{v_t(b)}{|b|}.
$$
The extracted assignment can be completed, by the same residual-capacity argument used in Section 3. Hence $S\geq J$.
Since $|b|\leq m$,
$$
S\geq U/m.
$$
For scaled valuations, weighted Cauchy–Schwarz gives
$$
U^2
\leq J\sum_{t,b\neq0}x_{t,b}v_t(b)|b|
\leq Jm/N.
$$
Also, the independent singleton assignment has welfare
$$
\frac1N\sum_t\mu_t\sum_g C_gv_t(e_g)
\geq\frac1N\sum_t\mu_t v_t(C)
=\frac1N.
$$
Thus
$$
S\geq\max\{1/N,\ NU^2/m\}\geq U/\sqrt m.
$$
This establishes the advertised factors $m$ and $\sqrt m$.
It suffices first to use one category, with $C=m$ and $q=C/N$.
For $N\geq2$, use masses $1/N$ and $1-1/N$ and valuations
$$
v_H(b)=Mb,\qquad v_L(b)=b.
$$
Giving all $C$ copies to the high type uses exactly supply $q$, so
$$
U=Mq.
$$
Let $h$ be the smallest supported bundle size in any EF1 allocation. Strict increase implies every supported size is at most $h+1$. Since the average is $q$, every supported size is at most $\lceil q\rceil$. For integral $q$, the average additionally forces every supported size to equal $q$.
It follows that
$$
F\leq\frac{M}{N}\lceil q\rceil+q.
$$
Letting $M$ increase through positive integers gives the price lower bound
$$
\frac{C}{\lceil C/N\rceil}.
$$
This equals $m$ when $m\leq N$ and is at least $N/2$ when $m\geq N$.
Thus the unscaled lower bound is $\Omega(E)$.
Choose an integer $K$ satisfying $q<K\leq C$, and use
$$
v_H(b)=\min\{b/K,1\},\qquad
v_L(b)=b/C,
$$
with high-type mass
$$
\delta=q/K.
$$
These valuations are monotone, subadditive, and scaled.
Giving bundle $K$ to all high-type mass and zero to the low type is feasible. Both valuations are bounded above by $b/K$, so
$$
U=q/K.
$$
In an EF1 allocation, the minimum supported size $h$ satisfies $h\leq q<K$. Whichever type receives size $h$, its valuation is strictly increasing below that level’s cap. Consequently every supported size is at most $h+1$, and hence at most $\lceil q\rceil$.
If $C\leq N$ and $C\geq4$, choose $K=\lfloor\sqrt C\rfloor$. EF1 allocations then use only sizes zero and one; when $q=1$, only size one occurs. Assigning singletons first to all high-type mass gives
$$
F=\delta/K+(q-\delta)/C.
$$
Therefore
$$
\frac UF
=\frac{CK}{C+K^2-K}
\geq K/2
\geq\sqrt C/4.
$$
If $C\geq N$ and $N\geq4$, choose
$$
K=\lceil q\sqrt N\rceil.
$$
This satisfies $q<K\leq C$. Since all supported sizes are at most $\lceil q\rceil$,
$$
F\leq
\delta\frac{\lceil q\rceil}{K}+\frac qC
\leq\frac{q(q+1)}{K^2}+\frac1N
\leq\frac3N.
$$
Also,
$$
U=q/K\geq\frac1{\sqrt N+1}.
$$
Hence
$$
\frac UF
\geq\frac{N}{3(\sqrt N+1)}
\geq\frac{\sqrt N}{6}.
$$
The remaining bounded values of $E$ are covered by the elementary lower bound $1$.
Thus the scaled lower bound is $\Omega(\sqrt E)$.
For fixed $d=2$ and $m\geq2$, take
$$
C_1=m-1,\qquad C_2=1,
$$
and let both valuations depend only on the first category. The one-category welfare calculations remain valid.
To allocate the second category, split every supported mass into fractions $1/N$ receiving its additional copy and $1-1/N$ receiving none. This preserves EF1: if a comparison bundle has positive first-coordinate count, use its first-category EF1 removal; otherwise its value is zero.
Moreover,
$$
\min\{N,m-1\}\geq\frac12\min\{N,m\}.
$$
Thus the same asymptotic lower bounds hold for fixed $d=2$.
Together with the upper bounds, this proves the tight prices
$$
\boxed{
\Theta(\sqrt E)\text{ scaled},\qquad
\Theta(E)\text{ unscaled}
}
$$
for $d=1$ and $d=2$.
These lower bounds constrain every algorithm, regardless of running time, because its EF1 welfare cannot exceed $F$. Therefore the polynomial-time factors above are optimal in asymptotic order in these regimes.
The singleton, downward-rounding, and upward-rounding algorithms each use a rational LP with at most $\tau(d+1)$ allocation variables and $\tau+d$ equality constraints. Their coefficients come directly from the input and a polynomial number of table lookups. They run in $\operatorname{poly}(L)$ bit time and can return rational allocations with at most $\tau+d$ positive entries.
No algorithm iterates over $N$ agents or uses a common denominator of the type masses. Thus the running times remain polynomial even when $N$ or the mass denominators are large in binary encoding. In particular, they are polynomial in $N,m,d,\tau,L$ as requested.
The scaled one-category lower-bound tables have encoding length
$$
O(m\log(m+1)+\log N).
$$
For the unscaled constructions, if $\ell(M)$ denotes the binary encoding length of $M$, a sufficient bound is
$$
O\!\left(m(\log(m+1)+\ell(M))+\log N\right).
$$
This includes the scale parameter omitted from the previous notes.
For arbitrary dimension, the two rounding constructions establish positive-welfare EF1 existence whenever
$$
R\leq1\quad\text{or}\quad H\leq1.
$$
Their unscaled factor is $N$, improved to $m$ when $m\leq N$. Over this family, the one-category examples prove the tight unscaled order $\Theta(E)$.
Outside this family, the first unresolved cases have at least three nonintegral coordinates and satisfy
$$
d\geq3,\qquad m>N,\qquad R>1,\qquad H>1.
$$
No universal existence or welfare guarantee for these cases is proved here.
Even inside the rounding family, the tight scaled dependence for unbounded $d$ remains open. This includes integral supplies: the proved factor $\min\{N,1+\sqrt{dN}\}$ need not match the lower bounds established here. The [finite-agent theorem of Barman, Bhaskar, and Shah](https://www.cs.toronto.edu/~nisarg/papers/price-of-fairness.pdf) provides useful context, but none of the proofs above assumes a transfer of that theorem to arbitrary type masses.
⟨structured verdict parsed — rendered above⟩
Result: partial. The special-case proofs are correct as written. They establish the claimed welfare guarantees and tight asymptotic prices for $d\leq2$, as well as the additional stated subclasses. They do not settle USER_TASK for arbitrary dimension. I found no false central step or substantive mathematical gap in the special-case arguments.
The incompleteness is explicitly acknowledged by the prover; it is not an undisclosed failure of the proofs.
The bundle inequalities follow from the stipulated monotone subadditive valuation on copies. In particular, repeated subadditivity applies to a partition of any bundle into its individual copies.
The unrestricted feasible allocation has
$$
x_{t,C}=\mu_t/N,\qquad x_{t,0}=\mu_t(1-1/N),
$$
and satisfies every supply equality because $C_g/N=q_g$.
For $N=1$, every coordinate has average $C_g$ and is bounded above by $C_g$. Consequently, every positive-mass bundle equals $C$. Such an allocation is EF1 by monotonicity. The price is therefore $1$ whenever $U>0$, including in the unscaled case.
Assessment: correct, including the boundary case $N=1$.
For a nonempty comparison bundle $c$, the existential EF1 removal condition is precisely
$$
v_t(b)\geq \min_{g:c_g>0}v_t(c-e_g)=r_t(c).
$$
Assigning $r_t(0)=0$ introduces no extra restriction because valuations are nonnegative.
Both directions of the threshold characterization are valid:
There are finitely many threshold vectors. Each associated feasible set is a bounded, closed rational polytope. Thus their union is compact, and an EF1 welfare maximum exists whenever the union is nonempty.
The sparsity and encoding claims are also valid. A basic feasible solution has at most $\tau+d$ positive variables; redundant equalities can only reduce this bound. Rational coefficients of polynomial encoding length give polynomial-size basic solutions.
Since the complete tables imply $\tau K=O(L)$, constructing and solving each threshold LP costs $\operatorname{poly}(L)$ bit time. Enumeration therefore gives
$$
K^\tau\operatorname{poly}(L),
$$
which is polynomial for fixed $\tau$. The unrestricted optimization is one polynomial-size rational LP.
Assessment: correct. This is an exact algorithm, but not a general polynomial-time algorithm when $\tau$ varies.
The independent assignment is feasible because
$$
\sum_g\mu_t f_g=\mu_t R\leq\mu_t.
$$
Every allowed bundle is valid: an extra copy is included only where $q_g$ is nonintegral, so $r_g+1\leq C_g$.
The EF1 proof checks every comparison form. Removing the extra copy from $r+e_g$ leaves $r$. For a nonempty comparison bundle $r$, any removal leaves a bundle coordinatewise bounded by every allowed own bundle. Empty comparison bundles require no check.
The partition argument is valid because the residual counts $Nf_g$ are nonnegative integers with total at most $N$. Subadditivity applied to that partition proves the independent assignment’s welfare bound, and hence
$$
W_\downarrow\geq U/N.
$$
When $U>0$, this also proves positive EF1 welfare.
For the scaled argument:
Consequently, the displayed factor
$$
\alpha_\downarrow=
\min\left\{N,1+\sqrt{ND_\downarrow}+\sqrt{m_0}\right\}
$$
is justified. The subsequent simplifications of its constants and ranges are correct.
Assessment: correct under the explicitly stated hypothesis $R\leq1$.
The allowed bundles are valid because positive supplies and integral $C_g=Nq_g$ imply
$$
1\leq s_g\leq C_g.
$$
The independent assignment is feasible under $H\leq1$.
The EF1 case analysis is sound. When distinct omissions are compared, the copy selected for deletion exists: if $g\neq j$, category $g$ still has $s_g\geq1$ copies in $s-e_j$. Equal nonempty bundles satisfy EF1 by monotonicity; empty comparisons are exempt.
The partition argument is valid because all omission counts $Nh_g$ are integers and their total is at most $N$. It establishes the claimed unscaled and scaled baseline guarantees.
The independent-assignment value comparison also checks out:
In the exceptional case, its omission occurs with probability greater than $1/2$, establishing the claimed bound for $u=s-e_{g_*}$.
The exceptional-coordinate singleton embedding is feasible. The masses $z_t$ have total $q_*$, and all other omissions have total at most $q_*$. Those masses can therefore accommodate the other omissions, and every resulting bundle contains the exceptional copy.
The ensuing bounds justify
$$
\alpha_\uparrow=
\min\left\{N,2+\sqrt{2ND_\uparrow}+\sqrt{m_0}\right\}.
$$
The displayed simplified bounds, including $2+\sqrt{3m}$, have the stated constants.
Assessment: correct under $H\leq1$.
Each nonintegral coordinate contributes exactly $1$ to $R+H$, while each integral coordinate contributes zero. Thus
$$
R+H=k.
$$
For $d\leq2$, both rounding sums cannot exceed $1$. The coverage argument is therefore valid.
The combination with the singleton regime gives the advertised factors $O(\sqrt E)$ and $E$, where $E=\min\{N,m\}$.
For integral supplies, the downward construction uses only $q$, and its scaled and unscaled guarantees specialize as claimed.
The fixed-integral-supply unscaled lower bound is valid. Both types have strictly increasing values in the first coordinate. EF1 forces all supported first-coordinate counts to differ by at most one, even though the valuations ignore other categories. Removing a different category cannot reduce the first-coordinate value.
An integral average then forces the supported first-coordinate counts to be identical. The stated expression for $F$ and its limiting ratio are correct.
Assessment: correct. The exact unscaled supremum $N$ is established for each fixed positive integral supply vector.
The singleton LP is feasible when $m\leq N$, and every feasible singleton allocation is EF1.
The extraction and completion argument correctly gives $S\geq J$. Since each nonempty bundle has size at most $m$,
$$
S\geq U/m.
$$
For scaled valuations, the Cauchy–Schwarz calculation and the independent-assignment bound correctly establish
$$
S\geq\max\{1/N,NU^2/m\}\geq U/\sqrt m.
$$
Assessment: correct for arbitrary $d$ when $m\leq N$.
The one-category lower bounds remain valid with arbitrary real allocation masses.
For the unscaled construction, the strictly increasing valuations force supported sizes to differ by at most one. The average-size restriction then yields the stated bound involving $\lceil q\rceil$. Taking $M$ through positive integers proves the claimed $\Omega(E)$ lower bound.
For the scaled construction:
The two-category embedding is also sound. Deleting a first-category copy certifies EF1 whenever the comparison’s first-coordinate count is positive. Otherwise its value is zero. Splitting masses to assign the second-category supply preserves the first-coordinate welfare.
Assessment: correct. These examples establish tight asymptotic orders for the stated families. They do not establish lower bounds for every fixed supply vector or every support size, and the prover does not explicitly claim that stronger conclusion.
The allocation LPs have polynomially many variables and rational coefficients of polynomial encoding length. Their claimed $\operatorname{poly}(L)$ bit running times and polynomial-size rational outputs are justified.
The sparsity bound follows by choosing an optimal basic feasible solution in the full allocation variables. Neither construction requires enumerating $N$ agents or expanding denominators of type masses.
The stated lower-bound table encoding estimates are consistent with the displayed valuations and masses.
Assessment: correct.
Major issue — incomplete coverage of USER_TASK. The output does not establish universal EF1 existence or welfare guarantees outside the rounding family, and it does not determine tight scaled prices for unbounded dimension, even within that family.
This is the sole blocking issue identified. It does not invalidate the proved special cases.
To complete the assigned task, the prover must supply:
These require additional mathematical results, not merely clarification of the existing write-up. The unrestricted-parameter observation that both global suprema are infinite does not settle the requested parameter-dependent guarantees.
The cited finite-agent paper is used only as context; no step above depends on transferring its theorem to the mass model. Its stated finite-agent setting is consistent with that limited use. [Source](https://www.cs.toronto.edu/~nisarg/papers/price-of-fairness.pdf)
⟨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.