Which $L_p$ norm is the fairest? Approximations for fair facility location across all '$p$'
| Autor: | Gupta, Swati, Moondra, Jai, Singh, Mohit |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Fair facility location problems try to balance access costs to open facilities borne by different groups of people by minimizing the $L_p$ norm of these group distances. However, there is no clear choice of "$p$" in the current literature. We present a novel approach to address the challenge of choosing the right notion of fairness. We introduce the concept of portfolios, a set of solutions that contains an approximately optimal solution for each objective in a given class of objectives, such as $L_p$ norms. This concept opens up new possibilities for getting around the "right" notion of fairness for many problems. For $r$ client groups, we demonstrate portfolios of size $\Theta(\log r)$ for the facility location and $k$-clustering problems, with an $O(1)$-approximate solution for each $L_p$ norm. Further, motivated by the Justice40 Initiative that provides rolling budget investments, we impose a refinement-like structure on the portfolio. We develop novel approximation algorithms for these structured portfolios and show experimental evidence of their performance in two US counties. We also present a planning tool that provides potential ways to expand access to US healthcare facilities, which might be of independent interest to policymakers. Comment: A preliminary version of this article appeared as a one-page extended abstract in the proceedings of Economics and Computation (EC) 2023 conference |
| Databáze: | arXiv |
| Externí odkaz: |
|