We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.
翻译:我们研究了具有特定职位矩阵的选举性质(在这种选举中,每个候选人在每一个职位上排名由矩阵中指定的选民数排列)。我们发现,计算产生一个特定职位矩阵的选举是 #P-完成的。因此,对此类选举进行统一的随机抽样似乎具有挑战性,我们提出一个更简单的算法,而没有硬性的保证。接下来,我们考虑测试一个特定矩阵能否通过具有某种结构的选举(如单比分或群体分化)来实施的问题。最后,我们考虑检查一个特定职位矩阵能否由 Condorcet 获胜者进行。我们用实验来补充我们的理论结论。</s>