Strategyproof Deep Reinforcement Learning for Online Resource Allocation

Strategyproof Deep Reinforcement Learning for Online Resource Allocation Fariba Dehghan* , Sebastian Stein* , Vahid Yazdanpanah* , Stephanie Gauthier* * University of Southampton

UK {F.Dehghan, V.Yazdanpanah, S.Gauthier}@soton.ac.uk, ss2@ecs.soton.ac.uk

arXiv:2610.37504v1 [cs.MA] 27 Oct 2026

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.

Keywords Strategyproofness, critical payments, neural networks, online resource allocation, imitation learning

1

Introduction

In resource allocation problems, a limited capacity needs to be assigned among competing tasks. In the setting we study, each task has a value, a duration and a demand for one or more resource types. In the online version we study, later arrivals are unknown, and the provider must accept or reject each task upon arrival. This structure appears when packing jobs onto shared compute [13, 43], matching flexible electrical load to uncertain supply [44], and serving electric vehicles at a constrained charging site [11, 25]. Accepting a task earns value but reserves capacity that a later, more valuable task may need. The first challenge is therefore to maximise social welfare, the total true value of completed tasks, without knowing future demand. The second challenge is strategic reporting. Value, duration and demand are private, so a task owner may exaggerate value, understate the work it requires, or otherwise alter its report to obtain service or pay less. A mechanism is strategyproof when

reporting all three quantities truthfully maximises the task owner’s utility, regardless of the other reports. For an owner who values only complete service, utility is its value minus its payment. A standard route to strategyproofness combines a monotone allocation rule with a critical payment: a higher value cannot hurt acceptance, a longer duration or greater demand cannot help it, and an accepted task pays the smallest value that the deployed rule accepts [3, 29]. Our challenge is to retain this structure when the allocation rule is a nonlinear learned function whose threshold must be computed numerically. Analytical online mechanisms provide strategyproof allocation and payment rules for electric vehicles, flexible loads, reusable resources and multi-resource allocation [1, 2, 6, 11, 12, 14, 30, 40, 42, 44, 51]. Their allocation rules, however, are specified in advance. Reinforcement learning (RL) and deep-RL methods, on the other hand, learn adaptive charging, pricing and resource-allocation policies [4, 10, 17, 25, 26, 47, 50], but generally do not prove truthful reporting of value, duration and demand. Neural auction design often penalises empirical regret [7]; other one-shot architectures enforce stronger guarantees for restricted auction domains [8, 27, 39], including exact incentive compatibility by representing the mechanism as a menu from which the buyer selects [39], and post-hoc tools verify fixed networks [5]. These methods address complementary parts of the problem, yet they do not directly provide a per-arrival critical payment for a learned sequential rule whose current acceptance changes future capacity. Without strategyproofness, even a high-welfare learned rule cannot be used as intended [42, 44]. Owners can raise the reported value or change the duration or demand to obtain service that would otherwise be refused, so the mechanism decides on false information [43]; later arrivals are displaced, and the resulting schedule is inefficient because it is not based on true requests [12, 30]. The closest existing work is the strategyproof RL mechanism of Stein et al. [43]. It learns a linear difference between the predicted returns from accepting and rejecting, projects its coefficients after each update to preserve monotonicity, and obtains the critical value by solving a linear equation. That difference is linear in occupancy and task features, with a single occupancy coefficient shared across all tasks. As a result, one occupancy overlap of the following form can be represented that way, whereas two cannot. For example, when tasks require different combinations of resources, a shared occupancy weight can encode one overlap between a low-value class and a high-value class, but not two overlaps that need opposite occupancy weights (Example 1). By contrast, a later proximal policy optimisation (PPO) mechanism uses clustered past reports both to shape the training reward of a neural policy and to set a payment [28]. That shaping term acts only on reports seen in training, so the trained allocation need not be monotone in reported

Dehghan et al.

value, duration, and demand, and the payment is a cluster statistic rather than the smallest value the deployed rule accepts. We therefore need two rules: a learned allocation that represents these occupancy interactions, for welfare, and a critical payment that makes truthful reporting optimal. The second requires the first to remain monotone in every reported value, duration, and demand. To this end, a smooth min–max (SMM) network [19] constructs the accept–reject difference from nested smooth (log-sum-exp) minima and maxima of linear units, keeping the weights on reported coordinates positive. Nested min and max of increasing maps remain increasing, so the network can represent occupancy interactions while every permitted report keeps the required direction after every training update. We use this class because it is differentiable, hence trainable by RL or imitation, and monotone by construction rather than by a penalty on sampled reports [15]. The resulting mechanism, Strategyproof SMM (SP-SMM), is this allocation rule together with its critical payment. Because the neural threshold generally has no closed-form expression, we enclose it by verified numerical evaluation and charge the resulting bound. The same construction also applies to tasks that may require several resource types, without a task-specific pricing formula. Finally, we train the same network in two ways. RL learns from social welfare feedback in a simulator. Imitation instead copies accept/reject decisions from a teacher that do not need to be strategyproof. Discarding the teacher before deployment is what makes that permissible. The deployed mechanism is the monotone network with its critical payment, so strategyproofness comes from the deployed network, not from the teacher. In addition, imitation can reduce training cost. We compare behaviour cloning (BC), dataset aggregation (DAgger), and disturbances for augmenting robot trajectories (DART) [24, 36, 37].

Contributions (1) SP-SMM learns general nonlinear occupancy interactions while remaining monotone in every reported quantity, and a verified critical payment makes the rule strategyproof and individually rational for tasks that may require several resource types. (2) On the two-pair stream of Example 1, SP-SMM reduces the linear learner’s optimality gap to the offline LP bound from 6.2% to 2.2%, closing 65% of that gap, whereas linear rules remain competitive when a single occupancy weight suffices. (3) The same mechanism can be trained by RL or imitation without changing its incentives; imitation reaches a 2.5% optimality gap in 261 seconds, about 89 times faster than RL. The rest of this paper is as follows. Section 2 specifies the setting, Section 3 the mechanism, Section 4 the experiments, and Section 5 concludes.

2

Markov decision process (MDP) (Section 2.1). We then define sequential allocation, agent utility, and strategyproofness and individual rationality (Section 2.2). A table of the principal symbols is in Section B.

2.1

Environment

We model a resource provider that offers 𝑚 resource types 𝑟 ∈ {1, . . . , 𝑚} with capacities b = (𝑏 1, . . . , 𝑏𝑚 ) ∈ N𝑚 , so resource 𝑟 has 𝑏𝑟 units. We represent time as discrete slots 𝑡 ∈ {1, . . . ,𝑇 } over a horizon of 𝑇 slots, and we assume one task arrives per slot. We index tasks by arrival order 𝑖, and we represent the private type of task 𝑖 as 𝜃 𝑖 = (𝑣𝑖 , ℓ𝑖 , d𝑖 ),

(1)

with value 𝑣𝑖 ≥ 0, duration ℓ𝑖 ∈ N, and per-slot demand d𝑖 = (𝑑𝑖,1, . . . , 𝑑𝑖,𝑚 ) ∈ N𝑚 0 , where N0 = {0, 1, . . .} and 𝑑𝑖,𝑟 is the requirement on resource 𝑟 . We assume a bounded type domain Θ with 𝑣 max > 0 and ℓmax , Θ = [0, 𝑣 max ] × {1, . . . , ℓmax } ×

𝑚 Ö

{0, . . . , 𝑏𝑟 }.

(2)

𝑟 =1

