Private online allocation gets a meta-algorithm: PPOA adds noise to budgets and duals while keeping competitive ratios near the non-private ceiling
In online allocation, a shared budget turns one request's decision into a side channel on other users' contexts, while standard differential privacy barely lets an algorithm adapt actions to context. PPOA treats the remaining budget and the Lagrangian dual variable as the coordination quantities to privatize, and gives sufficient conditions for meeting budget constraints with asymptotically near-optimal performance under joint or local differential privacy. Of its two instantiations, PPOA-FTRL reaches a 0.834 competitive ratio when only joint privacy is required, and PPOA-DMD reaches 0.665 while satisfying both privacy notions.