TY - GEN
T1 - GAEA
T2 - 4th AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society, AIES 2021
AU - Ramachandran, Govardana Sachithanandam
AU - Brugere, Ivan
AU - Varshney, Lav R.
AU - Xiong, Caiming
N1 - Publisher Copyright:
© 2021 ACM.
PY - 2021/7/21
Y1 - 2021/7/21
N2 - Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. For example, urban infrastructure networks may enable certain racial groups to more easily access resources such as high-quality schools, grocery stores, and polling places. Similarly, social networks within universities and organizations may enable certain groups to more easily access people with valuable information or influence. Here we introduce a new class of problems, Graph Augmentation for Equitable Access (GAEA), to enhance equity in networked systems by editing graph edges under budget constraints. We prove such problems are NP-hard, and cannot be approximated within a factor of (1-1/3e). We develop a principled, sample- and time- efficient Markov Reward Process (MRP)-based mechanism design framework for GAEA. Our algorithm outperforms baselines on a diverse set of synthetic graphs. We further demonstrate the method on real-world networks, by merging public census, school, and transportation datasets for the city of Chicago and applying our algorithm to find human-interpretable edits to the bus network that enhance equitable access to high-quality schools across racial groups. Further experiments on Facebook networks of universities yield sets of new social connections that would increase equitable access to certain attributed nodes across gender groups.
AB - Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. For example, urban infrastructure networks may enable certain racial groups to more easily access resources such as high-quality schools, grocery stores, and polling places. Similarly, social networks within universities and organizations may enable certain groups to more easily access people with valuable information or influence. Here we introduce a new class of problems, Graph Augmentation for Equitable Access (GAEA), to enhance equity in networked systems by editing graph edges under budget constraints. We prove such problems are NP-hard, and cannot be approximated within a factor of (1-1/3e). We develop a principled, sample- and time- efficient Markov Reward Process (MRP)-based mechanism design framework for GAEA. Our algorithm outperforms baselines on a diverse set of synthetic graphs. We further demonstrate the method on real-world networks, by merging public census, school, and transportation datasets for the city of Chicago and applying our algorithm to find human-interpretable edits to the bus network that enhance equitable access to high-quality schools across racial groups. Further experiments on Facebook networks of universities yield sets of new social connections that would increase equitable access to certain attributed nodes across gender groups.
KW - dataset
KW - equity
KW - fairness
KW - reinforcement learning
KW - social networks
UR - http://www.scopus.com/inward/record.url?scp=85112421544&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112421544&partnerID=8YFLogxK
U2 - 10.1145/3461702.3462615
DO - 10.1145/3461702.3462615
M3 - Conference contribution
AN - SCOPUS:85112421544
T3 - AIES 2021 - Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society
SP - 884
EP - 894
BT - AIES 2021 - Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society
PB - Association for Computing Machinery
Y2 - 19 May 2021 through 21 May 2021
ER -