Exploring Algorithmic Fairness in Robust Graph Covering Problems

arXiv2006.06865MaRDI QIDQ6342714

Author name not available (Why is that?)

Publication date: 11 June 2020

Abstract: Fueled by algorithmic advances, AI algorithms are increasingly being deployed in settings subject to unanticipated challenges with complex social effects. Motivated by real-world deployment of AI driven, social-network based suicide prevention and landslide risk management interventions, this paper focuses on robust graph covering problems subject to group fairness constraints. We show that, in the absence of fairness constraints, state-of-the-art algorithms for the robust graph covering problem result in biased node coverage: they tend to discriminate individuals (nodes) based on membership in traditionally marginalized groups. To mitigate this issue, we propose a novel formulation of the robust graph covering problem with group fairness constraints and a tractable approximation scheme applicable to real-world instances. We provide a formal analysis of the price of group fairness (PoF) for this problem, where we show that uncertainty can lead to greater PoF. We demonstrate the effectiveness of our approach on several real-world social networks. Our method yields competitive node coverage while significantly improving group fairness relative to state-of-the-art methods.

Has companion code repository: https://github.com/Aida-Rahmattalabi/Fair-and-Robust-Graph-Covering-Problem

This page was built for publication: Exploring Algorithmic Fairness in Robust Graph Covering Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342714)