Optimal Communication-Distortion Tradeoff in Voting
Optimal Communication-Distortion Tradeoff in Voting
复制标题
投票中的最佳通信与失真权衡
DOI：
10.1145/3391403.3399510
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Woodruff, David P.
中科院分区：
文献类型：
--
作者：
Mandal, Debmalya;Shah, Nisarg;Woodruff, David P.
在最近的工作中，Mandal等人[2019]研究了投票中赢家选择问题的一个新框架，其中投票规则被视为启发规则和聚合规则的组合。启发规则要求投票者根据他们对一组备选方案的偏好来响应查询，聚合规则聚合投票者的响应以返回获胜的备选方案。他们研究了投票规则的通信复杂性与其失真之间的权衡，前者衡量每个投票人必须发送的信息比特数，后者衡量获胜者在功利主义社会福利方面的质量。他们证明了达到所需失真水平所需的通信复杂性的上限和下限，但它们的界限并不严格。重要的是，他们也留下了开放的问题，最好的随机规则是否可以显着优于最好的确定性规则。对于一个赢家选择规则，以实现失真d与m个替代品，我们表明，所需的通信复杂度是~Θ（m/d）时，使用确定性的启发，和~Θ（m/d3）时，使用随机启发，这两个界限是紧对数因子。我们的上限利用了流算法的最新进展。为了建立我们的下界，我们推导了一个多方通信复杂性问题的新下界，然后研究了投票中的k-选择问题，其中的目标是选择一组k个备选方案。对于一个k-选择规则，实现失真d与m个替代品，我们表明，最好的通信复杂度是~Θ（m/（kd））时，规则使用确定性启发和~Θ（m/（kd 3））时，规则使用随机启发。我们的最佳界限产生的非平凡的含义，k-选择问题变得严格更容易k增加。
In recent work, Mandal et al. [2019] study a novel framework for the winner selection problem in voting, in which a voting rule is seen as a combination of an elicitation rule and an aggregation rule. The elicitation rule asks voters to respond to a query based on their preferences over a set of alternatives, and the aggregation rule aggregates voter responses to return a winning alternative. They study the tradeoff between the communication complexity of a voting rule, which measures the number of bits of information each voter must send in response to its query, and its distortion, which measures the quality of the winning alternative in terms of utilitarian social welfare. They prove upper and lower bounds on the communication complexity required to achieve a desired level of distortion, but their bounds are not tight. Importantly, they also leave open the question whether the best randomized rule can significantly outperform the best deterministic rule.We settle this question in the affirmative. For a winner selection rule to achieve distortion d with m alternatives, we show that the communication complexity required is ~Θ (m/d) when using deterministic elicitation, and ~Θ (m/d3) when using randomized elicitation; both bounds are tight up to logarithmic factors. Our upper bound leverages recent advances in streaming algorithms. To establish our lower bound, we derive a new lower bound on a multi-party communication complexity problem.We then study the k-selection problem in voting, where the goal is to select a set of k alternatives. For a k-selection rule that achieves distortion d with m alternatives, we show that the best communication complexity is ~Θ (m/(kd)) when the rule uses deterministic elicitation and ~Θ (m/(kd3)) when the rule uses randomized elicitation. Our optimal bounds yield the non-trivial implication that the k-selection problem becomes strictly easier as k increases.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Gerdus Benade;Swaprava Nath;Ariel D. Procaccia;Nisarg Shah
通讯作者：
Nisarg Shah
DOI：
10.1145/1807406.1807441
发表时间：
2010-05
期刊：
--
影响因子：
--
作者：
Jason D. Hartline
通讯作者：
Jason D. Hartline
尽管沟通有限，投票几乎使社会福利最大化
影响因子：
14.4
作者：
I. Caragiannis;Ariel D. Procaccia
通讯作者：
Ariel D. Procaccia
DOI：
10.1609/aaai.v34i02.5544
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Georgios Amanatidis;Georgios Birmpas;Aris Filos;Alexandros A. Voudouris
通讯作者：
Alexandros A. Voudouris
通过精确采样的流算法
DOI：
--
发表时间：
2010
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Alexandr Andoni;Robert Krauthgamer;Krzysztof Onak
通讯作者：
Krzysztof Onak