Reproduce “Optimality and Impossibility in Multidimensional Strategyproof Facility Location” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jianan Lin
The authors analyze deterministic strategyproof facility placement. In the Euclidean plane, the coordinate-wise median is optimal for one facility among mechanisms; for three agents, its worst-case ratio is exactly √5/2. In ℓ∞, an anonymous rule achieves ratio one. For two or more facilities, no finite guarantee holds in the plane for 1<p<∞, or in higher dimensions under stated symmetry conditions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.