Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions

Sumit Goel and Wade Hann-Caruthers ()
Additional contact information
Wade Hann-Caruthers: California Institute of Technology

Social Choice and Welfare, 2023, vol. 61, issue 1, No 2, 34 pages

Abstract: Abstract We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in $$\mathbb {R}^2$$ R 2 . We show that for the p-norm ( $$p \ge 1$$ p ≥ 1 ) objective, the coordinate-wise median mechanism (CM) has the lowest worst-case approximation ratio in the class of deterministic, anonymous, and strategyproof mechanisms. For the minisum objective and an odd number of agents n, we show that CM has a worst-case approximation ratio (AR) of $$\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$$ 2 n 2 + 1 n + 1 . For the p-norm social cost objective ( $$p\ge 2$$ p ≥ 2 ), we find that the AR for CM is bounded above by $$2^{\frac{3}{2}-\frac{2}{p}}$$ 2 3 2 - 2 p . We conjecture that the AR of CM actually equals the lower bound $$2^{1-\frac{1}{p}}$$ 2 1 - 1 p (as is the case for $$p=2$$ p = 2 and $$p=\infty$$ p = ∞ ) for any $$p\ge 2$$ p ≥ 2 .

Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00355-022-01435-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sochwe:v:61:y:2023:i:1:d:10.1007_s00355-022-01435-1

Ordering information: This journal article can be ordered from
http://www.springer. ... c+theory/journal/355

DOI: 10.1007/s00355-022-01435-1

Access Statistics for this article

Social Choice and Welfare is currently edited by Bhaskar Dutta, Marc Fleurbaey, Elizabeth Maggie Penn and Clemens Puppe

More articles in Social Choice and Welfare from Springer, The Society for Social Choice and Welfare Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().