Timezone: »

Exploring Algorithmic Fairness in Robust Graph Covering Problems
Aida Rahmattalabi · Phebe Vayanos · Anthony Fulginiti · Eric Rice · Bryan Wilder · Amulya Yadav · Milind Tambe

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #109

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 a robust graph covering problem 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 remediate this issue, we propose a novel formulation of the robust covering problem with 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.

Author Information

Aida Rahmattalabi (University of Southern California)
Phebe Vayanos (University of Southern California)
Anthony Fulginiti (University of Denver)
Eric Rice (University of Southern California)
Bryan Wilder
Amulya Yadav (Pennsylvania State University)
Milind Tambe (USC)

More from the Same Authors