Monitoring Algorithmic Fairness under Partial Observations
Thomas A. Henzinger Konstantin Kueffner Kaushik Mallik
As AI and machine-learned software are used increasingly for making decisions
that affect humans, it is imperative that they remain fair and unbiased in
their decisions. To complement design-time bias mitigation measures, runtime
verification techniques have been introduced recently to monitor the
algorithmic fairness of deployed systems. Previous monitoring techniques assume
full observability of the states of the (unknown) monitored system. Moreover,
they can monitor only fairness properties that are specified as arithmetic
expressions over the probabilities of different events. In this work, we extend
fairness monitoring to systems modeled as partially observed Markov chains
(POMC), and to specifications containing arithmetic expressions over the
expected values of numerical functions on event sequences. The only assumptions
we make are that the underlying POMC is aperiodic and starts in the stationary
distribution, with a bound on its mixing time being known. These assumptions
enable us to estimate a given property for the entire distribution of possible
executions of the monitored POMC, by observing only a single execution. Our
monitors observe a long run of the system and, after each new observation,
output updated PAC-estimates of how fair or biased the system is. The monitors
are computationally lightweight and, using a prototype implementation, we
demonstrate their effectiveness on several real-world examples.