论文标题
在欧几里得空间中的Minimax Chamberlin-Courant规则下的多翼大选举
Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space
论文作者
论文摘要
我们考虑使用Minimax Chamberlin-Courant规则来考虑欧几里得空间中的多翼大选举。在这种情况下，选民和候选人被嵌入到$ d $维的欧几里得空间中，目标是选择一个$ k $候选人的委员会，以便将任何选民最喜欢的候选人的职级最小化。 （问题也等同于经典$ k $中心问题的序数版。）我们表明，该问题在任何维度$ d \ geq 2 $中都是np-hard，也很难近似。我们的主要结果是三个多项式时间近似方案，每个方案都发现一个委员会证明具有良好的最小值得分。在所有情况下，我们都表明我们的近似范围紧密或接近紧密。我们主要关注$ 1 $ - borda规则，但我们的一些结果也适用于更通用的$ r $ boda。
We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a $d$-dimensional Euclidean space, and the goal is to choose a committee of $k$ candidates so that the rank of any voter's most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical $k$-center problem.) We show that the problem is NP-hard in any dimension $d \geq 2$, and also provably hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with provably good minimax score. In all cases, we show that our approximation bounds are tight or close to tight. We mainly focus on the $1$-Borda rule but some of our results also hold for the more general $r$-Borda.
