Bayesian Strategy-Proof Facility Location via Robust Estimation
Emmanouil Zampetakis, Fred Zhang
Abstract
A seminal work by Moulin (1980) shows that the median voting scheme fully characterizes (deterministic) strategy-proof facility location mechanism for single-peaked preferences. In this simple setting, median also achieves the optimal social cost. In $d$ dimensions, strategy-proof mechanism is characterized by coordinate-wise median, which is known to have a large $\sqrt{d}$ approximation ratio of the social cost in the Euclidean space, whereas the socially optimal mechanism fails at being strategy-proof. In light of the negative results in the classic, worst-case setting, we initiate the study of Bayesian mechanism design for strategy-proof facility location for multi-dimensional Euclidean preferences, where the agents’ preferences are drawn from a distribution. We approach the problem via connections to algorithmic high-dimensional robust statistics. Specially, our contributions are the following: * We provide a general reduction from any robust estimation scheme to Bayesian approximately strategy-proof mechanism. This leads to new strategy-proof mechanisms for Gaussian and bounded moment distributions, by leveraging recent advances in robust statistics. * We show that the Lugosi-Mendelson median arising from heavy-tailed statistics can be used to obtain Bayesian approximately strategy-proof single-facility mechanism with asymptotically optimal social cost, under mild distributional assumptions. * We provide Bayesian approximately strategy-proof multi-facility mechanisms for Gaussian mixture distributions with nearly optimal social cost.
BibTeX
@InProceedings{pmlr-v206-zampetakis23a,
title = {Bayesian Strategy-Proof Facility Location via Robust Estimation},
author = {Zampetakis, Emmanouil and Zhang, Fred},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {4196--4208},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/zampetakis23a/zampetakis23a.pdf},
url = {https://proceedings.mlr.press/v206/zampetakis23a.html},
abstract = {A seminal work by Moulin (1980) shows that the median voting scheme fully characterizes (deterministic) strategy-proof facility location mechanism for single-peaked preferences. In this simple setting, median also achieves the optimal social cost. In $d$ dimensions, strategy-proof mechanism is characterized by coordinate-wise median, which is known to have a large $\sqrt{d}$ approximation ratio of the social cost in the Euclidean space, whereas the socially optimal mechanism fails at being strategy-proof. In light of the negative results in the classic, worst-case setting, we initiate the study of Bayesian mechanism design for strategy-proof facility location for multi-dimensional Euclidean preferences, where the agents’ preferences are drawn from a distribution. We approach the problem via connections to algorithmic high-dimensional robust statistics. Specially, our contributions are the following: * We provide a general reduction from any robust estimation scheme to Bayesian approximately strategy-proof mechanism. This leads to new strategy-proof mechanisms for Gaussian and bounded moment distributions, by leveraging recent advances in robust statistics. * We show that the Lugosi-Mendelson median arising from heavy-tailed statistics can be used to obtain Bayesian approximately strategy-proof single-facility mechanism with asymptotically optimal social cost, under mild distributional assumptions. * We provide Bayesian approximately strategy-proof multi-facility mechanisms for Gaussian mixture distributions with nearly optimal social cost.}
}