# Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

arXiv: https://arxiv.org/abs/2507.09473 · HTML: https://mlsanity.com/paper/2507.09473/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2025.

## Abstract (arXiv)

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains tildemathcal O(√ T) social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this tildemathcal O(√ T) regret near-matches the non-strategic Omega(√ T) lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.