Deep reinforcement learning ensures truthful resource sharing online
Strategyproof Deep Reinforcement Learning for Online Resource Allocation
Multiagent SystemsArtificial IntelligenceComputer Science and Game Theory
Summary
Allocating limited resources online is hard because future demands are uncertain and people might lie about what they need or value. The authors developed a deep reinforcement learning method that encourages truthful reporting by design, using special neural networks and payment rules. This method learns complex allocation patterns beyond simple linear rules and performs close to the best possible solution. It also learns faster when trained by mimicking an existing method.
What this means in practice
- •For cloud infrastructure teams: Automate truthful and efficient allocation of computing resources to users with varying and uncertain demands.
- •For online advertising platforms: Ensure advertisers report true valuations while optimizing the allocation of limited ad slots using flexible learned allocation strategies.
Authors
Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah, Stephanie Gauthier
Abstract
Online resource allocation faces two coupled challenges: (1) allocating scarce resources efficiently under uncertain future demand, and (2) ensuring that agents report task valuations and requirements truthfully (strategyproofness). Reinforcement Learning (RL) adapts allocation decisions through experience but does not necessarily ensure strategyproofness. Existing strategyproof RL uses a linear allocation rule, which limits the resource interactions it can represent. Neural mechanism design methods offer greater expressiveness, but provide only approximate incentive guarantees. Against this background, we introduce the first strategyproof deep RL mechanism for online resource allocation. It integrates three novel components: (i) a monotonic neural network that learns nonlinear interactions by construction (higher reported value cannot reduce acceptance, while a longer reported duration or larger resource requirement cannot increase it); (ii) a generalised critical payment: the lowest accepted value, with all other inputs fixed; and (iii) training by either RL or imitation of an existing rule. Together, monotonicity and the critical payment ensure strategyproofness and individual rationality, while the neural rule provides flexibility and imitation improves training efficiency. Empirically, on a four-resource stream with two partner pairs that a linear difference cannot represent, the neural rule achieves 97.8% of an offline welfare upper bound, compared with 93.8% for a linear learner and 89.0% for first-come, first-served, closing 65% and 80% of the remaining optimality gap, respectively. Moreover, imitation reaches 97.5% in only 261 seconds, about 89 times faster than RL.