We focus on the problem of placing two facilities along a linear space to serve a group of agents. Each agent is committed to minimizing the distance between her location and the closest facility. A mechanism is an algorithm that maps the reported agent locations to the facility locations. We are interested in mechanisms without money that are deterministic, strategy-proof, and provide a bounded approximation ratio for social cost. It is a fundamental problem to characterize the family of strategy-proof mechanisms with a bounded approximation ratio. Fotakis and Tzamos already demonstrated that the deterministic strategy-proof mechanisms for the 2-facility game problem are either dictatorial mechanisms or the leftmost-rightmost mechanism. In this paper, we first present a more refined characterization of the first family. We then reveal three new classes of strategy-proof mechanisms that show the intricacy of structure within this family. Besides, based on our refined characterization, we surprisingly find that prediction cannot effectively improve the performance of the mechanism in the two-facility game problem, while this methodology to overcome bad approximation ratio works in many other mechanism design problems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Design and Characterization of Strategy-Proof Mechanisms for Two-Facility Game on a Line

  • Pinyan Lu,
  • Zihan Luo,
  • Jialin Zhang

摘要

We focus on the problem of placing two facilities along a linear space to serve a group of agents. Each agent is committed to minimizing the distance between her location and the closest facility. A mechanism is an algorithm that maps the reported agent locations to the facility locations. We are interested in mechanisms without money that are deterministic, strategy-proof, and provide a bounded approximation ratio for social cost. It is a fundamental problem to characterize the family of strategy-proof mechanisms with a bounded approximation ratio. Fotakis and Tzamos already demonstrated that the deterministic strategy-proof mechanisms for the 2-facility game problem are either dictatorial mechanisms or the leftmost-rightmost mechanism. In this paper, we first present a more refined characterization of the first family. We then reveal three new classes of strategy-proof mechanisms that show the intricacy of structure within this family. Besides, based on our refined characterization, we surprisingly find that prediction cannot effectively improve the performance of the mechanism in the two-facility game problem, while this methodology to overcome bad approximation ratio works in many other mechanism design problems.