The oracle (or reductions) approach to fair machine learning reduces the fairness problem into a standard optimization problem.
Assume we have a black-box subroutine that can learn with minimum empirical error, . We can then introduce some fairness constraints
where and are two subgroups, and we restrict the difference in errors between the two subgroups to be within a certain threshold. Introducing variables for weights in with these constraints gives us a linear program,
We can solve this by alternating in a two-player game:
First, the learner picks the best .
Next, a regulator picks a pair of groups and where the constraint is most violated. (More generally, gives a distribution over all possible pairs.)
We calculate payoff for the regulator as
The payoff for the learner is just the negative of the above.
Our final result, after steps, is the mixture model formed from all intermediate models,
Let denote the set of all mixtures models formed by models in . In terms of game theory, the learner is playing a mixed strategy and the regulator plays a mixed strategy over fairness constraints. Our payoff creates a zero-sum game, and the Nash equilibrium is the constrained optimization solution.
It can be shown that if best responds to and updates using no-regret, this method will converge to a -optimal solution—our final error is within of the optimal solution and we violate constraints by .