Incentive-Aware Dynamic Resource Allocation under Long-Term Cost Constraints
This addresses resource allocation challenges in applications like cloud platforms and mobile health units, providing a robust solution for strategic settings, though it is incremental as it builds on primal-dual methods.
The paper tackles the problem of dynamically allocating reusable resources to strategic agents with private valuations while maximizing social welfare, satisfying long-term cost constraints, and ensuring truthful reporting. It develops an incentive-aware framework that achieves $ ilde{\mathcal{O}}(\sqrt{T})$ social welfare regret, matches non-strategic performance, and satisfies all constraints.
Motivated by applications such as cloud platforms allocating GPUs to users or governments deploying mobile health units across competing regions, we study the dynamic allocation of a reusable resource to strategic agents with private valuations. Our objective is to simultaneously (i) maximize social welfare, (ii) satisfy multi-dimensional long-term cost constraints, and (iii) incentivize truthful reporting. We begin by numerically evaluating primal-dual methods widely used in constrained online optimization and find them to be highly fragile in strategic settings -- agents can easily manipulate their reports to distort future dual updates for future gain. To address this vulnerability, we develop an incentive-aware framework that makes primal-dual methods robust to strategic behavior. Our design combines epoch-based lazy updates -- where dual variables remain fixed within each epoch -- with randomized exploration rounds that extract approximately truthful signals for learning. Leveraging carefully designed online learning subroutines that can be of independent interest for dual updates, our mechanism achieves $\tilde{\mathcal{O}}(\sqrt{T})$ social welfare regret, satisfies all cost constraints, and ensures incentive alignment. This matches the performance of non-strategic allocation approaches while being robust to strategic agents.