Compatibility of Fairness and Nash Welfare under Subadditive Valuations
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918189388005376 |
|---|---|
| author | Barman, Siddharth Suzuki, Mashbat |
| author_facet | Barman, Siddharth Suzuki, Mashbat |
| contents | We establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We prove that, for subadditive valuations, there always exists a partial allocation that is envy-free up to the removal of any good (EFx) and has NSW at least half of the optimal; here, optimality is considered across all allocations, fair or otherwise. We also prove, for subadditive valuations, the universal existence of complete allocations that are envy-free up to one good (EF1) and also achieve a factor $1/2$ approximation to the optimal NSW. Our EF1 result resolves an open question posed by Garg, Husic, Li, Végh, and Vondrák (STOC 2023).
In addition, we develop a polynomial-time algorithm which, given an arbitrary allocation $\widetilde{A}$ as input, returns an EF1 allocation with NSW at least $\frac{1}{e^{2/e}}\approx \frac{1}{2.08}$ times that of $\widetilde{A}$. Therefore, our results imply that the EF1 criterion can be attained simultaneously with a constant-factor approximation to optimal NSW in polynomial time (with demand queries), for subadditive valuations. The previously best-known approximation factor for optimal NSW, under EF1 and among $n$ agents, was $O(n)$ -- we improve this bound to $O(1)$.
It is known that EF1 and exact Pareto efficiency (PO) are incompatible with subadditive valuations. Complementary to this negative result, the current work shows that we regain compatibility by just considering a factor $1/2$ approximation: EF1 can be achieved in conjunction with $\frac{1}{2}$-PO under subadditive valuations. As such, our results serve as a general tool that can be used as a black box to convert any efficient outcome into a fair one, with only a marginal decrease in efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12461 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Compatibility of Fairness and Nash Welfare under Subadditive Valuations Barman, Siddharth Suzuki, Mashbat Computer Science and Game Theory We establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We prove that, for subadditive valuations, there always exists a partial allocation that is envy-free up to the removal of any good (EFx) and has NSW at least half of the optimal; here, optimality is considered across all allocations, fair or otherwise. We also prove, for subadditive valuations, the universal existence of complete allocations that are envy-free up to one good (EF1) and also achieve a factor $1/2$ approximation to the optimal NSW. Our EF1 result resolves an open question posed by Garg, Husic, Li, Végh, and Vondrák (STOC 2023). In addition, we develop a polynomial-time algorithm which, given an arbitrary allocation $\widetilde{A}$ as input, returns an EF1 allocation with NSW at least $\frac{1}{e^{2/e}}\approx \frac{1}{2.08}$ times that of $\widetilde{A}$. Therefore, our results imply that the EF1 criterion can be attained simultaneously with a constant-factor approximation to optimal NSW in polynomial time (with demand queries), for subadditive valuations. The previously best-known approximation factor for optimal NSW, under EF1 and among $n$ agents, was $O(n)$ -- we improve this bound to $O(1)$. It is known that EF1 and exact Pareto efficiency (PO) are incompatible with subadditive valuations. Complementary to this negative result, the current work shows that we regain compatibility by just considering a factor $1/2$ approximation: EF1 can be achieved in conjunction with $\frac{1}{2}$-PO under subadditive valuations. As such, our results serve as a general tool that can be used as a black box to convert any efficient outcome into a fair one, with only a marginal decrease in efficiency. |
| title | Compatibility of Fairness and Nash Welfare under Subadditive Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.12461 |