Top

Social Choice and Welfare

Published in:

25-10-2022 | Original Paper

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

Authors: Sumit Goel, Wade Hann-Caruthers

Published in: Social Choice and Welfare | Issue 1/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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$. We show that for the p-norm ($p \ge 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}$. For the p-norm social cost objective ($p\ge 2$), we find that the AR for CM is bounded above by $2^{\frac{3}{2}-\frac{2}{p}}$. We conjecture that the AR of CM actually equals the lower bound $2^{1-\frac{1}{p}}$ (as is the case for $p=2$ and $p=\infty$) for any $p\ge 2$.

previous article A topological characterization of generalized stable sets

next article Two new classes of methods to share the cost of cleaning up a polluted river

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Since $sc(\mathbf {p}, z)^p$ is convex as a function of z and the composition of a convex function with a nondecreasing function is quasi-convex, $sc(\mathbf {p}, z) = (sc(\mathbf {p}, z)^p)^\frac{1}{p}$ is quasi-convex as a function of z.

When $n=2m$ is even, the version of the coordinate-wise median mechanism given by $c(\mathbf {p}) = (\text {median}(-\infty ,\mathbf {x}),\text {median}( -\infty ,\mathbf {y}))$ has worst-case approximation ratio equal to $\sqrt{2}$. This follows from the bound in Lemma 3 and the worst-case profile $\mathbf {p}$ where $p_1=p_2 \dots p_m=(1,0)$ and $p_{m+1}=p_{m+2} \dots p_{2m}=(0,1)$.

The set $[p_i', g(\mathbf {p}')] \cap \Gamma$ is non-empty because $g(\mathbf {p}')$ cannot be in the same quadrant as $p_i'$. Any point in the same quadrant as $p_i'$ subtends an angle of less than $90^{\circ }$ with the other two points and hence it cannot be the geometric median.

The lower bound actually holds more generally in that if f is a deterministic, strategyproof mechanism defined for all n, then $\sup _{n \in N} AR(f) \ge 2^{1-\frac{1}{p}}$. If f is anonymous as well, the bound is a corollary of Theorem 3 due to the optimality of Coordinate-wise median (Theorem 1) for any n. For any f, the argument used to prove Lemma 4 in Feigenbaum et al. (2017) extends to this setting as well and is in the appendix proof.

The same argument applies if we just take $n=2$ but we wanted to illustrate that the result holds even under the restriction to odd number of agents.

Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) Strategyproof approximation of the minimax on networks. Math Oper Res 35:513–526CrossRef

Barberà S, Gul F, Stacchetti E (1993) Generalized median voter schemes and committees. J Econ Theory 61:262–289CrossRef

Bespamyatnikh S, Bhattacharya B, Kirkpatrick D, Segal M (2000) Mobile facility location (extended abstract). In: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications—DIALM ’00, vol. 4, ACM Press, Boston, Massachusetts, United States, pp 46–53

Black D (1948) On the rationale of group decision-making. J Polit Econ 56:23–34CrossRef

Border KC, Jordan JS (1983) Straightforward elections, unanimity and phantom voters. Rev Econ Stud 50:153CrossRef

Bordes G, Laffond G, Le Breton M (2011) Euclidean preferences, option sets and strategyproofness. SERIEs 2:469–483CrossRef

Chan H, Filos-Ratsikas A, Li B, Li M, Wang C (2021) Mechanism design for facility location problems: a survey, arXiv:2106.03457 [cs], arXiv: 2106.03457

Cheng Y, Zhou S (2015) A survey on approximation mechanism design without money for facility games. In: Gao D, Ruan N, Xing W (eds) Advances in global optimization, vol 95. Springer Proceedings in Mathematics & Statistics. Springer International Publishing, Cham, pp 117–128CrossRef

Dokow E, Feldman M, Meir R, Nehama I (2012) Mechanism design on discrete lines and cycles. In: Proceedings of the 13th ACM Conference on Electronic Commerce—EC ’12, vol. 13, ACM Press, Valencia, Spain, p 423

Durocher S, Kirkpatrick D (2009) The projection median of a set of points. Comput Geom 42:364–375CrossRef

