0人工智能267（2019）58-770目录列表可在ScienceDirect上找到0人工智能0www.elsevier.com/locate/artint0优化位置评分规则进行排名聚合 �0Ioannis Caragiannis a，Xenophon Chatzigeorgiou a，George A. Krimpas a，Alexandros A.Voudouris b，�0a 帕特拉斯大学计算机工程与信息学系，希腊 b 牛津大学计算机科学系，英国0a r t i c l e i n f o a b s t r a c t0文章历史：2017年8月8日收到2018年10月26日修订稿收到 2018年11月7日接受2018年11月13日在线发布0关键词：计算社会选择位置评分投票规则 众包 学习和投票偏好学习 近似算法0如今，几个众包项目利用社会选择方法根据工人提供的个人排名计算备选方案的综合排名。受到这些系统的启发，我们考虑了一个设置，每个工人被要求对一定数量的备选方案进行排名，然后使用位置评分规则计算综合排名。在看似无限的规则中，哪个是最好的规则？为了回答这个问题，我们假设我们部分地了解底层真实排名。然后，要解决的重要优化问题是计算位置评分规则，其结果在应用于个人排名的概要中尽可能接近我们所知道的底层真实排名的部分。我们从理论角度研究了这个基本问题，并提出了积极和消极的复杂性结果，并通过对真实世界和合成数据的实验来补充我们的理论发现。0© 2018 Elsevier B.V.版权所有。01. 引言0社会选择理论[8]研究了计算获胜备选方案或可用备选方案的排名的投票规则（也称为社会选择或社会福利函数）从选民偏好中。通常，每个选民的偏好被认为是对所有可用备选方案的排名。我们偏离了这个假设，相反，我们将注意力集中在每个选民（或者为了我们的目的更好的说，代理人）仅对一小部分备选方案进行排名的情况。这种不完整的排名在文献中似乎是非标准的；文献[16,18,39]是一些值得注意的例外。0我们采用不完整排名的原因是众包[25]和评级应用。例如，假设请求者想要使用工人群体的专家意见对大量备选方案进行排名。询问每个工人对整个备选方案集的意见（即对它们的完整排名）可能存在问题，因为很可能工人不会了解大多数备选方案。即使她试图获取更多信息，也很难在她熟悉的备选方案和她完全不了解的备选方案之间得出一致的比较，因为备选方案的数量太大。相反，如果工人们专注于小的固定集合，这个任务将会更容易。0�本文的初步版本发表在第31届AAAI人工智能大会（AAAI）论文集中，第430-436页，2017年。本工作得到帕特拉斯大学Caratheodory研究基金E.114的部分支持，得到奥纳西斯基金会的博士奖学金的支持，以及欧洲研究理事会（ERC）在639945号授权下的支持（ACCORD）。*通讯作者。0电子邮件地址：alexandros.voudouris@cs.ox.ac.uk（A.A. Voudouris）。0https://doi.org/10.1016/j.artint.2018.11.001 0004-3702/ ©2018 Elsevier B.V.版权所有。0I. Caragiannis等/人工智能267（2019）58-77 590请求者可以给每个工作者不同的少量备选方案进行排名。然后，对较小的输入进行处理并合并它们以得到所有备选方案的全局排名对于请求者来说也更容易。0这种方法最近在大规模在线开放课程（MOOCs）中的序数同行评分背景下得到了应用；有关这种方法的论文，请参见[3, 10, 11, 38, 40,41]。在这种设置中，将评分一次参与学生众多的考试任务外包给学生自己。每个学生被要求对其他学生的少量考试论文进行排名，最终评分（所有学生的排名）通过聚合学生提供的输入来获得。序数同行评分也被用于评估研究资金提案，例如NSF的传感器和感知系统（SSS）计划在2013年使用了Merri�eld和Saari早期提出的Borda-like方法[34]（参见[24]）。0我们设想的评级应用的一个例子如下。酒店预订系统的用户被要求对他们最近入住过的特定城市的酒店进行排名。该系统的目标是计算出酒店的完整排名（或者可能根据不同的相关标准，如价格、清洁度、位置等，计算出不同的排名），以帮助新用户。显然，每个用户只能为少数几家酒店提供有意义的反馈。同样，在这种情况下，系统可能要求每个用户只关注她所了解的酒店的一个子集。类似的评级应用示例包括与排名餐馆、大学等相关的系统。0除了在上述情景中每个个体被要求对不同的备选方案进行排名之外，另一个隐含的特征是存在一个潜在的真实排名（例如，以质量为标准的考试论文排名或以设施为标准的酒店排名），我们希望在聚合个体偏好时计算出来。我们是否可以使用简单的类似投票的规则来做到这一点？我们采用了一种优化方法，可以用以下问题来描述：0假设我们对潜在真实排名有部分了解，并且可以访问抽样的个人偏好，那么当应用于抽样的个人偏好时，哪种规则可以产生与（我们对）潜在真实排名尽可能一致的结果？0我们研究了上述问题的位置评分规则（或者简单地说，评分规则），它们在社会选择理论中起着核心作用。导致这个决定的两个因素是它们的简单性和有效性；简单性是由它们的定义决定的，有效性则是通过我们的实验结果证明的。特别是，我们考虑的设置是每个代理人被要求对相同数量d的备选方案进行排名；这与在MOOCs [11, 38]或NSF pilot[22]中应用的序数同行评分方法是一致的。在我们的设置中，位置评分规则由一个评分向量（s1，s2，...，sd）定义。它以代理人的不完整个体排名作为输入，并按照以下方式为备选方案计算分数。每当一个代理人将备选方案排名为第k位时，备选方案就会获得sk个点，其分数是它的总点数。最终排名是通过按照得分的非递增顺序对所有备选方案进行排序获得的。0我们的问题的输入由个人不完整排名的配置文件和希望对备选方案对之间的关系（被认为是潜在真实排名的一部分）以及相应的权重（表示每个关系的重要性）组成。在给定这个输入的情况下，我们希望计算位置评分规则，其结果 - 当应用于配置文件上时 -最大化满足所需的成对关系的总权重。我们将这个看似基本的优化问题称为“优化位置评分规则”（OptPSR）。01.1. 我们的贡献0我们的技术贡献包括OptPSR的理论和实验结果。我们首先提出了一种精确算法，称为Regions，它在时间上的复杂度仅依赖于参数d的指数。因此，当d是常数时，Regions可以在多项式时间内运行。对于具有较高d值的实例，我们有两个近似算法。第一个算法称为BestApproval，它在t-approval投票规则类中搜索（使用由t个1后跟d-t个0组成的评分向量，其中t∈[d]），并返回满足最高总权重约束的规则。BestApproval返回的解至少是1/d-近似的。这意味着满足的约束的总权重至少是任何评分规则可以同时满足的最大总权重的1/d倍。我们通过构造简单的实例来证明我们的分析是紧密的，在这些实例中，任何批准投票规则都是（最多）1/d-近似的。我们还提出了第二个更复杂的近似算法，称为Apx-PSR，它以更好的近似比率实现，但代价是更高的（但仍然是多项式时间）运行时间。在负面方面，我们表明OptPSR不仅在计算上很难（特别是NP-hard）精确计算，而且在近似计算上也是NP-hard的。我们提出了一个明确的近似界限为23/24；我们的证明基于从最大化线性方程组的满足方程数的优化问题MAX-3LIN-2的近似保持约简，并利用了Håstad[21]的著名近似性结果。0此外，我们描述了在许多OptPSR实例上执行评分规则/算法的实验。我们使用了两个我们精心收集的真实世界配置文件，以及通过模拟遵循Bradley-Terry [7]和Plackett-Luce [29,36]噪声模型的排名行为的代理生成的许多合成配置文件。与我们的理论工作相反，它基于最坏情况的假设，我们的实验结果表明，众所周知的评分规则以及我们的算法ApxPSR和BestApproval表现出色，并且几乎恢复了100%的060 I. Caragiannis et al. / 人工智能 267 (2019) 58–770在我们研究的所有场景中，期望的约束条件都得到满足；这正是我们选择首先研究优化问题OptPSR的原因。01.2. 相关工作0社会选择理论传统上假设选民对所有备选方案提供完整的排名（严格的线性顺序）。最近有一些偏离这一传统的尝试。Boutilier和Rosenschein[6]等人讨论了将不完整的排名作为选票的情况。一般来说，这些模型属于以下几个类别。一些论文（例如[4, 17,20]）考虑将选民的排名限制在他们最喜欢的几个备选方案上。其他论文，如本文，考虑将选民的排名限制在任意的备选方案子集上。这些包括[16, 18,39]等论文，其中选民对他们了解的备选方案进行排名。例如，在[18]中，备选方案是网页，选民是不同的搜索引擎，它们不一定完全覆盖整个网络。在上述关于序数同行评分的论文中[3, 10, 11, 24, 34, 38, 40,41]，“选民”被要求对特定的备选方案子集进行排名。从这个意义上说，即使他们原则上有能力评估其他备选方案，但他们从未被要求这样做，因此在他们的排名中不包括它们。在最一般的情况下，每个投票可以是所有备选方案的一个偏序。这包括上述情况以及某些备选方案对之间的关系未给出的情况。Konczak和Lang [23]是第一个在计算社会选择中考虑这种情况的人，随后是Pini等人[35]，Xia和Conitzer [44]等人。0在具有替代方案的偏序作为投票的情况下，与如何将投票扩展到完整排名相关的重要问题。上述提到的论文[23, 35,44]考虑了这样一个问题：是否存在一个偏序投票的扩展，使得给定的替代方案成为获胜者。还研究了一个给定替代方案是否是任何投票扩展中的获胜者的问题。这两个问题引出了优雅的计算问题，非正式地称为可能的获胜者和必要的获胜者。Lu和Boutilier[26]将在不同可能的获胜者之间的选择视为一个鲁棒优化问题，并使用最小最大遗憾的概念来解决它。他们的技术扩展到多个获胜者的确定[27]。然而，所有这些论文都集中在获胜替代方案上，而我们在这里的兴趣是在具有不完整投票的投票规则应用时返回的整个排名。0我们的工作中存在一个基础真实排名的假设。这与社会选择中的一个趋势密切相关，该趋势假设存在一种客观正确的替代方案排名（基本事实），并将选票视为对该排名的噪声估计。在这种情况下，最常见的方法是将投票规则视为最大似然估计器[14,46]，并假设每个选民将基本事实隐式转化为她的投票，遵循特定的概率分布或噪声模型。如果一个投票规则是噪声模型的最大似然估计器，那么当应用于一组投票时，它将返回一个最有可能产生该投票组合的排名或获胜替代方案的结果，假设选民遵循噪声模型。最著名的结果是由Young[46]证明的，他证明了Kemeny投票规则是噪声模型的最大似然估计器，该噪声模型可以追溯到Marquis de Condorcet[15]，今天更为人所知的是Mallows模型[30]。关于MLE方法的最新结果的讨论可以在Elkind和Slinko的章节中找到[19]。其中，Xia和Conitzer[45]以及Lu和Boutilier[28]使用MLE方法应用于具有不完整投票的投票规则。相关的研究方向旨在建立样本复杂性结果。为了以高概率恢复基本事实，需要多少投票（来自给定的噪声模型）？这些论文[9, 12, 13]遵循这个方向。0另一种方法，甚至更接近当前的论文，具有优化的特点。我们小组的关于序数同行评分的论文[10, 11]以及deWeerdt等人的论文[16]旨在确定其结果排名与基本事实排名的期望距离尽可能小的投票规则。一般来说，这些投票规则不是最大似然估计器。与这些论文以及遵循MLE方法的论文相反，在这里我们假设我们可以访问基本事实的部分信息。此外，在我们的理论研究中，我们不利用投票可能是某些基本事实的噪声估计这一事实，而是将其视为任意的；这引发了几个优化挑战。另一方面，我们的实验场景使用基本事实排名和遵循两种众所周知的噪声模型的选民（代理人）。0最后，我们的优化问题OptPSR旨在计算最适合输入的位置评分规则。这在概念上与寻找与给定示例一致的评分规则的学习理论研究相关；例如，参见Boutilier等人的论文[5]和Procaccia等人的论文[37]，它们在其他结果中研究了评分规则的样本复杂性，通过限制其广义维度。与我们的理论研究一样，他们的设置更加通用，不依赖于特定的噪声模型。01.3. 路线图0本文的其余部分结构如下。我们首先在第2节中对 OptPSR 问题进行正式描述，并介绍必要的预备知识，包括定义、示例以及一个朴素的精确算法OptPSR。在第3节中，我们介绍并分析了精确算法 Regions。我们在第4节中介绍并分析了近似算法 BestApproval 和ApxPSR。在第5节中，我们给出了 OptPSR的不可近似性结果的证明。我们的实验结果在第6节中呈现。我们在第7节中讨论了开放问题和可能的扩展。与我们的实验相关的附加材料在附录中给出。I. Caragiannis et al. / Artificial Intelligence 267 (2019) 58–77611x1 ≻ x2 ≻ x6 ≻ x42x3 ≻ x1 ≻ x4 ≻ x22x5 ≻ x6 ≻ x4 ≻ x21x7 ≻ x3 ≻ x4 ≻ x21x5 ≻ x4 ≻ x3 ≻ x63x7 ≻ x5 ≻ x4 ≻ x2scs(x,�) =d�j=1ν j(x,�) · s j.d�j=1δ j(x, y,�) · s j > 0.0表1 是示例1中代理排名的配置文件 � 。这里使用符号 �来表示代理的偏好关系。例如，根据表的第二行，有两个代理将备选项x3 排在第一位，备选项 x1 排在第二位，备选项 x4排在第三位，备选项 x2 排在最后。0代理数 排名02. 问题陈述0我们考虑具有代理集合 N 和备选项集合 A 的设置。代理 i 对备选项集合 A i 表达她的偏好；她的偏好（或投票）是备选项 A i的严格线性顺序（以下简称为排名）。偏好配置文件（或简称为配置文件）�由所有代理的偏好组成。在本文中，我们假设所有代理的偏好中备选项的数量 d ≥ 2 相同，即对于每个代理 i ，有 | A i | = d 。0社会福利函数以配置文件 � 为输入，并输出 A 中所有备选项的排名。位置评分规则（或者简称为评分规则）是一种使用评分向量 s = ( s 1 , ..., s d )的社会福利函数，其中对于 i = 1 , ..., d − 1 ，有 s i ≥ s i + 1 ，且 s d ≥ 0；每个投票中位置 k 的备选项被分配 s k个点数，并且备选项的排名是根据它们的总分（或得分）按照单调非递增顺序进行排序。在接下来的内容中，我们滥用符号s，既指评分向量，也指使用它的相应评分规则。形式上，对于备选项 x ，让 ν j ( x , � ) 表示在配置文件 � 中将 x 排在位置 j的代理数量。然后，给定评分规则 s ，备选项 x 的得分定义为0我们注意到，这个得分定义没有考虑到备选项 x 的受欢迎程度（即，x 在配置文件的排名中出现的次数）。另一种定义将得分归一化，通过将 x在配置文件中出现的次数进行除法运算。我们之所以选择当前的定义，仅仅是为了概念验证的目的。0我们还假设我们可以访问一组约束 C ，表示我们对备选项之间的一组有序关系的（可能是部分）了解。C 中的每个约束由备选项的有序对 ( x , y )组成，并要求备选项 x 在评分规则 s 的结果中排名高于备选项 y 。对于备选项对 ( x , y ) ，令 δ j ( x , y , � ) = ν j ( x , � ) − ν j ( y , � )。现在，观察到，为了使备选项 x 在最终排名中确定地排在 y 之上，必须满足 sc s ( x , � ) > sc s ( y , � ) ，等价地，0使用 δ ( x , y , � ) = (δ 1 ( x , y , � ), ..., δ d ( x , y , � )) ，上述表达式可以简洁地写成点积 δ ( x , y , � ) ∙ s > 0。为了我们的目的，我们不再将配置文件 �视为代理提供的排名集合，而是使用数量 δ ( x , y , � ) 来描述它，其中 ( x , y ) 在 C 中的每个约束都使用这些数量；我们使用符号 δ ( � )来表示这些数量的集合，并简称为配置文件。每个约束 ( x , y ) ∈ C 都有一个相应的非负权重 w ( x , y ) ，表示约束的重要性。0现在，OptPSR问题（代表“优化位置评分规则”）的定义如下。我们给定一个概要δ(�)和一组约束C。OptPSR的目标是找到一个评分规则s，以便产生对所有备选方案的排名，使得总权重（或收益）0g(s,δ(�),C) = �0(x,y)∈C w(x,y)∙1{δ(x,y,�)∙s>0}，0满足的约束数量最大化。当X为真时，1{X}的值为1，否则为0。0示例1.考虑十个代理，一个由七个备选方案A={x1,x2,x3,x4,x5,x6,x7}组成的集合，出现在表1中的大小为d=4的排名概要，以及出现在表2中的约束以及相应权重和表示δ(�)的表示。Let us now give an equivalent view of OptPSR. A scoring rule s can be thought of as a point in R , and, in particular,in the region R0 of Rd formed by the inequalities si − si+1 ≥ 0 for i = 1, ..., d − 1 and sd ≥ 0 that define all valid scoring vectors. We can define subregions of R0 by considering any subset C′ ⊆ C of constraints and the inequality δ(x, y, �) · s > 0for every constraint associated with the pair of alternatives (x, y) ∈ C′ and the inequality δ(x, y, �) ·s ≤ 0 for every constraint (x, y) ∈ C \ C′. In this way, the collection of all subsets of constraints in C partition R0 into disjoint subregions; of course, some of them may be infeasible. Hence, in order to maximize g(s, δ(�), C), it suffices to find any point s in the non-empty subregion of Rthat satisfies the subset of constraints with maximum total weight.062 I. Caragiannis等/人工智能267（2019）58-770表2中给出了约束、相应权重、使用数量δ(x,y,�)的概要的备选方案表示以及示例1中使用的引发不等式。例如，权重为4的第一个约束要求备选方案x1在最终排名中出现在x2之上。根据表1中的概要�，由于有两个代理将备选方案x1放在第二位置，而只有一个代理将备选方案x2放在第二位置，我们有δ2(x1,x2,�)=1；可以轻松验证表中其余值。给定这些数量，不等式是由于δj(x1,x2,�)对于j∈[4]是分配给位置j的点的变量sj的系数。0约束 权重 δ1(∙,�) δ2(∙,�) δ3(∙,�) δ4(∙,�) 不等式0(x1,x2) 4 1 1 0 −8s1 + s2 − 8s4 > 0 (x4,x5) 2 −3 −2 8 1 −3s1 − 2s2 + 8s3 + s4 > 0 (x3,x4) 3 2 0 −7 −1 2s1 − 7s3 − s4 > 0 (x4,x6) 2 0 −1 7 0 −s2 + 7s3 > 0 (x3,x2) 1 2 0 1 −8 2s1 +s3 − 8s4 > 00表3中给出了示例1中考虑的位置评分规则及其相应的总收益。0规则 评分向量 收益0opt(4,4,1,0) 10 Borda count(3,2,1,0) 7 1-approval(1,0,0,0) 82-approval(1,1,0,0) 8 3-approval(1,1,1,0) 9 4-approval(1,1,1,1) 40首先，观察到前三个约束不能同时满足；这很容易看出，因为将相应的不等式相加得到−s2 + s3 − 8s4 > 0，这与s2 ≥ s3和s4 ≥0相矛盾。因此，在最好的情况下，最优评分规则可以满足除前三个约束中权重最小的约束之外的所有约束。这样一个评分规则使用评分向量(4,4,1,0)，满足所有约束，除了第二个约束，总收益为10。相比之下，著名的评分规则，如使用评分向量(3,2,1,0)的Borda计数和使用t-approval规则（其中t∈[4]）的评分规则，其评分向量为t个1后跟4-t个0，满足总收益为7、8（对于t=1）、8（对于t=2）、9（对于t=3）和4（对于t=4）的约束；另请参阅表3。20为此，我们可以枚举C的所有约束子集，使用线性规划检查相应区域的可行性，并报告子区域中产生最大收益的任何点。假设该算法接收δ（�）和C作为输入，它的运行时间在2 | C |和d中是多项式的。实际上，参数d（即输入排名的大小）预计是一个小常数，而备选方案的数量和因此约束的数量| C|将会更大得多。因此，以| C|为指数运行时间的算法显然是不切实际的。在下一节中，我们将介绍一种使用更聪明的可行子区域枚举的算法，以获得产生最大收益的子区域。03. 一种改进的OptPSR算法0我们将介绍另一种（精确的）OptPSR算法，称为Regions。其运行时间仅在参数d上呈指数级增长，因此当d是一个常数时，它是多项式的。我们注意到，这种时间复杂性只在理论上有趣。正如我们稍后在第6节中描述我们的实验时提到的，即使d很小（比如等于6），该算法在约束的数量上也无法很好地扩展。0Regions计算R0的非空子区域池，每个子区域满足不同的约束子集。初始时，池中只包含区域R0，并在考虑新的约束条件C时进行更新。当考虑新的约束条件时，池中的每个区域可以分为满足约束条件和不满足约束条件的两个子区域。当区域的所有点都满足约束条件或区域的所有点都不满足约束条件时，该区域不会被分割，并且作为整体保留在池中。0特别地，该算法逐个考虑C的约束条件。在每个步骤t中，保持一个区域池P；在每个步骤开始时，池中的所有区域都是活动的。对于P中的每个区域R，算法保持通过已考虑到步骤t并且满足区域R的评分向量的约束所获得的增益val（R）。算法在池中只有区域R0时开始执行。当考虑到新的约束条件（x，y）并且权重为w（x，y）时0I. Caragiannis等/人工智能267（2019）58-77 630，算法尝试更新P中的每个活动区域R，如下所示。它定义候选区域Rxy和R¬xy，使得0• Rxy由形成R的不等式和不等式δ（x，y，�）∙s>0（定义满足约束（x，y）的点集）定义，以及0• R¬xy由形成R的不等式和不等式δ（x，y，�）∙s≤0（定义不满足约束（x，y）的点集）定义。0如果Rxy和R¬xy都不为空（即，对应的不等式集合是可行的），算法将包括Rxy和R¬xy。0并将P中的Rxy和R¬xy设置为非活动状态，将它们的增益val（Rxy）：= val（R）+w（x，y）和val（R¬xy）：=val（R）设置为val（R）并从池中删除区域R。如果只有Rxy是可行的（而R¬xy是不可行的），则val（R）增加w（x，y)。如果只有R¬xy是可行的（而Rxy是不可行的），算法不执行任何操作。在最后两种情况下，不会向池中添加新的区域。显然，Rxy和R¬xy都不可行的情况是不可能的。同样，可以通过解决具有d个变量和最多| C|个约束的线性规划来高效地检查可行性。在步骤t结束时（即，池中没有其他活动区域需要考虑时），非活动区域变为活动区域，算法继续进行t +1步。当考虑到C的所有约束条件时，算法计算具有最大val（R�）的活动区域R�并返回R�中的任何评分向量。算法的伪代码描述如算法1所示。0Algorithm 1：Regions。0输入：参数d，配置文件δ（�），约束集合C输出：得分向量s=（s1，...，sd）R0：={s1≥s2，...，sd-1≥sd，sd≥0}val（R0）：= 0P：={R0}for（x，y）∈C do0active：= P for R ∈active do0active：= active \ {R}R xy：= {R，δ（x，y，�）∙ s >0}R ¬ xy：= {R，δ（x，y，�）∙ s ≤ 0}if R xy 可行且R ¬ xy 可行 then0val（R xy）：= val（R）+w（x，y）val（R ¬ xy）：=val（R）P：= {P \ {R} ∪ {R0else if R xy 可行且 R ¬ xy 不可行 then0val（R）：= val（R）+w（x，y）0结束0结束0结束R *：= arg max R ∈ P{val（R）}return s ∈ R *0例2. 我们将通过一个简单的例子来说明 Regions 在具有备选项 x1，x2，x3，y1，y2 和 y3 以及 d = 2 的配置文件 � 上的工作原理（见图1）。集合 C有三个约束条件（x1，y1），（x2，y2）和（x3，y3），对应的权重分别为3，1和2。配置文件的特征是δ（x1，y1，�）=（-7，2），δ（x2，y2，�）=（4，-2），δ（x3，y3，�）=（-2，3）。因此，约束条件定义了不等式 -7s1 + 2s2 > 0，4s1 - 2s2 > 0和 -2s1 + 3s2 > 0。0现在，算法的步骤如下。最初（见图1a），算法具有区域R0，由线s2 = 0和s1 - s2 =0定义，其增益为0。在下一步（见图1b）中，算法考虑约束条件（x1，y1），并用区域R1 = Rx1y10和R2 =R¬x1y10替换R0；R1是满足第一个约束条件且增益为3的R0的子区域，而R2是不满足第一个约束条件且增益为0的R0的子区域（线-7s1+ 2s2 =0将两个子区域分开）。接下来（见图1c），约束条件（x2，y2）使得区域R1和R2都留在池中，并将它们的增益都增加1。最后（见图1d），第三个约束条件（x3，y3）用区域R3 = Rx3y31和R4 =R¬x3y31替换区域R1；R3是满足约束条件且增益等于6的R1的子区域（R1的增益增加了约束条件的权重），而R4是不满足约束条件且增益为4（与R1相同）的R1的子区域。注意，在最后一步中，区域R2也满足第三个约束条件，因此其增益也增加了2。具有最大增益的区域是R3，算法将输出该区域中的某个得分向量。0接下来，我们证明我们改进的 OptPSR 算法是正确的，并且其运行时间仅依赖于参数 d 的指数。0定理1. 给定 OptPSR 的一个实例，其中参数d，约束集合C和配置文件�，算法Regions在时间O（|C|d∙poly（|C|，d））内正确返回一个解。64I. Caragiannis et al. / Artificial Intelligence 267 (2019) 58–770图1. 在具有d =2的配置文件�上执行Regions的示例。子图（a）-（d）描述了逐步考虑约束条件以及如何更新活动区域。在每个子图中，蓝线对应于考虑的新约束条件。在子图（b）-（d）中，+和-标记了蓝线定义的两个子区域中满足约束条件的向量和不满足约束条件的向量。用+标记的子区域的增益增加了约束条件的权重（较深的灰色表示较高的增益）。子图（e）描述了区域池的内容及其相应的增益的演变。具体来说，树的每个级别中的节点表示算法的每个步骤中池的内容和相应的增益。（有关图中颜色的解释，请参阅本文章的网络版本。）0证明。算法的正确性应该是显而易见的。它考虑了Rd中对应于得分向量的所有（子）区域，并将其划分为同时满足的约束的包含最大子集定义的所有（子）区域。在所有这些区域中，它找到了那些对应于满足C约束的得分向量的点的区域，其总权重最大。0当考虑C的最后一个约束时，将R0扩展为池中的区域可以被视为一个非完全二叉树T，其中节点对应于区域（见图1e的示例）。T以对应于R0的节点为根，并且对于每个处于t-1级的节点，对应于区域R，如果区域R在步骤t被分割并替换为两个子区域，则在级别t有两个子节点，否则有一个子节点（表示该区域在步骤t期间保留在池中）。找到所有区域所需的总时间与T的大小成比例。由于所有非叶节点至少有一个子节点，T的大小最多是其高度|C|乘以叶子节点的数量。叶子节点的数量为t = 1, ..., K , we set δi(xt, yt, �) = −D, δi+1(xt, yt, �) = D + 1, and δ j(xt, yt, �) = 0realized as follows. Alternative xt appears D times in position i and alternative yt appears D + 1 times in position i + 1; again, all other positions are filled with additional alternatives that do not appear in the constraints of C. Observe that the definition of D implies that δ(xt, yt, �) · s = −si D + si+1(D + 1) < 0, i.e., s does not satisfy any constraint. In contrast, the (i + 1)-approval vector s∗ (consisting of 1s in the first i + 1 positions and 0s in the remaining ones) satisfies all constraints of C.0I. Caragiannis等人/人工智能267（2019）58-77 650实际上是不同非空区域的数量，其上限由每个约束（x，y）在C中定义的数量δ(x，y，�)∙s的不同符号模式的数量限制。由于这些|C|个数量是向量s的d个坐标上的线性函数，Alon的结果[1]（也参见Warren [43]）表明不同符号的总数0模式的数量最多为�8e|C|0d×d。对于T的每个节点，可以通过解决两个具有d个变量和最多d个约束的线性规划来检查可行性。0在时间复杂度为poly(|C|,d)的情况下，最多有|C|个变量和|C|个约束。定理得证。20根据定理1，我们得到以下推论。为了比较，前一节末尾提到的朴素算法在|C|至多对数级别的d的非常特殊情况下是多项式时间的。0推论2. 算法Regions在多项式时间内解决了参数为常数d的OptPSR实例。04. 近似OptPSR0由于精确算法Regions在前一节中的运行时间取决于d的指数增长，因此我们的目标是设计更快的（即多项式时间）算法来计算近似的OptPSR解。给定一个OptPSR实例，参数为d，配置文件为�，约束集合为C，令s�是满足C约束的得分向量，其总权重最大。对于特定实例，得分向量s是ρ-近似解，其中ρ∈[0,1]，如果g(s,δ(�),C)≥ρ∙g(s�,δ(�),C)，即s满足的约束的总权重至少是s�满足的约束的总权重的ρ倍。如果算法对于OptPSR的每个实例都计算出ρ-近似解，则称该算法为ρ-近似算法。我们将ρ称为算法的近似比。理想情况下，我们希望设计尽可能高效的近似算法，即多项式时间运行且具有尽可能高的近似比。0让我们先观察到单个位置评分规则（例如Borda、多数派、k-approval）不能作为高效的近似算法，因为它的近似比为0。这在下一个引理中说明。0引理3.设d是一个正整数。对于每个得分向量s∈Rd≥0，其中s1≥...≥sd，存在一个OptPSR实例，参数为d，配置文件为�，约束集合为C，使得s是0-近似的。0证明。显然，得分向量s =(0，...，0)不满足任何约束。因此，在接下来的讨论中，我们假设s1>0。对于任何正整数K>0，我们将构造一个由不相交的替代对（xt，yt）组成的约束集合C，其中t =1，...，K。我们将根据s的结构区分两种情况。对于每种情况，我们将构造一个OptPSR实例（由适当定义的配置文件和约束集合C组成），其中s不满足任何约束，而另一个得分向量s�满足所有约束。0如果s1=...=sd>0，则对于每个约束(xt,yt)，我们设置δ1(xt,yt,�)=1，δ2(xt,yt,�)=−2，并且对于j=3,...,d，设置δj(xt,yt,�)=0。概要�可以如下实现。替代方案xt在位置1出现一次，替代方案yt在位置2出现两次；所有其他位置都填充有不出现在约束C中的其他替代方案。观察到对于每个t=1,...,K，δ(xt,yt,�)∙s=s1−2s2<0，即s不满足任何约束。相反，多数规则向量�=(1,0,...,0)满足C的所有约束。0对于每个约束(xt,yt)0在这两种情况下，评分向量s是一个0-近似解。20我们得出结论，高效的近似算法应该考虑许多候选评分向量，并选择最适合给定OptPSR实例的向量。这是算法BestApproval和ApxPSR在4.1和4.2节中所遵循的方法。04.1.使用批准评分向量近似OptPSR0我们将展示一个非常简单的算法，它检查一组简单的评分向量并返回其中最好的向量，从而实现了一个1/d近似解。具体来说，对于t∈[d]，t-approval规则是一种位置评分规则，它使用评分向量在前t个位置上为1，在其余位置上为0。我们的算法称为BestApproval，它考虑所有的t-approval规则，并返回满足最大总权重约束的规则。BestApproval的伪代码描述如算法2所示。Xk =(x, y) ∈ X :δ j(x, y,�) > 0g(k,δ(�), C) ≥�(x,y) Xw(x, y) ≤Xw(x, y) ≤w(x, y) ≤066 I. Caragiannis et al. / 人工智能 267 (2019) 58–770算法2：BestApproval。0输入：参数d，概要δ(�)，约束集合C输出：t�-approval规则，其中t∈[d] do0t:=(1,...,1,����0g(t,δ(�),C):=∑(x,y)∈Cw(x,y)∙1{δ(x,y,�)∙t>0}0end return t�∈arg max t{g(t,δ(�),C)}0通过以下两个定理，我们证明BestApproval是OptPSR的一个1/d-近似算法（定理4），并且进一步通过提供一个特定实例证明了该界限是紧的，对于任何t-approval规则都是（最多）1/d-近似解（定理5）。0定理4.对于给定参数d的OptPSR实例，约束集合C和概要�，算法BestApproval返回一个1/d近似解。0证明。为了证明近似比的界限，我们将展示存在某个t∈[d]，使得相应的t-approval
我的内容管理
展开
