Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in $L_p$ Space
- Resource Type
- Working Paper
- Source
- Subject
Computer Science - Computer Science and Game Theory - Language
2$ 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.
Comment: This paper is accepted by COCOA 2020