Mitigating Bias via Algorithms with Fairness Guarantees

Abstract

The rapid integration of automated decision-making systems in critical domains such as resume screening, loan approval, content recommendation, and disaster containment has raised significant concerns regarding biases in these systems. This research investigates both theoretical and practical aspects of fairness in machine learning models, proposing novel fairness definitions and algorithmic frameworks that mitigate bias while maintaining performance.

Ranking systems shape decision-making across various fields but often introduce biases disproportionately affecting underrepresented groups. In applications like resume screening, ensuring fair representation in expectation is insufficient or even unlawful. We propose a novel randomized ranking algorithm that produces group-fair rankings by sampling from a probability distribution satisfying the natural fair ranking axioms we define. We further show that our sampler enables in-processing for ex-post fairness in learning-to-rank systems. Experiments on real-world datasets, such as credit risk assessments and student admissions, demonstrate that our approach effectively balances fairness and accuracy.

Ensuring fairness requires addressing group fairness (equitable treatment across demographic groups) and individual fairness (similar treatment for similar individuals). Given group fairness constraints in ranking, we first define underranking—a phenomenon where meritorious individuals are systematically pushed down in rankings to satisfy the group fairness constraints. We prove a theoretical lower bound on underranking and propose an efficient post-processing algorithm with simultaneous group fairness and underranking guarantees comparable to the lower bound. We also give an efficient algorithm that samples rankings from a distribution over group-fair rankings that also satisfies probabilistic individual fairness. Empirical results show that our algorithm achieves both fairness notions while outperforming state-of-the-art baselines. Extending beyond ranking, we propose a novel algorithm for fairness in graph min-cut problems, with theoretical and experimental validation.

Beyond traditional fairness constraints, we explore error-based fairness, ensuring that different groups incur a fair error distribution. Inspired by socially-fair clustering (Ghadiri et al., 2021; Abbasi et al., 2021), we develop approximation algorithms for socially-fair (k,z) clustering (including k-median, k-means, and socially-fair linear subspace clustering) using strong coresets. Experimental evaluations validate their effectiveness in mitigating bias. In ranking, we introduce a cascaded-norm objective function for fair error measurement in settings where the ranker learns from noisy pairwise preferences. We establish theoretical lower bounds for both group-blind and group-aware fair ranking algorithms, showing that our group-blind algorithm nearly matches the sample complexity lower bound. In contrast, our group-aware approach achieves better sample complexity in real-world experiments.