Strategyproof Deep Reinforcement Learning for Online Resource Allocation

Fariba Dehghan; Sebastian Stein; Vahid Yazdanpanah; Stephanie Gauthier

cs.MAOct 27, 2026

Strategyproof Deep Reinforcement Learning for Online Resource Allocation

Authors: Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah, Stephanie Gauthier

Organizations: University of Southampton

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.

Figures & tables

stream	$\mathbf{b}$	$T$	class probabilities	tasks	$\mathrm{OPT}$
Partner	$[3,1,1,3]$	$80$	$(0.22,0.22,0.28,0.28)$	A,B: $\{r_{1},r_{2}\}$ , $\{r_{3},r_{4}\}$ , $v{=}24$ , $\ell{=}6$ ; C,D: $r_{1}$ / $r_{4}$ , $v{=}6$ , $\ell{=}12$	LP
Small	$10$	$20$	fixed	$v{=}1$ , $\ell{=}11$ except $t{=}11$ : $v{=}15$ , $\ell{=}1$	exact
Large	$5$	$100$	$0.1/0.9$	$v{=}100$ , $\ell{=}1$ ; else $v{=}20$ , $\ell{=}25$	exact
Cont.	$[20,10]$	$80$	$0.15/0.85$	$\ell\sim\mathrm{Unif}\{1,\ldots,15\}$ ; high-density mixed demand, else sparse	LP
Compl.	$[6,6]$	$80$	$0.30/0.30/0.40$	joint $[1,1]$ : premium $v{=}10$ , $\ell{=}2$ or long $v{=}2.5$ , $\ell{=}10$ ; else $v{=}1.5$ , $\ell{=}10$ , $3$ units of one resource	LP

Table 1. Allocation streams.

Figure 1. (a)–(e) RL

W/\mathrm{OPT}

(mean

\pm

s.e.); hatched bars are planner cloning. (f) Partner time: circles RL, squares Union BC, diamonds planner BC. RL welfare over OPT on five streams with planner cloning as hatched bars, and Partner training time.

Figure 2. Partner stream. (a)–(b) misreport search; (c)–(d) class service; (e)–(f) revenue in value units. Partner-stream regret, by-lie rate, class service, Jain index, revenue and revenue share.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$m,r,b_{r},T,t,i$	number of resource types; resource index; capacity; horizon; slot; arrival
$\theta_{i}=(v_{i},\ell_{i},\mathbf{d}_{i})$	true type
$\hat{\theta}_{i}$ , $\hat{\Theta}_{<i}$	report; history before $i$
$s$ , $\mathbf{f}(s)$ , $f_{r}(s)$	state; free-capacity vector and its resource- $r$ coordinate
$\mathcal{M}=(x,p)$	allocation and payment
$W$ , $U_{i}$ , $c$ , $\mathbf{1}[\cdot]$	welfare; utility of $i$ ; covering indicator; indicator

Appendix

Table B.1. Principal notation used in the main text.

quantity	value
$\varepsilon$	$0.1\to 0$ linearly
LinearMono	SGD, learning rate $0.1\to 0$
SP-SMM / SMNN	Adam ( Kingma and Ba, 2015 ) , $5\cdot 10^{-3}\to 10^{-5}$
other neural models	Adam, $10^{-2}\to 10^{-5}$
gradient clipping (neural)	$\ell_{2}$ norm at $5$
fitted SARSA refresh / passes / minibatch	$20$ episodes / $5$ / $64$

Appendix

Table D.1. Training and imitation settings.

	welfare / $\mathrm{OPT}$					Partner
method	Partner	Small	Large	Cont.	Compl.	gap	train (s)
SP-SMM	$\mathbf{0.978\pm 0.001}$	$0.942\pm 0.017$	$0.912\pm 0.021$	$0.812\pm 0.010$	$0.953\pm 0.003$	$\mathbf{2.2\%}$	23,255
LipschitzMono ( Nolte et al., 2023 )	$0.960\pm 0.006$	$0.883\pm 0.117$	$\mathbf{0.946\pm 0.014}$	$0.804\pm 0.007$	$0.946\pm 0.010$	4.0%	84,607
SMNN ( Kim and Lee, 2024 )	$0.957\pm 0.001$	$0.717\pm 0.127$	$0.795\pm 0.072$	$\mathbf{0.824\pm 0.006}$	$0.949\pm 0.006$	4.3%	12,558
MonoDense ( Runje and Shankaranarayana, 2023 )	$0.946\pm 0.003$	$0.883\pm 0.076$	$0.914\pm 0.037$	$0.808\pm 0.003$	$0.959\pm 0.001$	5.4%	9,119
MonoNet ( Nguyen and Martínez, 2019 )	$0.943\pm 0.001$	$0.767\pm 0.143$	$0.785\pm 0.066$	$0.769\pm 0.011$	$0.913\pm 0.031$	5.7%	9,003

Appendix

Table E.1. RL welfare divided by the offline optimum, with Partner training time.

