On the Capacitated Facility Location Problem with Scarce Resources

Gennaro Auricchio, Harry J. Clough, Jie Zhang
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:186-202, 2024.

Abstract

This paper investigates the Mechanism Design aspects of the $m$-Capacitated Facility Location Problem where the total facility capacity is lower than the number of agents. Following \cite{aziz2020capacity}, the Social Welfare of the facility location is determined through a First-Come-First-Served (FCFS) game where agents compete after the facility positions are established. When the number of facilities is $m>1$, the Nash Equilibrium (NE) of the FCFS game is not unique, thus the utility of the agents and the notion of truthfulness are not well-defined. To address these issues, we consider absolutely truthful mechanisms, i.e. mechanisms able to prevent agents from misreporting regardless of the strategies played during the FCFS game. We pair this more stringent truthfulness requirement with the notion of Equilibrium Stable (ES) mechanism, i.e. mechanisms whose Social Welfare does not depend on the NE of the FCFS game. We show that the class of percentile mechanisms is absolutely truthful and characterize under which conditions they are ES. We then show that the approximation ratio of each ES percentile mechanism is bounded and determine its value. Notably, when all the facilities have the same capacity and the number of agents is large enough, it is possible to achieve an approximation ratio smaller than $1+\frac{1}{2m-1}$. We enhance our findings by empirically evaluating the mechanisms’ performances when agents’ true positions follows a distribution.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-auricchio24a, title = {On the Capacitated Facility Location Problem with Scarce Resources}, author = {Auricchio, Gennaro and Clough, Harry J. and Zhang, Jie}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {186--202}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/auricchio24a/auricchio24a.pdf}, url = {https://proceedings.mlr.press/v244/auricchio24a.html}, abstract = {This paper investigates the Mechanism Design aspects of the $m$-Capacitated Facility Location Problem where the total facility capacity is lower than the number of agents. Following \cite{aziz2020capacity}, the Social Welfare of the facility location is determined through a First-Come-First-Served (FCFS) game where agents compete after the facility positions are established. When the number of facilities is $m>1$, the Nash Equilibrium (NE) of the FCFS game is not unique, thus the utility of the agents and the notion of truthfulness are not well-defined. To address these issues, we consider absolutely truthful mechanisms, i.e. mechanisms able to prevent agents from misreporting regardless of the strategies played during the FCFS game. We pair this more stringent truthfulness requirement with the notion of Equilibrium Stable (ES) mechanism, i.e. mechanisms whose Social Welfare does not depend on the NE of the FCFS game. We show that the class of percentile mechanisms is absolutely truthful and characterize under which conditions they are ES. We then show that the approximation ratio of each ES percentile mechanism is bounded and determine its value. Notably, when all the facilities have the same capacity and the number of agents is large enough, it is possible to achieve an approximation ratio smaller than $1+\frac{1}{2m-1}$. We enhance our findings by empirically evaluating the mechanisms’ performances when agents’ true positions follows a distribution.} }
Endnote
%0 Conference Paper %T On the Capacitated Facility Location Problem with Scarce Resources %A Gennaro Auricchio %A Harry J. Clough %A Jie Zhang %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-auricchio24a %I PMLR %P 186--202 %U https://proceedings.mlr.press/v244/auricchio24a.html %V 244 %X This paper investigates the Mechanism Design aspects of the $m$-Capacitated Facility Location Problem where the total facility capacity is lower than the number of agents. Following \cite{aziz2020capacity}, the Social Welfare of the facility location is determined through a First-Come-First-Served (FCFS) game where agents compete after the facility positions are established. When the number of facilities is $m>1$, the Nash Equilibrium (NE) of the FCFS game is not unique, thus the utility of the agents and the notion of truthfulness are not well-defined. To address these issues, we consider absolutely truthful mechanisms, i.e. mechanisms able to prevent agents from misreporting regardless of the strategies played during the FCFS game. We pair this more stringent truthfulness requirement with the notion of Equilibrium Stable (ES) mechanism, i.e. mechanisms whose Social Welfare does not depend on the NE of the FCFS game. We show that the class of percentile mechanisms is absolutely truthful and characterize under which conditions they are ES. We then show that the approximation ratio of each ES percentile mechanism is bounded and determine its value. Notably, when all the facilities have the same capacity and the number of agents is large enough, it is possible to achieve an approximation ratio smaller than $1+\frac{1}{2m-1}$. We enhance our findings by empirically evaluating the mechanisms’ performances when agents’ true positions follows a distribution.
APA
Auricchio, G., Clough, H.J. & Zhang, J.. (2024). On the Capacitated Facility Location Problem with Scarce Resources. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:186-202 Available from https://proceedings.mlr.press/v244/auricchio24a.html.

Related Material