| paper | d4-conf-wine-2023-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 20
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 unit-mass population has \(\tau\) types with binary-rational masses \(\nu_r\). Item \(t\) arrives with per-capita supply \(q_t\) and values \(v_{rt}\); the policy chooses per-capita amounts \(a_{rt}\), subject to \(\sum_r\nu_r a_{rt}\le q_t\). Utilities are \(u_r=\sum_t v_{rt}a_{rt}\), and the objective is weighted Nash welfare \(\exp(\sum_r\nu_r\log u_r)\), compared with the offline optimum. Scaling total supply with population size preserves fixed per-capita supply.
The mirror covers the competitive lower bounds in Theorems 20 and 19, including the binary-value variant noted for Theorem 20. It leaves the paper’s online algorithmic upper bounds and prediction results unmirrored.
The strongest mirror is an online allocation problem for a large population with a small number of recurring utility types. The paper’s divisible items are already part of its outcome model; the mirror changes the population. For example, a food bank may serve hundreds of thousands of people whose additive values for food categories fall into a few dietary profiles. Donations still arrive in discrete rounds, and the distributor still has to allocate each batch immediately.
Let the population have types \(r\in\mathcal R\), with \(|\mathcal R|=\tau\), and rational masses \(\nu_r>0\) summing to \(1\). At round \(t\), an item arrives with per-capita supply \(q_t\) and value \(v_{rt}\) for each type. The decision \(a_{rt}\) is the amount allocated per person of type \(r\), subject to
\[
\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 the population’s Nash welfare is
\[
\mathrm{NW}_{\nu}(a)=\exp\!\left(\sum_{r\in\mathcal R}\nu_r\log u_r\right).
\]
The policy sees each supply and value column when that item arrives, as in the paper; it does not see the future sequence. If the actual population has \(M\) people, the corresponding total supply is \(M q_t\). This scaling keeps per-person supply fixed as the population grows. Each type describes agents identical in every respect relevant to the allocation.
My lead is the impartial-population online Nash-welfare problem. In the numbered arXiv version, Theorem 20, proved in this paper, says that for \(\mu^*\)-impartial instances no online algorithm can achieve a competitive ratio better than
\[
\min\!\left\{(\log\mu^*)^{1-o(1)},\frac{N-1}{e}\right\}.
\]
Here \(\mu^*\) is the ratio between the largest and smallest utilities in an offline Nash-welfare-maximizing allocation. The paper also remarks that the lower bound holds when values are \(0\) or \(1\). The theorem is proved from the paper’s own lower-bound construction and lemmas. [The numbered arXiv version](https://arxiv.org/abs/2211.03077)
The continuous question is: for a population distribution supported on \(\tau\) types and promised to be \(\kappa\)-impartial, what is the best worst-case competitive ratio achievable by an online allocation policy? The instance consists of the type masses, the online sequence of item supplies and type values, and the impartiality promise; a solution is an online policy and a competitive guarantee, or a lower-bound proof applying to every policy. I expect the paper’s lower bound to transfer at the type-support scale: in particular, equal masses on \(\tau\) types should give a lower bound of order \(\min\{(\log\kappa)^{1-o(1)},(\tau-1)/e\}\).
There is a direct reason to expect that transfer. The paper’s hard construction has \(n\) agents and \(n\) item rounds. Give each of its \(n\) agents a type of mass \(1/n\), then replicate each type across arbitrarily many identical people while scaling total supplies with population. The weighted Nash welfare is the same as in the \(n\)-agent instance. More generally, averaging any clones’ allocations gives a feasible per-type allocation; concavity of \(\log\) means unequal treatment of identical clones cannot improve their group’s geometric-mean utility over that average. Thus the high-multiplicity population retains the lower bound.
A second useful anchor is Theorem 19, also proved in this paper. It states that no algorithm can achieve a competitive ratio better than
\[
\min\!\left\{(\log(\lambda^*N))^{1-o(1)},\frac{N-1}{e}\right\}
\]
on \(\lambda^*\)-balanced instances, where \(\lambda^*\) is the ratio of the largest to smallest monopolist utility. Its proof combines the authors’ construction with their restatement of a lower bound by Banerjee et al. as Lemma 16. The corresponding continuous question is to determine the optimal worst-case online ratio for societies with \(\tau\) types and a \(\lambda\)-balance promise. The natural transferred lower bound is the same expression at the support scale \(\tau\), with \(\lambda\) in place of \(\lambda^*\).
These are online competitive impossibility questions, rather than NP-hardness claims. In the programme’s trichotomy, I expect the lower bounds to transfer: their finite-agent witnesses embed in equal-mass type distributions, so the continuum does not remove this difficulty. The model is plausible as a mirror of the authors’ problem because it preserves their objective, additive utilities, irrevocable online decisions, and offline benchmark; it aggregates only agents who are truly identical for the problem.
The mirror covers Theorems 19 and 20, not the paper’s entire algorithmic contribution. It also raises a useful next question: can the paper’s upper bounds be stated directly in \(\tau\), the type masses, and their bit length, rather than the total number of people? Small masses may matter in the weighted objective, so the right bound may need to depend on more than support size.
The weak point is that this argument does not produce a lower bound growing with the total population when \(\tau\) is fixed. The hard family needs its number of types to grow; cloning makes the population arbitrarily large while preserving that support-sized difficulty. So the claim is a genuine high-multiplicity mirror with a support-based lower bound, not a claim that an ever-larger crowd with a fixed set of types necessarily gets harder.
The strongest case against is that these lower bounds are driven by diversity of valuation profiles, not by the number of people in the population. For a fixed small set of types, the paper’s \(N\)-dependent bounds do not imply that adding more people makes the online problem harder. The paper also studies competitive ratios under adversarial arrivals, so a mirror would need to preserve the online information structure and state its dependence on type masses; simply replacing \(N\) by the support size is not justified for arbitrary masses.
That concern does not defeat either anchor. For the impartiality lower bound, take its \(n\)-agent hard instance and make each agent a type of mass \(1/n\). Set per-capita item supply to \(s_t/n\), where \(s_t\) was the original supply. The type allocation constraint is then equivalent to the original constraint, each type has the original agent’s utility, and the weighted log welfare is \(\frac1n\sum_i\log u_i\). The construction and its \(\mu^*\)-impartiality promise survive exactly, however many identical people represent each type. The balanced lower bound transfers by the same construction. Neither anonymity nor fractional treatment within a type erases the adversary’s choices.
In fact, any rational type masses can be represented by finitely many identical clones using a common denominator. Averaging clones’ allocations within each type preserves feasibility and, by concavity of \(\log\), cannot reduce their group’s geometric-mean utility. So the mirror is a high-multiplicity, compressed representation of finite-agent online allocation. That makes the case against look narrower: these theorems establish difficulty as the number of distinct types grows, but do not show that population growth with fixed support creates new difficulty.
I cannot turn that limitation into an honest argument that no worthwhile mirror exists. The proposed questions remain computationally meaningful: can algorithms and competitive guarantees be expressed in the support size and binary-encoded masses rather than the expanded clone count? The programme explicitly treats that high-multiplicity bridge as a deliverable. Both anchors survive the strongest objection I can substantiate, so the universal negative case is weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.