论文标题
多翼人投票的度量失真
The Metric Distortion of Multiwinner Voting
论文作者
论文摘要
我们将最近引入的度量失真框架扩展到多翼型投票。在此框架中，$ n $代理商和$ m $替代品位于基础度量空间中。代理和替代方案之间的确切距离是未知的。取而代之的是，每个代理都提供替代方案的排名，从最接近最接近的序列订购。通常，目标是选择一个替代方案，该替代方法大约可以最大程度地减少与代理的总距离，并且最差的案例近似比称为失真。在多翼票投票的情况下，目标是选择一个$ k $替代方案的委员会，该委员会（大约）将所有代理商的总成本降至最低。我们考虑了委员会代理商的成本是她与委员会最接近的$ q $ the替代方案的距离。我们揭示了以$ k $和$ q $的扭曲的扭曲，这令人惊讶的是，当$ k/3 <q/3 <q \ leq k/2 $时，当代理数量均非线性，而当$ q/q/q/q/q/q/q q/q q k/q k/2 $不变时，失真是无限的。
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 \leq k/3$, asymptotically linear in the number of agents when $k/3 < q \leq k/2$, and constant when $q > k/2$.