We further assume that only agent 𝑖 knows 𝜃 𝑖 , and the provider must accept or reject each task upon arrival, before later arrivals are known, and that the decision is irrevocable. The provider cannot measure value, and neither duration nor demand is verifiable before that decision, so we model the mechanism as acting on a report 𝜃ˆ𝑖 = (𝑣ˆ𝑖 , ℓˆ𝑖 , d̂𝑖 ) ∈ Θ. We do not assume that 𝜃ˆ𝑖 = 𝜃 𝑖 . By contrast, we do not consider strategic reporting of the arrival time. In particular, the provider observes the slot at which the task appears. This is realistic for time-sensitive tasks; for example, an electric vehicle already at a charging site [11, 25] or a compute job that must start when submitted [43]. When discussing the current arrival we drop ˆ ℓ,ˆ d̂). the index 𝑖 and write (𝑣, We represent the provider’s state 𝑠 by the current slot 𝑡 and the remaining busy time 𝑜𝑟,𝑘 (𝑠) of each unit 𝑘 ∈ {1, . . . , 𝑏𝑟 } of each resource 𝑟 . We write 𝑓𝑟 (𝑠) for the number of those coordinates that are zero, so f (𝑠) = (𝑓1 (𝑠), . . . , 𝑓𝑚 (𝑠)) ∈ N𝑚 0 is the currently free capacity. We treat a report as feasible when 𝑑ˆ𝑖,𝑟 ≤ 𝑓𝑟 (𝑠)

∀𝑟 ∈ {1, . . . , 𝑚}

and ℓˆ𝑖 ≤ 𝑇 − 𝑡 + 1.

(3)

Consequently, every accepted task completes by slot 𝑇 , and infeasible reports are rejected. This 𝑠 is therefore the state of an MDP [45]: accepting a task changes occupancy for later slots, so each arrival is a sequential decision. The actions are accept and reject. Let 𝐼𝑟 ⊆ {𝑘 : 𝑜𝑟,𝑘 (𝑠) = 0} with |𝐼𝑟 | = 𝑑ˆ𝑖,𝑟 be the idle units of resource 𝑟 assigned when the report is accepted, and 𝐼𝑟 = ∅ otherwise, ∀𝑟 ∈ {1, . . . , 𝑚}. The next slot then has time 𝑡 + 1 and remaining busy times ( max( ℓˆ𝑖 − 1, 0) if 𝑘 ∈ 𝐼𝑟 , 𝑜𝑟,𝑘 ← (4) max(𝑜𝑟,𝑘 (𝑠) − 1, 0) otherwise,

System Model

This section specifies the allocation setting. We first model resource capacities, private types, reports, occupancy and the sequential

∀𝑟 ∈ {1, . . . , 𝑚}, ∀𝑘 ∈ {1, . . . , 𝑏𝑟 }. This occupancy update is the MDP transition. The next report, however, is unknown.

Strategyproof Deep RL

2.2

3

Mechanism, utility and incentives

Because types are private, the provider cannot allocate from 𝜃 𝑖 directly. The next definition is the sequential rule that turns a report into an allocation decision and a payment. Definition 1 (Mechanism). A mechanism is a map [11, 29, 43]
M (E, 𝜃ˆ𝑖 , Θ̂<𝑖 ) = 𝑥 (𝜃ˆ𝑖 , Θ̂<𝑖 ), 𝑝 (𝜃ˆ𝑖 , Θ̂<𝑖 ) , (5) with 𝑥 ∈ {0, 1}, 𝑝 ≥ 0, and 𝑥 = 0 =⇒ 𝑝 = 0.1 The input is the environment E = (𝑚, b,𝑇 , Θ, (𝑜𝑟,𝑘 )) of Section 2.1, the current report 𝜃ˆ𝑖 ∈ Θ of agent 𝑖, and the history Θ̂<𝑖 = (𝜃ˆ1, . . . , 𝜃ˆ𝑖 −1 ) ∈ Θ𝑖 −1 . The output is acceptance (𝑥 = 1) or rejection (𝑥 = 0) and agent 𝑖’s payment. We take M to be deterministic, so occupancy 𝑜𝑟,𝑘 at arrival 𝑖 is determined by Θ̂<𝑖 (Equation (4)). With E as in Section 2.1, 𝑥 and 𝑝 therefore depend only on 𝜃ˆ𝑖 and Θ̂<𝑖 . We denote a report as covering the true type when its reported duration and demands are at least the corresponding true quantities,   𝑐 (𝜃ˆ𝑖 , 𝜃 𝑖 ) = 1 ℓˆ𝑖 ≥ ℓ𝑖 , 𝑑ˆ𝑖,𝑟 ≥ 𝑑𝑖,𝑟 ∀𝑟 ∈ {1, . . . , 𝑚} , (6) where 1[·] denotes the indicator of the event in brackets. An understated duration or demand (where 𝑐 (𝜃ˆ𝑖 , 𝜃 𝑖 ) = 0) then fails to complete the true task [43]. We take social welfare to be the total true value of accepted covering reports, and we maximise 𝑊 rather than revenue because the provider allocates a shared resource [43]: ∑︁ 𝑊 = 𝑥 (𝜃ˆ𝑖 , Θ̂<𝑖 ) 𝑐 (𝜃ˆ𝑖 , 𝜃 𝑖 ) 𝑣𝑖 . (7) 𝑖

We assume that agent 𝑖 maximises utility when choosing a report [29], and with the covering convention we represent that payoff as: Definition 2 (Agent utility). The utility of agent 𝑖 is 𝑈𝑖 (𝜃ˆ𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ) = 𝑥 (𝜃ˆ𝑖 , Θ̂<𝑖 ) 𝑐 (𝜃ˆ𝑖 , 𝜃 𝑖 ) 𝑣𝑖 − 𝑝 (𝜃ˆ𝑖 , Θ̂<𝑖 ).

(8)

Under this utility, an accepted report that understates duration or demand yields no value but still incurs a payment, whereas a rejection yields 𝑈𝑖 = 0, since 𝑥 = 0 and 𝑥 = 0 =⇒ 𝑝 = 0. A misreport is profitable exactly when it raises 𝑈𝑖 . A mechanism is strategyproof when truthful reporting is a dominant strategy, and individually rational when a truthful agent is never worse off than not participating [29]: Definition 3 (Strategyproofness and individual rationality). M is strategyproof if 𝑈𝑖 (𝜃 𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ) ≥ 𝑈𝑖 (𝜃ˆ𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ), ∀𝑖, ∀𝜃 𝑖 , ∀𝜃ˆ𝑖 , ∀Θ̂<𝑖 . It is individually rational if 𝑈𝑖 (𝜃 𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ) ≥ 0, ∀𝑖, ∀𝜃 𝑖 , ∀Θ̂<𝑖 . Because we assume irrevocable decisions before later arrivals (Section 2.1), future reports cannot affect the current decision or payment, so these definitions need only the preceding history. Strategyproofness matters because 𝑥 is decided on reports, while 𝑊 uses true values 𝑣𝑖 . The two align only under truthful reporting. This can be achieved using the characterisation of Blumrosen and Nisan [3]. Specifically, with our arrival model and the covering convention, agents are single-minded in their sense, so a monotone allocation rule together with the critical-value payment (i.e., the lowest reported value the rule accepts) is strategyproof and individually rational [3, 29]. Section 3 constructs that pair as SP-SMM. 1We omit the arguments of 𝑥 and 𝑝 when they are clear from context.

Strategyproof Smooth Min–Max

This section constructs SP-SMM from action values on the MDP of Section 2.1 (Section 3.1), a monotone network (Section 3.2), and a critical payment (Section 3.3).

3.1

Action values

The realised welfare that follows acceptance or rejection cannot be evaluated exactly (Section 2.1). We therefore learn estimates of the expected return (in terms of welfare) for both actions from sampled episodes [45], giving us a direct value for each action, rather than outputting only an accept/reject probability. During training, exploration provides experience of both actions and the occupancy, i.e., state, they produce. Q-learning would retain the action actually taken, its reward and the resulting occupancy, but would bootstrap from the highest estimated continuation at the next state. On-policy SARSA instead bootstraps from the next action selected by the behaviour policy. We use SARSA to evaluate continuation under that policy, including its exploratory choices. To keep those bootstrap targets fixed within each fitting iteration, we collect transitions, compute targets from a frozen network snapshot, and fit the network to those targets in batches; we then refresh the targets. That adapts the fitted-batch scheme of fitted Q-iteration [9, 34] to SARSA (Algorithm 1). The components of this learner, and their roles, are as follows. First, the state 𝑠 is the occupancy record of Section 2.1 together with the current report, so the action-value can depend on both free capacity and the request. Second, the action 𝑎 is the allocation 𝑥: 𝑎 = acc if 𝑥 = 1 and 𝑎 = rej if 𝑥 = 0. The transition remains the occupancy update of Equation (4). Consequently, the reward’s role is to credit remaining welfare at the accept/reject decision. The action-value 𝑄 𝑤 (𝑠, 𝑎) then estimates the undiscounted return from that decision. We record these objects as follows. Definition 4 (Action values and features). Let 𝑤 denote the network parameters, and let 𝑣 max and ℓmax be the bounds in Θ. The immediate reward and the undiscounted return from slot 𝑡 are 𝑇 ∑︁ ˆ 𝑅(𝑠, 𝑎) = 1[𝑎 = acc] 𝑣, 𝐽𝑡 = 𝑅(𝑠𝑘 , 𝑎𝑘 ). (9) 𝑘=𝑡

Under truth-telling, E[𝐽𝑡 ] is the expected social welfare from slot 𝑡 onward, and 𝑄 𝑤 (𝑠, 𝑎) is its estimate given 𝑠 and 𝑎. The accept–reject action-value difference and the greedy policy on feasible reports are Δ𝑤 (𝑠) = 𝑄 𝑤 (𝑠, acc) − 𝑄 𝑤 (𝑠, rej),

𝜋 𝑤 (𝑠) = acc ⇐⇒ Δ𝑤 (𝑠) ≥ 0. (10) When Δ𝑤 equals the true difference of expected returns, 𝜋 𝑤 maximises expected social welfare [45]. With remaining busy times ordered 𝑜𝑟,1 (𝑠) ≤ · · · ≤ 𝑜𝑟,𝑏𝑟 (𝑠), the normalised occupancy and the feature map are
𝑜 (𝑠) = 𝑜𝑟,𝑘 (𝑠)/max(ℓmax − 1, 1) 𝑟,𝑘 , (11)
ˆ max, 𝑑ˆ1 /𝑏 1, . . . , 𝑑ˆ𝑚 /𝑏𝑚 , 𝑜 (𝑠) . (12) ˆ max, ℓ/ℓ 𝜙 (𝑠) = 1, 𝑡/𝑇 , 𝑣/𝑣 Let 𝜙 𝑗 be the 𝑗-th coordinate of 𝜙 (𝑠); each 𝜙 𝑗 ∈ [0, 1]. This normalisation places elements on a common scale without changing their order or introducing interactions between them. In particˆ max ∈ [0, 1] and write 𝜙 (𝑠, 𝑢) for 𝜙 (𝑠) ular, we write 𝑢 = 𝑣/𝑣

Dehghan et al.

with the normalised-value coordinate set to 𝑢. In addition, context 𝑧 (𝑠) = (1, 𝑡/𝑇 , 𝑜 (𝑠)) collects time and occupancy. ˆ ℓ,ˆ d̂), only those Because the agent chooses only the report (𝑣, coordinates are constrained: Definition 5 (Monotone Δ𝑤 ). Δ𝑤 is monotone if, with time and occupancy held fixed, ˆ ℓ,ˆ d̂) Δ𝑤 (𝑣ˆ′, ℓˆ′, d̂′ ) ≥ Δ𝑤 (𝑣, (13) for every permitted pair of reports and every parameter vector 𝑤. ˆ 𝑣ˆ′ ≥ 𝑣,

ℓˆ′ ≤ ℓ,ˆ

𝑑ˆ𝑟′ ≤ 𝑑ˆ𝑟 ∀𝑟

=⇒

By contrast, time and occupancy enter only through 𝑧(𝑠), which Definition 5 holds fixed. We therefore need a representation of Δ𝑤 that satisfies Definition 5 while still letting occupancy change the accept/reject comparison. Because a shared baseline on 𝑠 cancels in Δ𝑤 , we parameterise Δ𝑤 directly as a difference network on the constrained report and unrestricted 𝑧 (𝑠). Occupancy may then interact with the report, rather than enter as one shared linear weight. Section 3.2 constructs that network. A linear Δ𝑤 with occupancy weights shared across tasks is a special case of the same comparison; Example 1 is a setting that special case cannot represent. Example 1 (Two partner pairs). Low-value tasks C need only 𝑟 1 and valuable tasks A need 𝑟 1 and 𝑟 2 together: we call this a partner pair, because accepting C can block A only while the partner resource 𝑟 2 remains free. A second partner pair is low-value D on 𝑟 4 with valuable B on 𝑟 3 and 𝑟 4 . Later tasks are unknown. Keep 𝑟 1 and 𝑟 4 free. The welfare-maximising decisions then reverse with occupancy: Occupancy 𝑟 2 busy, 𝑟 3 free 𝑟 2 free, 𝑟 3 busy

C

D

accept reject

reject accept

Thus the same report C is accepted when 𝑟 2 is busy and often rejected when 𝑟 2 is free, so only 𝑧(𝑠) differs. Although task-specific intercepts can shift C relative to D, a linear Δ𝑤 with occupancy weights shared across tasks cannot represent both rows: the first places a greater weight on 𝑟 2 than on 𝑟 3 , whereas the second places the opposite weight. A product of C’s demand with occupancy of 𝑟 2 would restore the four decisions; however, it is not a coordinate of that linear difference. Algorithm 1 fits 𝑤 from these objects. Line 16 of Algorithm 1 supplies 𝜙 (𝑠) and 𝑧 (𝑠). Line 28 is

Algorithm 1 Fitted SARSA on the allocation MDP Require: 𝜀 ∈ [0, 1], 𝑤, 𝑁 , 𝐵 ∈ N 1: function Select(𝑠, 𝜀, 𝑤) 2: if 𝑑ˆ𝑟 > 𝑓𝑟 (𝑠 ) for some 𝑟 , or ℓˆ > 𝑇 − 𝑡 + 1 then 3: return (rej, 0) 4: sample 𝜉 ∼ Unif [0, 1] 5: if 𝜉 < 𝜀 then 6: sample 𝑎 ∼ Unif {acc, rej} 7: return (𝑎, 1) 8: else 9: return (𝜋 𝑤 (𝑠 ), 0) 10: D ← ∅ 11: for 𝑛 = 1, . . . , 𝑁 do 12: (𝑜𝑟,𝑘 ) ← 0 ∀𝑟, 𝑘 13: for 𝑡 = 1, . . . ,𝑇 do ˆ ℓ,ˆ d̂) 14: observe 𝜃ˆ = ( 𝑣,
15: 𝑠 ← 𝑡, (𝑜𝑟,𝑘 ), 𝜃ˆ 𝜙 (𝑠 ) ← Equation (12), 𝑧 (𝑠 ) ← (1, 𝑡 /𝑇 , 𝑜 (𝑠 ) ) (𝑎, 𝑒 ) ← Select(𝑠, 𝜀, 𝑤 ) 𝑅 ← (1 − 𝑒 ) 1[𝑎 = acc] 𝑣ˆ if 𝑡 < 𝑇 then (𝑜𝑟,𝑘 ) ← Equation (4)
21: observe 𝜃ˆ′ ; 𝑠 ′ ← 𝑡 + 1, (𝑜𝑟,𝑘 ), 𝜃ˆ′ ′ ′ ′ 22: (𝑎 , 𝑒 ) ← Select(𝑠 , 𝜀, 𝑤 ) 23: else 24: 𝑠 ′ ← ⊥; 𝑎 ′ ← ⊥ 25: D ← D ∪ { (𝑠, 𝑎, 𝑅, 𝑠 ′ , 𝑎 ′ ) } 26: if 𝑛 mod 𝐵 = 0 then 27: for all (𝑠, 𝑎, 𝑅, 𝑠 ′ , 𝑎 ′ ) ∈ D do 28: 𝑦 ← 𝑅 if 𝑠 ′ = ⊥, else 𝑦 ← 𝑅 + 𝑄 𝑤 (𝑠 ′ , 𝑎 ′ ) 29: hold {𝑦 } fixed and update 𝑤 30: 𝜀 ← 0 16: 17: 18: 19: 20:

by 𝑘 ∈ {1, . . . , 𝐾 } and ℎ ∈ {1, . . . , 𝐻 }. Holding coordinates other than 𝑢 fixed, we take unit (𝑘, ℎ) to be 𝜁𝑘ℎ (𝑢) = 𝑎𝑘ℎ + 𝑤𝑘ℎ𝑢,

𝑤𝑘ℎ > 0,

(15)

with intercept 𝑎𝑘ℎ ∈ R. In addition, we store an unconstrained number for each weight attached to a report coordinate and exponentiate it, so the weight remains positive after every optimiser update. The unnormalised log-sum-exp maps are ∑︁ smax(𝜻 ) = log exp(𝜁ℎ ), smin(𝜻 ) = − smax(−𝜻 ). (16) ℎ

𝑅(𝑠, 𝑎) + 𝑄 𝑤 (𝑠 ′, 𝑎 ′ ),

(14)

when 𝑠 ′ ≠ ⊥, with 𝑎 ′ the stored next action (line 25); otherwise, line 24 sets 𝑦 = 𝑅 at a terminal slot. In addition, line 18 stores 𝑅 = 0 when 𝑒 = 1, so the randomised training policy is not the deployed mechanism. For this reason, line 30 sets 𝜀 = 0.

3.2

Smooth min–max network

We represent Δ𝑤 with the SMM network of Igel [19]. Because Definition 5 requires Δ𝑤 to decrease in duration and demand, we first map those coordinates by 𝜙 𝑗 ↦→ 1 − 𝜙 𝑗 , which is valid because Equation (12) places them in [0, 1]. After that map, every report coordinate is increasing, so the units below need only positive weights. The core consists of 𝐾 groups of 𝐻 linear units, indexed

We then take a smooth maximum over the units of each group and a smooth minimum over groups. With learned scale 𝛽 ∈ R and offset 𝛾 ∈ R, 𝑓SMM (𝑢) = e−𝛽 smin𝑘 ≤𝐾 smaxℎ≤𝐻 𝜁𝑘ℎ (𝑢) + 𝛾 .

(17)

We also represent context by an unconstrained multilayer perceptron (MLP) with logistic activation that reads only 𝑧 (𝑠) and returns a value 𝑓ctx [15]. We write 𝑓𝑤 (𝑢) = 𝑓SMM (𝑢) + 𝑓ctx . Finally, we apply a bounded output head to 𝑓𝑤 . We calibrate a centre 𝜇 and scale 𝜈 > 0 once at initialisation and then keep them fixed. For 𝐹𝑠 (𝑢) = Δ𝑤 (𝜙 (𝑠, 𝑢)), a learned positive gain 𝜆 ≤ 𝜆max and offset 𝑏 0 give  
𝐹𝑠 (𝑢) = clip [ −2𝜆max , 2𝜆max ] 𝜆 tanh (𝑓𝑤 (𝑢) − 𝜇)/𝜈 + 𝑏 0 . (18)

Strategyproof Deep RL

Lemma 1 (SMM monotonicity). Every parameter vector 𝑤 of Equations (17) and (18) yields a monotone Δ𝑤 in the sense of Definition 5.

Algorithm 2 Verified critical value before allocation ˆ ℓ,ˆ d̂), 𝐹𝑠 ) 1: procedure DecideAndPrice(𝑠, ( 𝑣, 2:

if d̂ ≰ f (𝑠 ) or ℓˆ > 𝑇 − 𝑡 + 1 then return (𝑥, 𝑝 ) = (0, 0)

Proof. After the duration–demand flip, every report coordinate is increasing and every report weight is positive, so each unit 𝜁𝑘ℎ increases in the report. Nested smin and smax of increasing maps remain increasing [19]. The context term 𝑓ctx does not depend on the report, and tanh, scaling by 𝜆 > 0, and clipping are non-decreasing. The composition therefore satisfies Definition 5 for every 𝑤. □

3: 4: 5: 6:

In particular, training may change the shape of the rule but cannot reverse a required report direction.

10: 11: 12: 13: 14: 15: 16:

𝑝 lo ← 𝑝 hi ← ⊥ for 𝑃 ∈ {64, 128, 256} bits do enclose 𝐹𝑠 (0), 𝐹𝑠 (1) at 𝑃 bits if 𝐹𝑠 (1) < 0 verified then return (𝑥, 𝑝 ) = (0, 0) if 𝐹𝑠 (0) ≥ 0 verified then 𝑝 lo ← 𝑝 hi ← 0; break if 𝐹𝑠 (0) < 0 ≤ 𝐹𝑠 (1) unverified then continue 𝑢 lo ← 0, 𝑢 hi ← 1 while 𝑣max (𝑢 hi − 𝑢 lo ) > 𝜏 do if SMM then 𝑢 ← Newton else 𝑢 ← midpoint if 𝐹𝑠 (𝑢 ) < 0 then 𝑢 lo ← 𝑢 else if 𝐹𝑠 (𝑢 ) ≥ 0 then 𝑢 hi ← 𝑢 else continue at next 𝑃 𝑝 lo ← 𝑣max𝑢 lo , 𝑝 hi ← 𝑣max𝑢 hi ; break if 𝑝 hi = ⊥ then return unresolved error 𝑞 ← min{𝑣max , ⌈𝑝 hi + 𝜏 rank( ℓ,ˆ d̂) ⌉ F } 𝑥 ← 1[ 𝑣ˆ ≥ 𝑞 ], 𝑝 ← 𝑥𝑞; return (𝑥, 𝑝 )

7: 8: 9:

Proposition 1 (Coefficient projection). If Δ𝑤 is linear in 𝜙, then Δ𝑤 satisfies Definition 5 if and only if the coefficients of normalised value, duration and demand have the required signs. The same coordinate-wise sign repair does not imply Definition 5 for a general MLP. Proof. For a linear map the partial derivative in each coordinate of 𝜙 is the corresponding coefficient, so Definition 5 holds at every report if and only if the value coefficient is nonnegative and the duration and demand coefficients are nonpositive. Projecting those coefficients onto the corresponding half-lines after each update restores the signs [43]. A general MLP has input-dependent derivatives, so clipping a first-layer weight does not control 𝜕Δ𝑤 /𝜕𝜙 𝑗 at every report. □ A monotonicity or regret penalty, on the other hand, only discourages violations at sampled reports; an unsampled report may still violate the required order [15].

3.3

Computing the critical payment

The same smoothness that yields Lemma 1 also means 𝐹𝑠 has no algebraic inverse: smooth extrema mix every unit and the tanh head is nonlinear, whereas a hard min–max network of the same groups would have a closed form [41]. We therefore invert the trained map itself: the complete action-value difference in Equation (18). In particular, with duration and demand held fixed, that map is non-decreasing in 𝑢 ∈ [0, 1]. The mathematical threshold uses a candidate 𝑢 in place of the current reported value, 𝑢 ★ (𝑠) = inf {𝑢 ∈ [0, 1] : 𝐹𝑠 (𝑢) ≥ 0}, 𝑝 ★ (𝑠) = 𝑣 max𝑢 ★ (𝑠). Thus, if 𝐹𝑠 (0) ≥ 0, then 𝑝 ★ = 0. If 𝐹𝑠 (1) < 0, no permitted value is accepted and we write 𝑝 ★ = ∞. Otherwise, the threshold lies between a rejecting value and an accepting value. Importantly, the search uses the candidate 𝑢, not the current reported value. Algorithm 2 implements three stages. First, we evaluate candidate values with verified arithmetic. We then search until we have a proved bracket around 𝑝 ★. Finally, we correct the upper endpoint and use that value as the payment. We start by evaluating the network with Arb ball arithmetic [21]. The weights in a checkpoint are finite binary numbers, but ordinary floating-point evaluation need not return the exact real value of 𝐹𝑠 (𝑢). Rounding matters most near zero, where the accept/reject decision changes. For this reason, we represent a ball by the interval 𝐵 = [𝑚𝐵 − 𝜌 𝐵 , 𝑚𝐵 + 𝜌 𝐵 ], 𝜌 𝐵 ≥ 0, where 𝑚𝐵 is its midpoint and 𝜌 𝐵 its radius. Outward rounding after every network operation guarantees that the exact real-valued result for the stored checkpoint lies in this interval [21]. The guarantee is deterministic; the ball is not a

17: 18: 19:

confidence interval. In particular, a negative upper endpoint proves rejection, and a nonnegative lower endpoint proves acceptance. If the lower endpoint is negative and the upper endpoint is nonnegative, the sign remains unresolved. Line 5 of Algorithm 2 evaluates these balls at 𝑢 = 0 and 𝑢 = 1. Thus, if 𝐹𝑠 (1) < 0 is verified, line 6 rejects every permitted value; if 𝐹𝑠 (0) ≥ 0 is verified, lines 7–8 set the threshold to zero. Arb verifies these evaluations but does not search for the threshold. We then search for that threshold. After classifying the two endpoints, we either handle an endpoint case or start from the full interval 𝐼 = [0, 1] with the invariant 𝐹𝑠 (𝑢 lo ) < 0,

𝐹𝑠 (𝑢 hi ) ≥ 0.

is non-decreasing, 𝑢 ★ ∈ [𝑢

(19)

Because 𝐹𝑠 lo , 𝑢 hi ]. Line 10 of Algorithm 2 initialises this bracket. At each step we evaluate a new candidate with Arb. By default we take the midpoint: a verified negative sign moves the lower endpoint, and a verified nonnegative sign moves the upper endpoint (line 13). Each successful bisection halves the interval, so after 𝑛 steps its normalised width is at most 2−𝑛 . If a sign is unresolved, line 15 restarts the same search at 128 and then 256 bits (line 9 does the same when an endpoint sign cannot be verified). Higher precision nevertheless reduces arithmetic uncertainty but does not move either bracket endpoint by itself. If the endpoint signs or requested width still cannot be verified, line 17 returns an unresolved error rather than substituting an ordinary floating-point result. In addition, for SMM we may try interval Newton (line 12), because the SMM core is smooth along the value axis [19]. On a bracket where the output clamp is inactive, Arb can enclose the derivative of the complete action-value difference throughout the bracket. When that interval is strictly positive, interval Newton proposes a smaller root interval [32]. We use that proposal only if it is at least twice as narrow and fresh endpoint evaluations restore the rejecting–accepting invariant; otherwise we bisect. Newton therefore speeds up SMM but never replaces the bracketing proof.

Dehghan et al.

We also write the interval form in Section A.1. We stop the search when the corresponding critical value interval has width at most 𝜏 = 10−6 (line 11): 𝑝 lo = 𝑣 max𝑢 lo ≤ 𝑝 ★ ≤ 𝑣 max𝑢 hi = 𝑝 hi,

𝑝 hi − 𝑝 lo ≤ 𝜏 .

(20)

Line 16 records these endpoints. We convert each endpoint back to binary64 with outward rounding and check the result. Thus 𝑝 hi is a proved upper bound on the mathematical network threshold, not an exact symbolic root. By contrast, a midpoint estimate would not give this one-sided guarantee. Finally, we turn 𝑝 hi into the deployed payment. However, two independently rounded upper bounds can appear in the wrong order when their exact thresholds differ by less than 𝜏. For the integer duration and demands in Equation (1), we define the report Í ˆ rank rank( ℓ,ˆ d̂) = ( ℓˆ − 1) + 𝑚 𝑗=1 𝑑 𝑗 . The rank is an ordering device, not a measure of resource cost or welfare. It counts unit increases from the least-demanding report ( ℓ,ˆ d̂) = (1, 0). Let ⌈𝑧⌉ F denote the smallest binary64 number no smaller than 𝑧. We take the deployed critical value to be n l m o 𝑞(𝑠) = min 𝑣 max, 𝑝 hi (𝑠) + 𝜏 rank( ℓ,ˆ d̂) . (21) F

Line 18 of Algorithm 2 computes this 𝑞. The formula uses 𝑝 hi , duˆ We add the stored binary inputs ration and demand, but not 𝑣. exactly and round upward once; let 𝜌𝑞 be that final increase. Be
cause 𝑝 hi ≤ 𝑝 ★ + 𝜏, 0 ≤ 𝑞 − 𝑝 ★ ≤ rank( ℓ,ˆ d̂) + 1 𝜏 + 𝜌𝑞 , when the cap does not bind; the cap can only reduce the difference while remaining at least 𝑝 ★. Here 0 ≤ 𝜌𝑞 < ulp(𝑣 max ). On the partner benchmark, rank ≤ 19, so the two terms are at most 2 · 10−5 and 4 · 10−15 value units. We then accept and charge using this 𝑞. Line 2 first rejects infeasible reports. Lines 19–19 compare 𝑞(𝑠) with the original value report, not a value reconstructed after normalisation, and charge 𝑞(𝑠) upon acceptance. If we verify that no permitted value is accepted, we define 𝑞 = +∞. On a feasible report (Equation (3)) the deployed allocation is therefore   𝑥 (𝑠) = 1 𝑣ˆ ≥ 𝑞(𝑠) , (22) and 𝑥 (𝑠) = 0 otherwise. An accepted task pays 𝑝 (𝑠) = 𝑞(𝑠). In short, the network threshold 𝑝 ★, the verified interval [𝑝 lo, 𝑝 hi ], and the deployed value 𝑞 are different objects: 𝑝 hi is a proved upper bound on 𝑝 ★, and 𝑞 is the number the implemented rule actually uses. Altogether, the incentive properties of this rule are Theorem 1. Theorem 1 (Strategyproofness and individual rationality). Assume integer duration and demand reports and a monotone Δ𝑤 (Definition 5). This hypothesis holds for every SMM parameter vector (Lemma 1) and, for a linear model, exactly after coefficient projection (Proposition 1). Suppose that, for every feasible report, the calculation verifies either Equation (20) or that no permitted value is accepted. Then the mechanism defined by (21) and (22), taking 𝑞 = +∞ when no permitted value is accepted, is strategyproof and individually rational for every 𝑤. Proof. For fixed duration and demand, 𝑞 is computed after replacing the reported value by the search variable 𝑢; hence, it is inˆ Equation (22) accepts exactly when 𝑣ˆ ≥ 𝑞 and dependent of 𝑣. charges 𝑞, so 𝑞 is the critical value of the deployed rule. Raising the reported value cannot hurt acceptance. Now compare two duration–demand reports. Report 2 has weakly greater duration

and demand in every coordinate than report 1, with at least one strict inequality. First suppose both have finite thresholds. Let 𝐺𝑖 = 𝑝 hi,𝑖 + 𝜏 rank𝑖 denote the exact dyadic sum before its fi★ nal conversion to binary64. Report monotonicity gives 𝑝 ★ 2 ≥ 𝑝1 , while rank2 ≥ rank1 +1. The enclosure guarantee then gives 𝐺 2 ≥ ★ 𝑝★ 2 + 𝜏 rank2 ≥ 𝑝 1 + 𝜏 (rank1 +1) ≥ 𝐺 1 . Rounding upward to the least binary64 number is a non-decreasing map, and taking the minimum with the same 𝑣 max is also non-decreasing. Therefore 𝑞 2 ≥ 𝑞 1 . If report 2 has no crossing, then 𝑞 2 = +∞. If report 1 has no crossing, report monotonicity forces report 2 to have no crossing as well. These cases preserve the same order. A shorter duration or smaller demand also cannot destroy feasibility. The deployed allocation is therefore monotone in value, duration, and every demand coordinate. For example, take two resources and the exaggerated tolerance 𝜏 = 0.01. Report 1, with (ℓ1, d1 ) = (2, (1, 0)), has rank 2; the more demanding report 2, with (ℓ2, d2 ) = (3, (1, 0)), has rank 3. Suppose ★ their exact thresholds are 𝑝 ★ 1 = 5.000 and 𝑝 2 = 5.004, in the correct order, but separate verified searches return 𝑝 hi,1 = 5.010 and 𝑝 hi,2 = 5.004. The uncorrected upper endpoints are reversed. Before final binary64 rounding, the corrected values are 𝐺 1 = 5.010 + 0.01(2) = 5.030, 𝐺 2 = 5.004 + 0.01(3) = 5.034. The more demanding report again has the weakly higher critical value. The experiments use 𝜏 = 10−6 ; the larger value here only makes the correction visible. It remains to compare utilities [3, 29]. For this proof only, write the critical value as +∞ when no permitted value is accepted. If the true duration and demand are infeasible, truthful reporting is rejected and gives zero utility. Every covering report remains infeasible, whereas any feasible report must understate a binding duration or demand and therefore gives no service value and utility at most zero. Truth is optimal in this case. Now suppose the true duration and demand are feasible. Let 𝑞𝑖 be the critical value for reporting them truthfully. If 𝑣𝑖 ≥ 𝑞𝑖 , truthful reporting is accepted and gives nonnegative utility 𝑣𝑖 − 𝑞𝑖 ; if 𝑣𝑖 < 𝑞𝑖 , it is rejected and gives zero. A report that understates duration or demand does not cover the true task. If accepted, it gives utility −𝑝 ≤ 0; if rejected, it gives zero. Any covering report has duration and demand at least as large as the true task, so its finite critical value 𝑞ˆ satisfies 𝑞ˆ ≥ 𝑞𝑖 , or it accepts no permitted value. When truth is accepted, such a report gives at most 𝑣𝑖 − 𝑞ˆ ≤ 𝑣𝑖 − 𝑞𝑖 . When truth is rejected, ˆ so the covering report is either rejected or accepted 𝑣𝑖 < 𝑞𝑖 ≤ 𝑞, at negative utility. No deviation is profitable, and truthful utility is always nonnegative.

4

Experiments

This section compares SP-SMM with other networks. We first describe training and imitation (Section 4.1) and the allocation streams (Section 4.2), then the results (Section 4.3).

4.1

Experimental setup

For RL, we run Algorithm 1 for 8000 episodes with five seeds and evaluate on 200 episodes. LinearMono is the closest published baseline [43]. We take LipschitzMono to be a slope-bounded MLP [33], SMNN to combine monotone unit types [22], MonoDense to stack constrained layers [38], and MonoNet to use positive-weight layers [31]. We take PMLinear to be a sign-constrained linear layer [48].

Strategyproof Deep RL

Neural models use Adam [23] and LinearMono uses projected RL Planner BC SGD [43]. We use the verified search of Algorithm 2; the corresponding calculations for the other monotone networks are in (a) Partner (b) Small (c) Large Section A. Optimiser schedules, network sizes, inversion bit-widths SP-SMM Lipschitz and imitation budgets are in Section D. SMNN For imitation, we fit the same monotone network from teacher MonoDense labels 𝑦 (𝑠) ∈ {0, 1}. We train the decision boundary with L (𝑤) =


MonoNet −𝑦 log 𝜎 Δ𝑤 (𝑠)/𝜅 − (1 − 𝑦) log 1 − 𝜎 Δ𝑤 (𝑠)/𝜅 , where 𝜎 is the Linear logistic function and 𝜅 controls the margin scale. We then freeze PMLinear that boundary and run fitted-SARSA sweeps on selected teacher FCFS transitions (Equation (14)), so the shared state-value term is fitted 0.4 0.7 1.0 0.4 0.7 1.0 0.4 0.7 1.0 without moving the imitated sign of Δ𝑤 . We do not follow this with RL episodes: imitation replaces the RL route rather than merely (d) Cont. (e) Compl. (f) Time initialising it. We separate the teacher, which defines 𝑦(𝑠), from the SP-SMM SP-SMM Lipschitz collection protocol, which determines the states labelled. BC labels Lipschitz SMNN SMNN teacher-visited states [36]; DAgger labels and aggregates studentMonoDense MonoDense visited states [37]; DART labels states downstream of perturbed MonoNet MonoNet teacher actions [24]. We take DAggerW to use DAgger’s data but Linear Linear PMLinear to select the fitted round with highest held-out welfare rather than PMLinear HLattice lowest L. The loss gives equal weight to errors with different welFCFS C-Lattice fare consequences; DAggerW addresses that mismatch at selection 0.4 0.7 1.0 0.4 0.7 1.0 5 3 10 10 time. W/OPT W/OPT Time (s) We use two teachers. One is a hand-specified Union rule (Section 4.2). The other is a receding-horizon planner. At each state we Figure 1: (a)–(e) RL 𝑊 /OPT (mean ± s.e.); hatched bars are draw forecasts 𝐹 (1) , . . . , 𝐹 (𝑁 ) from the arrival process and solve two planner cloning. (f) Partner time: circles RL, squares Union mixed-integer packing problems per forecast, one forced to accept BC, diamonds planner BC. and one forced to reject the current task. Writing 𝑊pack (1, 𝐹 ) and
Í𝑁 𝑊pack 1, 𝐹 (𝑛) ≥ 𝑊pack (0, 𝐹 ) for their welfare, we accept if and only if 𝑛=1
Í𝑁 (𝑛) . The planner samples possible arrivals rather 𝑛=1 𝑊pack 0, 𝐹 4.3 Results than reading the realised future. We do not use a clairvoyant mixedOn the partner stream (Figure 1), SP-SMM reaches 0.978 of OPT. integer teacher, because its labels could depend on future informaIn particular, it cuts the remaining gaps of LinearMono (6.2%) tion absent from the student’s inputs. and FCFS (11.0%) by 65% and 80%, respectively, and matches the in-sample Union rule (0.973). By contrast, a linear boundary is already competitive when a single occupancy weight suffices: LinearMono reaches 0.992 on Small and, together with MonoDense, 4.2 Benchmarks 0.959 on Complementary. On Large, LipschitzMono reaches Table 1 lists the five streams. In particular, Partner is the two-pair 0.946, ahead of SP-SMM at 0.912. On Continuous, SMNN reaches instance of Example 1, so one occupancy coefficient cannot serve 0.824 and SP-SMM 0.812. We fit separate weights for each stream. both low-value classes. By contrast, Small and Large are the singleThese comparisons therefore support a nonlinear rule precisely resource streams of Stein et al. [43], on which a linear boundary is alwhere two occupancy interactions cannot share coefficients. The ready competitive. Continuous mixes high-density multi-resource corresponding numbers, with standard errors, are in Section E. Imdemand with a sparse class, and Complementary pairs singleportantly, Partner welfare is close among the monotone networks, resource fillers with joint-demand premium tasks. We report welyet SP-SMM is the only one that is jointly first on welfare and fare as a fraction of an offline optimum OPT from the complete worst-class service while still extracting more than 0.94 of welarrival sequence: an LP upper bound where the table lists LP, and the fare as critical-value revenue, as does LipschitzMono (Figures 1 integer packing optimum where it lists exact. We compare against and 2). SMNN and LinearMono extract about one third. Moreover, LinearMono [43] and the monotone networks of Section 4.1: LipsLipschitzMono’s RL run is several times slower, and a Lipschitz chitzMono [33], SMNN [22], MonoDense [38], MonoNet [31], bound can restrict approximation [19, 33]. Lattice cloning reaches and PMLinear [48]. In addition, HLattice and CalibratedLattice (Csimilar Partner welfare, but its fitting time is of the same order Lattice) are lattice baselines used here for cloning [48, 49]. U-MLP as SP-SMM’s RL run, in line with lattice parameter growth in the constrains none of value, duration and demand, whereas V-MLP is constrained coordinates [19, 48, 49]. In addition, SMM units give a monotone only in reported value; neither is a strategyproof mechavalue-axis derivative, so the verified search can try interval Newton nism. Hand-specified references are first-come, first-served (FCFS) (Section 3.3). and Union, an in-sample rule that accepts a filler when its partner Consequently, imitation preserves almost all of this Partner welis busy, or its own resource is plentiful. Sampling, posted prices [43], fare at a fraction of the RL cost (Figure 1(f)). Behaviour cloning of and the LinearThresh family are in Section C. the Union teacher reaches 0.975 of OPT in 261 seconds, compared

Dehghan et al.

Table 1: Allocation streams. b

𝑇

class probabilities

tasks

Partner [3, 1, 1, 3] Small 10 Large 5 Cont. [20, 10] Compl. [6, 6]

80 20 100 80 80

(0.22, 0.22, 0.28, 0.28) fixed 0.1/0.9 0.15/0.85 0.30/0.30/0.40

A,B: {𝑟 1 , 𝑟 2 }, {𝑟 3 , 𝑟 4 }, 𝑣=24, ℓ=6; C,D: 𝑟 1 /𝑟 4 , 𝑣=6, ℓ=12 LP 𝑣=1, ℓ=11 except 𝑡 =11: 𝑣=15, ℓ=1 exact 𝑣=100, ℓ=1; else 𝑣=20, ℓ=25 exact ℓ ∼ Unif {1, . . . , 15}; high-density mixed demand, else sparse LP joint [1, 1]: premium 𝑣=10, ℓ=2 or long 𝑣=2.5, ℓ=10; else 𝑣=1.5, LP ℓ=10, 3 units of one resource

stream

with 0.978 in 23,255 seconds (6.46 hours) for RL, so imitation is 89.1 times faster in these runs. Cloning the short-horizon planner reaches 0.973 in 386 seconds. Times include teacher rollouts, label fitting, SARSA value fitting and held-out checks for cloning; they exclude the cached rule search and exclude final evaluation for both. Both routes used the same SMM architecture, Partner stream, certified pricing path and cluster request (4 CPUs, 8 GB). Variation among cluster nodes means this is a measured comparison, not an architecture-independent complexity result. HLattice and CalibratedLattice (C-Lattice) have cloning times only. No imitation protocol is best on every stream. The remaining architectures, protocols, and the Union-teacher search are in Section F. (a) Regret

(b) By lie monotone U-MLP V-MLP

0.2 0.1 0.0

101

102

103

(c) Worst class SP-SMM Lipschitz SMNN MonoDense MonoNet Linear PMLinear U-MLP V-MLP FCFS 0.0

0.2

minηk

By lie (%)

Regret / vmax

0.3

60 40 20 0

101

102

103

0.8

1.0

(d) Jain

0.4

k

(e) Revenue

0.4

0.6

J

(f) Share

SP-SMM Lipschitz SMNN MonoDense MonoNet Linear PMLinear U-MLP V-MLP FCFS

OPT

the remaining methods are in Section H. U-MLP charges nothing, so it is omitted from Figure 2(e)–(f). At the most exploitable checkpoint, 43% of U-MLP’s audited states and 29% of V-MLP’s have a profitable lie. After training, U-MLP’s zero regret coincides with charging 0, whereas SP-SMM and LinearMono remain at zero regret while still selecting. The misreport grid and remaining scores are in Section G.

5

Conclusions and Future Work

Online resource allocation requires both adaptive decisions under uncertainty and truthful reporting by self-interested participants. To achieve this, SP-SMM combines three novel components. First, a monotonic neural network learns nonlinear occupancy interactions by construction. Second, a generalised critical payment charges the lowest accepted value with the other inputs fixed. Third, the same network can be trained by RL or by imitation. Together, monotonicity and that payment guarantee strategyproofness and individual rationality, while the network provides flexibility and imitation learning improves training efficiency. Importantly, those guarantees do not depend on the training procedure, since the monotonicity is architectural. In particular, on a four-resource stream with two partner pairs, SP-SMM reaches 97.8% of the offline upper bound. Moreover, imitation reaches 97.5% in 261 seconds, about 89 times faster than reinforcement learning. Two modelling choices remain open for future work. In the current work, we assumed observability of the arrival time of tasks. We plan to relax this assumption and use pre-commitment [42, 44] to keep strategyproofness when owners can delay or otherwise misreport when they appear [11, 35]. Moreover, we assumed that each task owner interacts once with the mechanism. We plan to extend this to iterative interactions using sequential mechanisms [40], so that incentives cover a sequence of reports and associated payments.

Acknowledgments 0

200

400

Revenue (value units)

0.0

0.5

Share

1.0

Figure 2: Partner stream. (a)–(b) misreport search; (c)–(d) class service; (e)–(f) revenue in value units. In addition, high Partner welfare comes with even class service and high payment (Figure 2). Jain’s index is 1 when every class is served at the same rate, not when every arrival is served [20]. SPSMM serves about 44% of each class, so 𝐽 = 1.000 while worst-class service is 0.440. By contrast, V-MLP starves a filler in four seeds, which lowers both 𝐽 and the worst-class rate. The index formula and

The authors acknowledge support from the Engineering and Physical Sciences Research Council (EPSRC) through the Turing artificial intelligence (AI) Fellowship “Citizen-Centric AI Systems (CCAIS)” (EP/V022067/1) and FEVER project (EP/W005883/1), as well as the IRIDIS High Performance Computing Facility and the Low Carbon Comfort Centre (LCCC) at the University of Southampton.

References [1] Ramsundar Anandanarayanan, Swaprava Nath, and Prasant Misra. 2025. Truthful and Welfare-maximizing Resource Scheduling with Application to Electric Vehicles. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, Sanmay Das, Ann Nowé, and Yevgeniy Vorobeychik (Eds.). International

Strategyproof Deep RL

Foundation for Autonomous Agents and Multiagent Systems / ACM, 124–132. doi:10.5555/3709347.3743524 [2] Haris Aziz. 2020. Strategyproof multi-item exchange under single-minded dichotomous preferences. Auton. Agents Multi Agent Syst. 34, 1 (2020), 3. doi:10.1007/s10458-019-09426-w [3] Liad Blumrosen and Noam Nisan. 2007. Combinatorial Auctions. Cambridge University Press, 267–300. doi:10.1017/cbo9780511800481.013 [4] Yongsheng Cao, Hao Wang, Demin Li, and Guanglin Zhang. 2022. Smart Online Charging Algorithm for Electric Vehicles via Customized Actor-Critic Learning. IEEE Internet Things J. 9, 1 (2022), 684–694. doi:10.1109/jiot.2021.3084923 [5] Michael J. Curry, Ping-Yeh Chiang, Tom Goldstein, and John Dickerson. 2020. Certifying Strategyproof Auction Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https://proceedings.neurips.cc/paper/2020/hash/ 3465ab6e0c21086020e382f09a482ced-Abstract.html [6] Zehao Dong, Sanmay Das, Patrick J. Fowler, and Chien-Ju Ho. 2021. Efficient Nonmyopic Online Allocation of Scarce Reusable Resources. In AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021, Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (Eds.). ACM, 447–455. doi:10.5555/3463952.3464009 [7] Paul Duetting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. 2019. Optimal Auctions through Deep Learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 1706–1715. http://proceedings.mlr.press/v97/duetting19a.html [8] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. 2024. Optimal Auctions through Deep Learning: Advances in Differentiable Economics. J. ACM 71, 1 (2024), 5:1–5:53. doi:10.1145/3630749 [9] Damien Ernst, Pierre Geurts, and Louis Wehenkel. 2005. Tree-Based Batch Mode Reinforcement Learning. J. Mach. Learn. Res. 6 (2005), 503–556. https: //jmlr.org/papers/v6/ernst05a.html [10] Tesfay Zemuy Gebrekidan, Sebastian Stein, and Timothy J. Norman. 2024. Deep Reinforcement Learning with Coalition Action Selection for Online Combinatorial Resource Allocation with Arbitrary Action Space. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024, Auckland, New Zealand, May 6-10, 2024, Mehdi Dastani, Jaime Simão Sichman, Natasha Alechina, and Virginia Dignum (Eds.). International Foundation for Autonomous Agents and Multiagent Systems / ACM, 660–668. doi:10.5555/3635637.3662918 [11] Enrico H. Gerding, Valentin Robu, Sebastian Stein, David C. Parkes, Alex Rogers, and Nicholas R. Jennings. 2011. Online mechanism design for electric vehicle charging. In 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, Liz Sonenberg, Peter Stone, Kagan Tumer, and Pinar Yolum (Eds.). IFAAMAS, 811–818. https: //dl.acm.org/citation.cfm?id=2031733 [12] Enrico H. Gerding, Sebastian Stein, Sofia Ceppi, and Valentin Robu. 2016. Online Mechanism Design for Vehicle-to-Grid Car Parks. In Proceedings of the TwentyFifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, Subbarao Kambhampati (Ed.). IJCAI/AAAI Press, 286–293. http://www.ijcai.org/Abstract/16/048 [13] Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. 2011. Dominant Resource Fairness: Fair Allocation of Multiple Resource Types. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2011, Boston, MA, USA, March 30 April 1, 2011, David G. Andersen and Sylvia Ratnasamy (Eds.). USENIX Association. https://www.usenix.org/conference/nsdi11/dominant-resource-fairnessfair-allocation-multiple-resource-types [14] Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, and Makoto Yokoo. 2022. Fair and Truthful Mechanism with Limited Subsidy. In 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 534–542. doi:10.5555/3535850.3535911 [15] Akhil Gupta, Naman Shukla, Lavanya Marla, Arinbjörn Kolbeinsson, and Kartik Yellepeddi. 2019. How to Incorporate Monotonicity in Deep Networks While Preserving Flexibility? https://arxiv.org/abs/1909.10662 [16] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. Python in Science Conference (2008). doi:10.25080/tcwv9851 [17] Luyang Hou, Shuai Ma, Jun Yan, Chun Wang, and Jia Yuan Yu. 2020. Reinforcement Mechanism Design for Electric Vehicle Demand Response in Microgrid Charging Stations. In 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, United Kingdom, July 19-24, 2020. IEEE, 1–8. doi:10.1109/ijcnn48605.2020.9207081

[18] Qi Huangfu and J. A. J. Hall. 2018. Parallelizing the dual revised simplex method. Math. Program. Comput. 10, 1 (2018), 119–142. doi:10.1007/s12532-017-0130-5 [19] Christian Igel. 2024. Smooth Min-Max Monotonic Networks. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 (Proceedings of Machine Learning Research, Vol. 235), Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (Eds.). PMLR / OpenReview.net, 20908–20923. https://proceedings.mlr.press/v235/igel24a.html [20] Rajendra K. Jain, Dah-Ming W. Chiu, and William R. Hawe. 1984. A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems. Technical Report DEC-TR-301. Digital Equipment Corporation, Maynard, MA. [21] Fredrik Johansson. 2017. Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic. IEEE Trans. Computers 66, 8 (2017), 1281–1292. doi:10.1109/ tc.2017.2690633 [22] Hyunho Kim and Jong-Seok Lee. 2024. Scalable Monotonic Neural Networks. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https://openreview.net/forum? id=DjIsNDEOYX [23] Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). doi:10.48550/arxiv.1412.6980 [24] Michael Laskey, Jonathan Lee, Roy Fox, Anca D. Dragan, and Ken Goldberg. 2017. DART: Noise Injection for Robust Imitation Learning. In 1st Annual Conference on Robot Learning, CoRL 2017, Mountain View, California, USA, November 13-15, 2017, Proceedings (Proceedings of Machine Learning Research, Vol. 78). PMLR, 143–156. http://proceedings.mlr.press/v78/laskey17a.html [25] Zachary J. Lee, George Lee, Ted Lee, Cheng Jin, Rand Lee, Zhi Low, Daniel Chang, Christine Ortega, and Steven H. Low. 2021. Adaptive Charging Networks: A Framework for Smart Electric Vehicle Charging. IEEE Trans. Smart Grid 12, 5 (2021), 4339–4350. doi:10.1109/tsg.2021.3074437 [26] Fangqi Liu, Rishav Sen, Jose Paolo Talusan, Ava Pettet, Aaron Kandel, Yoshinori Suzue, Ayan Mukhopadhyay, and Abhishek Dubey. 2025. Reinforcement Learning-based Approach for Vehicle-to-Building Charging with Heterogeneous Agents and Long Term Rewards. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, Sanmay Das, Ann Nowé, and Yevgeniy Vorobeychik (Eds.). International Foundation for Autonomous Agents and Multiagent Systems / ACM, 1345–1353. doi:10.5555/3709347.3743767 [27] Yunxuan Ma, Steven Siqiang Wang, Zhijian Duan, Yukun Cheng, and Xiaotie Deng. 2026. Learning Truthful Mechanisms without Discretization. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2026, Paphos, Cyprus, May 25-29, 2026, Viviana Mascardi, John Thangarajah, Chris Amato, and Louise A. Dennis (Eds.). ACM, 662–670. doi:10.65109/jtxl5273 [28] Pankaj Mishra and Ahmed Moustafa. 2023. Reinforcement learning based monotonic policy for online resource allocation. Future Gener. Comput. Syst. 138 (2023), 313–327. doi:10.1016/j.future.2021.09.023 [29] Roger B. Myerson. 1981. Optimal Auction Design. Math. Oper. Res. 6, 1 (1981), 58–73. doi:10.1287/moor.6.1.58 [30] Mark M. Nejad, Lena Mashayekhy, Ratna Babu Chinnam, and Daniel Grosu. 2017. Online scheduling and pricing for electric vehicle charging. IISE Transactions 49, 2 (2017), 178–193. doi:10.1080/0740817x.2016.1213467 [31] An-phi Nguyen and María Rodríguez Martínez. 2019. MonoNet: Towards Interpretable Models by Learning Monotonic Features. CoRR abs/1909.13611 (2019). doi:10.48550/arxiv.1909.13611 [32] Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2 ed.). Springer, New York, NY. doi:10.1007/978-0-387-40065-5 [33] Niklas Nolte, Ouail Kitouni, and Mike Williams. 2023. Expressive Monotonic Neural Networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. https://openreview.net/forum?id=w2P7fMy_RH [34] Martin A. Riedmiller. 2005. Neural Fitted Q Iteration - First Experiences with a Data Efficient Neural Reinforcement Learning Method. In Machine Learning: ECML 2005, 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005, Proceedings (Lecture Notes in Computer Science, Vol. 3720), João Gama, Rui Camacho, Pavel Brazdil, Alípio Jorge, and Luís Torgo (Eds.). Springer, 317–328. doi:10.1007/11564096_32 [35] Valentin Robu, Enrico H. Gerding, Sebastian Stein, David C. Parkes, Alex Rogers, and Nick R. Jennings. 2013. An Online Mechanism for Multi-Unit Demand and its Application to Plug-in Hybrid Electric Vehicle Charging. J. Artif. Intell. Res. 48 (2013), 175–230. doi:10.1613/jair.4064 [36] Stéphane Ross and Drew Bagnell. 2010. Efficient Reductions for Imitation Learning. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010 (JMLR Proceedings, Vol. 9), Yee Whye Teh and D. Mike Titterington (Eds.). JMLR.org, 661–668. http://proceedings.mlr.press/v9/ross10a.html

Dehghan et al.

[37] Stéphane Ross, Geoffrey J. Gordon, and Drew Bagnell. 2011. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011 (JMLR Proceedings, Vol. 15), Geoffrey J. Gordon, David B. Dunson, and Miroslav Dudík (Eds.). JMLR.org, 627–635. https://proceedings.mlr.press/v15/ross11a.html [38] Davor Runje and Sharath M. Shankaranarayana. 2023. Constrained Monotonic Neural Networks. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 29338–29353. https://proceedings.mlr.press/v202/runje23a.html [39] Weiran Shen, Pingzhong Tang, and Song Zuo. 2019. Automated Mechanism Design via Neural Networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Agents and Multiagent Systems, 215–223. https://dl.acm.org/citation.cfm?id=3331696 [40] Sujoy Sikdar, Xiaoxi Guo, Haibin Wang, Lirong Xia, and Yongzhi Cao. 2021. Sequential Mechanisms for Multi-type Resource Allocation. In AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021, Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (Eds.). ACM, 1209–1217. doi:10.5555/3463952.3464092 [41] Joseph Sill. 1997. Monotonic Networks. In Advances in Neural Information Processing Systems 10, [NIPS Conference, Denver, Colorado, USA, 1997], Michael I. Jordan, Michael J. Kearns, and Sara A. Solla (Eds.). The MIT Press, 661–667. http://papers.nips.cc/paper/1358-monotonic-networks [42] Sebastian Stein, Enrico H. Gerding, Valentin Robu, and Nicholas R. Jennings. 2012. A model-based online mechanism with pre-commitment and its application to electric vehicle charging. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), Wiebe van der Hoek, Lin Padgham, Vincent Conitzer, and Michael Winikoff (Eds.). IFAAMAS, 669–676. https://dl.acm.org/citation.cfm?id=2343792 [43] Sebastian Stein, Mateusz Ochal, Ioana-Adriana Moisoiu, Enrico H. Gerding, Raghu K. Ganti, Ting He, and Tom La Porta. 2020. Strategyproof Reinforcement Learning for Online Resource Allocation. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An, and Neil Yorke-Smith (Eds.). International Foundation for Autonomous Agents and Multiagent Systems, 1296–1304. doi:10.5555/3398761.3398911 [44] Philipp Ströhle, Enrico H. Gerding, Mathijs de Weerdt, Sebastian Stein, and Valentin Robu. 2014. Online mechanism design for scheduling non-preemptive jobs under uncertain supply and demand. In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, Paris, France, May 5-9, 2014, Ana L. C. Bazzan, Michael N. Huhns, Alessio Lomuscio, and Paul Scerri (Eds.). IFAAMAS/ACM, 437–444. https://dl.acm.org/citation.cfm?id=2615803 [45] Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement learning - an introduction, 2nd Edition. MIT Press. http://www.incompleteideas.net/book/thebook-2nd.html [46] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, et al. 2020. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17 (3 2020), 261–272. Issue 3. doi:10.1038/s41592-019-0686-2 [47] Shuoyao Wang, Suzhi Bi, and Ying-Jun Angela Zhang. 2021. Reinforcement Learning for Real-Time Pricing and Scheduling Control in EV Charging Stations. IEEE Trans. Ind. Informatics 17, 2 (2021), 849–859. doi:10.1109/tii.2019.2950809 [48] Hiroki Yanagisawa, Kohei Miyaguchi, and Takayuki Katsuki. 2022. Hierarchical Lattice Layer for Partially Monotone Neural Networks. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (Eds.). http://papers.nips.cc/paper_files/paper/2022/hash/ 47ed62021460f2e9bba7be3e74260090-Abstract-Conference.html [49] Seungil You, David Ding, Kevin Robert Canini, Jan Pfeifer, and Maya R. Gupta. 2017. Deep Lattice Networks and Partial Monotonic Functions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 2981–2989. https://proceedings.neurips.cc/paper/2017/hash/ 464d828b85b0bed98e80ade0a5c43b0f-Abstract.html [50] Zhonghao Zhao and Carman K. M. Lee. 2022. Dynamic Pricing for EV Charging Stations: A Deep Reinforcement Learning Approach. IEEE Transactions on Transportation Electrification 8, 2 (2022), 2456–2468. doi:10.1109/tte.2021.3139674 [51] Suli Zou, Zhongjing Ma, Xiangdong Liu, and Ian A. Hiskens. 2017. An Efficient Game for Coordinating Electric Vehicle Charging. IEEE Trans. Autom. Control. 62, 5 (2017), 2374–2389. doi:10.1109/tac.2016.2614106

Strategyproof Deep RL

A

Critical payments for every monotone network

A verified critical payment requires two numerical guarantees: each network evaluation must enclose the exact output of the stored checkpoint, and the search must keep the first accepted value inside a proved rejecting–accepting bracket. The main text states this procedure as Algorithm 2 in Section 3.3, together with the finite-precision correction in that section. We derive both guarantees from the underlying interval arithmetic before describing the architecture-specific calculations.

A.1

Verified arithmetic and threshold search

We separate three intervals. An input interval describes the values at which a network operation is evaluated. An output ball encloses every exact result of that operation over the input interval. A root bracket [𝑢 lo, 𝑢 hi ] records where the first accepted value can lie (Section 3.3). Neither an output ball nor a root bracket is a probability statement. We represent a real number by the ball 𝐵 = [𝑚𝐵 − 𝜌 𝐵 , 𝑚𝐵 + 𝜌 𝐵 ],

𝜌 𝐵 ≥ 0,

(23)

with midpoint 𝑚𝐵 and radius 𝜌 𝐵 . We import each stored checkpoint parameter exactly into Arb and enclose the result of every subsequent operation [21]. For 𝐵 1 = [𝑚 1 − 𝜌 1, 𝑚 1 + 𝜌 1 ],

𝐵 2 = [𝑚 2 − 𝜌 2, 𝑚 2 + 𝜌 2 ],

𝑢 hi − 𝑢 lo ≤ 2−𝑛 ,

𝑝 hi − 𝑝 lo ≤ 𝑣 max 2−𝑛 .

After outward conversion we compare the two binary64 endpoints as exact dyadic fractions, so we verify the requested width without a further rounded subtraction. The method gains at most one binary digit per step, and a ball that straddles zero cannot move either endpoint; that case is arithmetic and is handled by the precision restart in Algorithm 2 of Section 3.3. Safe acceleration with interval Newton. Point Newton sends 𝑚 to 𝑚 − 𝐹𝑠 (𝑚)/𝐹𝑠′ (𝑚). A rounded derivative, a nearly zero slope, or an unfortunate initial point can send the iterate outside the current bracket [32]. We enclose a derivative interval 𝐹𝑠′ (𝐼 ) that contains 𝐹𝑠′ (𝑧) for every 𝑧 in the current bracket 𝐼 = [𝑎, 𝑏] [21]. If this interval contains zero, interval division is unsafe and we discard the proposal; this includes every bracket that reaches the outer clamp. Otherwise, with 𝑚 = (𝑎 + 𝑏)/2, the interval-Newton image is 𝐹𝑠 (𝑚) 𝑁 (𝐼 ) = 𝑚 − ′ . (26) 𝐹𝑠 (𝐼 ) Suppose 𝑢 ★ ∈ 𝐼 is a root. The mean-value theorem gives some 𝜉 between 𝑚 and 𝑢 ★ such that

the exact set of pairwise sums is  𝐵 1 + 𝐵 2 = (𝑚 1 + 𝑚 2 ) − (𝜌 1 + 𝜌 2 ),  (𝑚 1 + 𝑚 2 ) + (𝜌 1 + 𝜌 2 ) .

rejection, [0.01, 0.03] proves acceptance, and [−0.01, 0.02] proves neither. Bisection of that rejecting–accepting bracket needs no slope estimate and cannot overshoot the root. Starting from [0, 1], after 𝑛 successful steps

0 = 𝐹𝑠 (𝑢 ★) = 𝐹𝑠 (𝑚) + 𝐹𝑠′ (𝜉)(𝑢 ★ − 𝑚). (24)

A convenient enclosure of all products has midpoint 𝑚 1𝑚 2 and radius |𝑚 1 |𝜌 2 + |𝑚 2 |𝜌 1 + 𝜌 1 𝜌 2 . (25) These formulae describe exact real arithmetic. We must also round the stored midpoint and radius: Arb rounds the lower endpoint downward and the upper endpoint upward, enlarging the ball just enough to retain containment [21]. For an increasing elementary function ℎ, the exact image of [𝑎, 𝑏] is [ℎ(𝑎), ℎ(𝑏)]. Arb evaluates and outward-rounds those endpoints, and its validated implementations similarly enclose the exponential, logarithm, and other transcendental operations used by softplus and the network head [21]. Induction over the computation graph therefore yields the invariant used in Section 3.3: the reported output ball contains the exact real result obtained from the stored checkpoint. Even a point input can produce a nonzero radius, because intermediate results must be rounded. Interval evaluation can be conservative. Evaluating 𝑧 − 𝑧 while treating its two appearances as independent copies of [𝑎, 𝑏] gives [𝑎−𝑏, 𝑏−𝑎], although the true result is exactly zero. This dependency effect can widen a ball but cannot exclude the exact answer [21]. Increasing the working precision reduces rounding error; subdividing an input interval can additionally reduce dependency overestimation. Consequently, the sign tests themselves are those of Section 3.3. One additional endpoint convention is required by the tie rule: 𝑈 (𝑢) = 0 proves only 𝐹𝑠 (𝑢) ≤ 0, whereas acceptance needs a nonnegative lower endpoint. For example, [−0.03, −0.01] proves

Rearranging places 𝑢 ★ at 𝑚 − 𝐹𝑠 (𝑚)/𝐹𝑠′ (𝜉). Since 𝐹𝑠′ (𝜉) ∈ 𝐹𝑠′ (𝐼 ), validated interval division proves 𝑢 ★ ∈ 𝑁 (𝐼 ). We intersect 𝑁 (𝐼 ) with 𝐼 . A proposal becomes the new bracket only after the endpoint tests of Section 3.3 restore the rejecting–accepting invariant.

A.2

LinearMono

The same search applies to each monotone architecture. For LinearMono we represent Δ𝑤 (𝜙 (𝑠, 𝑢)) = (wacc − wrej ) · 𝜙 (𝑠, 𝑢). We write 𝑗 𝑣 for the normalised-value coordinate and 𝑤𝑢 = 𝑤 acc 𝑗𝑣 − 𝑤 𝑗𝑣 . If 𝑤𝑢 = 0, Δ𝑤 is constant along the value axis, so the endpoint test of Section 3.3 either accepts every permitted value or none. If 𝑤𝑢 > 0, we take the mathematical threshold to be ! Í rej acc 𝑗≠𝑗 𝑣 𝜙 𝑗 (𝑤 𝑗 − 𝑤 𝑗 ) ★ 𝑢 = max 0, . (27) 𝑤𝑢 rej

If the untruncated fraction exceeds 1, every permitted value is rejected. We keep 𝑤𝑢 ≥ 0 by the coefficient projection of Stein et al. [43]. We import the stored binary coefficients into Arb and perform that division with outward rounding [21]. This expression is the mathematical threshold 𝑢 ★; the deployed critical value remains the finite-precision correction of Section 3.3. Example. We take 𝑣 max = 24 and Δ𝑤 = 2𝑢 − 0.5. Then 𝑢 ★ = 0.25 and 𝑝 ★ = 6.

Dehghan et al.

A.3

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

Hard min–max model

By contrast, we obtain Sill’s hard min–max network by replacing the smooth extrema of Section 3.2 with ordinary maxima and minima [41]. Because every value-axis weight is positive (Section 3.2), we take the hard threshold for a target level 𝐿 to be 𝐿 − 𝑎𝑘ℎ . 𝑘 ≤𝐾 ℎ≤𝐻 𝑤 𝑘ℎ

𝑢 hard = max min

(28)

A unit ℎ reaches 𝐿 at (𝐿 −𝑎𝑘ℎ )/𝑤𝑘ℎ . The group maximum reaches 𝐿 when its earliest unit does, hence the inner minimum; the network minimum reaches 𝐿 only when every group does, hence the outer maximum. The implemented SMM uses log-sum-exp (Section 3.2), so every affine unit contributes and Equation (28) is not the smooth root. We therefore do not seed the search with 𝑢 hard . The formula is included only to explain why the hard network has a closed form while SMM does not.

A.4

Symbol

Meaning

𝑚, 𝑟, 𝑏𝑟 ,𝑇 , 𝑡, 𝑖

number of resource types; resource index; capacity; horizon; slot; arrival true type report; history before 𝑖 state; free-capacity vector and its resource-𝑟 coordinate allocation and payment welfare; utility of 𝑖; covering indicator; indicator reward; return from 𝑡 ; action values; accept– reject action-value difference; parameters; greedy policy bounds; occupancy; features; context

𝜃𝑖 = (𝑣𝑖 , ℓ𝑖 , d𝑖 ) 𝜃ˆ𝑖 , Θ̂<𝑖 𝑠, f (𝑠 ), 𝑓𝑟 (𝑠 ) M = (𝑥, 𝑝 ) 𝑊 , 𝑈𝑖 , 𝑐, 1[ · ] 𝑅, 𝐽𝑡 , 𝑄 𝑤 , Δ𝑤 , 𝑤, 𝜋 𝑤

𝑣max , ℓmax , 𝑜 (𝑠 ), 𝜙 (𝑠 ), 𝑧 (𝑠 ) wacc , wrej 𝑢, 𝑢 ★ , 𝜙 (𝑠, 𝑢 ), 𝐹𝑠 (𝑢 )

Smooth min-max model 𝐾, 𝐻, 𝑘, ℎ

Instead, we take the value-axis derivative of a smooth maximum to be a softmax-weighted average of its unit slopes [19]. Writing exp(𝜁𝑘ℎ ) 𝜋𝑘ℎ = Í , ℎ ′ exp(𝜁𝑘ℎ ′ )

exp(− smaxℎ 𝜁𝑘ℎ ) 𝛼𝑘 = Í , 𝑘 ′ exp(− smaxℎ 𝜁𝑘 ′ ℎ )

we obtain, before the output head, ∑︁ ∑︁ 𝑓𝑤′ (𝑢) = e−𝛽 𝛼𝑘 𝜋𝑘ℎ 𝑤𝑘ℎ > 0. 𝑘 ≤𝐾

ℎ≤𝐻

The context term of Section 3.2 does not depend on 𝑢. Each map of the bounded difference in Section 3.2 is non-decreasing, so the chain rule multiplies 𝑓𝑤′ by a nonnegative factor; that factor is zero on the outer clamp. We therefore enclose the complete derivative of 𝐹𝑠 and apply interval Newton only as in Section A.1.

A.5

Critical values

The remaining monotone networks have no closed form. We invert them by bisection of 𝐹𝑠 with verified signs (Section 3.3), not by a closed-form root. None of LipschitzMono, SMNN, MonoDense or MonoNet has an algebraic inverse. A lattice is piecewise linear inside each cell [49]. Neither a signconstrained linear map nor a lattice makes the complete actionvalue difference piecewise linear, because the bounded difference in Section 3.2 applies a nonlinear tanh head. We therefore bisect the full 𝐹𝑠 for PMLinear as well, rather than interpolating an inner map whose sign is not the acceptance test. U-MLP and V-MLP are controls and are not run through this inversion (Section G).

B

Notation

Table B.1 shows the principal symbols used in the main text.

C

Allocation streams and reference rules

The five streams, including Partner as Example 1 in Section 3.1, are listed in Section 4.2. This section presents sampling, the offline programmes, and the hand-specified rules that the main text names. In particular, fillers occupy capacity for twice as long as premium tasks while providing one-quarter of the value, and offered load

𝑎𝑘ℎ , 𝑤𝑘ℎ , 𝛽, 𝛾 𝑓SMM , 𝑓ctx , 𝑓𝑤 𝜇, 𝜈, 𝜆, 𝜆max , 𝑏 0 𝐵, 𝑚𝐵 , 𝜌 𝐵 𝐼 = [𝑎, 𝑏 ], 𝑚, 𝐹𝑠′ (𝐼 ), 𝑁 (𝐼 ), 𝜉 𝑢 lo , 𝑢 hi , 𝜏, 𝑃 𝑝 ★ , 𝑝 lo , 𝑝 hi , 𝑞 (𝑠 ), 𝑝 (𝑠 )

rank( ℓ,ˆ d̂) ⌈ · ⌉ F , 𝜌𝑞 , ulp 𝜀, 𝑊 FCFS , 𝑠 ′ , 𝑎 ′ 𝑦, 𝜅, 𝑁 , 𝐹 (𝑛) ,𝑊pack 𝜎 (𝜒) 𝛼𝑟 , 𝜏𝑐 , 𝑥 LT 𝑟 (𝑐 ), 𝑟 ★ (𝑐 ), 𝛿𝑐 ¯ 𝜂𝑘 , 𝐽 (𝜼) 𝑝,

LinearMono accept and reject weights normalised candidate value; threshold; features at 𝑢; value-axis action-value difference numbers of SMM groups and units; their indices SMM intercepts, slopes, scale, offset SMM core; context MLP; 𝑓SMM + 𝑓ctx output-head centre, scale, gain, cap, and offset arithmetic ball; midpoint; radius current interval; midpoint; derivative enclosure; interval-Newton image; intermediate point root bracket; critical-value tolerance; working precision mathematical threshold; lower and upper enclosure endpoints; deployed critical value; payment charged integer report rank used by the finite-precision correction upward binary64 rounding; its increase; unit in the last place exploration; FCFS scale; SARSA successor teacher label; margin scale; number of forecasts; packing welfare logistic sigmoid (1 + e−𝜒 ) −1 LinearThresh weights, class threshold, allocation filler resource, partner, Union threshold posted price; class service rate; Jain index

(expected requested resource-time divided by available resourcetime) is 1.32–1.56. On Continuous, the high-density class in Section 4.2 draws each demand uniformly from the positive integers up to [5, 3] and value density from N (5, 0.52 ), truncated below at 0.01; otherwise each demand may be zero (an all-zero draw becomes one unit of the first resource) and density from N (1, 0.32 ), again truncated Í below at 0.01. Value is that density times ℓ 𝑚 𝑟 =1 𝑑𝑟 , capped at 𝑣 max . On Complementary, single-resource tasks create unequal free capacities, while premium and long-duration joint-demand tasks need the two resources together.

Strategyproof Deep RL

Where that table lists LP, OPT is the LP relaxation of the integer packing problem, one variable per task and one capacity constraint per resource and time, solved with SciPy’s HiGHS interface [18, 46]. The relaxation may accept fractions of tasks, so 𝑊 /OPT is then a ratio to an upper bound. Where the table lists exact, OPT is the integer offline optimum obtained by min-cost flow [16]. A ratio of 1 means the online rule matched this programme. In addition, LinearThresh and Union are hand-specified families, not trained learners. For LinearThresh, let 𝛼𝑟 be a global weight on an idle unit of resource 𝑟 and 𝜏𝑐 a cutoff for class 𝑐: Í 𝑥 LT (𝑠) = 1 if and only if 𝑚 𝑟 =1 𝛼𝑟 𝑓𝑟 (𝑠) ≥ 𝜏𝑐 . Every class uses the same 𝜶 = (𝛼 1, . . . , 𝛼𝑚 ). Fillers with different scarce partners need different class–occupancy interactions, which one global weight vector cannot express. LinearMono additionally reads time and the remaining busy time of every capacity unit; however, it still uses one occupancy coefficient per resource, so the four decisions of Example 1 in Section 3.1 cannot hold together. Union accepts every feasible multi-resource task. For a class 𝑐 that uses only resource 𝑟 (𝑐), it looks for a two-resource class that also uses 𝑟 (𝑐); if one exists, the other resource of that class is the partner 𝑟 ★ (𝑐). With class threshold 𝛿𝑐 , the one-resource task is accepted when 𝑓𝑟 ★ (𝑐 ) (𝑠) = 0 or 𝑓𝑟 (𝑐 ) (𝑠) ≥ 𝛿𝑐 . If no partner is found, only the capacity-threshold condition applies, so the rule reduces to per-class capacity thresholds on a single-resource stream. For each family we report the parameter choice with highest welfare on a shared reference block of 200 episodes (seeds 10000–10199) from the streams in Section 4.2. These are deliberately favourable, in-sample values showing what each hand-specified family can express; they are not held-out estimates for a trained learner. We also include the posted-price rule of Stein et al. [43]. That rule uses one occupancy-blind price 𝑝¯ ≥ 0: a feasible report is accepted iff Í ˆ 𝑣ˆ ≥ 𝑝¯ · ℓˆ 𝑚 𝑟 =1 𝑑𝑟 . We search 𝑝¯ ∈ [0, 4] on the reference block. On the partner stream every class occupies 12 unit-slots, so a single 𝑝¯ cannot separate fillers from premium tasks.

D

Training and inversion settings

In addition to the episode counts, seeds, and imitation loss of Section 4.1, Table D.1 records optimiser schedules, network sizes, inversion bit-widths, and imitation budgets.

E

Table D.1: Training and imitation settings. quantity

value

𝜀 LinearMono SP-SMM / SMNN other neural models gradient clipping (neural) fitted SARSA refresh / passes / minibatch SARSA discount reward scale neural TD targets gain cap 𝜆max SMM 𝐾 × 𝐻 context MLP width

0.1 → 0 linearly SGD, learning rate 0.1 → 0 Adam [23], 5 · 10−3 → 10−5 Adam, 10 −2 → 10−5 ℓ2 norm at 5 20 episodes / 5 / 64 1 (undiscounted) 1/𝑊 FCFS (20 FCFS episodes) clipped to [ −5, 5] 2 6×6 64 (sigmoid hidden layer, linear output) 0.1 [24] verified interval upper endpoint verified interval, then finiteprecision correction 10 −6 / 64, 128, 256 bits 200 / 50 30 / 64 / 0.05 20 / 5 5 / 10 3 / 24

DART action-flip probability reported experiments complete mechanism critical-value tolerance / precision teacher-transition / labelled episodes imitation L passes / minibatch / 𝜅 value fitting sweeps / passes per sweep DAgger rounds / selection rollouts planner forecasts / look-ahead slots

reports 𝑊 /OPT; Table F.2 reports fitting time. No protocol ranks first on every stream. On Large, DAggerW exceeds DAgger for LipschitzMono (0.963 versus 0.934), as it does for SP-SMM in Section 4.3; the same comparison changes little on the partner stream. On the partner stream, U-MLP and V-MLP both stay near FCFS welfare (0.891) under most protocols, so dropping duration and demand monotonicity does not buy a welfare gain here. Neither a report constraint nor a strong teacher alone ensures high welfare; the teacher, collection protocol, and function class also matter. Classlevel service after imitation is Table F.3. V-MLP matches FCFS on that table under both protocols, so we omit its row.

Numeric reinforcement learning welfare G

Using those settings, Table E.1 is the numeric counterpart of the welfare figure in Section 4.3: it adds standard errors, Partner RL training time, and the in-sample LinearThresh and posted-price rows that the figure omits.

F

Imitation grid

Turning from RL welfare to imitation, the loss, protocols, and teachers are those of Section 4.1. In particular, DART’s flip probability, the planner window, 𝜅, and the label budget appear in Table D.1. For the partner stream we compare the hand-specified families of Section C on 40 episodes disjoint from training and final evaluation, and we take the selected Union rule as the teacher. We then report, for every neural architecture, BC from that rule and planner BC, DAgger, DAggerW, and DART, using five seeds. Monotone rows use Algorithm 2 in Section 3.3. Table F.1

Unconstrained and value-only controls

Separately, U-MLP and V-MLP are the controls of Section 4.2. From random initialisation, U-MLP matches FCFS welfare on Partner, Small, Large, and Complementary (0.891, 0.417, 0.559, 0.742) and is below FCFS on Continuous (0.616 ± 0.154 versus 0.770). V-MLP is below FCFS on Partner (0.781±0.027) and above it on the remaining streams. Misreport search. We freeze each trained score and look for a profitable misreport. We follow the grid used for online electricvehicle mechanisms [35] and neural auctions [7]. We take reported value from the 21-point grid {0, 𝑣 max /20, . . . , 𝑣 max } together with the true value, jointly with duration or a single demand coordinate. Utility is that of Section 2.2. We write 𝑅𝑖 for the utility gain of agent 𝑖, 𝑅𝑖 = 𝑈𝑖 (𝜃ˆ𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ) −𝑈𝑖 (𝜃 𝑖 , 𝜃 𝑖 , Θ̂<𝑖 ). We take by lie to be the fraction of audited states at which this gain is positive. A zero in

Dehghan et al.

Table E.1: RL welfare divided by the offline optimum, with Partner training time. welfare / OPT method SP-SMM LipschitzMono [33] SMNN [22] MonoDense [38] MonoNet [31] LinearMono [43] PMLinear [48]

Small

Large

Cont.

Compl.

gap

train (s)

0.978 ± 0.001 0.960 ± 0.006 0.957 ± 0.001 0.946 ± 0.003 0.943 ± 0.001 0.938 ± 0.002 0.929 ± 0.005

0.942 ± 0.017 0.883 ± 0.117 0.717 ± 0.127 0.883 ± 0.076 0.767 ± 0.143 0.992 ± 0.008 0.950 ± 0.020

0.912 ± 0.021 0.946 ± 0.014 0.795 ± 0.072 0.914 ± 0.037 0.785 ± 0.066 0.888 ± 0.023 0.882 ± 0.043

0.812 ± 0.010 0.804 ± 0.007 0.824 ± 0.006 0.808 ± 0.003 0.769 ± 0.011 0.792 ± 0.007 0.781 ± 0.009

0.953 ± 0.003 0.946 ± 0.010 0.949 ± 0.006 0.959 ± 0.001 0.913 ± 0.031 0.959 ± 0.000 0.951 ± 0.004

2.2% 4.0% 4.3% 5.4% 5.7% 6.2% 7.1%

23,255 84,607 12,558 9,119 9,003 51 861

0.559 0.764 0.960 0.960

0.770 0.821 0.795 0.791

0.741 0.954 0.956 0.936

11.0% 11.0% 8.3% 2.7%

– – – –

Reference policies (fixed in-sample episode block) FCFS 0.890 0.417 posted-price 0.890 0.625 LinearThresh 0.917 1.000 Union 0.973 1.000

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

method

Rule BC

Planner BC

DAgger

DAggerW

DART

Partner SP-SMM 0.975 ± 0.000 0.973 ± 0.001 0.972 ± 0.002 0.973 ± 0.001 0.971 ± 0.002 LipschitzMono 0.975 ± 0.001 0.971 ± 0.001 0.974 ± 0.002 0.974 ± 0.002 0.970 ± 0.002 SMNN 0.937 ± 0.002 0.933 ± 0.006 0.933 ± 0.002 0.938 ± 0.004 0.919 ± 0.012 MonoDense 0.947 ± 0.008 0.941 ± 0.004 0.940 ± 0.003 0.940 ± 0.006 0.937 ± 0.006 MonoNet 0.938 ± 0.002 0.917 ± 0.003 0.918 ± 0.003 0.931 ± 0.002 0.927 ± 0.003 PMLinear 0.936 ± 0.002 0.930 ± 0.004 0.927 ± 0.002 0.931 ± 0.001 0.928 ± 0.003 V-MLP 0.891 ± 0.000 0.891 ± 0.000 0.891 ± 0.000 0.891 ± 0.000 0.891 ± 0.000 U-MLP 0.891 ± 0.000 0.891 ± 0.000 0.905 ± 0.015 0.905 ± 0.015 0.891 ± 0.000 Small

Partner

Partner

SP-SMM 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 LipschitzMono 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 SMNN 0.650 ± 0.143 0.650 ± 0.143 1.000 ± 0.000 1.000 ± 0.000 0.650 ± 0.143 MonoDense 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 0.767 ± 0.143 MonoNet 0.767 ± 0.143 0.767 ± 0.143 1.000 ± 0.000 1.000 ± 0.000 0.883 ± 0.117 PMLinear 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 1.000 ± 0.000 V-MLP 0.417 ± 0.000 0.417 ± 0.000 0.417 ± 0.000 0.458 ± 0.042 0.417 ± 0.000 U-MLP 0.417 ± 0.000 0.417 ± 0.000 0.650 ± 0.143 0.650 ± 0.143 0.417 ± 0.000

Large

SP-SMM 0.960 ± 0.000 0.887 ± 0.026 0.920 ± 0.015 0.945 ± 0.009 0.911 ± 0.016 LipschitzMono 0.955 ± 0.002 0.911 ± 0.021 0.934 ± 0.019 0.963 ± 0.004 0.915 ± 0.015 SMNN 0.960 ± 0.000 0.926 ± 0.024 0.955 ± 0.013 0.963 ± 0.008 0.929 ± 0.012 MonoDense 0.960 ± 0.000 0.926 ± 0.017 0.939 ± 0.010 0.960 ± 0.002 0.947 ± 0.014 MonoNet 0.960 ± 0.000 0.922 ± 0.018 0.894 ± 0.028 0.957 ± 0.009 0.935 ± 0.019 PMLinear 0.960 ± 0.000 0.898 ± 0.016 0.900 ± 0.026 0.931 ± 0.010 0.926 ± 0.013 V-MLP 0.765 ± 0.000 0.783 ± 0.019 0.782 ± 0.092 0.905 ± 0.037 0.765 ± 0.000 U-MLP 0.345 ± 0.213 0.180 ± 0.180 0.641 ± 0.082 0.641 ± 0.082 0.181 ± 0.181

Cont.

SP-SMM 0.805 ± 0.002 0.841 ± 0.006 0.839 ± 0.006 0.848 ± 0.005 0.841 ± 0.003 LipschitzMono 0.787 ± 0.006 0.852 ± 0.007 0.839 ± 0.007 0.849 ± 0.004 0.837 ± 0.006 SMNN 0.795 ± 0.005 0.834 ± 0.010 0.812 ± 0.011 0.840 ± 0.006 0.823 ± 0.009 MonoDense 0.804 ± 0.002 0.838 ± 0.006 0.845 ± 0.007 0.852 ± 0.002 0.834 ± 0.006 MonoNet 0.806 ± 0.002 0.837 ± 0.005 0.817 ± 0.005 0.828 ± 0.002 0.821 ± 0.003 PMLinear 0.801 ± 0.003 0.828 ± 0.005 0.815 ± 0.003 0.835 ± 0.005 0.825 ± 0.003 V-MLP 0.769 ± 0.001 0.770 ± 0.000 0.770 ± 0.000 0.770 ± 0.000 0.770 ± 0.000 U-MLP 0.770 ± 0.000 0.770 ± 0.000 0.770 ± 0.000 0.770 ± 0.000 0.770 ± 0.000

Compl.

SP-SMM 0.956 ± 0.000 0.949 ± 0.006 0.952 ± 0.003 0.957 ± 0.001 0.958 ± 0.000 LipschitzMono 0.956 ± 0.000 0.951 ± 0.005 0.955 ± 0.002 0.956 ± 0.002 0.958 ± 0.001 SMNN 0.956 ± 0.000 0.910 ± 0.029 0.925 ± 0.021 0.940 ± 0.009 0.941 ± 0.009 MonoDense 0.956 ± 0.000 0.950 ± 0.002 0.954 ± 0.003 0.955 ± 0.003 0.957 ± 0.001 MonoNet 0.956 ± 0.000 0.943 ± 0.006 0.951 ± 0.004 0.955 ± 0.001 0.953 ± 0.004 PMLinear 0.956 ± 0.000 0.947 ± 0.004 0.948 ± 0.006 0.948 ± 0.006 0.955 ± 0.001 V-MLP 0.954 ± 0.000 0.954 ± 0.000 0.954 ± 0.000 0.954 ± 0.000 0.954 ± 0.000 U-MLP 0.785 ± 0.043 0.742 ± 0.000 0.742 ± 0.000 0.742 ± 0.000 0.742 ± 0.000

the search means the grid found no improving deviation, not that none exists outside the grid. After training, the grid returns 𝑅𝑖 = 0 for every score in Table G.1, including the controls, so we omit a by-lie column. U-MLP’s zero regret coincides with accepting every feasible request and charging 0. By contrast, the same search returns 𝑅𝑖 = 0 for SP-SMM and

LinearMono while they remain selective. That is required by Theorem 1 in Section 3.3; it is a consistency check of the implementation, not an empirical proof. During training, only the two controls ever have 𝑅𝑖 > 0. Consequently Tables G.2 and G.3 list those controls only; the Partner by-lie rates in Section 4.3 are the worst-checkpoint column of Table G.2. Every monotone score stays at zero regret on every stream, including SMNN’s most selective Partner checkpoint (18% accepted).

H

Service across classes

Finally, the audit figure in Section 4.3 plots worst-class service and Jain’s index on the partner stream. This section shows the formula and the remaining methods. We write 𝜂𝑘 for the fraction of class-𝑘 arrivals that complete, 𝑘 ∈ {𝐴, 𝐵, 𝐶, 𝐷 }, and 𝜼 = (𝜂𝐴 , 𝜂𝐵 , 𝜂𝐶 , 𝜂𝐷 ). Jain’s index [20] is
2 Í 𝑘 𝜂𝑘 (29) 𝐽 (𝜼) = Í 2 . 4 𝑘 𝜂𝑘 The index equals 1/4 when a single class receives all of the service. We also report the worst-class rate min𝑘 𝜂𝑘 , because 𝐽 can remain high while one class is poorly served. Served is the fraction of all arrivals that complete, so a rule that allocates nothing cannot top the table: 𝐽 is undefined on the zero vector. FCFS is a reference for class-level differences caused by the arrival process, because it makes no value-based selection. Table H.1 lists 𝐽 , the worst-class rate, and served fraction after RL from random initialisation. U-MLP’s post-training rule accepts every feasible request (Section G), so its class mix matches FCFS and we omit its row. The worst-served class is always a filler. VMLP starves class C in four of five seeds; those four seeds have 𝐽 = 0.50, while its overall mean is 0.595 ± 0.095 because the fifth seed has FCFS-like service. None of the networks monotone in every reported quantity starves a class in these runs.

Strategyproof Deep RL

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

Table F.2: Imitation fitting time in seconds. setting

score

accepted

rev.

welf.

46% 26% 44% 45% 44% 43% 42% 42% 40%

0 223 168 465 475 144 364 366 458

456 403 478 491 495 484 485 482 483

U-MLP V-MLP LinearMono SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear

accepted

by lie

max mean regret /𝑣max

U-MLP V-MLP

36% 44%

43% 29%

0.351 0.215

386 724 278 247 237 197 219 185

410 751 339 256 273 206 221 189

412 739 472 272 292 214 220 189

382 808 268 244 279 198 217 195

Small

SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear V-MLP U-MLP

54 64 34 36 28 31 37 20

119 71 38 94 26 59 37 19

52 71 37 31 27 24 27 21

89 76 37 35 29 27 33 21

47 63 38 36 26 22 27 26

Large

SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear V-MLP U-MLP

320 961 200 190 160 115 142 118

377 879 267 234 227 146 168 128

386 915 367 368 223 157 166 127

400 978 528 248 219 147 173 132

444 884 269 231 203 143 225 134

Cont.

SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear V-MLP U-MLP

631 952 309 287 211 101 129 90

682 980 500 412 420 344 363 333

799 952 682 450 451 401 369 342

810 1,014 572 460 500 367 375 348

685 890 486 410 412 347 363 341

Compl.

SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear V-MLP U-MLP

337 688 251 164 162 132 117 113

441 746 383 301 299 227 252 216

527 777 431 318 339 238 262 217

567 861 456 317 348 240 265 224

456 839 384 300 318 226 253 215

Table G.3: Maximum mean regret during training as a fraction of 𝑣 max , controls only. score

Partner

Small

Large

Cont.

Compl.

U-MLP V-MLP

0.351 0.215

0.076 0.050

0.200 0.193

0.090 0.038

0.450 0.342

Table H.1: Per-class service after training from random initialisation. U-MLP matches FCFS and is omitted. method FCFS SP-SMM LipschitzMono LinearMono SMNN MonoDense MonoNet PMLinear V-MLP

Jain 𝐽 (𝜼)

min. rate

served

0.974 1.000 ± 0.000 0.997 ± 0.001 0.998 ± 0.001 0.997 ± 0.001 0.995 ± 0.003 0.996 ± 0.001 0.985 ± 0.004 0.595 ± 0.095

0.372 0.440 ± 0.002 0.413 ± 0.013 0.414 ± 0.003 0.403 ± 0.007 0.384 ± 0.016 0.386 ± 0.006 0.335 ± 0.017 0.074 ± 0.074

0.456 0.446 0.436 0.436 0.426 0.422 0.417 0.405 0.252

Rule BC Planner BC DAgger DAggerW DART 261 643 173 134 133 88 109 90

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

method

Partner SP-SMM LipschitzMono SMNN MonoDense MonoNet PMLinear V-MLP U-MLP

Table F.3: Class-level service after imitation on the partner benchmark. Union BC method

Jain

min. rate

SP-SMM 0.999 ± 0.000 0.424 ± 0.001 LipschitzMono 0.999 ± 0.000 0.423 ± 0.003 SMNN 0.995 ± 0.002 0.393 ± 0.010 MonoDense 0.997 ± 0.001 0.401 ± 0.010 MonoNet 0.998 ± 0.001 0.405 ± 0.007 PMLinear 0.999 ± 0.000 0.420 ± 0.003 U-MLP 0.974 ± 0.000 0.372 ± 0.000

DAggerW served 0.439 0.439 0.422 0.429 0.427 0.433 0.456

Jain

min. rate

1.000 ± 0.000 0.443 ± 0.001 1.000 ± 0.000 0.442 ± 0.002 0.997 ± 0.002 0.412 ± 0.005 0.995 ± 0.003 0.405 ± 0.009 0.994 ± 0.001 0.398 ± 0.004 0.994 ± 0.001 0.397 ± 0.002 0.979 ± 0.005 0.384 ± 0.012

served 0.449 0.450 0.439 0.446 0.447 0.447 0.455

Related documents

• Strategyproof Deep Reinforcement Learning for Online Resource Allocation#1469174
• Elastic Spectral State Space Models for Train-Once Budgeted Inference#1013504
• Streaming Deep Reinforcement Learning Finally Works#1050732
• DiffusionART: Efficient, Stable and Scalable Reinforcement of Diffusion Models#1313566
• DiffusionART: Efficient, Stable and Scalable Reinforcement of Diffusion Models#1296579