{"ID":2829651,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.11193","arxiv_id":"2512.11193","title":"Learning-Augmented Facility Location Mechanisms for Envy Ratio","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.11193","url_pdf":"https://arxiv.org/pdf/2512.11193v2","authors":"[\"Haris Aziz\",\"Yuhang Guo\",\"Alexander Lam\",\"Houyu Zhou\"]","published":"2025-12-12T00:45:00Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}