Online Selection with Cardinality Constraints under Bias

ACO Student Seminar
Friday, September 11, 2020 - 1:00pm for 1 hour (actually 50 minutes)
Jad Salem – Math, Georgia Tech – jsalem7@gatech.edu
He Guo

Optimization and machine learning algorithms often use real-world data that has been generated through complex socio-economic and behavioral processes. This data, however, is noisy, and naturally encodes difficult-to-quantify systemic biases. In this work, we model and address bias in the secretary problem, which has applications in hiring. We assume that utilities of candidates are scaled by unknown bias factors, perhaps depending on demographic information, and show that bias-agnostic algorithms are suboptimal in terms of utility and fairness. We propose bias-aware algorithms that achieve certain notions of fairness, while achieving order-optimal competitive ratios in several settings.