论文标题
扭曲的浓度：额外选民在随机社会选择中的价值
Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice
论文作者
论文摘要
我们研究了公制隐式功利模型中随机社会选择的较高统计瞬变。社会选择机制的扭曲是相对于最佳功利性社会成本（OPT）的预期近似因素。 $ k^{th} $变形时刻是相对于$ k^{th} $ opt的预期近似因素。我们考虑通过随机抽样选民为自己喜欢的替代方案来引起替代方案的机制。我们设计了两个机制家族，它们提供了恒定的（相对于选民数量和替代方案的数量），如果所有选民都可以在拟议的替代方案中参与投票，或者只有$ 2K-1 $ $的样本，则仅使用$ k $样本的变形时刻使用损坏时刻，如果只有样本选民才能参加。我们还表明，这些样品数量很紧。这种机制偏离了恒定近似值，以概率在样本数量中呈指数下降的概率，而与选民总数和替代方案无关。我们以对现实世界参与式预算数据的模拟进行了结论，以定性地补充我们的理论见解。
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.
