The k-Facility Location Problem Via Optimal Transport: A Bayesian Study of the Percentile Mechanisms
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929414402473984 |
|---|---|
| author | Auricchio, Gennaro Zhang, Jie |
| author_facet | Auricchio, Gennaro Zhang, Jie |
| contents | In this paper, we investigate the $k$-Facility Location Problem ($k$-FLP) within the Bayesian Mechanism Design framework, in which agents' preferences are samples of a probability distributed on a line. Our primary contribution is characterising the asymptotic behavior of percentile mechanisms, which varies according to the distribution governing the agents' types. To achieve this, we connect the $k$-FLP and projection problems in the Wasserstein space. Owing to this relation, we show that the ratio between the expected cost of a percentile mechanism and the expected optimal cost is asymptotically bounded. Furthermore, we characterize the limit of this ratio and analyze its convergence speed. Our asymptotic study is complemented by deriving an upper bound on the Bayesian approximation ratio, applicable when the number of agents $n$ exceeds the number of facilities $k$. We also characterize the optimal percentile mechanism for a given agent's distribution through a system of $k$ equations. Finally, we estimate the optimality loss incurred when the optimal percentile mechanism is derived using an approximation of the agents' distribution rather than the actual distribution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06398 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The k-Facility Location Problem Via Optimal Transport: A Bayesian Study of the Percentile Mechanisms Auricchio, Gennaro Zhang, Jie Computer Science and Game Theory 91B03 49Q22 In this paper, we investigate the $k$-Facility Location Problem ($k$-FLP) within the Bayesian Mechanism Design framework, in which agents' preferences are samples of a probability distributed on a line. Our primary contribution is characterising the asymptotic behavior of percentile mechanisms, which varies according to the distribution governing the agents' types. To achieve this, we connect the $k$-FLP and projection problems in the Wasserstein space. Owing to this relation, we show that the ratio between the expected cost of a percentile mechanism and the expected optimal cost is asymptotically bounded. Furthermore, we characterize the limit of this ratio and analyze its convergence speed. Our asymptotic study is complemented by deriving an upper bound on the Bayesian approximation ratio, applicable when the number of agents $n$ exceeds the number of facilities $k$. We also characterize the optimal percentile mechanism for a given agent's distribution through a system of $k$ equations. Finally, we estimate the optimality loss incurred when the optimal percentile mechanism is derived using an approximation of the agents' distribution rather than the actual distribution. |
| title | The k-Facility Location Problem Via Optimal Transport: A Bayesian Study of the Percentile Mechanisms |
| topic | Computer Science and Game Theory 91B03 49Q22 |
| url | https://arxiv.org/abs/2407.06398 |