  A machine-learned system that is fair in static decision-making tasks may
have biased societal impacts in the long-run. This may happen when the system
interacts with humans and feedback patterns emerge, reinforcing old biases in
the system and creating new biases. While existing works try to identify and
mitigate long-run biases through smart system design, we introduce techniques
for monitoring fairness in real time. Our goal is to build and deploy a monitor
that will continuously observe a long sequence of events generated by the
system in the wild, and will output, with each event, a verdict on how fair the
system is at the current point in time. The advantages of monitoring are
two-fold. Firstly, fairness is evaluated at run-time, which is important
because unfair behaviors may not be eliminated a priori, at design-time, due to
partial knowledge about the system and the environment, as well as
uncertainties and dynamic changes in the system and the environment, such as
the unpredictability of human behavior. Secondly, monitors are by design
oblivious to how the monitored system is constructed, which makes them suitable
to be used as trusted third-party fairness watchdogs. They function as
computationally lightweight statistical estimators, and their correctness
proofs rely on the rigorous analysis of the stochastic process that models the
assumptions about the underlying dynamics of the system. We show, both in
theory and experiments, how monitors can warn us (1) if a bank's credit policy
over time has created an unfair distribution of credit scores among the
population, and (2) if a resource allocator's allocation policy over time has
made unfair allocations. Our experiments demonstrate that the monitors
introduce very low overhead. We believe that runtime monitoring is an important
and mathematically rigorous new addition to the fairness toolbox.
