d4-conf-sagt-2022-0008 (d4-conf-sagt-2022-0008)

Given a finite type set \(T\), fixed positive rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and an adversarially revealed stream of item value vectors \(u^j\in[0,1]^T\), each assigned whole and irrevocably to one type, define \(W_t=\mu_t^{-1}\sum_j u_t^j x_{tj}\) and let \(\mathrm{OPT}_\mu\) be the offline optimum for \(\min_{t\in T}W_t\). What is the largest \(\rho\) achievable by a randomized online policy such that its expected welfare is at least \(\rho\,\mathrm{OPT}_\mu-o(\mathrm{OPT}_\mu)\) as \(\mathrm{OPT}_\mu\to\infty\), against an oblivious adversary; is it \(1/|T|\) for every fixed \(\mu\)?

A society is given by its support: a nonempty list \(T\) of \(\tau=|T|\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
An oblivious adversary fixes a finite stream \(\sigma=(u^1,\ldots,u^m)\), with \(u^j\in[0,1]^T\), independently of the policy's random choices. The policy knows the masses, but not \(m\) or future vectors; each entire vector is revealed before its item must be assigned whole and irrevocably to exactly one type.
An allocation has \(x_{tj}\in\{0,1\}\) and \(\sum_{t\in T}x_{tj}=1\). Define \(W_t(x,\sigma)=\mu_t^{-1}\sum_{j=1}^m u_t^j x_{tj}\), \(F_\mu(x,\sigma)=\min_{t\in T}W_t(x,\sigma)\), and \(\mathrm{OPT}_\mu(\sigma)=\max_x F_\mu(x,\sigma)\), using the same whole-item constraints offline.
For fixed \(\mu\), let \(\rho^*(\mu)\) be the supremum of ratios \(\rho\) for which a randomized online policy satisfies \(\mathbb E[F_\mu(x,\sigma)]\geq\rho\,\mathrm{OPT}_\mu(\sigma)-g_\mu(\mathrm{OPT}_\mu(\sigma))\) for every stream, where \(g_\mu(z)\geq0\) and \(g_\mu(z)/z\to0\); expectation is over the policy's randomness.
State any running times in \(m,\tau,L\) and any algorithmic parameters, where \(L\) is the total binary input length on rational-valued streams.

What is \(\rho^*(\mu)\) for each fixed positive rational mass vector \(\mu\)? Is \(\rho^*(\mu)=1/\tau\) for every such vector?

For discrete agents with additive values in \([0,1]\), every randomized online algorithm has asymptotic competitive ratio at most \(1/n\), and uniform random allocation achieves it against an oblivious adversary. [Source](https://arxiv.org/pdf/2111.07235)
Consequently, equal masses have optimal ratio \(1/\tau\). No result settling this exact model for unequal masses was located in the literature search.

Exact competitive ratio

For every fixed positive rational mass vector \(\mu\) with support size \(\tau\),
\[ \rho^*(\mu)=\frac1\tau. \]
Uniform random allocation attains this ratio with an explicit sublinear additive error. Both bounds below use whole-item allocations.

1. Lower bound: uniform random allocation

Assign each arriving item independently and uniformly to one of the \(\tau\) types. This policy requires neither the horizon nor future values.

Fix an arbitrary stream \(\sigma\), and write \(z=\mathrm{OPT}_\mu(\sigma)\). If \(z=0\), the required inequality follows from nonnegativity. Suppose \(z>0\).

An optimal whole-item allocation \(x^*\) exists because there are finitely many allocations. For each type \(t\), define
\[ a_{tj}=\frac{u_t^j x^*_{tj}}{\mu_t}. \]
Optimality gives \(\sum_j a_{tj}\geq z\). Hence we can choose deterministic coefficients \(b_{tj}\) satisfying
\[ 0\leq b_{tj}\leq a_{tj}, \qquad \sum_j b_{tj}=z. \]
For example, retain coefficients successively until their sum reaches \(z\), reducing the last retained coefficient if necessary. These coefficients are only an analytical device; the online policy does not compute them or split items.

Let \(I_{tj}\) indicate that the online policy assigns item \(j\) to type \(t\), and put
\[ Y_t=\sum_j b_{tj}I_{tj}, \qquad q=\frac z\tau. \]
Since \(b_{tj}\leq u_t^j/\mu_t\), every realization satisfies \(W_t\geq Y_t\). Consequently, \(F_\mu\geq\min_t Y_t\).

For each fixed \(t\), the indicators \(I_{tj}\) are independent across items, with probability \(1/\tau\). Therefore,
\[ \mathbb E[Y_t]=q, \qquad \operatorname{Var}(Y_t) =\frac1\tau\left(1-\frac1\tau\right)\sum_j b_{tj}^2. \]
Because \(b_{tj}\leq1/\mu_t\) and \(\sum_j b_{tj}=z\),
\[ \operatorname{Var}(Y_t) \leq \frac{\tau-1}{\tau^2}\frac z{\mu_t}. \]
No independence between different types is needed.

Pointwise,
\[ q-\min_t Y_t =\max_t(q-Y_t) \leq \sqrt{\sum_t(Y_t-q)^2}. \]
Taking expectations and applying Cauchy–Schwarz yields
\[ \mathbb E[F_\mu] \geq \frac z\tau- \sqrt{\frac{\tau-1}{\tau^2}\,z\sum_{t\in T}\frac1{\mu_t}}. \]
Thus the policy satisfies the requested guarantee with
\[ g_\mu(z)= \sqrt{\frac{\tau-1}{\tau^2}\,z\sum_{t\in T}\frac1{\mu_t}}. \]
For fixed positive \(\mu\), this function is nonnegative and \(g_\mu(z)/z\to0\). Hence \(\rho^*(\mu)\geq1/\tau\).

2. Upper bound: a mass-scaled hard instance

The following is the mass-scaled version of the construction in [Kawase–Sumita, Theorem 5](https://arxiv.org/pdf/2111.07235).

Fix any randomized online policy and any positive integer \(k\). Present \(k\) identical items with \(u_t=\mu_t\) for every \(t\). Let \(N_t\) count the prefix items assigned to \(t\). Since \(\sum_tN_t=k\), some type \(h\) satisfies \(\mathbb E[N_h]\leq k/\tau\).

Complete the stream with \((\tau-1)k\) identical items having \(u_h=0\) and \(u_t=\mu_t\) for \(t\neq h\). Choose \(h\) using the policy’s distribution, before its random choices are realized. The stream is therefore oblivious; its prefix is identical for every choice of \(h\).

Each prefix item contributes exactly one normalized unit to its recipient. Type \(h\) receives no suffix value, so \(F_\mu\leq N_h\). Offline, assigning the prefix to \(h\) and \(k\) suffix items to each other type achieves value \(k\). Type \(h\)’s total available normalized value is \(k\), proving \(\mathrm{OPT}_\mu=k\).

Any claimed guarantee therefore implies
\[ \rho k-g_\mu(k)\leq\mathbb E[F_\mu]\leq\frac k\tau. \]
Divide by \(k\) and let \(k\to\infty\). Sublinearity gives \(\rho\leq1/\tau\).

3. Running time and conclusion

On rational streams of total binary input length \(L\), uniform allocation can read and discard the values and sample each recipient exactly by rejection sampling from independent fair bits. Its expected running time is \(O(L+m\log(\tau+1))\) bit operations, with \(O(\log(\tau+1))\) auxiliary bits beyond input/output buffers. It has no approximation parameter and performs no rational arithmetic.

The two bounds prove the claimed equality for every fixed mass vector. For \(\tau=1\), the unique allocation is optimal and the additive error above is zero.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output establishes \(\rho^*(\mu)=1/\tau\) for every fixed positive rational mass vector. I found no mathematical gaps or false steps.

1. Lower bound

• The policy is admissible. Independent uniform assignment allocates each item whole to exactly one type and requires neither the horizon nor future vectors.

• The offline comparison is well defined. A finite stream has finitely many feasible allocations, so an optimal allocation exists. Its normalized value for each type is at least \(z=\mathrm{OPT}_\mu(\sigma)\).

• The coefficients exist. Each finite nonnegative sequence \((a_{tj})_j\) has sum at least \(z\), so the stated truncation procedure produces coefficients satisfying \(0\leq b_{tj}\leq a_{tj}\) and \(\sum_j b_{tj}=z\). These coefficients are deterministic for the fixed stream. Their use does not relax either allocation problem’s whole-item constraints.

• The pointwise comparison is correct. The bound \(b_{tj}\leq u_t^j/\mu_t\) gives \(Y_t\leq W_t\) for every realization, and therefore \(\min_tY_t\leq F_\mu\).

• The moment calculations are correct. For fixed \(t\), the assignment indicators are independent Bernoulli variables with parameter \(1/\tau\). Thus the displayed expectation and variance formulas hold. The estimate

\(\sum_jb_{tj}^2\leq \mu_t^{-1}\sum_jb_{tj}=z/\mu_t\)
verifies the stated variance bound, including its constant.

• The bound on the expected minimum is valid. The displayed pointwise maximum is bounded by the Euclidean norm of the deviations. Cauchy–Schwarz then bounds its expectation by the square root of the sum of the variances. Independence between types is unnecessary.

• The additive error satisfies the required quantifiers. Its coefficient depends only on the fixed mass vector, and \(g_\mu(z)/z\to0\) as \(z\to\infty\). At \(z=0\), the displayed function is zero and nonnegativity supplies the guarantee.

Consequently, the lower bound establishes an admissible ratio of \(1/\tau\).

2. Upper bound

• The constructed vectors are legal. Positive masses summing to one satisfy \(0<\mu_t\leq1\). Both prefix and suffix vectors therefore belong to \([0,1]^T\), and their coordinates are rational.

• The averaging argument is correct. Since \(\sum_tN_t=k\) in every realization, at least one type satisfies \(\mathbb E[N_h]\leq k/\tau\).

• The adversary is oblivious. The selected type depends on the policy’s distribution, not on its realized random choices. All candidate streams have the same prefix, and an online policy cannot condition prefix decisions on the unseen suffix. The resulting complete stream is fixed before execution.

• The online upper bound is pointwise. Each prefix item contributes one normalized unit to its recipient, and type \(h\) has zero suffix value. Hence \(W_h=N_h\) and \(F_\mu\leq N_h\).

• The offline optimum is exactly \(k\). The described allocation gives every type normalized value \(k\). Conversely, type \(h\) has only \(k\) normalized units available across the entire stream, so no allocation can exceed \(k\).

• The limiting argument respects the guarantee’s quantifiers. For one fixed policy and its one fixed function \(g_\mu\), the construction supplies a stream for every positive integer \(k\). Although \(h\) may vary with \(k\), the optimum always equals \(k\). Thus \(\rho\leq1/\tau+g_\mu(k)/k\), and sublinearity gives \(\rho\leq1/\tau\).

The attribution matches the prefix/suffix construction in [Kawase–Sumita, Theorem 5](https://arxiv.org/pdf/2111.07235). The submitted argument verifies the scaled construction directly, so it requires no unstated transfer theorem.

3. Running time and edge cases

The expected bit-operation bound is consistent with reading \(L\) input bits and using exact rejection sampling for each recipient. Sampling uses \(O(\log(\tau+1))\) bits per attempt and a constant expected number of attempts. The stated auxiliary-space bound is consistent with storing the type count and current sample, with input/output buffers excluded as specified.

For \(\tau=1\), the sole allocation is optimal, the variance and additive error vanish, and the upper-bound stream has an empty suffix. An empty stream, if allowed, is covered by the \(z=0\) case.

No repair or additional mathematical clarification is needed. The established result is an optimal asymptotic competitive guarantee; it does not classify the complexity of exact offline optimization.

⟨structured verdict parsed — rendered above⟩