TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems Using Game Theory
Z Yin, A Jiang, M Tambe, C Kiekintveld, K Leyton-Brown, T Sandholm, J Sullivan
In AI Magazine.
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 fare evasion depends on the unpredictability
and effectiveness of the patrols. In
this article, 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 execute. We present an efficient algorithm
for computing such patrol strategies and
present experimental results using real-world
ridership data from the Los Angeles Metro Rail
system. The Los Angeles County Sheriff's
Department is currently carrying out trials of
TRUSTS.
