Fair and Efficient Online Allocations with Normalized Valuations

The strongest mirror is a high-multiplicity version of the paper’s two-agent online allocation problem. The population, rather than the arriving resources or time, is the continuous object.

Take two types \(A\) and \(B\), each with mass \(1/2\). A type is a complete normalized valuation stream \(v_\theta=(v_{\theta 1},\ldots,v_{\theta T})\), with \(v_{\theta t}\ge0\) and \(\sum_t v_{\theta t}=1\). A concrete finite approximation has \(K\) identical agents of each type and \(K\) divisible units of every item. All agents of type \(\theta\) have the same value density \(v_{\theta t}\) for round \(t\). If \(x_{\theta t}\) is the average amount of round \(t\)'s batch allocated to one member of type \(\theta\), symmetry gives the capacity constraint \(x_{At}+x_{Bt}\le1\). This is exactly the \(K\to\infty\) high-multiplicity regime: \(N=2K\) agents but only \(\tau=2\) types.

The scaling is substantive but natural. A full batch has value \(K\) to an agent whose normalized stream sums to one, so the usual fair-share threshold is \(K/(2K)=1/2\), exactly the threshold in the paper. Define \(u_\theta=\sum_t v_{\theta t}x_{\theta t}\), and normalized welfare \(W=u_A+u_B\). The offline welfare benchmark is \(\mathrm{OPT}=\sum_t\max\{v_{At},v_{Bt}\}\). Values for round \(t\) are revealed only when that batch arrives, and \(x_{At},x_{Bt}\) are irrevocable.

Thus the problem remains online fair division with normalized additive valuations. What has changed is that individual identities and idiosyncratic histories have been replaced by mass of indistinguishable agents. Items remain discrete in time and divisible, as in the paper; I am not using outcome-space continuity as a substitute for population continuity.

My lead question is:

\(\mathrm{COFA}^{\mathrm{guard}}_2\): Given \(T\), two type valuation streams, and the online revelation protocol above, construct an online rule producing \(x_{At},x_{Bt}\) such that \(u_A,u_B\ge1/2\) for every stream, and maximize the worst-case ratio \(W/\mathrm{OPT}\). A solution is an online policy mapping every observed prefix to the next feasible type-level allocation.

The natural candidate is precisely the guarded poly-proportional rule from the paper: while no type is at a critical point, use \(x_{\theta t}=v_{\theta t}^p/(v_{At}^p+v_{Bt}^p)\); once a type’s accumulated utility plus its remaining possible value reaches \(1/2\), allocate all subsequent batches to that type. The paper’s Lemma 4, proved here, establishes that the guarded rule satisfies fair-share for every \(p\ge0\).

The main anchor is Theorem 3, proved here. It states that the guarded poly-proportional algorithm with \(p=2.7\) achieves a \(0.916\) approximation to optimal social welfare. In the mirror, the theorem asks whether the same rule, interpreted as a mass allocation to two large homogeneous populations, guarantees \(W\ge0.916\,\mathrm{OPT}\). The paper’s proof is unusually suggestive for continuization: after fixing the valuation ratios, the worst-case program is linear in the remaining mass variables, and the extremal instance has only a few positive rounds. That is exactly the sort of finite-dimensional collapse one would hope to exploit in a population-continuous formulation.

I expect \(\mathrm{COFA}^{\mathrm{guard}}_2\) to be tractable, at least for fixed \(p\) and fixed approximation accuracy. Its input is a finite type distribution, its policy is closed-form, and its worst-case analysis reduces to continuous optimization over a small number of active rounds. The programme’s open question would be whether the numerical \(0.916\) can be certified exactly, improved, or generalized to unequal type masses and more than two types.

The corresponding optimal-policy question is:

\(\mathrm{COFA}^{\star}_2\): For the same continuous two-type instance space, determine \(\alpha^\star_2=\sup_{\mathcal A}\inf_v W_{\mathcal A}(v)/\mathrm{OPT}(v)\), where \(\mathcal A\) ranges over all online policies satisfying \(u_A,u_B\ge1/2\) on every valuation stream. The output is either the optimal competitive ratio or an online policy attaining a specified target \(\alpha\).

The second anchor is Theorem 4, also proved here. It states that no fair-share online algorithm can achieve an approximation better than \(0.933\) to optimal social welfare, even if it knows the number of rounds \(T\) in advance. The proof uses two valuation streams with the same first-round observation: in both, the first-round values are \(0.568\) and \(0.427\); one stream ends with second-round values \(0.432\) and \(0.573\), while the other gives type \(B\) values \(0.306\) and then \(0.267\) in a third round. Any policy must make the same first decision on both prefixes, and either fairness or the welfare ratio then fails.

This lower bound carries over exactly to the high-multiplicity mirror. Every one of the \(K\) agents of a type sees the same prefix, and the \(K\)-batch scaling makes the inequalities identical. Therefore the continuous population does not erase the online impossibility: it preserves a nontrivial gap \(0.916\le\alpha^\star_2\le0.933\). I would expect \(\mathrm{COFA}^{\star}_2\) to be approachable by low-dimensional robust optimization rather than by a hardness reduction driven by population multiplicity. The unresolved issue is whether the gap is an artefact of the guarded family or reflects the true optimum.

The regime is plausible in the paper’s own applications. Think of two large pools of soup kitchens, charities, or software teams, where every member of a pool has the same normalized demand profile across the sequence of arriving resources. The number of agents is \(2K\), the number of types is \(2\), and \(K\) can be arbitrarily large. This is not the objection that prices or costs became type-level: the agents genuinely are identical in every respect used by the model. Any identity-level allocation can be symmetrized within each type without changing aggregate welfare or fair-share utilities.

This mirror covers the paper’s central two-agent algorithmic results, especially Theorems 3 and 4. It does not claim to continuize every result in the paper, nor does it use the \(n\ge3\) section. The paper contains no named NP-hardness, W[1]-hardness, or completeness theorem, so there is no honest hardness anchor to prefer; its relevant named results are approximation and impossibility bounds.

The weak point is that, after symmetry and scaling, the two-type continuous problem has essentially the same formulas as the paper’s two-agent problem. An opponent can fairly say that the continuum mainly removes redundant clone identities rather than creating a radically new combinatorial object. My answer is that this is exactly what a high-multiplicity mirror should do: it tests whether the named-agent formulation was really about individuals or about masses of interchangeable agents. Here the authors’ online question survives intact, while the population becomes genuinely continuous and the number of types stays fixed as the population grows.