MIT Researchers' IAPD Framework Solves Strategic Resource Allocation with Near-Optimal Regret

In a paper accepted to NeurIPS 2025, MIT researchers tackle the fundamental problem of allocating indivisible resources to strategic agents over time while maximizing social welfare, satisfying long-term constraints, and ensuring truthful reporting. They show that standard primal-dual methods are fragile—agents can manipulate reports to distort dual variables, sacrificing efficiency for individual gain. To counter this, the team proposes the Incentive-Aware Primal-Dual (IAPD) framework.

On the primal side, IAPD integrates three components: a VCG-based payment to neutralize immediate misreporting benefits, epoch-based lazy updates, and random exploration to ensure any potential future gains are outweighed by immediate penalties. On the dual side, they design O-FTRL-FP, an optimistic online learning algorithm that uses a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. The mechanism achieves O(√T) social welfare regret—matching the non-strategic lower bound—while satisfying all long-term constraints and inducing a near-truthful equilibrium. It also generalizes smoothly to multi-unit multi-demand problems, demonstrating that incentive-awareness can be achieved at nearly no cost.