Proportionally Fair Online Allocation of Public Goods with Predictions

My strongest case is a narrow but credible Class A mirror, led by Theorem 5. The paper has no NP-hardness or \(P\)/\(W[1]\)-hardness theorem; its named computational anchors are online approximation guarantees and lower bounds. Theorem 5 is stated here and proved in the authors’ full version, Banerjee et al. [2022b]; it is not merely cited from prior work.

The natural regime is a large participatory-budgeting society: millions of residents, but only \(\tau\) recurring preference-and-value cohorts. A type is a complete cohort description: its cardinal valuation for every possible public-good class, its total-value prediction, and its prediction-error parameters. Mass \(\mu_\theta\) is the fraction of residents of type \(\theta\), with \(\sum_\theta\mu_\theta=1\). This is plausible for neighbourhoods, stakeholder groups, or demographic cohorts with repeated valuation templates. Public goods are important here: the resource need not scale with population, because one funded park or road benefits the whole population.

The lead problem is \(\textsc{Typed-Batched-PF}_{\infty}\). An instance consists of a finite type set \(\Theta\), rational masses \(\mu_\theta\), \(T\) rounds, \(L\) goods arriving per round, and budget \(B\). At round \(t\), the policy observes the current values \(v_{\theta,\ell,t}\), but not future rounds, and irrevocably chooses \(x_{\ell,t}\in[0,1]\), subject to

\[ \sum_{\ell=1}^{L}x_{\ell,t}\le 1 \qquad\text{and}\qquad \sum_{t=1}^{T}\sum_{\ell=1}^{L}x_{\ell,t}\le B. \]

Type \(\theta\)'s utility is

\[ u_\theta(x)=\sum_{t=1}^{T}\sum_{\ell=1}^{L}v_{\theta,\ell,t}x_{\ell,t}. \]

Given prediction \(\widehat V_\theta\) for \(V_\theta=\sum_{t,\ell}v_{\theta,\ell,t}\), and error parameters \(c_\theta,d_\theta\), the policy must produce \(x\) satisfying

\[ \max_{w\in\mathcal F} \sum_{\theta\in\Theta} \mu_\theta \frac{u_\theta(w)}{c_\theta u_\theta(x)} \le \alpha, \]

for every legal adversarial arrival sequence consistent with the predictions. In the exact-prediction case \(c_\theta=d_\theta=1\), this is precisely the paper’s proportional-fairness objective with the finite-agent average replaced by a population integral.

The expected answer is an efficient type-level version of Algorithm 1. In round \(t\), form the favourite-good set

\[ F_t=\bigcup_{\theta\in\Theta} \arg\max_{\ell}v_{\theta,\ell,t}, \]

so \(|F_t|\le \min\{\tau,L\}\), allocate a set-aside amount \(B/(2|F_t|T)\) to every good in \(F_t\), and use the remaining budget in the paper’s greedy convex program, replacing the unweighted agent average by

\[ \sum_{\theta\in\Theta}\mu_\theta \ln \widetilde u_{\theta,t}. \]

The predicted promised utility uses the type mass only through this weighted objective. The conjectured analogue of Theorem 5 is therefore

\[ \alpha\ge 4\ln\!\left( \frac{2\min\{\tau,L\}T}{B} \right) + 4\sum_{\theta\in\Theta}\mu_\theta\ln d_\theta. \]

With exact predictions, this gives \(\mathcal O(\log(\min\{\tau,L\}T/B))\), independent of the potentially enormous number of named residents. The original Theorem 5 gives the same form with \(N\) in place of \(\tau\); replacing \(N\) by \(\tau\) is the new continuous-population claim that requires proof.

This is recognisably the authors’ problem rather than a tractable redesign. The online stream, irrevocability, public-good budget, cardinal utilities, predictions, and proportional-fairness objective are all retained. Only the population representation changes. For rational \(\mu\), clearing denominators creates a finite population of identical clones, and

\[ \frac1N\sum_i \frac{u_i(w)}{c_i u_i(x)} = \sum_{\theta}\mu_\theta \frac{u_\theta(w)}{c_\theta u_\theta(x)}. \]

Thus the mirror has exact rational-clone fidelity while potentially being exponentially smaller than the expanded population.

A useful secondary anchor is the paper’s binary approval case, combining Theorem 1 and Theorem 2. Theorem 1 gives the \(\Omega(\log N)\) lower bound, and Theorem 2 gives the matching \(O(\log N)\) algorithm; both are original results stated here with proofs deferred to [Banerjee et al. 2022b].

The corresponding problem, \(\textsc{Typed-Approval-PF}_{\infty}\), has types \(\theta\in\{0,1\}^{T}\), rational masses \(\mu_\theta\), unit budget \(\sum_t x_t\le1\), and utility

\[ u_\theta(x)=\sum_{t=1}^{T}\theta_t x_t. \]

The policy sees the current approval pattern at each arrival, may know each type’s total number of approved goods, and must minimize the worst-case

\[ \max_{w:\,\sum_t w_t\le1} \sum_\theta \mu_\theta \frac{u_\theta(w)}{u_\theta(x)}. \]

The type-level set-aside argument should give \(O(\log\tau)\), since only the first liked good of each type matters to the set-aside budget. The lower bound survives in a genuine high-multiplicity regime: take a hard \(N=\tau\)-type instance and replace every type by \(K\) identical agents. The mass vector is unchanged, the fairness objective is unchanged, but the finite population is \(K\tau\), arbitrarily larger than the number of types. The expected answer is therefore a tight \(\Theta(\log\tau)\) online guarantee, not a dependence on the raw population size.

These mirrors cover Theorem 5, its Corollary 2, the \(L=1\) specialization corresponding to Theorem 3, and the binary Theorems 1–2. They do not claim to continuize every result in the paper, nor do they address the private-goods special case.

The weakest point is that the crucial \(N\)-to-\(\tau\) improvement is not proved in the paper. It depends on an explicit information model in which the policy receives type-aggregated current values and masses without being shown future valuation trajectories. If types are nearly unique, or if revealing type identity reveals the future, the compression disappears or the online problem changes. So this is best presented as a faithful, author-recognisable high-multiplicity extension of their theorems—not as an automatic corollary.