Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
Tomer Ezra, Michal Feldman, Zhihao Gavin Tang · 2024
In Bayesian online settings, every element is associated with a value drawn from a known underlying distribution. This distribution, representing the population from which the element is drawn, is referred to as the element's identity. The elements arrive sequentially, with their values being revealed in an online manner. Most previous work has assumed that, upon the arrival of a new element, the online algorithm observes its value and its identity. However, practical scenarios frequently require algorithms to make decisions based solely on the element's value, disregarding its identity. This necessity emerges either from the algorithm's lack of knowledge about the element's identity or in the pursuit of fairness, aiming for bias-free decisions across varying identities. We call such algorithms identity-blind algorithms, and propose the identity-blindness gap as a metric to evaluate the performance loss in online algorithms caused by identity-blindness. This gap is defined as the maximum ratio between the expected performance of an identity-blind online algorithm and an optimal online algorithm that knows the arrival order, thus also the identities.