{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:02:50Z","timestamp":1750492970008},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cost (OPT). The k'th moment of Distortion is the expected approximation factor with respect to the k'th power of OPT. We consider mechanisms that elicit alternatives by randomly sampling voters for their favorite alternative. We design two families of mechanisms that provide constant (with respect to the number of voters and alternatives) k'th moment of Distortion using just k samples if all voters can then participate in a vote among the proposed alternatives, or 2k-1 samples if only the sampled voters can participate. We also show that these numbers of samples are tight. Such mechanisms deviate from a constant approximation to OPT with probability that drops exponentially in the number of samples, independent of the total number of voters and alternatives. We conclude with simulations on real-world  Participatory Budgeting data to qualitatively complement our theoretical insights.<\/jats:p>","DOI":"10.24963\/ijcai.2020\/16","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T08:12:10Z","timestamp":1594195930000},"page":"110-116","source":"Crossref","is-referenced-by-count":1,"title":["Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice"],"prefix":"10.24963","author":[{"given":"Brandon","family":"Fain","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University, USA"}]},{"given":"William","family":"Fan","sequence":"additional","affiliation":[{"name":"North Carolina School of Science and Mathematics, USA"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, USA"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-PRICAI-2020","name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","start":{"date-parts":[[2020,7,11]]},"theme":"Artificial Intelligence","location":"Yokohama, Japan","end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T22:12:54Z","timestamp":1594246374000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/16"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/16","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}