2025/07/13 by Yan Dai, Dai, Yan, Negin Golrezaei +3
Computer Science · Engineering · #Cloud Computing and Resource Management #Computer Science and Game Theory (cs.GT) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2507.09473
openalex publication_date 2025/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 \mathcal 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 \mathcal O(√ T) regret near-matches the non-strategic Ω(√ T) lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.