⚡ electrical engineering

Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

This paper introduces a new observable signal-based policy-cost formulation for autonomous pickup-and-delivery routing under internal adversarial influence, demonstrating that stability is equivalent to uniformly bounding expected canceled requests and proving that finite time windows are essential to prevent degenerate stability regimes characterized by large backlogs.

Original authors: Roee M. Francos, Daniel Garces, Orhan Eren Akgün, Stephanie Gil

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Roee M. Francos, Daniel Garces, Orhan Eren Akgün, Stephanie Gil

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy city where a central dispatcher manages a fleet of self-driving taxis. Their job is simple: match available cars to people waiting for rides. In a perfect world, every car is honest, follows the dispatcher's orders, and picks up the passengers.

But in this paper, the authors imagine a scenario where some of the taxis are "rogue agents." These aren't broken cars; they are malicious. They lie about where they are on the map to trick the dispatcher into sending them a ride request. Once they get the assignment, they don't pick up the passenger. Instead, they sit there, blocking that request, while the honest cars are sent on wild goose chases or left idle.

The paper asks a big question: How do we know if the whole system is still working well when these liars are around?

The Problem with Old Rules

Traditionally, engineers measure if a system is "stable" by counting how many rides are waiting in line (the backlog). If the line doesn't grow forever, they say, "Great, the system is stable!"

The authors argue this is a trap. Imagine a restaurant where the waiter keeps taking orders but never brings the food. The kitchen might only have 10 orders in the queue at any one time (so the line looks short), but the customers have been waiting for hours, and eventually, they just leave angry.

The Trap: The old rule says the system is "stable" because the line isn't infinite.
The Reality: The system is actually failing because customers are being abandoned.

The authors call this "Degenerate Stability." It's like a car that is technically "running" because the engine is on, but it's stuck in mud going nowhere.

The New Solution: Counting the "Left Behind"

To fix this, the authors propose a new way to measure stability. Instead of just counting the line, they count two things:

The Line: How many people are currently waiting?
The Left Behind: How many people have given up and left because they waited too long?

They introduce a rule called Time Windows. Every ride request has a deadline. If a car doesn't pick up the passenger within that time, the request "expires" and is marked as Canceled.

The Big Discovery:
The authors prove mathematically that if you have a limit on how many new requests come in and a limit on how long people will wait (the time window), then the "Line" will never get too huge on its own. The only thing that can make the system truly unstable is if the number of Canceled requests keeps growing forever.

So, in their new system, a policy is only "stable" if it keeps the number of abandoned requests under control. If the system is constantly canceling rides, it's unstable, even if the waiting line looks short.

The Game of "Cat and Mouse"

The paper also looks at how these rogue taxis try to cause the most damage. They tested three levels of "smartness" for the bad guys:

The Novice: Just looks at where the requests are and lies to get close to one.
The Team Player: Knows where the other bad taxis are and coordinates to block multiple requests.
The All-Knowing: Knows exactly what the dispatcher is thinking, where every good taxi is, and can predict exactly which rides the good taxis would have taken. They lie specifically to steal those rides.

They also tested three different ways the dispatcher assigns rides:

Greedy: "Give the nearest car the nearest ride." (Fast, but maybe not the best overall).
Instant Assignment (No Reassignment): "Once a car gets a ride, it's stuck with it." (Harder for bad guys to trick, but less flexible).
Instant Assignment with Reassignment: "Keep changing the plan to find the best match." (Very flexible, but the bad guys can keep changing their location to mess up the plan over and over).

The Results

Using real taxi data from San Francisco, they ran simulations.

