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

2020/11/26 by Jianan Lin, Lin, Jianan · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2011.13133

openalex publication_date 2020/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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₂ (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.

Cited by

• Obnoxious Facility Location Problems: Strategyproof Mechanisms Optimizing L_p-Aggregated Utilities and Costs
• Strategyproof Mechanisms for Facility Location with Prediction Under the Maximum Cost Objective

Related

• Design and Characterization of Strategy-Proof Mechanisms for Two-Facility Game on a Line
• On the Power of Deterministic Mechanisms for Facility Location Games
• Constant-Approximate and Constant-Strategyproof Two-Facility Location
• Strategy Proof Mechanisms for Facility Location in Euclidean and\n Manhattan Space
• Improved Lower Bounds and Output Augmentation for Facility Location Mechanisms