Unbiased Sequential Prediction for Fairness in Predictions-to-Decisions Pipelines

We develop an efficient sequential (online adversarial) algorithm for making high-dimensional vector predictions --- to be fed into a downstream decision maker --- such that these predictions are fair in various senses with respect to the predictions-to-decisions pipeline, and in particular fair conditional on downstream actions taken by the decision maker as a function of these predictions. (1) As a major example, in the online problem where at each round, a subset of k-many candidates is selected by a downstream selection method as a function of our predictions about each of these candidates' success rates, our algorithm can give predictions that are fair to each candidate, in the sense that the candidate's average predicted probability is unbiased relative to the true empirical average, both \emph{over those days when the candidate was selected} and also \emph{over days when the candidate wasn't selected}. Thus, e.g., each candidate can be assured that their probability of success is not systematically underestimated whenever they aren't picked, and conversely, that no other candidate's chances of success are systematically overestimated when they are picked.(2) Via another instantiation of our prediction algorithm, we improve on the online multigroup fairness result of Blum and Lykouris (2020), who produce predictions with no \emph{external} regret conditional on all demographic groups of interest. We directly improve on this by providing the much stronger no \emph{swap} regret guarantees for each group.(3) Our efficient algorithm, in its general form, can make unbiased predictions conditional on any polynomially many subsequences of rounds, which can be functions of our predictions themselves. This is classically achievable via (full) online calibration (Foster and Vohra, 1998), which is however inefficient and statistically suboptimal in high dimensions. Our algorithm is thus a novel computationally and statistically efficient relaxation of calibration.