Improved Regret Bounds for Online Fair Division with Bandit Learning

My lead anchor is Theorem 1 (proved here): when values are normalized, Algorithm 1 achieves regret \(\tilde O(n^5m^3\sqrt T)\) while satisfying proportionality in expectation with probability \(1-1/T\). The paper’s algorithm is not polynomial-time—it explicitly has exponential runtime in \(n\) and \(m\)—but the theorem identifies a natural continuous-computational target.

The appropriate mirror is a high-multiplicity population of recipients. Let \(\Theta=\{1,\ldots,\tau\}\) be finitely many recipient types, with known population masses \(\rho_\theta>0\) and \(\sum_\theta\rho_\theta=1\). A type includes the complete value-generating law for that category, so all recipients of type \(\theta\) have the same unknown mean value \(v_{\theta k}\) for item type \(k\). Assume \(v_{\theta k}\in[a,b]\), \(\sum_kv_{\theta k}=1\), and value observations are sub-Gaussian. The number of actual recipients \(N\) may be enormous, with \(N\rho_\theta\) copies of each type, while \(\tau\) and \(m\) remain modest.

At round \(t\), before seeing the arriving item type, the algorithm chooses a matrix \(x_t\), where \(x_{\theta k}\) is the fraction of item type \(k\) assigned to recipient type \(\theta\). Thus \(\sum_\theta x_{\theta k}=1\). If type \(k\) arrives, the item is assigned to type \(\theta\) with probability \(x_{\theta k}\), then to a uniformly selected recipient of that type. The item remains indivisible; \(x_t\) is the aggregate assignment law induced by many interchangeable recipients.

A member of type \(\theta\) receives item type \(k\) at a rate proportional to \(x_{\theta k}/\rho_\theta\). Define proportionality by requiring, at every round and for every type, \( \sum_k (x_{\theta k}/\rho_\theta)v_{\theta k}\ge 1 \). Uniform random assignment, \(x_{\theta k}=\rho_\theta\), is always feasible because the values are normalized.

The clairvoyant benchmark is

\(W^\star(v)=\max_x \frac{1}{m}\sum_{\theta,k}x_{\theta k}v_{\theta k}\)

subject to \(\sum_\theta x_{\theta k}=1\), \(x_{\theta k}\ge0\), and \( \sum_k (x_{\theta k}/\rho_\theta)v_{\theta k}\ge1 \) for every \(\theta\). The continuous online problem asks for an algorithm that observes only the value of the type receiving each item, maintains proportionality with high probability at every time, and has pseudo-regret

\(T W^\star(v)-\sum_{t=0}^{T-1}\frac{1}{m}\sum_{\theta,k}x_{t,\theta k}v_{\theta k}\)

bounded by roughly \(\tilde O(\tau^5m^3\sqrt T)\), with dependence on \(\rho_{\min}^{-1}\) where necessary. The intended computational version additionally asks whether each \(x_t\) can be computed in time polynomial in the type-level input size, rather than in \(N\).

This is a genuine population continuization, not merely a fractional-outcome reformulation. For a finite election with \(N\) recipients and identical groups, set \(\rho_\theta=N_\theta/N\). When all groups have equal size, \(x_{\theta k}=X_{ik}\) and \(x_{\theta k}/\rho_\theta=nX_{ik}\), so the continuous proportionality constraint is exactly \(X_i\cdot v_i\ge1/n\). The welfare objective and feedback process also coincide. The only thing removed is the irrelevant identity of recipients within a type. A realistic instance is a large food-bank network with hundreds of thousands of pantries but perhaps \(\tau=10\)–\(30\) stable pantry categories, each category having a common but initially unknown response distribution to \(m\) food types.

I expect this mirror to be Class A in its population dimension. The paper’s supporting Lemmas 1–3 point in exactly that direction: uniform allocation gives a universally safe exploration point; the optimal welfare value is continuous in the unknown mean matrix; and near-optimal allocations with proportionality slack exist. Those properties survive naturally after replacing named recipients by type masses. The real open issue is computational implementation of the second optimization round, not whether the mass model is meaningful.

My second anchor is Theorem 2 (proved here). It states that for some \(a,b,n,m\), no algorithm can simultaneously maintain envy-freeness in expectation and achieve regret below \(T^{2/3}/\log T\) with probability \(1-1/T\). Its continuous mirror is the following.

For the same type-mass instance, define envy-freeness by

\(\sum_k (x_{\theta k}/\rho_\theta)v_{\theta k}\ge \max_{\theta'}\sum_k (x_{\theta' k}/\rho_{\theta'})v_{\theta k}\)

for every type \(\theta\). The continuous problem asks for an online algorithm that learns the unknown type-level means, satisfies these inequalities at every round with high probability, and minimizes regret against the clairvoyant envy-free optimum.

Here the expected verdict is hardness transfers. The lower-bound construction already uses three players and three item types. Take \(\tau=3\), \(\rho_\theta=1/3\), and replicate each of those three player types arbitrarily many times. The aggregate assignment process, observed value distributions, fairness constraints, welfare, and statistical indistinguishability are unchanged. Thus the \(T^{2/3}\) barrier is present in a high-multiplicity population with constant support; it is not caused by the number of named recipients. This is a useful negative boundary for the mirror.

The main further questions are whether Theorem 1’s \(\sqrt T\) rate admits a genuinely polynomial-time type-level implementation; how its dependence on rare types \(\rho_{\min}\) behaves; whether deterministic item baskets preserve the same guarantees; and whether other fairness constraints, such as equitability, have the structural properties needed for the same rate. For envy-freeness, the three-type embedding suggests that increasing population multiplicity will not remove the lower bound.

My weakest point is that the positive anchor is a regret theorem, not an efficient-algorithm theorem: the authors explicitly leave Algorithm 1 with exponential runtime. Therefore I cannot honestly claim that the paper already demonstrates a polynomial-time Class A mirror. What it does provide is unusually strong evidence that the high-multiplicity version is the right object: its action space is a finite type-mass LP, its fairness constraints retain the paper’s exact structure, and its population-size dependence can plausibly disappear. The continuous mirror is consequently a credible computational research problem, with Theorem 1 as the lead target and Theorem 2 as its inherited boundary.