Search versus Search for Collapsing Electoral Control Types
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra, David E. Narváez, Conor Taliancich, Henry B. Welles
选举控制类型是试图通过改变选举结果的方式改变选举结果[BTT92]。 我们说两个兼容的(即具有相同的输入类型)控制类型,即与相同的选举系统E形成崩溃的对,如果对于每个可能的输入(通常由候选人集,投票集,焦点候选人,有时与未遂更改的性质相关的其他参数)可以成功执行,无论是还是两者都不能成功进行。 对于Hemaspaandra,Hemaspaandra和Menton[HHM20]发现的七名将军(即举行所有选举制度)中的每一对选举控制类型崩溃对,以及Carleton等人发现的每一对额外的选举控制类型崩溃对。 [CCH+24)对于否决权和批准(以及许多其他选举制度,根据该文件定理3.6和3.9),坍塌对的成员具有相同的复杂性,因为它们是相同的集合。 然而,具有相同的复杂性(如集合)不足以保证作为搜索问题,它们具有相同的复杂性。 在本文中,我们探讨了崩溃对的搜索版本之间的关系。 对于Hemaspaandra,Hemaspaandra和Menton [HHM20]和Carleton等人的崩溃对。 [CCH+24],我们证明这对成员的搜索版本的复杂性是多项式相关的(给定的访问,对于赢家问题本身不在多项式时间的情况下,到获胜者问题的神谕)。 除此之外,我们提供高效的减少,从解决方案到计算解决方案到另一个解决方案。 对于具体的系统多元化,否决权和批准,我们完全确定它们的哪个(由于我们的结果)多项式相关的崩溃搜索-问题对是多项式时间可计算的,哪些是NP-硬的。
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [BTT92]. We say two compatible (i.e., having the same input types) control types that are about the same election system E form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the att...
