Learning-Augmented Facility Location Mechanisms for Envy Ratio

HARIS AZIZ, Yuhang Guo, Alexander Lam, Houyu Zhou

Advances in Neural Information Processing Systems 38 (NeurIPS 2025) Main Conference Track

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 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 a mechanism which utilizes predictions to achieve $\alpha$-consistency and $\frac{\alpha}{\alpha - 1}$-robustness for a selected parameter $\alpha \in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [2020], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to $1.8944$. Building upon these advancements, we construct a novel randomized mechanism which incorporates predictions to achieve improved performance guarantees.