setting	method	Rule BC	Planner BC	DAgger	DAggerW	DART
Partner	SP-SMM	$\mathbf{0.975\pm 0.000}$	$0.973\pm 0.001$	$0.972\pm 0.002$	$0.973\pm 0.001$	$0.971\pm 0.002$
	LipschitzMono	$\mathbf{0.975\pm 0.001}$	$0.971\pm 0.001$	$0.974\pm 0.002$	$0.974\pm 0.002$	$0.970\pm 0.002$
	SMNN	$0.937\pm 0.002$	$0.933\pm 0.006$	$0.933\pm 0.002$	$\mathbf{0.938\pm 0.004}$	$0.919\pm 0.012$
	MonoDense	$\mathbf{0.947\pm 0.008}$	$0.941\pm 0.004$	$0.940\pm 0.003$	$0.940\pm 0.006$	$0.937\pm 0.006$
	MonoNet	$\mathbf{0.938\pm 0.002}$	$0.917\pm 0.003$	$0.918\pm 0.003$	$0.931\pm 0.002$	$0.927\pm 0.003$
	PMLinear	$\mathbf{0.936\pm 0.002}$	$0.930\pm 0.004$	$0.927\pm 0.002$	$0.931\pm 0.001$	$0.928\pm 0.003$

Appendix

Table F.1. Imitation welfare divided by offline optimum.

setting	method	Rule BC	Planner BC	DAgger	DAggerW	DART
Partner	SP-SMM	261	386	410	412	382
	LipschitzMono	643	724	751	739	808
	SMNN	173	278	339	472	268
	MonoDense	134	247	256	272	244
	MonoNet	133	237	273	292	279
	PMLinear	88	197	206	214	198

Appendix

Table F.2. Imitation fitting time in seconds.

	Union BC			DAggerW
method	Jain	min. rate	served	Jain	min. rate	served
SP-SMM	$0.999\pm 0.000$	$0.424\pm 0.001$	$0.439$	$1.000\pm 0.000$	$0.443\pm 0.001$	$0.449$
LipschitzMono	$0.999\pm 0.000$	$0.423\pm 0.003$	$0.439$	$1.000\pm 0.000$	$0.442\pm 0.002$	$0.450$
SMNN	$0.995\pm 0.002$	$0.393\pm 0.010$	$0.422$	$0.997\pm 0.002$	$0.412\pm 0.005$	$0.439$
MonoDense	$0.997\pm 0.001$	$0.401\pm 0.010$	$0.429$	$0.995\pm 0.003$	$0.405\pm 0.009$	$0.446$
MonoNet	$0.998\pm 0.001$	$0.405\pm 0.007$	$0.427$	$0.994\pm 0.001$	$0.398\pm 0.004$	$0.447$

Appendix

Table F.3. Class-level service after imitation on the partner benchmark.

score	accepted	rev.	welf.
U-MLP	$46\%$	$0$	$456$
V-MLP	$26\%$	$223$	$403$
LinearMono	$44\%$	$168$	$478$
SP-SMM	$45\%$	$465$	$491$
LipschitzMono	$44\%$	$475$	$495$
SMNN	$43\%$	$144$	$484$

Appendix

Table G.1. After-training misreport search on the partner stream: accepted share, revenue, and welfare.

score	accepted	by lie	max mean regret $/v_{\max}$
U-MLP	$36\%$	$43\%$	$0.351$
V-MLP	$44\%$	$29\%$	$0.215$

Appendix

Table G.2. Worst checkpoint during training on the partner stream, controls only.

score	Partner	Small	Large	Cont.	Compl.
U-MLP	$0.351$	$0.076$	$0.200$	$0.090$	$0.450$
V-MLP	$0.215$	$0.050$	$0.193$	$0.038$	$0.342$

Appendix

Table G.3. Maximum mean regret during training as a fraction of

v_{\max}

, controls only.

method	Jain $J(\boldsymbol{\eta})$	min. rate	served
FCFS	$0.974$	$0.372$	$0.456$
SP-SMM	$1.000\pm 0.000$	$0.440\pm 0.002$	$0.446$
LipschitzMono	$0.997\pm 0.001$	$0.413\pm 0.013$	$0.436$
LinearMono	$0.998\pm 0.001$	$0.414\pm 0.003$	$0.436$
SMNN	$0.997\pm 0.001$	$0.403\pm 0.007$	$0.426$
MonoDense	$0.995\pm 0.003$	$0.384\pm 0.016$	$0.422$

Appendix

Table H.1. Per-class service after training from random initialisation. U-MLP matches FCFS and is omitted.

Online Resource Allocation

Online resource allocation studies how to assign scarce capacity to arriving requests under uncertainty while balancing reward, cost, fairness, and feasibility.

See all 95 papers

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation
Jul 13, 2025Yan Dai, Negin Golrezaei, Patrick JailletGame Theory Online Convex Optimization
Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.
Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand
Jun 9, 2026Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1Sequential Decision Making Fair Resource Allocation
Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA
Fair Online Resource Allocation
Jun 17, 2026Christopher En, Yuri Faenza, Andrea Lodi +1Sequential Decision Making Fair Resource Allocation
Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

Jul 13, 2025J/K move · Enter open · S save

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

Yan Dai, Negin Golrezaei, Patrick Jaillet

Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Game Theory Online Convex Optimization Mechanism Design Primal-Dual Optimization Online Resource Allocation Constrained Optimization+1

Open paper AskPDF arXiv

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

\tilde{\mathcal O}(\sqrt 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

\tilde{\mathcal O}(\sqrt T)

regret near-matches the non-strategic

Ω(\sqrt T)

lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Abstract

Online Resource Allocation

Explore similar work

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand

Fair Online Resource Allocation