English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we initiate the study of the $m$-Capacitated Facility LocationProblem ($m$-CFLP) within a Bayesian Mechanism Design framework. We considerthe case in which every agent's private information is their position on a lineand assume that every agent's position is independently drawn from a common andknown distribution $\mu$. In this context, we propose the Extended RankingMechanisms (ERMs), a truthful generalization of the recently introduced RankingMechanisms, that allows to handle problems where the total facility capacityexceeds the number of agents. Our primary results pertain to the study of theefficiency guarantees of the ERMs. In particular, we demonstrate that the limitof the ratio between the expected Social Cost of an ERM and the expectedoptimal Social Cost is finite. En route to these results, we reveal that theoptimal Social Cost and the Social Cost of any ERMs can be expressed as theobjective value of a suitable norm minimization problem in the Wassersteinspace. We then tackle the problem of determining an optimal ERM tailored to a$m$-CFLP and a distribution $\mu$. Specifically, we aim to identify an ERMwhose limit Bayesian approximation ratio is the lowest compared to all otherERMs. We detail how to retrieve an optimal ERM in two frameworks: (i) when thetotal facility capacity matches the number of agents and (ii) when $\mu$ is theuniform distribution and we have two facilities to place. Lastly, we conductextensive numerical experiments to compare the performance of the ERMs againstother truthful mechanisms and to evaluate the convergence speed of the Bayesianapproximation ratio. In summary, all our findings highlight that a well-tunedERM consistently outperforms all other known mechanisms, making it a validchoice for solving the $m$-CFLP within a Bayesian framework.

Extended Ranking Mechanisms for the m-Capacitated Facility Location Problem in Bayesian Mechanism Design