The "No-Deadline" Scenario: When they removed the time limits, the system looked stable (the line didn't grow), but the bad guys had successfully blocked hundreds of rides. This proved the "Degenerate Stability" trap.
The "With-Deadline" Scenario: When they added the time limits, the system immediately showed it was failing. The number of canceled rides skyrocketed, correctly flagging the system as unstable.

They found that the "All-Knowing" bad guys caused the most chaos. They also found that the "Reassignment" policy (constantly changing plans) was the most vulnerable to these liars because the bad guys could keep tricking the system into changing its mind.

The Takeaway

The paper concludes that to truly know if a self-driving fleet is working, you can't just look at the waiting list. You have to look at the failures. If requests are expiring and people are being left behind, the system is broken, no matter how short the line looks. By counting the "left behind" requests, we get a true picture of whether the system is actually serving its purpose.

Technical Summary: Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

Problem Statement
The paper addresses the vulnerability of autonomous pickup-and-delivery systems to internal adversarial agents. In these systems, a centralized scheduler matches available agents to service requests. However, compromised or strategic agents within the fleet may spoof their reported locations to capture task assignments and intentionally leave those requests unserviced. This behavior disrupts the scheduler, causing delays, request cancellations, and inefficient resource utilization.

A central challenge identified is defining "policy stability" in such adversarial environments. Traditional stability definitions rely on:

Queueing-theoretic workloads: These require analyzing agent-specific route execution, which is infeasible when agents deviate arbitrarily or fail to service requests.
Discounted Reinforcement Learning (RL) costs: These depend on a discount factor that may underweight long-horizon degradation and mask cumulative adversarial effects.
Backlog-only metrics: These fail to distinguish between requests that are eventually served after excessive delay and those that are never served within an operationally acceptable time window.

The authors argue that existing criteria are ill-suited for adversarial settings where non-cooperative agents arbitrarily deviate from assigned routes.

Methodology
The authors propose a new framework for analyzing stability based on observable system-level signals rather than inferred agent-level actions.

New Stability Formulation: The paper introduces an average-cost stability criterion defined by two observable quantities:
1. The number of outstanding requests ( $O_t$ ).
2. The cumulative number of canceled requests ( $C_t$ ).
  The stage cost is defined as $g = O_t + C_t$ . A policy is stable if the expected average cost over an infinite horizon is finite.
Theoretical Analysis:
- Assumptions: The analysis assumes bounded request arrivals and finite request time windows (requests expire if not serviced within a specific duration).
- Key Theorem: Under these assumptions, the number of outstanding requests is uniformly bounded over time (Remark 1). Consequently, the paper proves (Theorem 1) that stability under the proposed average-cost criterion is equivalent to keeping the expected cumulative number of canceled requests uniformly bounded over time.
- Degenerate Stability: The authors characterize a pathological regime called "degenerate stability." Without finite time windows, a system might satisfy classical backlog-based stability criteria while maintaining a large, operationally unacceptable backlog of delayed requests. Finite time windows convert excessive waiting into observable cancellations, thereby ruling out this degenerate regime.
Adversarial Models and Assignment Policies:
- Adversarial Knowledge: Three models are defined based on information availability: Request-Only (limited info), Team-Information (coordination among adversaries), and Omnipotent (full system awareness and knowledge of the scheduler's algorithm).
- Assignment Policies: Three policies are studied: Greedy (local nearest-neighbor), Instantaneous Assignment (IA) (global optimal matching with commitment), and Instantaneous Assignment with Reassignment (IA-RA) (global matching allowing reassignment before pickup).
- Feasibility-Aware Allocation: The authors introduce assignment mechanisms that restrict matches to agent-request pairs capable of meeting the time-window constraints before expiration.

Key Contributions

Observable Average-Cost Stability: A stability formulation based on system-level signals (outstanding and canceled requests) that does not require reconstructing agent-level route execution, making it applicable to both cooperative and adversarial settings.
Equivalence Theorem: A proof showing that under bounded arrivals and finite time windows, stability is equivalent to bounding the expected cumulative number of canceled requests.
Identification of Degenerate Stability: A characterization of a regime where backlog-based criteria falsely certify stability despite poor service quality, motivating the necessity of finite time windows and cancellation penalties.
Adversarial Framework: Development of feasibility-aware assignment procedures and adversarial knowledge models that capture varying levels of strategic awareness and coordination.
Empirical Evaluation: A case study using real-world San Francisco mobility-on-demand taxi data to evaluate the proposed framework.

Results
The empirical study, conducted on a simulated San Francisco road network with real demand data, yielded the following findings:

Fleet Calibration: Cooperative fleet sizes derived from existing queueing-theoretic baselines were verified to produce stable behavior under finite time windows.
Degenerate Stability Validation: In settings without request expiration, the number of outstanding requests plateaued, leading classical backlog metrics to classify the system as stable despite significant delays. This confirmed the existence of degenerate stability.
Adversarial Impact: Under finite time windows, the proposed average-cost metric correctly identified instability through sustained growth in policy cost driven by request cancellations.
- Instability increased with the proportion of adversarial agents.
- Omnipotent adversaries caused the most severe degradation, followed by Team-Information and Request-Only models.
- The IA-RA policy was found to be more vulnerable than IA or Greedy because reassignment mechanisms allow adversaries to repeatedly redirect cooperative agents, amplifying disruption.
Metric Comparison: The proposed metric (backlog + cancellations) identified unstable regimes that a backlog-only metric missed, demonstrating that bounded backlog alone is insufficient for assessing service quality in time-sensitive adversarial systems.

Significance
The paper claims that its primary significance lies in providing a stability definition that is directly tied to operational service failures (cancellations) rather than theoretical workloads. By linking stability to the boundedness of canceled requests, the formulation offers a meaningful metric for time-sensitive routing systems where delays are unacceptable.

The authors emphasize that finite request time windows are not merely a modeling detail but are essential for distinguishing between acceptable operation and a regime of "degenerate stability" where systems appear stable but fail to serve requests within acceptable timeframes. This work bridges the gap between routing stability analysis, security against internal spoofing, and the practical constraints of time-windowed service, offering a framework that remains robust even when agents deviate from prescribed behaviors.