Skip to main content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

25.10.2022 | Original Paper

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

verfasst von: Sumit Goel, Wade Hann-Caruthers

Erschienen in: Social Choice and Welfare

Einloggen, um Zugang zu erhalten
share
TEILEN

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\).
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
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.
 
2
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)\).
 
3
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.
 
4
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.
 
5
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.
 
Literatur
Zurück zum Zitat Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) Strategyproof approximation of the minimax on networks. Math Oper Res 35:513–526 CrossRef Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) Strategyproof approximation of the minimax on networks. Math Oper Res 35:513–526 CrossRef
Zurück zum Zitat Barberà S, Gul F, Stacchetti E (1993) Generalized median voter schemes and committees. J Econ Theory 61:262–289 CrossRef Barberà S, Gul F, Stacchetti E (1993) Generalized median voter schemes and committees. J Econ Theory 61:262–289 CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Black D (1948) On the rationale of group decision-making. J Polit Econ 56:23–34 CrossRef Black D (1948) On the rationale of group decision-making. J Polit Econ 56:23–34 CrossRef
Zurück zum Zitat Border KC, Jordan JS (1983) Straightforward elections, unanimity and phantom voters. Rev Econ Stud 50:153 CrossRef Border KC, Jordan JS (1983) Straightforward elections, unanimity and phantom voters. Rev Econ Stud 50:153 CrossRef
Zurück zum Zitat Bordes G, Laffond G, Le Breton M (2011) Euclidean preferences, option sets and strategyproofness. SERIEs 2:469–483 CrossRef Bordes G, Laffond G, Le Breton M (2011) Euclidean preferences, option sets and strategyproofness. SERIEs 2:469–483 CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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–128 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–128
Zurück zum Zitat 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 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
Zurück zum Zitat Durocher S, Kirkpatrick D (2009) The projection median of a set of points. Comput Geom 42:364–375 CrossRef Durocher S, Kirkpatrick D (2009) The projection median of a set of points. Comput Geom 42:364–375 CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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–447 CrossRef 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–447 CrossRef
Zurück zum Zitat 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, 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
Zurück zum Zitat 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 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
Zurück zum Zitat Fotakis D, Tzamos C (2014) On the power of deterministic mechanisms for facility location games. ACM Trans Econ Comput 2:1–37 CrossRef Fotakis D, Tzamos C (2014) On the power of deterministic mechanisms for facility location games. ACM Trans Econ Comput 2:1–37 CrossRef
Zurück zum Zitat Fotakis D, Tzamos C (2016) Strategyproof facility location for concave cost functions. Algorithmica 76:143–167 CrossRef Fotakis D, Tzamos C (2016) Strategyproof facility location for concave cost functions. Algorithmica 76:143–167 CrossRef
Zurück zum Zitat Gershkov A, Moldovanu B, Shi X (2019) Voting on multiple issues: what to put on the ballot? Theor Econ 14:555–596 CrossRef Gershkov A, Moldovanu B, Shi X (2019) Voting on multiple issues: what to put on the ballot? Theor Econ 14:555–596 CrossRef
Zurück zum Zitat Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica 41:587 CrossRef Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica 41:587 CrossRef
Zurück zum Zitat Kim K, Roush F (1984) Nonmanipulability in two dimensions. Math Soc Sci 8:29–43 CrossRef Kim K, Roush F (1984) Nonmanipulability in two dimensions. Math Soc Sci 8:29–43 CrossRef
Zurück zum Zitat 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 CrossRef 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 CrossRef
Zurück zum Zitat Lee Brady R, Chambers CP (2016) A spatial analogue of May’s Theorem. Social Choice Welf 47:127–139 CrossRef Lee Brady R, Chambers CP (2016) A spatial analogue of May’s Theorem. Social Choice Welf 47:127–139 CrossRef
Zurück zum Zitat Meir R (2018) Strategic voting, synthesis lectures on artificial intelligence and machine. Learning 12:1–167 Meir R (2018) Strategic voting, synthesis lectures on artificial intelligence and machine. Learning 12:1–167
Zurück zum Zitat Meir R (2019) Strategyproof facility location for three agents on a circle. arXiv:1902.08070 [cs], arXiv: 1902.08070 Meir R (2019) Strategyproof facility location for three agents on a circle. arXiv:1902.08070 [cs], arXiv: 1902.08070
Zurück zum Zitat Moulin H (1980) On strategy-proofness and single peakedness. Public Choice 35:437–455 CrossRef Moulin H (1980) On strategy-proofness and single peakedness. Public Choice 35:437–455 CrossRef
Zurück zum Zitat Peters H, van der Stel H (1990) A class of solutions for multiperson multicriteria decision making. Oper Res Spek 12:147–153 CrossRef Peters H, van der Stel H (1990) A class of solutions for multiperson multicriteria decision making. Oper Res Spek 12:147–153 CrossRef
Zurück zum Zitat Peters H, van der Stel H, Storcken T (1992) Pareto optimality, anonymity, and strategy-proofness in location problems. Internat J Game Theory 21:221–235 CrossRef Peters H, van der Stel H, Storcken T (1992) Pareto optimality, anonymity, and strategy-proofness in location problems. Internat J Game Theory 21:221–235 CrossRef
Zurück zum Zitat Peters H, Stel H, Storcken T (1993) Range convexity, continuity, and strategy-proofness of voting schemes. ZOR Methods Models Oper Res 38:213–229 CrossRef Peters H, Stel H, Storcken T (1993) Range convexity, continuity, and strategy-proofness of voting schemes. ZOR Methods Models Oper Res 38:213–229 CrossRef
Zurück zum Zitat Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans Econ Comput 1:1–26 CrossRef Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans Econ Comput 1:1–26 CrossRef
Zurück zum Zitat 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–217 CrossRef 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–217 CrossRef
Zurück zum Zitat 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 (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
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Walsh T (2020) Strategy proof mechanisms for facility location in Euclidean and Manhattan space. arXiv:2009.07983 [cs], arXiv: 2009.07983 Walsh T (2020) Strategy proof mechanisms for facility location in Euclidean and Manhattan space. arXiv:2009.07983 [cs], arXiv: 2009.07983
Metadaten
Titel
Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions
verfasst von
Sumit Goel
Wade Hann-Caruthers
Publikationsdatum
25.10.2022
Verlag
Springer Berlin Heidelberg
Erschienen in
Social Choice and Welfare
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-022-01435-1

Premium Partner