TY - JOUR
AU - Procaccia, Ariel
AU - Wajc, David
AU - Zhang, Hanrui
PY - 2018/04/25
Y2 - 2023/11/29
TI - Approximation-Variance Tradeoffs in Facility Location Games
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v32i1.11451
UR - https://ojs.aaai.org/index.php/AAAI/article/view/11451
SP -
AB - <p> We revisit the well-studied problem of constructing strategyproof approximation mechanisms for facility location games, but offer a fundamentally new perspective by considering risk averse designers. Specifically, we are interested in the tradeoff between a randomized strategyproof mechanism's approximation ratio, and its variance (which has long served as a proxy for risk). When there is just one facility, we observe that the social cost objective is trivial, and derive the optimal tradeoff with respect to the maximum cost objective. When there are multiple facilities, the main challenge is the social cost objective, and we establish a surprising impossibility result: under mild assumptions, no smooth approximation-variance tradeoff exists. We also discuss the implications of our work for computational mechanism design at large. </p>
ER -