We consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes -- which is often unrealistic in practice. Instead they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi-armed bandit problem where each arm corresponds to the choice of a data source, coupled with the online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by $\mathcal{O}(\sqrt{T})$. A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions. We also show that in some instances, the estimates used can be learned on the fly.

本文探讨了在不观察个体保护属性的情况下，使用不同质量的数据源估算这些属性以降低公平惩罚的在线分配问题，并提出了一种在多臂赌博问题的框架下同时解决两个问题的算法，该算法可以适应多种不同的公平概念，并且在一些情况下可以学习使用的估计值。

在在线分配中平衡价格与数据质量以实现公平