R-Multi-Bribery问题的单指数时间固定参数算法

12ACM Transactions on Economics and Computation, Vol. 8, No. 3, Article 12. Publication date: June 2020.0在单指数时间内进行投票和贿赂0DUŠAN KNOP，捷克理工大学信息技术学院理论计算机科学系，捷克共和国布拉格 MARTINKOUTECKÝ，查尔斯大学，捷克共和国 MATTHIAS MNICH，汉堡科技大学，德国0我们提出了一个关于投票系统中贿赂的一般问题。在R-Multi-Bribery问题中，目标是以最小成本贿赂一组选民，以便在投票规则R下，所需的候选人成为赢家。选民为撤销他们的选票、交换他们偏好顺序中两个连续候选人的位置以及扰乱他们的赞成票数以支持候选人分配价格。0作为我们的主要结果，我们证明了R-Multi-Bribery是固定参数可解的，参数化为0候选人数量|C|与|C|的单指数依赖关系，适用于许多自然投票规则R，包括所有自然评分协议，最小规则，Bucklin规则，Fallback规则，SP-AV和任何C1规则。在少数候选人设置中进行的绝大多数先前工作是通过将选民分为最多|C|！种类型，根据其偏好构建一个具有|C|！2个变量的整数线性规划，并通过Lenstra的算法在时间|C|！|C|！2内解决它，因此在|C|方面是双指数的。请注意，无法以这种方式编码大量不同的选民成本，并且仍然获得固定参数算法，因为这将增加选民类型的数量，从而增加维度。这两个双指数复杂性和受限成本的障碍已被Bredereck等人制定为“计算社会选择中的九个研究挑战”的“挑战＃1和＃2”。0因此，我们的结果解决了上述投票中R-Swap-Bribery的参数化复杂性问题0规则加Kemeny规则，对于除Kemeny规则外的所有规则，将对|C|的依赖关系降低到单指数。我们取得进展的引擎是使用了一种新的整数线性规划公式，使用所谓的“n重整数规划”。由于其格式相当严格，我们引入了“扩展n重IP”，它允许许多有用的建模技巧。然后，我们将R-Multi贿赂建模为扩展n重IP，并应用Hemmecke等人的算法[Math. Prog. 2013]。0CCS概念：• 计算理论 → 参数化复杂性和精确算法；0附加关键词和短语：投票系统，交换贿赂，整数规划0ACM参考格式：Dušan Knop，Martin Koutecký和MatthiasMnich。2020年。在单指数时间内进行投票和贿赂。ACM Trans. Econ. Comput. 8，3，Article12（2020年6月），28页。https://doi.org/10.1145/33968550该工作得到欧洲研究理事会306465号资助，德国研究基金会MN 59/4-1号资助，OP VVVMEYS资助的项目CZ.02.1.01/0.0/0.0/16019/0000765“信息学研究中心”资助，查尔斯大学项目UNCE/SCI/004资助，以及GA ČR项目19-27871X资助。作者地址：D.Knop，捷克理工大学信息技术学院理论计算机科学系，Thákurova 9，16000，布拉格，捷克共和国；电子邮件：dusan.knop@fit.cvut.cz；M.Koutecký，查尔斯大学，捷克共和国马蒂斯科-菲兹卡尔大学，查尔斯大学计算机科学研究所，Malostranské nám. 25，11800，布拉格，捷克共和国；电子邮件：koutecky@iuuk.mff.cuni.cz；M.Mnich，汉堡科技大学，算法与复杂性研究所，Blohmstr. 15，21079汉堡，德国；电子邮件：mmnich@tuhh.de。0本作品采用知识共享署名-相同方式共享4.0国际许可协议。0© 2020版权归所有者/作者所有。2167-8375/2020/06-ART12 https://doi.org/10.1145/339685512:2D. Knop et al.1INTRODUCTION0在这项工作中，我们解决了来自选举和贿赂领域的算法问题。在这些问题中，我们的输入是一次选举，它由候选人集合C和选民集合V组成，每个选民v都配备有一个线性顺序�v，表示他们对候选人集合C的偏好。此外，我们有一个固定的投票规则R（不是输入的一部分），它确定如何将选民的顺序聚合以确定选举中的获胜者。投票规则R的流行示例包括“评分协议”，如多数制（plurality）——其中获得大多数选民第一名的候选人获胜——或Borda规则，其中每个候选人从被选民排名为第i位中获得|C|-i个点数，得分最高的候选人获胜；以及Copeland规则，它根据候选人的多数派胜利数减去他们的多数派失败数对候选人进行排序。0以使指定的候选人c*成为选举（C，V）Γ在投票规则R下的获胜者。这些扰动问题模拟了各种现实生活中的问题，例如实际贿赂、竞选管理或选举后的检查，如破坏性贿赂（被称为“胜利边际”）；关于贿赂问题的许多变体的概述，请参阅Faliszewski和Rothe的最近调查[35]。0R-Multi-Bribery。扰动是通过交换两个相邻候选人的位置来执行的。0通过推动操作干扰某个选民的偏好顺序中相邻的候选人，通过控制变化（激活/去激活）某些选民。算法问题是通过执行成本最低的操作来实现目标。为了衡量交换的成本，我们考虑了Elkind等人引入的模型，其中每个选民可以为在其偏好顺序中交换两个连续候选人c、c'分配不同的价格σv(c,c')；这捕捉了小的变化概念，并包含了选民的偏好。如果选民v参与交换或推动操作，则会产生一次性影响成本ιv。我们还允许推动操作的选民个体成本πv，以及激活和去激活的选民个体成本αv和δv。我们的模型足够通用，甚至允许负成本。除非另有说明，我们假设偏好顺序是完全的，以下是一些例外情况。我们假设在PossibleWinner问题中给出了一般的偏序。此外，我们假设在R-Extension-Bribery中给出了顶部截断的顺序；在顶部截断的顺序中，选民只对他们最喜欢的候选人进行排名，并对其他候选人持中立态度。最后，我们还可以处理弱（或桶）顺序，这是候选人分区的线性顺序，选民在每个部分之间对候选人持中立态度，请参见第2节。一般偏序中的交换贿赂问题是一个非平凡且有趣的问题，我们稍后会讨论。我们称这个非常通用的设置为R-Multi-Bribery问题。0文献中已经研究了R-Multi-Bribery问题的许多特殊情况；请参阅0请参阅表1，了解R-Multi-Bribery涵盖了哪些问题。例如，在R-Swap-Bribery中，只允许进行交换。然而，在R-Support-Bribery中，只允许进行推动操作。在YoungScore问题中，只允许进行控制变化。0上述许多R-Multi-Bribery的特殊情况已经得到了广泛研究；请参阅0从算法的角度来看，这些问题大多数都是NP难的，例如R-Swap-Bribery、R-Shift-Bribery等。因此，我们预计解决这些问题的算法需要超多项式时间（假设P≠NP）。然而，在许多应用场景中，假设候选人的数量|C|很小是合理的；因此，设计NP难分数（获胜者确定）和贿赂算法一直是非常有兴趣的事情。01在这里，选民v的批准计数指定了有多少个顶级候选人从v那里获得了一些分数。另请参阅SP-AV的描述。0ACM Transactions on Economics and Computation，第8卷，第3期，第12篇文章。出版日期：2020年6月。0在单指数时间内进行投票和贿赂12:30表1. R-Multi-Bribery推广了几个研究过的贿赂问题，0我们在附录A中给出其正式定义0问题名称R-Multi-Bribery的特化0R-$Bribery σv ≡ 0，πv ≡ ∞，αv ≡ δv ≡ ∞0R-Manipulation ιv ≡ 0对于v ∈ M，ιv ≡ ∞对于v � M0R-CCAV/R-CCDV ιv ≡ 0，σv ≡ πv ≡ ∞0R-Swap-Bribery πv ≡ ∞，αv ≡ δv ≡ ∞，ιv ≡ 00R-Shift-Bribery R-Swap-Bribery，其中σv（c，c'）= ∞对于c��{c，c'}0R-Support Brib. σv ≡ αv ≡ δv ≡ ∞，ιv ≡ 00R-Extension-Bribery σv（c，c'）= 0，如果c，c'未排名，则σv（c，c'）= ∞；αv ≡ δv ≡ ∞，ιv0R-Possible Winner缩小到R-Swap-Bribery [25，Thm. 2]0Dodgson得分Condorcet-Swap-Bribery，其中σv ≡ 10Young得分Condorcet-CCDV，其中δv ≡ 10对于R-Manipulation，操纵者集合M � V在输入中给出。如果选民v参与交换或推动行动，则会发生一次性影响成本ιv。0利用这一特性的问题。特别是，人们寻求解决规模为n的实例I的算法，其运行时间为f（|C|）∙nO（1），其中f是可计算函数；这样的算法被称为固定参数算法。固定参数算法与所谓的XP算法相对应，其运行时间形式为nf（|C|）。虽然XP算法通常被认为即使对于小实例I和少数候选人也是不切实际的，但固定参数算法有可能是实际可行的，前提是函数f的增长适度。0目前关于操纵、控制和贿赂问题的情况确实是，有很多0在选举操纵、控制和贿赂的NP难问题中，已经设计了大量的固定参数算法，当以|C|为参数时，适用于多种投票规则[2，6，10，11，13-15，22，30]。例如，这个方向上的原型算法是由Dorn和Schlotter提出的[22]，他们展示了如何在时间2 2O（|C|）∙nO（1）内解决具有统一成本的R-Swap-Bribery问题20对于所有所谓的线性可描述的投票规则R；这里，统一成本意味着对于所有选民，交换任意两个相邻候选人的成本始终相同。在多个为少数候选人设计的固定参数算法中，Dorn-Schlotter算法中的函数f（|C|）通常以指数形式随|C|增长，这使得这些算法即使对于非常少的候选人来说也是不切实际的。由于这些算法中对|C|的双指数依赖通常源于通过Lenstra的著名算法[53]解决某个整数线性规划（ILP）的子例程，Bredereck等人[9]提出了以下“挑战＃1”，作为他们“计算社会选择中的九个研究挑战”的一部分：02 Bredereck等人[10]指出，Dorn和Schlotter的算法仅适用于统一成本。0ACM Transactions on Economics and Computation，第8卷，第3期，第12篇文章。出版日期：2020年6月。012:4 D. Knop等人0“ILP-based approach”的另一个缺点是它本质上将选民视为非个体-0而不是作为具有共享偏好的群体。这使得很难获得其中来自同一群体的选民在某种程度上不同，例如通过贿赂他们的成本。因此，他们的“挑战＃2”如下所示：01.1我们的贡献0我们的主要结果是一个针对许多基本投票规则R的以候选人数量为参数的R-Multi-Bribery的固定参数算法。我们的算法相对于先前的工作具有一些优势，因为它适用于依赖于选民的成本函数，并且在| C | 中的时间仅为单指数。该算法适用于许多投票规则R，例如每个候选人从每个选民那里最多获得| C | 分的所有自然评分协议。0定理1.1. R-Multi-Bribery在候选人数量为参数的情况下是固定参数可解的0候选人，并且可以在时间内解决0• 当 R 是任何自然评分协议、任何C1规则或真诚策略时，2 O ( | C | 6 log | C | ) ∙ n 30• 当 R 是maximin、Bucklin或Fallback规则时，2 O ( | C | 6 log | C | ) ∙ n4，• 当 R 是Kemeny规则时，2 O ( | C | ! 6 log | C | ) ∙ n 3。0总之，我们的算法包含并改进了所有先前设计的针对R-Multi-Bribery的算法0在表1中列出的问题。对于一些问题，例如Young-Score，我们的算法是自1977年以来的首次改进；我们在表2中总结了比较结果。0定理1.1的应用。我们认为R-Multi-Bribery推广了许多经过深入研究的问题0投票和贿赂问题，以候选人数量为参数。定理1.1的一个直接推论如下：0推论1.2. 让 R 是任何自然评分协议，C1规则，maximin规则，Bucklin规则0规则，SP-AV规则，Fallback规则或Kemeny规则。然后，R-Swap-Bribery在候选人数量 | C |的参数化下是固定参数可解的。0这解决了Bredereck等人的“挑战＃2”。特别是对于评分协议，maximin0规则，以及Bucklin规则，推论1.2扩展并改进了Dorn和Schlotter[22]的算法，该算法仅适用于R-Swap-Bribery的均匀成本情况，并且需要双指数运行时间2 2 O ( |C | ) ∙ n O ( 1 )。0我们注意到，不清楚（参见参考文献[30，第338页]）是否可以描述Kemeny规则0通过线性不等式，如Dorn和Schlotter[22]所定义的那样；即使如此，我们的算法也是第一个针对Kemeny规则下的R-Swap-Bribery的固定参数算法，因为Dorn和Schlotter的算法只适用于单位成本情况。0ACM Transactions on Economics and Computation，Vol. 8，No. 3，Article 12。出版日期：2020年6月。0在单指数时间内进行投票和贿赂 12:50表2.本文对R-Multi-Bribery的结果总结与比较0对特殊情况的先前工作0先前的最佳结果 新的结果0R -$Bribery 2 2 O ( | C | ) n O ( 1 ) Approval [13] 2 O ( | C | 6 log | C | ) ∙ n 30R -Manipulation 2 2 O ( | C | ) n O ( 1 ) Borda [7] 2 O ( | C | 6 log | C | ) ∙ n 30R -CCAV/ R -CCDV 2 2 O ( | C | ) n O ( 1 ) Approval [13] 2 O ( | C | 6 log | C | ) ∙ n 30R -Swap-Bribery 2 2 O ( | C | ) n O ( 1 )，均匀成本Approval [22] 2 O ( | C | 6 log | C | ) ∙ n 30R -Shift-Bribery XP -alg0FPT -AS，受限制成本Maximin [14] 2 O ( | C | 6 log | C | ) ∙ n 40R-Support Brib. NP-hard Fallback，SP-AV [60] 2O(|C|6log|C|)∙n40R-Mixed-Bribery NP-hard SP-AV [25] 2O(|C|6log|C|)∙n30R-Extension-Bribery NP-hard Borda，Cope-land 0，Maximin [4] 2O(|C|6log|C|)∙n40R-Possible Winner 2 2 O(|C|)nO(1) Bucklin，Copeland，pos. scoring protocols [6] 2O(|C|6log|C|)∙n30R-$Bribery XP-algor.，arbitrary cost Kemeny [29] 2O(|C|!6log|C|)∙n40Dodgson分数2 2 O(|C|)nO(1)[2] 2O(|C|6log|C|)∙n30Young分数2 2 O(|C|)nO(1)[63] 2O(|C|6log|C|)∙n30在对应于问题R-Problem的每一行中，我们陈述了对于投票规则R，已知R-Problem是NP-hard的候选人数量|C|的先前最佳依赖关系。对于R-Shift-Bribery，FPT-AS是指固定参数逼近方案，它是一种算法，在f(1/ε,|C|)∙nO(1)的时间内产生(1-ε)近似解，其中f是超多项式函数，ε>0；因此，它是比固定参数算法更弱的结果。0定理1.1的另一个推论是：0候选人，对于R是Borda规则，maximin规则和Copeland α规则。0通过Dorn和Schlotter的固定参数算法[22]，我们同时改进了0对于统一成本，由Bredereck等人提出的XP算法和任意成本的固定参数逼近方案[10]。此外，我们还有以下结果：0批准-CCAV和批准-CCDV可以解决0时间2O(|C|6log|C|)∙n40这改进了Bredereck等人最近的结果[13]，他们在时间上解决了这些问题0是双指数级的，与|C|成正比。01.2我们的方法0在定理1.1中我们实现的运行时间（除了Kemeny规则）只有在|C|方面是单指数级的。为了实现这一点，我们避免使用Lenstra的算法来解决固定维度的整数线性规划问题[53]，这是迄今为止的选择方法（导致双指数级的运行时间）。通常，当使用Lenstra的算法时，必须“分组对象”以便能够用所使用的参数来限制它们的数量。相反，我们以n倍整数规划（IP）的形式来表达R-Multi-Bribery问题。与固定维度的整数线性规划问题不同，n倍IP允许变量维度，但以约束矩阵的更刚性的块结构为代价。我们设法将许多投票规则R的R-Multi-Bribery问题编码为具有这种结构的约束矩阵。0ACM经济与计算交易，第8卷，第3期，第12篇文章。出版日期：2020年6月。012:6 D. Knop等人。0所需的结构。这些公式并不直接：相反，我们以“扩展”的n倍IP的形式对问题进行建模，其格式比文献中讨论的“标准”n倍IP要更一般。然后我们展示如何将任何扩展的n倍IP高效地转化为标准的n倍IP。这个IP的维度（即变量的数量）不受候选人数量|C|的任何函数的限制；然而，我们将每个块的维度限制为|C|的多项式。然后我们通过Hem-mecke等人的算法[44]解决标准的n倍IP，该算法的运行时间仅依赖于其每个块的最大维度的指数。该算法具有相当的组合特性，因为它通过迭代增广的方式工作，类似于通过（快速）循环取消解决最小成本流问题；参见Hemmecke等人[44]。通过这种方式，我们在解决Bredereck等人的“挑战＃1”方面做出了实质性的贡献[9]。0参数化复杂性。参数化问题是一个决策问题（语言）P�Σ�0伴随一个参数κ：Σ�→N，将P的实例映射到参数的值。如果存在一个算法，它能够在运行时间f(κ(x))∙|x|O(1)内决定x是否属于P，其中f：N→N是一个可计算函数（与|x|无关），则参数化问题(P,κ)是固定参数可解的（并且属于类FPT）。如果存在一个算法，它能够在运行时间|x|f(κ(x))内决定x是否属于P，其中f：N→N是一个可计算函数，则参数化问题(P,κ)属于类XP。设(P,κ),(P',κ')是两个参数化问题。如果存在一个算法，它能够在时间f(κ(y))∙|y|O(1)内产生一个实例x，其中κ(x)≤f(κ'(y))(对于某个可计算函数f：N→N)，使得当且仅当y∈P'时，x∈P。如果每个W[1]问题都可以归约到(P,κ)，则参数化问题(P,κ)是W[1]-难的。有关背景知识，我们参考Flum和Grohe的书[39]或Cygan等人的书[18]。01.3 相关工作0投票系统中的贿赂问题已经得到了广泛研究[10, 22, 25,29]。我们研究的最重要的贿赂模型——交换贿赂——是由Elkind等人首次引入和考虑的[25]。我们还继续了Faliszewski等人的研究[30]，他们在Bartholdi等人的控制框架[2]中提出了多重攻击的研究（即同时使用多个控制范式，例如删除一个候选人并同时添加一些迄今为止潜在的选民）。Dorn和Schlotter[22]使用贿赂的整数线性规划模型为给定选举中的候选人数量提供了固定参数算法，例如，对于每次交换的统一成本和R作为评分协议的情况。Bredereck等人[10]考虑了移位贿赂的参数化复杂性（由Elkind和Faliszewski[24]引入，特别关注贿赂和竞选管理之间的关系），其中候选人可以在选民的偏好顺序中向上移动若干位置；这是交换贿赂的特例。他们模型的扩展[15]允许竞选经理以单个贿赂行为积极或消极地影响多个选票中首选候选人的位置，适用于大规模竞选活动。Bredereck等人[14]研究了允许多个获胜者的选举的贿赂的复杂性，例如当形成委员会时。Faliszewski等人[34]研究了Bucklin和fallback选举中（交换）贿赂的计算复杂性。Maushagen等人[55]研究了迭代投票程序中的贿赂作为一种操纵方式，即候选人逐轮被淘汰，这里通常建立了使用Baldwin或Nanson规则的贿赂的NP难度。Dey等人[21]研究了所谓的节俭贿赂，即只有在选民从中受益时才能贿赂选民，即选民更喜欢选举的新结果而不是当前的结果。同一组作者[20]研究了找到可能的结果的复杂性0ACM Transactions on Economics and Computation，第8卷，第3期，第12篇文章。出版日期：2020年6月。lagramming), and ILPs in fixed dimension (due to the algorithms of Lenstra [53] and Kannan [47]).Courcelle’s theorem [17] and Freuder’s algorithm [40] implies that solving ILPs is fixed-parametertractable parameterized by the treewidth of the constraint matrix and the maximum domain sizeof the variables. Ganian and Ordyniak [41] showed fixed-parameter tractability for the combinedparameter the treedepth and the largest absolute value in the constraint matrix, and contrastedthACM Transactions on Economics and Computation, Vol. 8, No. 3, Article 12. Publication date: June 2020.0在单指数时间内进行投票和贿赂 12:70一组操纵者（即可以通过协同工作改变选举结果的选民）。他们的研究主要集中在经典复杂性，主要是在小规模操纵者的情况下（例如，大小为O(1)的集合）。还考虑了不同的成本模型：Faliszewski等人[29]要求每个选民都有自己的价格，该价格与对被贿赂选票所做的更改无关。Faliszewski[27]和Faliszewski等人[31]的更一般模型允许价格取决于选民被贿赂者要求的更改量（后一种情况被称为微贿赂）。0胜利的边际或稳健性。据我们所知，这种范式是由Magrino等人和Cary独立引入的。后来，Xia研究了计算胜利边际的各种（经典）复杂性方面。值得注意的是，这些论文只涉及单位成本，即贿赂成本对所有选民均一致。在同一背景下，Shiryaev等人研究了作为更精细度量的交换贿赂。在多赢家设置中，研究(建设性)贿赂的一个可能动机可能来自于衡量候选人的成功（在他或她不在获胜委员会中的情况下）0研究(破坏性)贿赂的主要动机来自于研究所谓的0Baumeister和Rothe或Faliszewski和Rothe；参见，例如参考文献。0对于其他已经进行算法研究的贿赂模型，请参见，例如0由于相应多面体的整数性和线性规划的多项式性，ILPs在固定维度（由于Lenstra和Kannan的算法）和固定维度（由于Lenstra和Kannan的算法）中是多项式可解的。Courcelle的定理和Freuder的算法意味着通过约束矩阵的树宽和变量的最大定义域大小参数化，解决ILPs是固定参数可解的。Ganian和Ordyniak证明了通过树深度和约束矩阵中的最大绝对值的组合参数的固定参数可解性，并将其与通过树宽交换树深度时的W [1]-难度结果进行了对比。0关于整数线性规划(ILPs)，可解的片段包括其定义矩阵完全单调的ILPs0本文在引起对n重IP的关注方面起到了重要的催化剂作用0相关的IPs。通过对Hemmecke等人的算法进行仔细检查，我们能够获得“组合n重IPs”的特殊情况的改进版本，其中包括目前研究的R-Multi贿赂模型。上述改进的动态规划方法的技术贡献，导致了在参数和维度n方面对一般n重IPs的加速，最终导致了由Eisenbrand等人提出的目前最佳算法。此外，Altmanová等人进行了初步的实验评估，表明迭代增量算法在实际应用中具有潜力，因为具有某些“适应性”属性。迄今为止，扩展n重IP的概念在其他地方尚未使用，但它可能使这里使用的一些建模技巧变得流行，参见Faliszewski等人。12:8D. Knop et al.ACM Transactions on Economics and Computation, Vol. 8, No. 3, Article 12. Publication date: June 2020.0组织。在第2节中，我们提供了解决问题所需的背景知识。0然后，在第3节中，我们定义了扩展的n重IP，这样可以更容易地进行问题建模。我们在第4节中给出了几个R-Multi-Bribery问题的扩展n重IP公式。复杂性下界和难度结果在第5节中给出。我们在第6节中总结。02 投票和贿赂问题0我们给出了我们处理的问题的概念；有关背景，我们参考Brams和Fishburn[8]以及Faliszewski和Rothe [35]的调查。0选举。选举(C,V)由候选人集合C和选民集合V组成，选民在C上表达他们的偏好。选民的偏好可以用许多方式建模；在本文中，我们使用一种序数模型的变体，其中每个选民v的偏好通过偏好顺序�v表示，除非另有说明，该顺序是C上的一个全序。在我们研究的一些问题中，我们研究只为他们的“首选候选人”指示偏好的选民；我们用“截断顺序”来模拟这一点。对于整数t∈N，如果存在一个排列π在{1,...,|C|}上，使得�v的形式为cπ(1)�v∙∙∙�vcπ(t)�v{cπ(t+1),...,cπ(|C|)}；也就是说，v在集合{cπ(t+1),...,cπ(|C|)}的成员之间是无差别的，我们称之为未排名的候选人；我们将{cπ(1),...,cπ(t)}称为排名候选人。对于排名候选人c，我们用rank(c,v)表示他们在�v中的排名；然后v最喜欢的候选人的排名为1，他们最不喜欢的候选人的排名为|C|。此外，对于t个顶部截断的偏好顺序�v，对于所有排名候选人c∈C，rank(c,v)≤t。我们在这里指出，如果�v是一个弱序（或桶序），即当它是一个线性序，其中候选人没有偏好一个组中的候选人，我们可以用�v的任何线性扩展替换它，并将交换两个候选人c,c′的成本设置为0。独立于选民，对于候选人集合C，我们还将C上的线性序�C称为C的排名（即排名是候选人的线性序的简写）。对于不同的候选人c,c′∈C，如果选民v更喜欢c而不是c′，我们写作c�vc′。为了简化表示，我们有时将候选人集合C与集合{1,...,|C|}等同，特别是在表示C上的排列时。所有研究的问题都指定了C中的一个候选人；我们总是用c�来表示它。0在原始顺序中，当rank(c,v)=rank(c′,v)时，我们将交换的成本设置为0。与选民无关，对于候选人集合C，我们还将C上的线性序�C称为C的排名（即排名是候选人的线性序的简写）。对于不同的候选人c,c′∈C，如果选民v更喜欢c而不是c′，我们写作c�vc′。为了简化表示，我们有时将候选人集合C与集合{1,...,|C|}等同，特别是在表示C上的排列时。所有研究的问题都指定了C中的一个候选人；我们总是用c�来表示它。0接下来，我们描述了我们扰动给定选举(C,V)的行动。应用一组Γ0对(C,V)进行的操作会产生一个扰动的选举，我们用(C,V)Γ表示。执行一个操作会产生成本；我们通过函数指定这些成本，对于每个选民v∈V，指定他们执行操作的个体成本。02.1 操纵的行动0交换。设(C,V)是一次选举，v∈V是一名选民，�v是他们的偏好顺序。对于候选人c,c′∈C，交换s=(c,c′)v表示在�v中交换c和c′的位置；用�s表示扰动的顺序0在�v中，如果rank(c,v)=rank(c′,v)−1，则交换(c,c′)v是可接受的。0如果在�v中可以按顺序依次应用它们，其中每个交换都是可接受的，则交换集S在�v中是可接受的。注意，扰动的投票用�S表示0与  S  的交换顺序无关。我们还扩展了这种符号，用于在多个投票中应用交换，并将其表示为  V S。我们通过函数 σ v :  C  ×  C  →  Z 来指定 v的交换成本。交换的一个特殊情况是“移动”，即我们希望以适当的成本将  c �向前移动一些投票，使其在扰动选举中获胜，而不超过给定的预算。移动可以通过仅涉及  c �的交换来建模。kkis the Copelandα rule for a rational number α ∈ [0, 1], which specifies that for each head-to-head contest between two distinct candidates, if some candidate is preferred by a majorityof voters, then they obtain one point and the other candidate obtains zero points, and if aACM Transactions on Economics and Computation, Vol. 8, No. 3, Article 12. Publication date: June 2020.0在单指数时间内进行投票和贿赂 12:90将在下面定义），每个选民 v  ∈  V  还具有一个批准计数 a v ∈ { 0 , . . . ,  | C |} 。选民 v的批准计数 3 a v 表示他们批准他们偏好顺序中排名前 a v 多的候选人，并反对其他所有候选人。“推动操作”可以改变选民的批准计数：形式上，对于选民 v 和  t  ∈ {− a v , . . . ,  | C | −  a v }，一个推动操作 p v =  t  将他们的批准计数更改为  a v +  t 。我们通过函数  π v :  {− a v , . . . ,  | C| −  a v } →  Z 来指定推动操作的成本；我们规定  π v ( 0 )  =  0。如果选民 v参与交换或推动操作，则会发生一次性的影响成本  ι v 。0和一组潜在选民 V ℓ。只有活跃选民参与选举，但通过“控制变化”，潜在选民可以变为活跃选民，或者活跃选民可以变为潜在选民。（如果没有将 V 划分为 V a 和 V ℓ 的分区，则我们隐含地假设 V = V a 。）0选民 v  ∈  V ℓ  通过控制变化激活；用  ( V ℓ  ∪  V a ) γ  表示更改后的选民集合。我们用  α v表示激活选民 v 的成本，用  δ v 表示停用选民 v 的成本。02.2 投票规则0投票规则  R  是一个将选举  ( C , V  )  映射到一个子集  W  �  C 的函数，称为  获胜者。我们研究以下投票规则：0其中  s 1  ≥ ∙ ∙ ∙ ≥  s | C  |  ≥  0。对于每个位置  p  ∈ { 1 , . . . ,  | C |} ，值  s p  指定每个候选人  c从将其排名为第 p位的每个选民那里获得的点数。获得最大点数的任何候选人都是获胜者。评分协议的示例包括具有s  =  ( 1 ,  0 , . . . ,  0 ) 的多数制规则，具有  s  =  ( 1 , . . . ,  1 ,  0 , . . . ,  0 )  的d-批准规则（其中有 d 个1），以及具有  s  =  ( | C | −  1 ,  | C | −  2 , . . . ,  1 ,  0 ) 的 Borda规则。在整个过程中，我们仅考虑自然评分协议，其中  s 1  ≤ | C | ；这适用于前述的常见规则。0规则产生的候选人多于 n0获胜者是应用  k -批准规则时获得最大点数（对所有候选人而言）的任何候选人。0如果满足  |{ v  ∈  V  |  c  � v  c ′ }|  >  |{ v  ∈  V  |  c ′ � v  c }| ，则候选人  c  是  Condorcet赢家。如果存在 Condorcet 赢家，则投票规则是  Condorcet-consistent 的。Fishburn [ 37 ]根据确定获胜者所需的信息类型将投票规则分为 C1、C2 或 C3 类。对于候选人  c , c ′ ∈  C ，令 v( c , c ′ )  是更喜欢  c  而不是  c ′ 的选民数量，即 v ( c , c ′ )  =  |{ v  ∈  V  |  c  � v  c ′ }| ；我们写作c  < M  c ′ 如果 c 在两两对决中击败 c ′ ，即如果 v ( c , c ′ )  >  v ( c ′ , c ) 。0C1：如果知道v(c′,c)，v(c,c′)

下载后可阅读完整内容，剩余1页未读，立即下载