Proportional Fairness in Obnoxious Facility Location
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913572902141952 |
|---|---|
| author | Lam, Alexander Aziz, Haris Li, Bo Ramezani, Fahimeh Walsh, Toby |
| author_facet | Lam, Alexander Aziz, Haris Li, Bo Ramezani, Fahimeh Walsh, Toby |
| contents | We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight $ε$-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_04340 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Proportional Fairness in Obnoxious Facility Location Lam, Alexander Aziz, Haris Li, Bo Ramezani, Fahimeh Walsh, Toby Computer Science and Game Theory Artificial Intelligence Multiagent Systems Theoretical Economics We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight $ε$-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model. |
| title | Proportional Fairness in Obnoxious Facility Location |
| topic | Computer Science and Game Theory Artificial Intelligence Multiagent Systems Theoretical Economics |
| url | https://arxiv.org/abs/2301.04340 |