Exploring Algorithmic Fairness in Robust Graph Covering Problems
Exploring Algorithmic Fairness in Robust Graph Covering Problems
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Aida Rahmattalabi;P. Vayanos;Anthony Fulginiti;E. Rice;Bryan Wilder;A. Yadav;Milind Tambe
中科院分区：
文献类型：
--
作者：
Aida Rahmattalabi;P. Vayanos;Anthony Fulginiti;E. Rice;Bryan Wilder;A. Yadav;Milind Tambe
在算法进步的推动下，人工智能算法越来越多地被部署在具有复杂社会影响的不可预见挑战的环境中。受人工智能驱动的、基于社交网络的自杀预防和滑坡风险管理干预措施的现实部署的启发，本文重点研究了一个受群体公平约束的鲁棒图覆盖问题。我们发现，在没有公平性约束的情况下，最先进的算法的强大的图覆盖问题的结果有偏见的节点覆盖：他们倾向于歧视个人（节点）的基础上，在传统上边缘化的群体成员。为了解决这个问题，我们提出了一种新的配方的强大的覆盖问题的公平性约束和一个易于处理的近似计划适用于真实的世界的情况。我们提供了一个正式的分析组公平性（PoF）的价格为这个问题，我们表明，不确定性可以导致更大的PoF。我们证明了我们的方法在几个现实世界的社交网络的有效性。我们的方法产生竞争力的节点覆盖率，同时显着提高组公平性相对于国家的最先进的方法。
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.