Answer: —
Theorem 20 — class: hardness
Given a finite set of types \(\mathcal R\) with positive binary-rational masses \(\nu_r\) summing to \(1\), and a finite sequence of items whose per-capita supplies \(q_t\) and type values \(v_{rt}\) are revealed on arrival, each policy must irrevocably choose per-capita allocations \(a_{rt}\ge 0\) satisfying \(\sum_{r\in\mathcal R}\nu_r a_{rt}\le q_t\). Type \(r\)'s utility is \(u_r=\sum_t v_{rt}a_{rt}\), and welfare is \(\exp(\sum_r\nu_r\log u_r)\). On instances where every offline welfare-maximizing allocation has utility ratio at most \(\kappa\), determine the best worst-case competitive ratio achievable by an online policy as a function of the type support, masses, and their encoding length.
A society is given by its support: a list \(\mathcal R\) of \(\tau\ge1\) types with positive binary-rational masses \(\nu_r\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) divisible items. On arrival of item \(t\), its nonnegative binary-rational per-capita supply \(q_t\) and values \(v_{rt}\) are revealed. A policy immediately and irrevocably chooses real allocations \(a_{rt}\ge0\) with \(\sum_r\nu_ra_{rt}\le q_t\).
Utilities are \(u_r=\sum_t v_{rt}a_{rt}\), and welfare is \(W(a)=\prod_r u_r^{\nu_r}\), interpreted as zero if any utility is zero. Require \(\sum_tq_tv_{rt}>0\) for every type.
An instance is \(\kappa\)-impartial, for \(\kappa\ge1\), if every offline welfare-maximizing allocation satisfies \(\max_r u_r^*/\min_r u_r^*\le\kappa\). Policies know the support and masses initially, but receive no future information, horizon, or impartiality bound.
For a possibly randomized policy \(A\), its competitive ratio is \(\sup_I W^*(I)/\mathbb E[W(A(I))]\), over fixed adversarial sequences satisfying the promise. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\) and any additional parameters.
What is the best achievable worst-case competitive ratio for this continuous online problem as a function of \(\kappa,\tau,(\nu_r)_r\), and \(L\)?
For finite societies of \(N\) equally weighted agents, the verified competitive lower bound is \(\min\{(\log\mu^*)^{1-o(1)},(N-1)/e\}\), where \(\mu^*\) is the actual offline optimal utility ratio; it holds even for binary values. [Source](https://arxiv.org/pdf/2211.03077)
For general values, a finite-agent algorithm without an impartiality prediction achieves \(O((\log\mu^*)^2(\log\log\mu^*)^2)\) for large \(\mu^*\). No result settling the exact mass-weighted problem above was located. [Source](https://arxiv.org/pdf/2211.03077)
The general optimal competitive ratio remains unresolved. I prove the following results, including two advances beyond the notes:
$$
O\!\left(\min\left\{E(\nu),F(\kappa)\right\}\right),
$$
in polynomial bit time, where
$$
E(\nu)=\prod_r\nu_r^{-\nu_r},
\qquad
F(x)=(1+\log x)^2\bigl(1+\log(1+\log x)\bigr)^2.
$$
$$
\kappa\ge(4k)^k,
$$
every policy has competitive ratio at least
$$
\frac{1}{6e}\prod_r\min\left\{k,\frac1{\nu_r}\right\}^{\nu_r}.
$$
This lower bound uses binary values and does not depend on the smallest individual mass. Its instance length is bounded explicitly below.
$$
\frac2{\sqrt3}.
$$
The achieving policy receives no impartiality information.
For $\tau=1$, allocating every item completely is optimal, so the exact ratio is $1$. All logarithms below are natural unless a base is displayed.
Write
$$
B_r=\sum_tq_tv_{rt}.
$$
By hypothesis, $B_r>0$ for every type. The allocation $a_{rt}=q_t$ is feasible and gives utility $B_r$, so positive welfare is attainable.
Every feasible coordinate satisfies
$$
0\le a_{rt}\le\frac{q_t}{\nu_r}.
$$
The allocation set is therefore compact. Welfare is continuous, including at zero utilities, so an optimum exists and has positive utilities.
On positive utility vectors, welfare maximization is equivalent to maximizing
$$
\Phi(u)=\sum_r\nu_r\log u_r.
$$
This function is strictly concave because every mass is positive. If two optimal allocations had different utility vectors, their midpoint would be feasible and would have strictly larger $\Phi$. Hence the optimal utility vector $u^*$ is unique.
Consequently, the promise about every maximizing allocation is equivalent to
$$
\mu:=\frac{\max_ru_r^*}{\min_ru_r^*}\le\kappa.
$$
Suppose $a_{rt}^*>0$. For sufficiently small $\delta>0$, transfer total item amount $\delta$ from type $r$ to type $s$. Their per-capita allocations change by $-\delta/\nu_r$ and $\delta/\nu_s$. The derivative of $\Phi$ is
$$
-\frac{v_{rt}}{u_r^*}+\frac{v_{st}}{u_s^*}.
$$
Optimality implies that this derivative is nonpositive. Thus
$$
a_{rt}^*>0
\quad\Longrightarrow\quad
\frac{v_{rt}}{u_r^*}
=
\max_s\frac{v_{st}}{u_s^*}.
$$
In particular, with $v_t^{\max}=\max_sv_{st}>0$,
$$
a_{rt}^*>0
\quad\Longrightarrow\quad
v_{rt}\ge\frac{v_t^{\max}}{\mu}.
$$
Whenever $q_tv_t^{\max}>0$, an optimum also uses the entire supply. Otherwise, allocating some unused supply to a positively valuing type would strictly increase welfare.
The weighted geometric mean
$$
G(u)=\prod_ru_r^{\nu_r}
$$
is concave. Indeed, for positive $u$ and any direction $z$,
$$
D^2G(u)[z,z]
=
G(u)\left[
\left(\sum_r\nu_r\frac{z_r}{u_r}\right)^2
-
\sum_r\nu_r\left(\frac{z_r}{u_r}\right)^2
\right]\le0.
$$
The inequality is weighted Cauchy–Schwarz. Continuity extends concavity to nonnegative vectors.
Given a randomized policy, define a deterministic policy whose allocation on each input prefix is the randomized policy’s expected allocation on that prefix. This is an online, feasible policy. On every fixed sequence, its utilities are the expected randomized utilities, and hence
$$
W(\text{mean policy})\ge\mathbb E[W(\text{randomized policy})].
$$
No efficient procedure for computing these expectations is asserted. The existence of the mean policy suffices for the lower bounds.
The equal-per-capita policy allocates
$$
a_{rt}=q_t.
$$
It is feasible because $\sum_r\nu_r=1$, and its utilities are $B_r$.
For every feasible allocation,
$$
u_r\le\frac{B_r}{\nu_r}.
$$
Therefore
$$
\frac{W^*}{W_{\mathrm{eq}}}
\le
\prod_r\nu_r^{-\nu_r}
=
E(\nu).
$$
Also,
$$
\log E(\nu)
=
\sum_r\nu_r\log\frac1{\nu_r}
\le
\log\left(\sum_r\nu_r\frac1{\nu_r}\right)
=
\log\tau,
$$
by Jensen’s inequality. Thus $E(\nu)\le\tau$.
The policy simply copies each supply into $\tau$ output coordinates, requiring $O(m\tau)$ output entries and polynomial bit time.
Consider sequences in which, for each item $t$, values belong to $\{0,b_t\}$ for some common $b_t\ge0$.
Maintain current utilities $U_r$, initially zero. Ignore items with $q_tb_t=0$ or with no positively valuing type. Otherwise let
$$
T_t=\{r:v_{rt}=b_t\}.
$$
Choose the unique water level $z$ satisfying
$$
\sum_{r\in T_t}\nu_r(z-U_r)_+=q_tb_t,
$$
and allocate
$$
a_{rt}=\frac{(z-U_r)_+}{b_t}
\quad(r\in T_t),
$$
with zero allocations elsewhere. Existence and uniqueness follow because the left side is continuous, eventually strictly increasing, and unbounded.
Every positive recipient finishes at utility $z$, while every interested type finishes at or above $z$.
Let $u_r$ be the final water-filling utilities, and let $w_r>0$ be the utilities of any feasible benchmark.
Fix $s\ge0$ and any set $S$ satisfying $u_r\le s$ for all $r\in S$. Let $\mathcal T(S)$ consist of items positively valued by at least one member of $S$. Benchmark feasibility gives
$$
\sum_{r\in S}\nu_rw_r
\le
\sum_{t\in\mathcal T(S)}q_tb_t.
$$
For a fixed type $r$, its utility from these items is at most $\min\{s,u_r\}$. The bound by $u_r$ is immediate. To prove the bound by $s$, consider its last positive receipt from an item in $\mathcal T(S)$. An interested type in $S$ has utility after that item at most its final utility, hence at most $s$. The recipient finishes at the water level, which is no larger. All of its utility contributions from $\mathcal T(S)$ have accumulated by this last receipt.
Water filling distributes all positively valued supply. Summing these contribution bounds therefore yields
$$
\sum_{r\in S}\nu_rw_r
\le
\sum_r\nu_r\min\{s,u_r\}
\le s.
$$
Taking $S=\{r:u_r=0\}$ and $s=0$ shows that every final $u_r$ is positive.
Define
$$
\eta=\frac{\max_rw_r}{\min_rw_r},
\qquad
J=1+\lfloor\log_2\eta\rfloor.
$$
I claim that
$$
\frac{\prod_rw_r^{\nu_r}}{\prod_ru_r^{\nu_r}}
\le2eJ.
$$
Put $h=\min_rw_r$. Partition the types into nonempty classes
$$
C_j=\{r:2^jh\le w_r<2^{j+1}h\},
\qquad
p_j=\sum_{r\in C_j}\nu_r.
$$
There are at most $J$ occupied classes.
Apply the supply inequality to
$$
S=\{r\in C_j:u_r\le s\}.
$$
Since $w_r\ge2^jh$ on this set,
$$
\sum_{\substack{r\in C_j\\u_r\le s}}\nu_r
\le\frac{s}{2^jh}.
$$
Conditional on membership in $C_j$, use probabilities $\nu_r/p_j$. Then, for $x\ge0$,
$$
\Pr\!\left(u_r<2^jhp_je^{-x}\mid r\in C_j\right)\le e^{-x}.
$$
Integrating this tail bound gives
$$
\mathbb E\!\left[\left(\log\frac{2^jhp_j}{u_r}\right)_+
\middle|r\in C_j\right]\le1.
$$
Consequently,
$$
\sum_{r\in C_j}\nu_r\log u_r
\ge
p_j\log(2^jhp_j)-p_j.
$$
Since $w_r<2^{j+1}h$,
$$
\sum_{r\in C_j}\nu_r\log\frac{w_r}{u_r}
\le
p_j(1+\log2-\log p_j).
$$
The class masses sum to $1$, and their entropy is at most $\log J$. Summing and exponentiating proves the claim.
If all benchmark utilities equal $c$, there is no factor-of-two loss from class rounding. The same tail argument directly gives
$$
\prod_ru_r^{\nu_r}\ge\frac ce.
$$
This section proves the stated general upper bound rather than assuming it from the notes.
Fix an integer $K\ge1$. For an item with $q_tv_t^{\max}>0$, define
$$
d_t=
\max\left\{
1,
\left\lceil
\log_2
\frac{v_t^{\max}}{\min_{r:v_{rt}>0}v_{rt}}
\right\rceil
\right\}.
$$
For every ignored item, set $d_t=1$ by convention.
Replace a nonignored item by sub-items indexed by
$$
1\le\ell\le\min\{K,d_t\}.
$$
Each sub-item has supply $q_t/K$ and binary values
$$
\widehat v_{rt\ell}
=
\begin{cases}
v_t^{\max}/2^\ell,&v_{rt}\ge v_t^{\max}/2^\ell,\\
0,&\text{otherwise}.
\end{cases}
$$
Run water filling on these sub-items and sum their allocations. This defines a feasible policy $A_K$.
Suppose
$$
K\ge K_0:=\max\{1,\lceil\log_2\mu\rceil\}.
$$
For every positive optimal coordinate $a_{rt}^*$, there is a retained threshold satisfying
$$
\frac{v_{rt}}2
\le
\frac{v_t^{\max}}{2^\ell}
\le
v_{rt}.
$$
To check the depth, if $v_{rt}=v_t^{\max}$ choose $\ell=1$. Otherwise choose
$$
\ell=\left\lceil\log_2\frac{v_t^{\max}}{v_{rt}}\right\rceil.
$$
The optimality condition gives $\ell\le K_0$, and the definition of $d_t$ gives $\ell\le d_t$.
Assign $a_{rt}^*/K$ to one such sub-item. Each sub-item receives a subset of the original optimal allocation divided by $K$, so its supply constraint holds. The resulting benchmark utilities satisfy
$$
\frac{u_r^*}{2K}\le w_r\le\frac{u_r^*}{K}.
$$
Thus their ratio is at most $2\mu$, and their welfare is at least $W^*/(2K)$.
Applying the preceding lemma, and using that original values dominate rounded values, gives
$$
\frac{W^*}{W(A_K)}
\le
4eK\bigl(2+\lfloor\log_2\mu\rfloor\bigr).
$$
Use depths and weights
$$
K_j=2^j,
\qquad
p_j=\frac1{(j+1)(j+2)}
\quad(j\ge0).
$$
The weights telescope to $1$.
Normalize expert $A_{K_j}$ by multiplying its virtual utilities and allocations by $K_j$. Its normalized execution processes each retained sub-item with supply $q_t$.
At arrival $t$, put
$$
D_t=\max\{1,d_1,\ldots,d_t\},
\qquad
h_t=\lceil\log_2D_t\rceil.
$$
All experts with $j\ge h_t$ have retained every level encountered so far, so their normalized histories coincide.
Maintain separate normalized states for $j<h_t$ and one common state for $j\ge h_t$. When $h_t$ increases, copy the previous common state to initialize newly separated experts before processing the current item. This reproduces their histories exactly.
Let $\alpha_{rt}^{(j)}$ be expert $j$’s normalized allocation on the current item, summed over retained levels, and let $\alpha_{rt}^{(\infty)}$ be the common state’s allocation. Allocate
$$
a_{rt}^{\mathrm{mix}}
=
\sum_{j<h_t}\frac{p_j}{K_j}\alpha_{rt}^{(j)}
+
\frac{2p_{h_t}}{K_{h_t}}\alpha_{rt}^{(\infty)}.
$$
Each separated expert, after division by $K_j$, consumes at most $q_t$. The common normalized execution consumes at most $d_tq_t\le K_{h_t}q_t$. Hence actual consumption is at most
$$
q_t\left(\sum_{j<h_t}p_j+2p_{h_t}\right)
=
q_t\left(
1-\frac1{h_t+1}
+\frac2{(h_t+1)(h_t+2)}
\right)
\le q_t.
$$
Fix any expert $j$. When separated, its allocation appears with coefficient $p_j$. When common, its normalized allocation is the common allocation, and
$$
\frac{p_j}{K_j}
\le
\frac{p_{h_t}}{K_{h_t}}
\le
\frac{2p_{h_t}}{K_{h_t}}.
$$
Thus the mixture dominates $p_j$ times this expert’s allocation coordinatewise at every arrival. Welfare is monotone and homogeneous, so
$$
W(A^{\mathrm{mix}})\ge p_jW(A_{K_j}).
$$
For analysis only, choose the smallest $j_0$ with $2^{j_0}\ge K_0$. Then $2^{j_0}\le2K_0$, and
$$
\frac{W^*}{W(A^{\mathrm{mix}})}
\le
4e\,2^{j_0}
\bigl(2+\lfloor\log_2\mu\rfloor\bigr)
(j_0+1)(j_0+2)
=
O(F(\mu)).
$$
The policy never computes $\mu$ or $\kappa$.
Finally, average this policy’s allocation with the equal-per-capita allocation. The resulting welfare is at least half that of either component. Therefore a single deterministic policy satisfies
$$
\frac{W^*}{W(A)}
=
O\!\left(\min\{E(\nu),F(\mu)\}\right)
\le
O\!\left(\min\{E(\nu),F(\kappa)\}\right).
$$
Let $D=\max_td_t$. Explicit binary encoding implies $D=O(L)$: ratios between positive input values have logarithms bounded by their encoding lengths.
At one arrival, the number of normalized water-filling operations is at most
$$
\sum_{j<h_t}2^j+d_t
=
2^{h_t}-1+d_t
=
O(D).
$$
A water-filling operation can be implemented by sorting current utilities, scanning candidate filled sets, and solving the resulting linear equation. It uses
$$
O(\tau\log(\tau+1))
$$
rational arithmetic operations.
Here is an explicit denominator bound. Give the masses a common denominator $M$, of bit length $O(L)$. If current utilities have common denominator $Q$, a water level for a filled set $S$ is
$$
z=
\frac{q_tb+\sum_{r\in S}\nu_rU_r}{\sum_{r\in S}\nu_r}.
$$
Writing $\nu_r=n_r/M$, a common denominator for this update divides
$$
Q\,C\sum_{r\in S}n_r,
$$
where $C$ is a denominator of $q_tb$. Both $C$ and the positive integer $\sum_{r\in S}n_r$ have $O(L+D)$ bits. Thus each update increases a common denominator’s bit length by at most $O(L+D)$.
Apply this bound to a common denominator covering all virtual states, enlarging it after every update. There are $O(mD)$ updates. Their utility magnitudes have logarithms $O(L+\log(mD+2))$, since each update adds bounded input utility and every mass is at least $2^{-O(L)}$.
For the current item, division by its rounded values adds only a common input numerator factor and powers of two. The mixture coefficients add $O(D)$ denominator bits. Consequently all state and output rationals have bit length bounded by
$$
B=O\!\left(mD(L+D)+L+\log(mD+2)\right).
$$
Using the conservative bound $O(B^3)$ for exact rational arithmetic gives total bit time
$$
O\!\left(mD\tau\log(\tau+1)B^3\right)
=
\operatorname{poly}(m,\tau,L).
$$
The policy stores $O(\tau(1+\log(D+1)))$ virtual utility coordinates. Neither the final $L$ nor the horizon is required beforehand.
Partition the actual types into $J$ nonempty blocks, with block masses
$$
p_g=\sum_{r\in g}\nu_r.
$$
All constructed values will be identical within a block. Define
$$
p_{\min}=\min_gp_g,
\qquad
p_{\max}=\max_gp_g.
$$
Fix $0<\varepsilon\le1$, and choose a power of two $B$ satisfying
$$
B\ge1+\frac1{\varepsilon p_{\min}}.
$$
I prove that every policy has a binary-valued instance with $m=J$, impartiality at most
$$
B^{J-1}\frac{p_{\max}}{p_{\min}},
$$
and competitive ratio at least
$$
\frac{\prod_gp_g^{-p_g}}{e(1+\varepsilon)}.
$$
By Section 1, it suffices to construct the sequence against the deterministic mean policy.
Initially every block is active. At stage $i$, supply
$$
q_i=B^{i-1}
$$
and give value $1$ to all types in active blocks, and value $0$ to all other types.
Let $S_i$ be the total active mass. Define the block’s average per-capita allocation on this item by
$$
A_{gi}=\frac1{p_g}\sum_{r\in g}\nu_ra_{ri}.
$$
Feasibility implies that some active block $g_i$ satisfies
$$
A_{g_i i}\le\frac{q_i}{S_i}.
$$
Remove that block after this item.
Its final average utility, denoted $\bar u_{g_i}$, satisfies
$$
\bar u_{g_i}
\le
\frac{q_i}{S_i}
+
\frac1{p_{g_i}}\sum_{t<i}q_t
\le
\frac{q_i}{S_i}
+
\frac{q_i}{p_{g_i}(B-1)}.
$$
This procedure uses expected decisions on fixed prefixes, never realized random coins. Once all stages have been determined, the resulting sequence is a fixed adversarial sequence.
Allocate item $i$ entirely to block $g_i$, equally per capita within that block. Every type in it receives utility
$$
u_r^*=\frac{q_i}{p_{g_i}}.
$$
These utilities increase strictly in removal order because
$$
B>\frac{p_{\max}}{p_{\min}}.
$$
For any feasible utility vector $w$,
$$
\sum_r\nu_r\frac{w_r}{u_r^*}
=
\sum_i\sum_r\frac{\nu_ra_{ri}v_{ri}}{u_r^*}
\le
\sum_i\frac{q_i}{q_i/p_{g_i}}
=
\sum_ip_{g_i}
=
1.
$$
The inequality holds because the designated block has the smallest proposed utility among blocks interested in item $i$.
If any $w_r=0$, its welfare is zero and it cannot improve the proposed allocation. Otherwise, $\log x\le x-1$ gives
$$
\sum_r\nu_r\log\frac{w_r}{u_r^*}
\le
\sum_r\nu_r\left(\frac{w_r}{u_r^*}-1\right)
\le0.
$$
This proves optimality. Uniqueness of optimal utilities establishes the promise for every maximizer, with
$$
\mu\le B^{J-1}\frac{p_{\max}}{p_{\min}}.
$$
Every type values the first item, so the required positivity condition also holds.
Within each block, concavity of $\log$ gives
$$
W(A)\le\prod_g\bar u_g^{p_g}.
$$
If online welfare is zero, the lower bound is immediate. Otherwise,
$$
\frac{q_i/p_{g_i}}{\bar u_{g_i}}
\ge
\frac{S_i/p_{g_i}}
{1+S_i/(p_{g_i}(B-1))}
\ge
\frac{S_i/p_{g_i}}{1+\varepsilon}.
$$
Multiplication with block weights yields
$$
\frac{W^*}{W(A)}
\ge
\frac1{1+\varepsilon}
\exp\left(
-\sum_gp_g\log p_g
+
\sum_ip_{g_i}\log S_i
\right).
$$
Set $S_{J+1}=0$. The intervals $[S_{i+1},S_i]$ partition $[0,1]$ and have lengths $p_{g_i}$. Since $\log x$ is increasing,
$$
\sum_ip_{g_i}\log S_i
\ge
\int_0^1\log x\,dx
=
-1.
$$
This proves the claimed lower bound, including against randomized policies.
If $L_\nu$ is the encoding length of the original support and masses, the constructed instance has length
$$
O\!\left(L_\nu+\tau J+J^2(1+\log B)\right).
$$
Indeed, it has a binary $\tau$-by-$J$ valuation matrix, and supply $q_i$ has $O(1+i\log B)$ bits.
Define the truncated entropy quantity
$$
E_k(\nu)
=
\prod_r\min\left\{k,\frac1{\nu_r}\right\}^{\nu_r}
\qquad(k\ge1).
$$
It satisfies
$$
1\le E_k(\nu)\le\min\{k,E(\nu)\}.
$$
For every integer $k\ge1$, the support can be partitioned into $J\le\min\{k,\tau\}$ blocks such that
$$
p_g\ge\frac1k
\quad\text{for every block},
$$
and
$$
\prod_gp_g^{-p_g}\ge\frac{E_k(\nu)}3.
$$
To construct the partition, make every type with mass at least $1/k$ a singleton block. Process the remaining types in any order, closing a block whenever its accumulated mass reaches $1/k$. Each such completed block has mass less than $2/k$.
A residual block, if present, has mass $\delta<1/k$. If a completed small-type block exists, merge the residual into it. Otherwise merge it into a heavy singleton. If no heavy singleton exists, a completed small-type block must exist because total mass is $1$.
All final block masses are at least $1/k$, so $J\le k$.
Put
$$
H_k=\sum_r\nu_r\log\frac1{\max\{\nu_r,1/k\}},
\qquad
H(p)=-\sum_gp_g\log p_g.
$$
Then
$$
H_k-H(p)
=
\sum_r\nu_r
\log\frac{p_{g(r)}}{\max\{\nu_r,1/k\}}.
$$
If a completed small-type block exists, its possible residual merge produces mass less than $3/k$. Every heavy type remains a singleton. Thus every summand’s logarithmic factor is at most $\log3$, and
$$
H_k-H(p)\le\log3.
$$
Otherwise all light types have total mass $\delta<1/k$ and are merged with one heavy type of mass $h$. Only this merged block contributes to the difference:
$$
H_k-H(p)
=
h\log\frac{h+\delta}{h}
+
\delta\log\bigl(k(h+\delta)\bigr).
$$
Using $\log(1+x)\le x$ and $h+\delta\le1$,
$$
H_k-H(p)
\le
\delta(1+\log k)
\le
\frac{1+\log k}{k}
\le1<\log3.
$$
Here the penultimate inequality follows from $\log k\le k-1$. Exponentiating proves the partition lemma.
Use this partition, set $\varepsilon=1$, and let $B$ be the smallest power of two at least $k+1$. Then
$$
B<2(k+1)\le4k,
\qquad
B\ge1+\frac1{p_{\min}}.
$$
The construction in Section 5 has impartiality at most
$$
B^{J-1}\frac{p_{\max}}{p_{\min}}
\le
(4k)^{J-1}k
\le
(4k)^k.
$$
Its competitive lower bound is at least
$$
\frac{E_k(\nu)}{6e}.
$$
Therefore, whenever $\kappa\ge(4k)^k$, every policy has competitive ratio at least
$$
\boxed{
\max\left\{
1,\,
\frac1{6e}
\prod_r\min\left\{k,\frac1{\nu_r}\right\}^{\nu_r}
\right\}.
}
$$
The witness has
$$
m=J\le\min\{k,\tau\}
$$
and encoding length
$$
O\!\left(L_\nu+\tau J+J^2\log(k+1)\right).
$$
For a prescribed input-length cap, this lower bound applies when the cap permits this witness.
For equal masses,
$$
E_k(\nu)=\min\{k,\tau\}.
$$
For $\log\kappa\ge4$, the choice
$$
k=
\left\lfloor
\frac{\log\kappa}{\log(4\log\kappa)}
\right\rfloor
$$
is admissible: $k\le\log\kappa$, and hence
$$
k\log(4k)
\le
k\log(4\log\kappa)
\le
\log\kappa.
$$
Thus the explicit equal-mass lower bound has order
$$
\min\left\{\tau,\frac{\log\kappa}{\log\log\kappa}\right\}
$$
as $\kappa$ grows, subject to the stated encoding requirement.
For unequal masses, $E_k(\nu)$ records how much mass lies in types smaller than the scale $1/k$. Grouping improves on applying the original construction directly to every type, which would require supply growth controlled by $\nu_{\min}$.
Taking singleton blocks in Section 5 also recovers the unrestricted bounds
$$
\max\{1,E(\nu)/e\}
\le
\text{optimal unrestricted ratio}
\le
E(\nu).
$$
The lower inequality follows by letting $\varepsilon$ approach zero; the necessary impartiality and input length are then allowed to grow. Thus the unrestricted ratio is $\Theta(E(\nu))$, with universal constants.
For each item, retain only the types attaining its maximum value:
$$
T_t=\{r:v_{rt}=v_t^{\max}\}.
$$
Run weighted water filling on these types, using common value $b_t=v_t^{\max}$.
This policy receives no impartiality bound. Its guarantee here is restricted to perfectly impartial instances.
When $\mu=1$, write $u_r^*=c$ for every type. The optimality condition from Section 1 implies
$$
a_{rt}^*>0
\quad\Longrightarrow\quad
v_{rt}=v_t^{\max}.
$$
Thus the offline optimum remains feasible, with the same utilities, after all nonmaximum values are replaced by zero. The equal-benchmark version of the water-filling lemma gives
$$
W(A)\ge\frac ce=\frac{W^*}{e}.
$$
Assume $\tau=2$, $\nu_1=\nu_2=1/2$, and $\mu=1$.
For the maximum-value water-filling policy, let the final utilities be $u_1,u_2$. Both this policy and the optimum allocate all positive supply to maximum-valuing types. Therefore
$$
\frac{u_1+u_2}{2}
=
\sum_tq_tv_t^{\max}
=
c.
$$
Let $s=\min\{u_1,u_2\}$. Apply the supply inequality from Section 3 to a singleton type attaining this minimum. Its benchmark utility is $c$, so
$$
\frac c2
\le
\frac12\min\{s,u_1\}+\frac12\min\{s,u_2\}
=
s.
$$
Also $s\le c$, and the other utility equals $2c-s$. Hence
$$
W(A)^2=s(2c-s).
$$
This expression is increasing for $s\in[c/2,c]$, so
$$
W(A)^2\ge\frac c2\cdot\frac{3c}{2}
=\frac{3c^2}{4}.
$$
Since $W^*=c$, the competitive ratio is at most $2/\sqrt3$.
For the matching lower bound, give a first item with supply $1/2$ and value $1$ for both types. Against the deterministic mean policy, choose a type whose allocation on this item is $x\le1/2$. Give a second item with supply $1/2$ and value $1$ only for the other type.
The selected type’s final utility is $x$. Feasibility bounds the other type’s final utility by $2-x$. Thus
$$
W(A)\le\sqrt{x(2-x)}\le\frac{\sqrt3}{2}.
$$
The last inequality holds because $x(2-x)$ is increasing on $[0,1/2]$.
Offline, allocate the first item entirely to the selected type and the second entirely to the other. Both utilities are $1$. Every feasible allocation has weighted arithmetic mean utility at most $1$, so weighted arithmetic–geometric mean proves optimality. The unique optimal utility vector is $(1,1)$, establishing perfect impartiality.
The mean-policy argument transfers the lower bound to randomized policies. Consequently,
$$
\boxed{
\text{For }\tau=2,\ \nu_1=\nu_2=\tfrac12,\ \kappa=1,
\text{ the exact optimal ratio is }\frac2{\sqrt3}.
}
$$
Maximum-value water filling requires $O(m\tau\log(\tau+1))$ rational arithmetic operations. The denominator argument from Section 4, with one update per item, gives polynomial bit time in $m,\tau,L$.
There is a scaling error in the notes’ finite-agent transfer. For $N=\tau$ equally weighted types, the correct substitutions from finite-agent supplies $s_t$ and allocations $x_{rt}$ are
$$
q_t=\frac{s_t}{\tau},
\qquad
a_{rt}=x_{rt}.
$$
Indeed,
$$
\sum_r\nu_ra_{rt}
=
\frac1\tau\sum_rx_{rt}
\le
\frac{s_t}{\tau}
=
q_t.
$$
Utilities, welfare, and impartiality ratios are unchanged. The converse mapping is also feasible, so offline optimality is preserved.
Consequently, the finite-agent lower-bound families supplied in the question transfer to this model. Theorem 20 and its binary-value extension appear in [Huang, Li, Shu, and Wei, *Online Nash Welfare Maximization Without Predictions*](https://arxiv.org/pdf/2211.03077). Under a fixed input-length cap, their use still requires an admissible witness.
For arbitrary unequal masses, replacing types by equal-weight clones does not transfer unrestricted finite-agent hard instances: clones must have identical valuation histories. Section 6 instead groups actual types and explicitly respects this restriction.
The proved bounds do not determine the optimal ratio for general intermediate $\kappa$. They leave a gap between the truncated-entropy lower bound and the quadratic-logarithmic upper bound. They also do not settle sharp dependence on a prescribed input-length cap or exact constants for general masses.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but does not resolve the general best achievable competitive ratio requested in USER_TASK. Its principal bounds and exact two-type result are mathematically sound. I found no major correctness gap in those arguments, and two minor presentation issues.
The unresolved parts are acknowledged by the prover: the optimal dependence on general masses and intermediate $\kappa$, and sharp dependence on a prescribed input-length cap.
The allocation $a_{rt}=q_t$ is feasible because the masses sum to $1$. It gives every type positive utility by the assumed condition $B_r>0$.
The coordinate bounds $a_{rt}\le q_t/\nu_r$ make the feasible allocation set compact. Welfare is continuous on that set, including its boundary, and an optimum therefore exists. Since positive welfare is attainable, every optimum has positive utilities.
Strict concavity of
$$
\Phi(u)=\sum_r\nu_r\log u_r
$$
establishes uniqueness of the optimal utility vector, without claiming uniqueness of the allocation. Taking the midpoint of two feasible allocations produces the midpoint of their utilities, so the strict-concavity argument applies as written.
Consequently, replacing the promise concerning every maximizing allocation by $\mu\le\kappa$ is justified.
When $a_{rt}^*>0$, the proposed transfer is feasible for sufficiently small positive $\delta$. Its derivative is correctly computed as
$$
-\frac{v_{rt}}{u_r^*}+\frac{v_{st}}{u_s^*}.
$$
Optimality requires this derivative to be nonpositive for every recipient $s$. This establishes the displayed maximum condition.
Choosing a type attaining $v_t^{\max}$ then gives
$$
v_{rt}\ge v_t^{\max}\frac{u_r^*}{\max_su_s^*}
\ge\frac{v_t^{\max}}{\mu}.
$$
The claim that an optimum exhausts supply when $q_tv_t^{\max}>0$ is also valid: unused supply could increase a positive utility and hence increase welfare.
The Hessian calculation for the weighted geometric mean is correct. Weighted Cauchy–Schwarz supplies the asserted nonpositivity, and continuity extends concavity to nonnegative utilities.
An online randomized policy’s allocation distribution on a fixed prefix depends only on that prefix. Its expected allocations therefore define a deterministic online policy. Feasibility survives expectation, and utilities depend linearly on allocations. Jensen’s inequality consequently gives the claimed domination of expected welfare.
The output expressly declines to claim efficient computation of these expectations. That limitation causes no gap: the mean policy is used for existential lower bounds, rather than as the efficiently implemented upper-bound policy.
The coordinatewise bound
$$
u_r\le B_r/\nu_r
$$
follows directly from itemwise feasibility and nonnegative values. Multiplying with the specified exponents establishes the ratio $E(\nu)$.
The Jensen calculation establishing $E(\nu)\le\tau$ uses positive weights summing to $1$ and is correct. Copying each supply into every type’s per-capita allocation is feasible and has the stated polynomial implementation.
For a processed item, $q_tb_t>0$ and the interested set is nonempty. The water-level equation has a unique solution: its left side is continuous, unbounded, and strictly increasing once it becomes positive. Zero supplies and zero values are explicitly excluded from this operation.
The supply inequality is the critical step. Its two components are justified:
Summing these contributions is legitimate because water filling allocates all relevant supply. The resulting inequality also excludes zero final utilities whenever the benchmark utilities are positive.
The welfare argument checks out. Conditional class probabilities satisfy the stated exponential tail bound; integrating it bounds the positive part of the logarithmic deficit by $1$. The classwise inequalities, the entropy bound on class masses, and exponentiation yield $2eJ$ with the displayed constants.
For an equal benchmark, omitting the class-rounding loss gives the claimed factor $e$.
For every positive optimal coordinate, the selected threshold lies between $v_{rt}/2$ and $v_{rt}$. The special treatment of $v_{rt}=v_t^{\max}$ correctly accommodates the fact that retained levels begin at $\ell=1$.
The optimality condition bounds the required level by $K_0$, and the minimum positive input value bounds it by $d_t$. Assigning each coordinate to one retained sub-item respects that sub-item’s supply constraint. Therefore the benchmark utility bounds and its impartiality ratio are valid.
Applying the water-filling lemma gives
$$
\frac{W^*}{W(A_K)}
\le4eK\bigl(2+\lfloor\log_2\mu\rfloor\bigr),
$$
including the case $\mu=1$.
The finite representation of infinitely many experts is sound. Scaling virtual utilities and allocations by $K_j$ gives the stated normalized execution. Experts in the common group have encountered identical retained sub-items, so their histories agree. Copying the common state when experts separate reproduces their earlier histories.
The mixture’s supply calculation is correct, including $h_t=0$. Its coefficient dominates $p_j/K_j$ for every common expert, and separated experts appear with their exact coefficient. Coordinatewise domination and welfare homogeneity establish the competitive guarantee.
Minor issue: the processing order of sub-items is not explicitly specified. The common-history implementation requires a consistent order across experts.
Minimum clarification: state that retained levels are processed in increasing $\ell$, or specify another shared deterministic order.
Averaging with the equal-per-capita policy correctly loses at most a factor of $2$ relative to either component. Thus the claimed minimum of the two upper bounds follows.
The assertion $D=O(L)$ follows from explicit binary encoding of positive rational values. The number of normalized water-filling operations per arrival is correctly bounded by $O(D)$.
In the water-level formula, clearing the common mass denominator produces the asserted denominator divisor
$$
Q\,C\sum_{r\in S}n_r.
$$
The positive integer $\sum_{r\in S}n_r$ is at most the common mass denominator. Hence the claimed per-update denominator growth is valid.
There are $O(mD)$ updates, and virtual utility magnitudes have the stated logarithmic bound. Dividing by rounded values and applying mixture coefficients preserves polynomial output bit length. The conservative rational-arithmetic estimate therefore establishes polynomial bit time.
This verifies efficient computation of the displayed policy. It does not establish computation of an optimal competitive policy or a sharp competitive dependence on $L$.
Feasibility guarantees an active block with average allocation at most $q_i/S_i$. Bounding all earlier supply by its total divided by the selected block’s mass gives the stated final-utility estimate.
Selecting blocks using expected decisions on prefixes produces a fixed completed sequence. It does not depend on realized random coins, so the lower bound respects the fixed-adversary definition.
The proposed offline utilities increase strictly in removal order because the chosen $B$ exceeds $p_{\max}/p_{\min}$. Thus the designated block has the smallest proposed utility among blocks interested in its item. This verifies the reciprocal-utility inequality used in the offline certificate.
The subsequent application of $\log x\le x-1$ proves optimality. Previously established uniqueness of optimal utilities verifies the promise for every maximizer.
The welfare comparison handles unequal allocations inside blocks correctly through weighted logarithmic concavity. The factor $1+\varepsilon$ follows from the chosen supply growth. Finally,
$$
\sum_ip_{g_i}\log S_i\ge\int_0^1\log x\,dx=-1
$$
has the correct direction, including the final interval adjacent to zero.
The witness-length estimate accounts for both the valuation matrix and the binary lengths of the supplies.
The grouping construction ensures every final block has mass at least $1/k$, including after merging a residual block. Therefore $J\le\min\{k,\tau\}$.
Both cases in the entropy-loss estimate are valid. Completed small-type blocks have final mass below $3/k$; when no such block exists, the displayed heavy-block calculation bounds the loss by
$$
\frac{1+\log k}{k}\le1<\log3.
$$
The case $k=1$ is covered.
The chosen power of two satisfies the supply-growth requirement. The resulting impartiality bound is at most $(4k)^k$, and the competitive lower bound is $E_k(\nu)/(6e)$.
The equal-mass calculation and the admissibility check for the displayed logarithmic choice of $k$ are correct. The unrestricted $\Theta(E(\nu))$ statement also follows: letting $\varepsilon$ tend to zero is legitimate when witness lengths and impartiality are unrestricted.
These conclusions do not close the gap for general intermediate $\kappa$, and the output correctly says so.
When all optimal utilities equal $c$, the optimality condition confines every positive optimal allocation to maximum-valuing types. The benchmark therefore survives the policy’s removal of nonmaximum values. The equal-benchmark lemma proves the factor $e$ guarantee.
For two equal masses, both allocations exhaust positively valued supply at maximum values, giving
$$
u_1+u_2=2c.
$$
The singleton supply inequality gives $s\ge c/2$. The stated monotonicity calculation then establishes welfare at least $\sqrt3\,c/2$.
In the lower-bound construction, first-item feasibility ensures a selected type has allocation $x\le1/2$. Its final utility is $x$, and the other type’s utility is at most $2-x$. The resulting welfare bound is correct.
The offline allocation gives utilities $(1,1)$, and the weighted arithmetic–geometric mean certificate proves optimality. Utility uniqueness establishes perfect impartiality. The mean-policy argument transfers the lower bound to randomized policies. Thus the exact ratio $2/\sqrt3$ is established.
The substitutions $q_t=s_t/\tau$ and $a_{rt}=x_{rt}$ preserve feasibility in both directions, utilities, welfare, and impartiality. The cited finite-agent lower bound and its binary-value extension appear in Theorem 20 and the following remark of the [source paper](https://arxiv.org/pdf/2211.03077). The normalization therefore transfers the supplied lower-bound families.
Minor issue: “There is a scaling error in the notes’ finite-agent transfer” cannot be checked against the supplied inputs. USER_TASK contains no proposed scaling substitution.
Minimum clarification: remove that allegation or identify the specific earlier substitution being criticized. The displayed correct normalization does not depend on the allegation.
The appropriate adjudication is partial, rather than refuted. The proved bounds, polynomial implementation, and special-case optimum are genuine progress. Determining the general optimum and its sharp input-length dependence remains necessary to answer USER_TASK completely.
⟨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.