Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation
arXiv:2507.09473
The paper proposes an Incentive-Aware Primal-Dual framework for allocating indivisible resources to strategic agents under long‑term constraints, achieving near‑optimal social welfare regret while encouraging near‑truthful reporting.
Abstract
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 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 regret near-matches the non-strategic lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.
A preliminary version was accepted to NeurIPS 2025. This version includes extension to multi-unit resource allocation, expanded numerical simulation, extensively refind technical exposition, and enhanced literature review and positioning