Privacy, Prediction, and Allocation

1. Problem Statement

The paper addresses the fundamental tension in resource allocation systems (e.g., humanitarian aid, social welfare) between efficiency (targeting resources to those who benefit most) and privacy (protecting sensitive individual data).

• The Dilemma:
  • Individual-Level Allocation (ILA): Uses detailed personal data to target specific individuals. It is highly efficient but raises severe privacy concerns (e.g., revealing poverty status) and relies on data that may be expensive or impossible to collect.
  • Unit-Level Allocation (ULA): Uses aggregated data (e.g., geographic regions, demographic clusters) to allocate resources collectively. It is more privacy-preserving and inclusive but suffers from lower precision (coarse targeting).
• The Gap: While recent literature has shown that ULA can sometimes outperform ILA due to data limitations or inequality, and other works have advocated for ULA on privacy grounds, there is no unified theoretical framework quantifying the tradeoffs between privacy, efficiency, and targeting precision under Differential Privacy (DP) constraints.
• Objective: The authors aim to characterize the asymptotic regimes where ILA or ULA is optimal when the allocation mechanism must satisfy Differential Privacy, considering both the cost of data collection and the inherent unpredictability of welfare outcomes.

2. Methodology and Model

The authors extend the economic model of aid allocation proposed by Shirali et al. [60] by integrating Joint Differential Privacy (Joint DP).

• Model Setup:

  • A population $P$ is divided into $M$ units of size $N$.
  • Each individual $i$ has a welfare score $w_i \in [0, 1]$.
  • The goal is to maximize total welfare improvement (Utilitarian social welfare) by allocating $k$ units of aid.
  • Treatment Effect: Homogeneous; aiding a "low-welfare" individual increases their welfare by $\delta_w$.
  • Regret: Defined as the difference between the welfare achieved by the algorithm and the optimal non-private allocation.

• Privacy Framework:

  • The paper uses Joint $\psi$-zCDP (zero-Concentrated Differential Privacy).
  • Rationale: Standard DP is too strict for allocation because it prevents the output for an individual from depending on their own data. Joint DP allows an individual's output to depend on their own data but ensures that changing one individual's data does not significantly change the distribution of others' outputs. This is formalized via the Billboard Lemma.

• Three Analytical Settings:

  1. Directly Observable Welfare: True welfare scores are known; the challenge is only adding noise to satisfy DP.
  2. Costly Sampling (Fixed Scores): Administrators must pay a cost $c_2$ to sample individual welfare scores before allocating. This introduces an exploration/exploitation tradeoff (spending budget on data vs. aid).
  3. Learning from Features (Stochastic): Administrators have access to feature vectors $x_i$ for the whole population and sample labels $y_i$ to train a predictive model under DP.

3. Key Contributions

A. Private Algorithms for ILA and ULA

The authors design specific algorithms for both strategies that satisfy Joint DP:

• Private ILA ($\tilde{ILA}$): Uses a noisy empirical Cumulative Distribution Function (CDF) of welfare scores to determine a threshold. Individuals below the threshold receive aid.
• Private ULA ($\tilde{ULA}$): Computes a noisy estimate of the average welfare profile for each unit ($\rho_j$) and allocates aid to the units with the lowest profiles.
• Private ULA with Private Membership: A variant (Algorithm 3) that handles cases where unit membership itself is sensitive, using a composition of privacy budgets.

B. Regret Bounds and Asymptotic Regimes

The paper derives clean, interpretable bounds on the normalized regret for both strategies across the three settings.

1. Setting: Direct Observation (No Sampling Cost)

• Result: The "price of privacy" is asymptotically negligible ($O(1/\sqrt{\psi})$).
• Implication: Both ILA and ULA can achieve near-optimal performance relative to non-private baselines as the population size grows, provided the privacy parameter $\psi$ is fixed.

2. Setting: Costly Sampling (Fixed Welfare)

• Tradeoff: The optimal strategy depends on $\lambda = c_2/c$ (cost of sampling vs. cost of aid).
• Phase Transition:
  • If sampling is cheap ($\lambda$ is low), ILA is optimal because it can afford to sample enough individuals to target precisely.
  • If sampling is expensive ($\lambda$ is high), ULA dominates. ULA requires only a sublinear number of samples (to estimate unit averages) to achieve near-optimal targeting, whereas ILA requires a constant fraction of the budget just to sample.
  • Key Finding: When $\lambda \ge 1$ (sampling is as expensive as aid), ULA strictly dominates ILA.

3. Setting: Learning from Features (Stochastic)

• Decomposition: The authors decompose the error into Excess Risk (model bias/estimation error) and Irreducible Risk ($\sigma^2$, inherent unpredictability of outcomes).
• Robustness of ULA: ULA is significantly more robust to high irreducible risk ($\sigma^2$). By averaging over a unit, ULA "washes out" the noise in individual predictions. ILA, which targets individuals based on noisy predictions, suffers higher regret when outcomes are fundamentally unpredictable.
• Modeling vs. Sampling:
  • For ILA, modeling is superior to pure sampling when the cost of features is high.
  • For ULA, modeling only outperforms pure sampling if the number of units $M$ is large enough to leverage cross-unit similarities, and if the model can reduce the excess risk significantly.

4. Key Results and Insights

• The Role of Inequality (Gini Coefficient $G$):

  • High inequality between units makes unit membership a strong proxy for individual welfare.
  • ULA dominates ILA when inequality is high, budgets are small, data is expensive, or outcomes are hard to predict.
  • ILA dominates ULA only when inequality is low, budgets are large, and outcomes are highly predictable.

• Privacy Parameter Impact:

  • Surprisingly, the specific value of the privacy parameter $\psi$ has little impact on the choice of the optimal strategy (ILA vs. ULA). It affects the magnitude of the regret but not the asymptotic regime where one strategy outperforms the other.

• Unified Framework:

  • The paper provides the first general framework showing that the tradeoffs identified in non-private literature (Shirali et al.) hold even under strict DP constraints. Privacy does not fundamentally alter the conditions under which coarse targeting (ULA) is preferable to fine-grained targeting (ILA).

5. Significance

• Policy Guidance: The results offer concrete guidelines for administrators. If data collection is expensive or privacy risks are high, or if the target population is highly heterogeneous (high inequality), aggregating data at the unit level is not just a privacy compromise but an efficiency-optimal strategy.
• Theoretical Bridge: The work bridges the gap between the theoretical literature on Differential Privacy (which often assumes known valuations) and the applied literature on aid allocation (which deals with learning valuations under constraints).
• Privacy as a Feature, Not a Bug: The paper demonstrates that privacy constraints do not necessarily degrade system performance; rather, they shift the optimal operating point toward strategies (like ULA) that are inherently more robust to data scarcity and noise.
• Future Directions: The authors suggest extending the model to include adaptive sampling (bandits) and strategic behavior (performative prediction), acknowledging that the current model assumes static welfare scores.

In summary, this paper rigorously proves that Unit-Level Allocation is often the superior strategy in real-world scenarios characterized by limited budgets, expensive data, high inequality, and fundamental unpredictability, even when strict differential privacy is enforced.