## Abstract

In this paper, we initiate the study of the m-Capacitated Facility Location Problem (m-CFLP) within a Bayesian Mechanism Design framework. We consider the case in which every agent's private information is their position on a line and assume that every agent's position is independently drawn from a common and known distribution μ. In this context, we propose the Extended Ranking Mechanisms (ERMs), a truthful generalization of the recently introduced Ranking Mechanisms, that allows to handle problems where the total facility capacity exceeds the number of agents. Our primary results pertain to the study of the efficiency guarantees of the ERMs. In particular, we demonstrate that the limit of the ratio between the expected Social Cost of an ERM and the expected optimal Social Cost is finite. En route to these results, we reveal that the optimal Social Cost and the Social Cost of any ERMs can be expressed as the objective value of a suitable norm minimization problem in the Wasserstein space. We then tackle the problem of determining an optimal ERM tailored to a m-CFLP and a distribution μ. Specifically, we aim to identify an ERM whose limit Bayesian approximation ratio is the lowest compared to all other ERMs. We detail how to retrieve an optimal ERM in two frameworks: (i) when the total facility capacity matches the number of agents and (ii) when μ is the uniform distribution and we have two facilities to place. Lastly, we conduct extensive numerical experiments to compare the performance of the ERMs against other truthful mechanisms and to evaluate the convergence speed of the Bayesian approximation ratio. In summary, all our findings highlight that a well-tuned ERM consistently outperforms all other known mechanisms, making it a valid choice for solving the m-CFLP within a Bayesian framework.

Original language | English |
---|---|

Pages (from-to) | 87-95 |

Number of pages | 9 |

Journal | Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS |

Volume | 2024-May |

Publication status | Published - 10 May 2024 |

Event | 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024 - Auckland, New Zealand Duration: 6 May 2024 → 10 May 2024 |

### Funding

Gennaro Auricchio and Jie Zhang are partially supported by a Leverhulme Trust Research Project Grant (2021-2024). Jie Zhang is also supported by the EPSRC grant (EP/W014912/1). Mengxiao Zhang is supported by EPSRC Grant (EP/X01357X/1).

Funders | Funder number |
---|---|

Leverhulme Trust | 2021-2024 |

Engineering and Physical Sciences Research Council | EP/W014912/1, EP/X01357X/1 |

## Keywords

- Bayesian Mechanism Design
- Capacitated Facility Location Problem
- Optimal Transport

## ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Control and Systems Engineering