  We present a new data-driven model of fairness that, unlike existing static
definitions of individual or group fairness is guided by the unfairness
complaints received by the system. Our model supports multiple fairness
criteria and takes into account their potential incompatibilities. We consider
both a stochastic and an adversarial setting of our model. In the stochastic
setting, we show that our framework can be naturally cast as a Markov Decision
Process with stochastic losses, for which we give efficient vanishing regret
algorithmic solutions. In the adversarial setting, we design efficient
algorithms with competitive ratio guarantees. We also report the results of
experiments with our algorithms and the stochastic framework on artificial
datasets, to demonstrate their effectiveness empirically.
