Approximation-Variance Tradeoffs in Facility Location Games

Authors

  • Ariel Procaccia Carnegie Mellon University
  • David Wajc Carnegie Mellon University
  • Hanrui Zhang Duke University

Keywords:

Mechanism Design, Approximation, Variance, Tradeoff, Facility Location Games

Abstract

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.

Downloads

Published

2018-04-25

How to Cite

Procaccia, A., Wajc, D., & Zhang, H. (2018). Approximation-Variance Tradeoffs in Facility Location Games. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11451

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms