  Fairness of machine learning algorithms has been of increasing interest. In
order to suppress or eliminate discrimination in prediction, various notions as
well as approaches have been proposed to impose fairness. Given a notion of
fairness, an essential problem is then whether or not it can always be
attained, even if with an unlimited amount of data. This issue is, however, not
well addressed yet. In this paper, focusing on the Equalized Odds notion of
fairness, we consider the attainability of this criterion and, furthermore, if
it is attainable, the optimality of the prediction performance under various
settings. In particular, for prediction performed by a deterministic function
of input features, we give conditions under which Equalized Odds can hold true;
if the stochastic prediction is acceptable, we show that under mild
assumptions, fair predictors can always be derived. For classification, we
further prove that compared to enforcing fairness by post-processing, one can
always benefit from exploiting all available features during training and get
potentially better prediction performance while remaining fair. Moreover, while
stochastic prediction can attain Equalized Odds with theoretical guarantees, we
also discuss its limitation and potential negative social impacts.
