Separating and Collapsing Electoral Control Types
Separating and Collapsing Electoral Control Types
复制标题
DOI：
10.48550/arxiv.2207.00710
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Benjamin Carleton;Michael C. Chavrimootoo;L. Hemaspaandra;David E. Narv'aez;Conor Taliancich;Henry B. Welles
中科院分区：
文献类型：
--
作者：
Benjamin Carleton;Michael C. Chavrimootoo;L. Hemaspaandra;David E. Narv'aez;Conor Taliancich;Henry B. Welles
[HHM 20]发现，对于7对（C，D）看似不同的标准选举控制类型，C和D是相同的：对于每个输入I和每个选举系统，I是C和D的Yes实例，或者两者都不是。令人惊讶的是，这一直没有被发现，即使该领域是记分卡有多少性病。控制类型的选举系统是抗拒的;各种“不同“的细胞在这样的记分卡上，不知不觉地，重复的努力在同一个问题上。这自然会引起人们的担忧，即其他成对的控件类型也是相同的，因此工作仍然是不必要的重复。我们确定，对于所有的性病。控制类型，这对是，对于选举的选票是候选人的线性排序，总是相同的。我们表明，没有相同的控制对存在超出已知的7。我们为3个中央选举系统确定哪些控制对是相同的（“崩溃”）相对于这些系统，我们探索控制对之间的包容/不可比性关系。对于批准投票，其投票有不同的“类型”，[HHM 20]的7崩溃仍然有效。但我们发现14个额外的崩溃，持有赞成投票，但不为一些选举系统的选票是线性排序。我们发现否决权有1个额外的崩溃，而多数票没有。我们证明了上述3个选举系统中的每一个都没有崩溃，除了继承自[HHM 20]或在这里添加的那些。但是我们展示了许多新的包含关系，这些关系在一些分离的控制对之间保持，并且对于每个分离的std对。控制类型根据包含（总是，并且对某些输入严格）或不可比性对其分离进行分类。我们的工作，为一般情况下，这3个重要的选举制度，澄清景观的44标准。控件类型，为每对控件折叠或分隔它们，并提供有关分隔的更细粒度信息。
[HHM20] discovered, for 7 pairs (C,D) of seemingly distinct standard electoral control types, that C and D are identical: For each input I and each election system, I is a Yes instance of both C and D, or of neither. Surprisingly this had gone undetected, even as the field was score-carding how many std. control types election systems were resistant to; various"different"cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that other pairs of control types are also identical, and so work still is being needlessly duplicated. We determine, for all std. control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. We show that no identical control pairs exist beyond the known 7. We for 3 central election systems determine which control pairs are identical ("collapse") with respect to those systems, and we explore containment/incomparability relationships between control pairs. For approval voting, which has a different"type"for its votes, [HHM20]'s 7 collapses still hold. But we find 14 additional collapses that hold for approval voting but not for some election systems whose votes are linear orderings. We find 1 additional collapse for veto and none for plurality. We prove that each of the 3 election systems mentioned have no collapses other than those inherited from [HHM20] or added here. But we show many new containment relationships that hold between some separating control pairs, and for each separating pair of std. control types classify its separation in terms of containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these 3 important election systems, clarifies the landscape of the 44 std. control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.