Online assignment of reusable resources stops ranking by match score alone: LAG prices in opportunity cost and beats greedy by up to 12.3% on peer-review data
Synopsis
Online assignment of reusable resources such as reviewers, call agents and servers has long relied on greedy matching: dispatch whichever available resource scores highest now, ignoring the value lost when it is occupied later. LAG casts the problem as a contextual restless multi-armed bandit and uses an occupancy-measure linear program, together with its dual, to compute a closed-form index for each task-type and resource pair, equal to the match score minus the opportunity cost of keeping that resource free. On peer-review data and structured synthetic instances, LAG reaches 83–99% of that linear program's upper bound and improves over greedy by up to 12.3% on journal data and up to 36% on synthetic instances.
Interpretation
The decision signal in online assignment changes from a single match score to the match score minus an opportunity cost, so a resource can be held back for a later task that needs it more. The prior practice is greedy: rank currently available resources by match score and dispatch the highest, with no account of future demand; automated reviewer assignment and call-center routing take this form. On peer-review data and structured synthetic instances, LAG reaches 83–99% of the occupancy-measure linear program's upper bound, improving over greedy by up to 12.3% on journal data and up to 36% on synthetic instances.
Each task-type and resource pair receives a scalar index, and an arriving task takes free resources in decreasing index order. The index comes from the dual of the occupancy-measure linear program, whose dual splits the global assignment problem into one subproblem per resource, each solved by a threshold policy. The price term in the index is the shadow price of serving a task of that type, and the other term is the per-step cost of keeping a resource busy; in the load sweep, the program is solved once per load point and the indices are computed from that solution.
Under a scaling regime in which the number of copies of each resource and the number of arrivals per step grow together, LAG is proved asymptotically optimal. The classical scaling that grows only the resource count keeps one random arrival per step, so the fluid system never settles to a deterministic fixed point; a batch scaling that also grows arrivals instead lets resources pick the best task from a batch, changing the original problem. The new scaling randomly partitions each resource type into groups that each face one arrival, so every resource still sees only one context per step; in this regime LAG's normalized reward converges to the linear program bound and the blocking probability vanishes.
Perspective
The demonstrated setting is a discrete-time system with reusable resources, immediate assignment of each arriving task, and bounded service durations that depend only on task type; evaluation covers two real peer-review datasets, two synthetic call-center instances and two analytical instances, with load swept from 0.1 to 0.9. Asymptotic optimality holds only under a strict-underload assumption and in the new scaling regime where copies of each resource and arrivals per step grow together.
The asymptotic-optimality proof relies on the assumption that the fluid dynamics have a unique globally attracting fixed point, a property that is typically hard to verify analytically and is usually established through numerical evidence. At finite scale the blocking probability has no closed form and must be computed numerically, with the Erlang loss-network expression serving as a reference value.