TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems
Z Yin, A Jiang, M Johnson, M Tambe, C Kiekintveld, K Leyton-Brown, T Sandholm, J Sullivan
In Conference on Innovative Applications of Artificial Intelligence (IAAI 2012).
This is the author's version of the work.
Download
Abstract
In proof-of-payment transit systems, passengers are legally
required to purchase tickets before entering but are not physically
forced to do so. Instead, patrol units move about the
transit system, inspecting the tickets of passengers, who face
fines if caught fare evading. The deterrence of such fines depends
on the unpredictability and effectiveness of the patrols.
In this paper, we present TRUSTS, an application for scheduling
randomized patrols for fare inspection in transit systems.
TRUSTS models the problem of computing patrol strategies
as a leader-follower Stackelberg game where the objective
is to deter fare evasion and hence maximize revenue.
This problem differs from previously studied Stackelberg
settings in that the leader strategies must satisfy massive
temporal and spatial constraints; moreover, unlike in these
counterterrorism-motivated Stackelberg applications, a large
fraction of the ridership might realistically consider fare evasion,
and so the number of followers is potentially huge.
A third key novelty in our work is deliberate simplification
of leader strategies to make patrols easier to be executed.
We present an efficient algorithm for computing such patrol
strategies and present experimental results using realworld
ridership data from the Los Angeles Metro Rail system.
The Los Angeles Sheriff's department has begun trials
of TRUSTS.
