Operational Reliability of Deadline-Constrained Task Assignment: Stability Characterization and Adversarial Routing

Abstract

Automated task-assignment systems often serve stochastic tasks subject to finite deadlines. In these settings, conventional backlog-based stability can be misleading: finite task lifetimes may keep the number of outstanding tasks bounded even as deadline failures continue indefinitely, while average failure-rate criteria can still permit recurrent failures. We introduce average cost stability, a criterion which is particularly useful for time-sensitive tasks, combining two observable quantities: the number of outstanding tasks and the cumulative number of irrecoverable deadline failures. Under bounded arrivals and uniformly bounded service windows, we show that the outstanding-task count is uniformly bounded independently of the assignment policy and prove that our average cost stability is equivalent to bounded expected cumulative failures. We further characterize degenerate backlog stability, in which backlog remains bounded despite unbounded cumulative failures. We instantiate the framework in an adversarial pickup-and-delivery system where internal fleet agents spoof reported locations to attract assignments and leave requests unserviced. We develop deadline-aware assignment procedures and adversarial models with varying knowledge and coordination capabilities. Experiments using real mobility-on-demand request data and our proposed adversarial models demonstrate that backlog can remain bounded while cancellations persist, whereas our proposed average cost stability correctly identifies such behavior as unstable.

23 pages, 5 figures