El-Mhamdi E-M, Farhadkhani S, Guerraoui R, Hoang L-N (2021) On the strategyproofness of the geometric median. arXiv:2106.02394 [cs], arXiv: 2106.02394

Feigenbaum I, Sethuraman J, Ye C (2017) Approximately optimal mechanisms for strategyproof facility location: minimizing L $_{\rm p }$ norm of costs. Math Oper Res 42:434–447CrossRef

Feldman M, Wilf Y (2013) Strategyproof facility location and the least squares objective. In: Proceedings of the Fourteenth ACM Conference on Electronic commerce, vol. 14, ACM, Philadelphia Pennsylvania USA, pp 873–890

Feldman M, Fiat A, Golomb I (2016) On voting and facility location. In: Proceedings of the 2016 ACM Conference on economics and computation, vol. 17, ACM, Maastricht The Netherlands, pp 269–286

Fotakis D, Tzamos C (2014) On the power of deterministic mechanisms for facility location games. ACM Trans Econ Comput 2:1–37CrossRef

Fotakis D, Tzamos C (2016) Strategyproof facility location for concave cost functions. Algorithmica 76:143–167CrossRef

Gershkov A, Moldovanu B, Shi X (2019) Voting on multiple issues: what to put on the ballot? Theor Econ 14:555–596CrossRef

Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica 41:587CrossRef

Kim K, Roush F (1984) Nonmanipulability in two dimensions. Math Soc Sci 8:29–43CrossRef

Kyropoulou M, Ventre C, Zhang X (2016) Mechanism design for constrained heterogeneous facility location. In: Fotakis D, Markakis E (eds) Algorithmic game theory, vol 11801. Lecture Notes in Computer Science. Springer International Publishing, Cham, pp 63–76

Lee Brady R, Chambers CP (2016) A spatial analogue of May’s Theorem. Social Choice Welf 47:127–139CrossRef

Meir R (2018) Strategic voting, synthesis lectures on artificial intelligence and machine. Learning 12:1–167

Meir R (2019) Strategyproof facility location for three agents on a circle. arXiv:1902.08070 [cs], arXiv: 1902.08070

Moulin H (1980) On strategy-proofness and single peakedness. Public Choice 35:437–455CrossRef

Peters H, van der Stel H (1990) A class of solutions for multiperson multicriteria decision making. Oper Res Spek 12:147–153CrossRef

Peters H, van der Stel H, Storcken T (1992) Pareto optimality, anonymity, and strategy-proofness in location problems. Internat J Game Theory 21:221–235CrossRef

Peters H, Stel H, Storcken T (1993) Range convexity, continuity, and strategy-proofness of voting schemes. ZOR Methods Models Oper Res 38:213–229CrossRef

Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans Econ Comput 1:1–26CrossRef

Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217CrossRef

Sui X, Boutilier C (2015) Approximately strategy-proof mechanisms for (Constrained) facility location. In: Proceedings of the 2015 International Conference on autonomous agents and multiagent systems, Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, AAMAS ’15, vol. 14, pp 605–613

Sui X, Boutilier C, Sandholm T (2013) Analysis and optimization of multi-dimensional percentile mechanisms. In: Proceedings of the Twenty-Third international Joint Conference on artificial intelligence, vol. 23, AAAI Press, IJCAI ’13, Beijing, China, pp 367–374

Tang P, Yu D, Zhao S (2020) Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In: Proceedings of the 21st ACM Conference on economics and computation, pp 133–157, arXiv: 1808.06320

Walsh T (2020) Strategy proof mechanisms for facility location in Euclidean and Manhattan space. arXiv:2009.07983 [cs], arXiv: 2009.07983

Title: Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
Authors: Sumit Goel
Wade Hann-Caruthers
Publication date: 25-10-2022
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 1/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-022-01435-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2023

On the political economy of economic integration

Foundations of utilitarianism under risk and variable population

Two new classes of methods to share the cost of cleaning up a polluted river

Information disclosure under liability: an experiment on public bads

Polarization and conflict among groups with heterogeneous members

Families of abstract decision problems whose admissible sets intersect in a singleton