Learning-Augmented Facility Location Mechanisms for Envy Ratio
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911420273131520 |
|---|---|
| author | Aziz, Haris Guo, Yuhang Lam, Alexander Zhou, Houyu |
| author_facet | Aziz, Haris Guo, Yuhang Lam, Alexander Zhou, Houyu |
| contents | The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus on utilitarian and egalitarian objectives, we design learning-augmented facility location mechanisms on a line for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose the $α$-Bounding Interval Mechanism ($α$-BIM), which utilizes predictions to achieve $α$-consistency and $\fracα{α- 1}$-robustness for a selected parameter $α\in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [10], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to approximately $1.8944$. Building upon these advancements, we construct a novel randomized mechanism, the Bias-Aware Mechanism (BAM), which incorporates predictions to achieve improved consistency and robustness guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11193 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning-Augmented Facility Location Mechanisms for Envy Ratio Aziz, Haris Guo, Yuhang Lam, Alexander Zhou, Houyu Computer Science and Game Theory The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus on utilitarian and egalitarian objectives, we design learning-augmented facility location mechanisms on a line for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose the $α$-Bounding Interval Mechanism ($α$-BIM), which utilizes predictions to achieve $α$-consistency and $\fracα{α- 1}$-robustness for a selected parameter $α\in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [10], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to approximately $1.8944$. Building upon these advancements, we construct a novel randomized mechanism, the Bias-Aware Mechanism (BAM), which incorporates predictions to achieve improved consistency and robustness guarantees. |
| title | Learning-Augmented Facility Location Mechanisms for Envy Ratio |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2512.11193 |