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

Jul 13, 2025

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

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.

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

Ask PDF

Jun 9, 2026

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

Dynamic multi-resource allocation is a central problem in shared computing environments, where users' demands arrive sequentially and resources must be distributed fairly without knowledge of future demands. Existing methods emphasize fairness guarantees such as Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, but often overlook system utility. Moreover, these fairness criteria are mutually incompatible, preventing strict enforcement of them at the same time. We propose a neural allocation mechanism that reconciles fairness with utility through multi-objective optimization during sequential rollout. We first formalize fairness in the dynamic setting via stepwise loss functions for Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, enabling differentiable training. Leveraging non-wastefulness, we parameterized the solutions by constraining allocations to the subspace of demand while allowing elastic over-allocation when resources remain available. Empirical results demonstrate that our learned allocator achieves substantially higher utility at comparable levels of fairness, uncovering clear Pareto-frontier-like tradeoffs across metrics.

Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1

Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Online Resource Allocation

Ask PDF

Jun 17, 2026

Fair Online Resource Allocation

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an

Ω(1/γ)

fraction of the optimal unfair allocation, where

γ

is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.

Christopher En, Yuri Faenza, Andrea Lodi +1

Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Group Fairness Online Resource Allocation

Ask PDF

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