English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the problem of locating a single facility for 2 agents in $L_p$space ($1<p<\infty$) and give a nearly complete characterization of suchdeterministic strategyproof mechanisms. We use the distance between an agentand the facility in $L_p$ space to denote the cost of the agent. A mechanism isstrategyproof iff no agent can reduce her cost from misreporting her privatelocation. We show that in $L_p$ space ($1<p<\infty$) with 2 agents, anylocation output of a deterministic, unanimous, translation-invariantstrategyproof mechanism must satisfy a set of equations and mechanisms arecontinuous, scalable. In one-dimensional space, the output must be one agent'slocation, which is easy to prove in any $n$ agents. However, in $m$-dimensionalspace ($m\ge 2$), the situation will be much more complex, with only 2-agentcase finished. We show that the output of such a mechanism must satisfy a setof equations, and when $p=2$ the output must locate at a sphere with thesegment between the two agents as the diameter. Further more, for $n$-agentsituations, we find that the simple extension of this the 2-agent situationcannot hold when dimension $m>2$ and prove that the well-known general medianmechanism will give an counter-example. Particularly, in $L_2$ (i.e.,Euclidean) space with 2 agents, such a mechanism is rotation-invariant iff itis dictatorial; and such a mechanism is anonymous iff it is one of the threemechanisms in Section 4. And our tool implies that any such a mechanism has atight lower bound of 2-approximation for maximum cost in any multi-dimensionalspace.

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