Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in $L_p$ Space

Jianan Lin

We consider the problem of locating a single facility for 2 agents in $L_p$ space ($12$ and prove that the well-known general median mechanism will give an counter-example. Particularly, in $L_2$ (i.e., Euclidean) space with 2 agents, such a mechanism is rotation-invariant iff it is dictatorial; and such a mechanism is anonymous iff it is one of the three mechanisms in Section 4. And our tool implies that any such a mechanism has a tight lower bound of 2-approximation for maximum cost in any multi-dimensional space.

Knowledge Graph



Sign up or login to leave a comment