Abstract
We consider a social choice setting with agents that are partitioned into disjoint groups, and have metric preferences over a set of alternatives. Our goal is to choose a single alternative aiming to optimize various objectives that are functions of the distances between agents and alternatives in the metric space, under the constraint that this choice must be made in a distributed way: The preferences of the agents within each group are first aggregated into a representative alternative for the group, and then these group representatives are aggregated into the final winner. Deciding the winner in such a way naturally leads to loss of efficiency, even when complete information about the metric space is available. We provide a series of (mostly tight) bounds on the distortion of distributed mechanisms for variations of well-known objectives, such as the (average) total cost and the maximum cost, and also for new objectives that are particularly appropriate for this distributed setting and have not been studied before.
This work was partially supported by NSF awards CCF-1527497 and CCF-2006286.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that this objective is not exactly equivalent to the well-known (average) social cost objective, defined as the (average) total agent distance over all districts. All of our results extend for this objective as well, by adapting our mechanisms to weigh the representatives proportionally to the district sizes. When all districts have the same size, \(\mathtt{AVG}\circ \mathtt{AVG}\) coincides with the average social cost.
- 2.
See Theorem 1 and Proposition 6 in the arxiv version of [22].
- 3.
The latter condition, sometimes known as sub-homogeneity, is not usually included in the standard definition of subadditive functions. It is easily implied by the first subadditivity condition when c is an integer.
References
Abramowitz, B., Anshelevich, E.: Utilitarians without utilities: maximizing social welfare for graph problems using only ordinal preferences. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 894–901 (2018)
Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: A few queries go a long way: information-distortion tradeoffs in matching. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5078–5085 (2021)
Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: Peeking behind the ordinal curtain: improving distortion via cardinal queries. Artif. Intell. 296, 103488 (2021)
Anagnostides, I., Fotakis, D., Patsilinakos, P.: Metric-distortion bounds under limited information. CoRR arXiv:2107.02489 (2021)
Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., Skowron, P.: Approximating optimal social choice under metric preferences. Artif. Intell. 264, 27–51 (2018)
Anshelevich, E., Filos-Ratsikas, A., Shah, N., Voudouris, A.A.: Distortion in social choice problems: the first 15 years and beyond. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4294–4301 (2021)
Anshelevich, E., Postl, J.: Randomized social choice functions under metric preferences. J. Artif. Intell. Res. 58, 797–827 (2017)
Anshelevich, E., Zhu, W.: Ordinal approximation for social choice, matching, and facility location problems given candidate positions. In: Proceedings of the 14th International Conference on Web and Internet Economics (WINE), pp. 3–20 (2018)
Benadè, G., Nath, S., Procaccia, A.D., Shah, N.: Preference elicitation for participatory budgeting. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 376–382 (2017)
Benadè, G., Procaccia, A.D., Qiao, M.: Low-distortion social welfare functions. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 1788–1795 (2019)
Bhaskar, U., Dani, V., Ghosh, A.: Truthful and near-optimal mechanisms for welfare maximization in multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 925–932 (2018)
Borodin, A., Lev, O., Shah, N., Strangway, T.: Primarily about primaries. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 1804–1811 (2019)
Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A.D., Sheffet, O.: Optimal social choice functions: a utilitarian view. Artif. Intell. 227, 190–213 (2015)
Caragiannis, I., Nath, S., Procaccia, A.D., Shah, N.: Subset selection via implicit utilitarian voting. J. Artif. Intell. Res. 58, 123–152 (2017)
Caragiannis, I., Procaccia, A.D.: Voting almost maximizes social welfare despite limited communication. Artif. Intell. 175(9–10), 1655–1671 (2011)
Chen, X., Li, M., Wang, C.: Favorite-candidate voting for eliminating the least popular candidate in a metric space. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 1894–1901 (2020)
Fain, B., Goel, A., Munagala, K., Prabhu, N.: Random dictators with a random referee: constant sample complexity mechanisms for social choice. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 1893–1900 (2019)
Feldman, M., Fiat, A., Golomb, I.: On voting and facility location. In: Proceedings of the 2016 ACM Conference on Economics and Computation (EC), pp. 269–286 (2016)
Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 1–12. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44803-8_1
Filos-Ratsikas, A., Micha, E., Voudouris, A.A.: The distortion of distributed voting. Artif. Intell. 286, 103343 (2020)
Filos-Ratsikas, A., Voudouris, A.A.: Approximate mechanism design for distributed facility location. In: Caragiannis, I., Hansen, K.A. (eds.) SAGT 2021. LNCS, vol. 12885, pp. 49–63. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-85947-3_4
Gkatzelis, V., Halpern, D., Shah, N.: Resolving the optimal metric distortion conjecture. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1427–1438 (2020)
Goel, A., Krishnaswamy, A.K., Munagala, K.: Metric distortion of social choice rules: lower bounds and fairness properties. In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC), pp. 287–304 (2017)
Jaworski, M., Skowron, P.: Evaluating committees for representative democracies: the distortion and beyond. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 196–202 (2020)
Kempe, D.: An analysis framework for metric voting based on LP duality. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 2079–2086 (2020)
Kempe, D.: Communication, distortion, and randomness in metric voting. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 2087–2094 (2020)
Mandal, D., Procaccia, A.D., Shah, N., Woodruff, D.P.: Efficient and thrifty voting by any means necessary. In: Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 7178–7189 (2019)
Mandal, D., Shah, N., Woodruff, D.P.: Optimal communication-distortion tradeoff in voting. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp. 795–813 (2020)
Munagala, K., Wang, K.: Improved metric distortion for deterministic social choice rules. In: Proceedings of the 2019 ACM Conference on Economics and Computation (EC), pp. 245–262 (2019)
Procaccia, A.D., Rosenschein, J.S.: The distortion of cardinal preferences in voting. In: Klusch, M., Rovatsos, M., Payne, T.R. (eds.) CIA 2006. LNCS (LNAI), vol. 4149, pp. 317–331. Springer, Heidelberg (2006). https://doi.org/10.1007/11839354_23
Sen, A.: Social choice theory. In: Handbook of Mathematical Economics, vol. 3, pp. 1073–1181 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Anshelevich, E., Filos-Ratsikas, A., Voudouris, A.A. (2022). The Distortion of Distributed Metric Social Choice. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds) Web and Internet Economics. WINE 2021. Lecture Notes in Computer Science(), vol 13112. Springer, Cham. https://doi.org/10.1007/978-3-030-94676-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-94676-0_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-94675-3
Online ISBN: 978-3-030-94676-0
eBook Packages: Computer ScienceComputer Science (R0)