The Metric Distortion of Multiwinner Voting
The Metric Distortion of Multiwinner Voting
复制标题
多方投票的指标扭曲
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Alexandros A. Voudouris
中科院分区：
文献类型：
--
作者：
I. Caragiannis;Nisarg Shah;Alexandros A. Voudouris
我们最近推出的度量失真多赢家投票的框架。在这个框架中，n个代理和m个替代品位于一个底层度量空间。代理人和替代品之间的确切距离是未知的。相反，每个代理提供一个备选方案的排名，从最近到最远排序。通常情况下，目标是选择一个单一的替代方案，近似最小化总距离的代理，最坏情况下的近似比称为失真。在多赢家投票的情况下，目标是选择一个由k个备选方案组成的委员会，使所有代理人的总成本（近似）最小化。我们考虑的情况下，一个代理人的成本是她的距离，在委员会中的第q个最接近的替代品。我们揭示了一个令人惊讶的多赢家投票规则的扭曲在k和q方面的剖分：当q
We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the q-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: The distortion is unbounded when q
登录
查看更多内容
社会选择问题的扭曲：前 15 年及以后
DOI：
10.24963/ijcai.2021/589
发表时间：
2021
期刊：
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track.
影响因子：
--
作者：
Anshelevich, Elliot;Filos-Ratsikas, Aris;Shah, Nisarg;Voudouris, Alexandros A.
通讯作者：
Voudouris, Alexandros A.
将度量扭曲与社会选择规则的公平性联系起来
DOI：
10.1145/3230654.3230658
发表时间：
2018
期刊：
Systems and Computation
影响因子：
--
作者：
Goel, Ashish;Hulett, Reyna;Krishnaswamy, Anilesh K.
通讯作者：
Krishnaswamy, Anilesh K.
改进确定性社会选择规则的度量失真
DOI：
10.1145/3328526.3329550
发表时间：
2019
期刊：
Proceedings of the 2019 ACM Conference on Economics
影响因子：
--
作者：
Munagala, Kamesh;Wang, Kangning
通讯作者：
Wang, Kangning
DOI：
10.1145/3033274.3085138
发表时间：
2017
期刊：
EC '17 Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
Goel, Ashish;Krishnaswamy, Anilesh K.;Munagala, Kamesh
通讯作者：
Munagala, Kamesh