社会选择、匹配和设施选址问题的序近似

ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月F一F给定候选位置ELLIOT ANSHELEVICH和WENNAN ZHU，伦斯勒理工学院9在这项工作中，我们考虑一般的设施位置和社会选择问题，其中代理和设施位于度量空间中，我们的目标是将代理分配给设施（以及选择打开哪些设施）以优化社会成本。我们形成了新的算法，在只存在序数信息的情况下做到这一点，即，当代理人到设施的真实成本或距离未知，并且只有代理人对设施的顺序偏好可用时。我们的工作和以前的工作在这方面的主要区别是，虽然我们假设，只有序数信息代理的偏好是已知的，我们也知道可能的设施的确切位置。由于这些额外的信息，我们能够形成具有小失真的强大算法，即，执行几乎以及全知算法（知道代理和设施之间的真实数字距离），但只使用有关代理偏好的顺序信息例如，我们提出了自然的社会选择机制，选择一个单一的设施开放，失真最多为3，以最小化总成本和社会成本的中位数;这个因素是可以证明的最好的可能。我们分析了许多一般问题，包括匹配，k-中心和k-中位数，我们提出了从具有近似因子β的全知近似算法到具有近似因子1+ 2β的有序算法的黑盒约简，从而为许多重要问题提供了新的有序算法，并为将来分析此类问题建立了一个工具箱CCS概念：·计算理论→算法的设计和分析;附加关键词和短语：社会选择，匹配，失真，顺序信息，近似算法，设施位置ACM参考格式：Elliot Anshelevich和Wennan Zhu。2020年。给定候选位置的社会选择、匹配和设施选址问题的序近似ACM Trans. 经济Comput. 9，2，第9条（2021年1月），24页。https://doi.org/10.1145/34344171介绍许多重要的问题涉及到将代理分配给设施。例如，将病人分配到医院，将学生分配到大学，将人们分配到房屋等等，指派问题的目标通常是社会成本最小化或社会福利最大化。当我们考虑分配问题的社会成本时，很自然地假设代理人更喜欢“接近”的设施这项工作得到了NSF Award No.的部分支持CCF-1527497。作者Anshelevich和W.朱，伦斯勒理工学院，110第8街，特洛伊，纽约，12180;电子邮件：eanshel@cs.rpi.edu，zhuw5@rpi.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020计算机协会。2167-8375/2020/01-ART9 $15.00https://doi.org/10.1145/3434417ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月九：2E. Anshelevich和W.朱F一F因此，代理的成本通常由代理与其所分配的设施之间的距离表示除了距离的成本，还有许多其他的成本函数和约束不同的问题，例如，在容量限制的设施分配问题，每个设施有一个最大数量的代理，它可以容纳。在这项工作中，我们考虑一般的设施选址问题，其中代理和设施位于一个度量空间，我们的目标是分配代理设施（以及选择哪些设施开放），使代理被分配到设施，靠近他们。例如，可能包括开设新店的可能位置，目标可能是所有代理都在附近有一家商店，或者代理到他们被分配到的商店的距离之和很小，等等。此设置还捕获了许多社会选择问题，其中设施对应于候选人，目标是选择单个候选人（并将所有代理分配给该候选人），以便代理与所选候选人的距离很小。这里，距离对应于空间偏好，即，度量空间代表意识形态空间，在这个空间中，更受欢迎的候选人将更接近代理人;参见参考文献[4，24]，讨论社会选择中的这种空间偏好。我们的设置还捕获匹配和许多相关问题，其中我们将打开所有设施，但只能为每个设施分配一个agent，从而形成agent和设施之间的匹配;例如，这里的设施可以对应于房屋或物品。如果代理和设施之间的距离是已知的，那么我们可以计算出最佳解决这些分配问题。注意，许多设施选址问题是NP完全的，但至少可以在给定无限计算资源的情况下计算代理对设施的最优分配（或选择用于社会选择设置的最优候选者）。然而，对于我们上面提到的许多设置，我们不太可能知道代理与设施的确切距离。对于社会选择，这些距离将对应于选民对候选人的基本偏好，例如，更常见的是，只有代理对候选人的顺序偏好是已知的，即，“我喜欢X胜过Y”类似地，当试图形成匹配时，或者甚至在我们调查代理以找出他们的偏好的一般设施定位问题中，与精确的数字偏好相比，更容易得出顺序偏好（这些观察最近导致了大量的工作使用功利主义的方法，其中我们假设存在一些潜在的数字成本或效用，但我们只知道代理人的顺序偏好，而不是他们潜在的数字成本。例如，参见参考文献[4，6，16，21，28，33，45]中的社会选择设置，参见参考文献[1，7- 9 ]中的匹配和其他图形问题，以及参见参考文献[ 18 ]中这些工作的重点是测量各种算法的失真：一种衡量算法在只使用序数信息时的表现如何的方法，与能够访问真实底层数值信息的最佳算法相比。更正式地说，分配的失真[4，44]被定义为最坏情况下的社会成本与最优解的社会成本之比。在上面提到的工作中，我们假设只有序数信息代理和设施之间的距离是已知的。然而，虽然代理人的位置和数量偏好通常很难获得，但设施的位置大多是公开信息。政治候选人在意识形态空间中的位置可以根据他们的投票记录和公开声明进行合理的估计。当形成关于新开商店的调查时，我们可能不确切地知道顾客会在多大程度上喜欢一个商店而不是另一个商店，因为顾客位置可能是私人的，但是可能的商店的位置本身是公共知识。我们的工作和以前的工作在这个领域的主要区别是，我们假设：社会选择和其他问题的序近似九：3ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月AF虽然只知道关于代理偏好的序数信息，但我们知道可能设施F的确切位置。正如我们下面讨论的，关于设施相对于彼此的位置的额外信息使我们能够产生更强大的算法，并显示更好的失真范围请注意，这些信息可能在其他相关论文的背景下提供，但没有被明确利用。事实上，在很多情况下，我们甚至不需要有关设施位置的全部资料这篇文章的主要信息是，有少量的信息，候选人在社会选择设置，或设施的设施位置，使我们能够获得解决方案，证明是接近最优的一大类问题，即使我们唯一的信息，代理的偏好是有序的，因此它是不可能的（即使给定无限的计算资源）计算真正的最优解。我们的贡献。我们首先来看看社会选择的设置，在其中我们有一套n代理m候选人在度量空间中，我们给出了每个代理人都是候选人。这种设置被认为是在，例如，参考文献[4、6、21、28、33、35、45]。特别地，为了最小化代理与所选候选人的总距离，参考文献[4]表明Copeland和类似的投票机制总是具有至多5的失真最近的一篇论文给出了最著名的确定性算法[42]失真为4.236。虽然参考文献[4]表明没有确定性投票机制可以实现小于3的最坏情况失真，但关闭上界和下界仍然是一个悬而未决的问题。在这篇文章中，我们表明，如果我们知道候选人的确切位置， 除了代理的顺序排序之外，还有一个简单的算法，它实现了3的失真，并且没有更好的界限是可能的。换句话说，虽然我们不知道从代理到候选人的真实距离，但无论真实距离是多少，只要它们与给定的序数偏好一致，我们都可以计算出一个3近似的结果。此外，这种近似是可能的，即使对于每个代理，我们只给出他们的最爱（即，最佳选择）候选：代理不需要提交对所有备选方案的完整偏好等级。我们还研究了其他的目标函数，除了最小化总距离代理所选择的替代品。我们给出了一个自然的确定性投票机制，具有失真对于诸如最小化中间投票者成本、最小化最大投票者成本的平等主义目标以及许多其他目标，最多3。这种机制同时实现了所有这些近似保证，而且它不需要候选人的确切位置：它足以给出每个候选人到每个其他候选人的距离的顺序排名。换句话说，这种机制特别适合候选人是投票者子集的情况，因为我们的机制将获得每个投票者对所有候选人的顺序排名，这是唯一需要的信息。注意，参考[4]证明了没有一种确定性机制可以为中位数目标实现比5更好的失真;我们能够在这里实现失真3的原因正是因为我们还知道每个候选人如何排名所有其他候选人，以及每个选民如何排名所有候选人。然后，我们继续我们的一般设施分配模型。我们在度量空间中给出一组代理和一设施之间的距离是给定的，但代理和设施之间的距离是未知的;相反，我们只知道代理对设施的顺序偏好，这些偏好与真实的底层距离一致。在分配上可能存在任意约束，例如设施容量，或强制某些代理不能（或必须）分配给同一设施的约束，等等。有效的分配是在不违反约束的情况下将每个代理分配给设施我们考虑了许多不同的社会成本九：4E. Anshelevich和W.朱ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月表1.多项式时间算法在不同环境下的最佳已知失真无所不知：全程座席和设施位置仅座席prefs（下限）社会选择总数134.236（3）社会选择13第五章最小权二分匹配13n（3）平均二分匹配13- （2）设施选址1.488 [40]3.976∞（∞）k-中心第二章[36]5- （-）k-中位数2.675 [17]6.35- （Ω（n））“Omniscient”第二列表示我们的设置，其中代理的顺序偏好和设施之间的数值距离是已知的。最后一列表示纯序设置，其中只有代理的顺序偏好是已知的，但设施之间的距离是未知的;这种设置以前已经研究过，我们在括号中包括已知的可能失真的下限，包括我们在附录中证明的一些。功能优化。对于一般类型的成本函数（本质上是单调和次加性的），我们给出了一个黑盒约简，将该问题的全知版本的算法（即，真实距离已知的版本）到具有小失真的有序算法。具体来说，如果我们有一个全知算法，它总是产生一个最优的β-近似分配，那么使用它，我们可以创建一个序数算法，它只知道代理的序数偏好，而不是他们到设施的真实距离，但失真最多为1+ 2β。许多著名的问题都属于我们的设施分配模型;表1总结了我们的一些结果。例如，经典的设施选址与设施成本，最小权重二分匹配，平均二分匹配，k-中心，和k-中位数都是特殊情况。特别是，我们的研究结果表明，如果我们被赋予无限的计算资源，那么它总是可以形成一个分配与失真最多为3这些问题，没有更好的界限是可能的，仅仅是因为我们不拥有所有的相关信息来计算真正的最优。这是对以前已知的失真界限的一个很大的改进：对于最小成本有序匹配，最知名的失真界限是使用随机序列独裁的n[18];通过使用设施位置的知识，我们能够将这个近似比降低到3。讨论及相关工作。在许多环境中，包括社会选择[4，6，11，13，15，16，19，21，25，28，30，31，33，38，39]，研究了最小社会成本（或最大社会福利）与代理和替代品之间的潜在效用/距离的有序近似。41，43序数设置的一般假设是，我们只有代理人对备选方案的序数偏好，目标是形成一个具有接近最优社会成本的解决方案有不同的模型：社会选择、匹配、设施位置等;不同的目标：社会成本最小化、社会福利最大化、总成本目标、中位数目标、平均主义目标等;对效用或成本函数的不同假设：单位和、单位范围、度量空间等。在这篇文章中，我们研究了度量空间中的一般设施分配问题，并假设代理人对备选方案的顺序偏好是给定的。与以前的工作不同，这个主题，我们还假设的替代品的位置是已知的，我们表明，这些额外的信息使我们能够实现更好的近似比在纯序数设置的许多问题。社会选择和其他问题的序近似九：5ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月−社会选择函数的失真首先在参考文献[44]中引入，以描述最优候选者的总效用与仅使用顺序偏好的机制选择的候选者之间的比率。参考文献[4，33，45]研究了度量空间中社会选择函数的扭曲;假设潜在的数值成本具有这种度量属性，可以得到比更一般的成本更好的结果。特别是，为了最小化所选候选人的代理总数，上述论文能够为许多众所周知的机制显示良好的失真界限，特别是Copeland [4]的界限为5，Single Transferable Vote（STV）[45]的界限为O（ lnm）此外，参考文献[4]证明，没有确定性机制可以具有优于3的最坏情况失真，并且参考文献[45]表明，针对m个候选者的所有评分规则具有至少1+ 2平方米 。Abramowitz等人[2]研究了在一个度量中选民偏好强度的失真空间和Amanatidis等人[3]也研究了单位和或无限制效用函数的偏好强度。Goel等人。[33]表明，排名配对和Schulze规则的最坏情况失真至少为5，并且任何（加权）锦标赛规则的预期最坏情况失真至少为3。他们还引入了社会选择规则的“公平”概念，讨论了Copeland的公平比率，随机独裁，一类一般的成本函数，并研究了最近，Munagala etal.[42]提出了一种确定性算法，将失真提高到4.236，这是最知名的方法。在这篇文章中，我们表明，如果我们知道候选人的确切位置，除了顺序排名的代理，那么有一个简单的算法，实现失真3，没有更好的界限是可能的。虽然上述工作以及我们的文章仅关注确定性算法，但也考虑了社会选择中随机算法的扭曲，例如，参考文献[6，26，28，35]。参考文献[20，21]考虑了从选民集中随机独立抽取候选人的特殊情况，结果略有不同虽然我们将知道设施位置的随机算法的分析留给未来的工作，并考虑最坏情况下的候选位置，但值得指出的是，我们的确定性算法实现了3的失真，这也是任何只知道代理的顺序偏好的随机机制的最佳已知失真范围类似地，另一个共同的目标是形成匹配和社会选择的失真小的真实机制，如参考文献[8，18，28];我们在本文中关注一般机制，以了解只知道某些种类的序数信息的局限性，并将形成真实机制的目标留给未来的工作。对于社会选择问题的中位数目标，参考文献[4]表明，Copeland给出的失真最多为5，而没有确定性机制可以实现优于5的失真。参考文献[6]也给出了一个随机算法，其失真最多为4。在本文中，我们能够通过确定性机制将此约束改进为最坏情况下的扭曲3，因为我们还知道每个候选人如何对所有其他候选人进行排名，以及每个选民如何对所有候选人进行排名。在度量空间中匹配的失真受到的关注远远少于社会选择问题。参考文献[7-这与我们计算最小成本匹配的目标非常不同，对于最小成本匹配，没有比Ω（n）更好的序数近似。文献[18]研究了度量空间中的设施分配问题，考虑了有无资源增广的情况，而无增广的情况正好是最小权二部匹配问题。参考文献[18]表明，随机序列的近似比九：6E. Anshelevich和W.朱ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月−2D.一.A∈AF{}A{}∈S>S F ∈ AA ≤ F →≥∈A独裁（RSD）是最多的n，并给出了一个下界2 n 1的近似比串行独裁（SD），和一个下界n0。26个是RSD。他们的结果是最有名的ordinal近似这个问题。在这篇文章中，我们能够给出一个紧密的3-近似的最小权重匹配问题，除了代理的顺序偏好的设施的位置2社会选择机制的扭曲对于本文研究的社会选择问题，我们设= 1，2，.。，n是一组代理，设=F1，F2，.，F m是一组备选方案，我们有时也将其称为候选或设施。我们通常使用i和j来指代代理，W、X、Y、Z来指代备选方案。让是选择集上的全序集. 每一个特工有一个偏好排序σ;通过X iY，我们将意味着X在排序σ中优先于Y。虽然我们假设每个代理人都有一个总的优先顺序的替代品，这个顺序是已知的，我们的许多结果，它只需要每个代理人的首选是已知的。 我们说X是i的最佳选择，如果我在F中更喜欢X。 我们称向量σ =（σ1，. ，σ n）∈ Sn是一个偏好剖面. 我们说，一个替代X两两击败Y，如果|{i∈ A：X>iY}|>n. 我们的目标是选择一个单一的获胜选择。基本公制成本。在这项工作中，我们采取功利主义的观点，并假设顺序偏好σ来自潜在的（潜在的）基数代理成本。形式上，我们假设存在一个任意的度量d：（）2R0的代理和替代品的集合。的代理i因选择备选方案X而产生的成本由d（i，X）表示，它是i和X之间的距离。这样的空间偏好是相对常见的并且动机良好，参见例如参考文献[4，24]和其中的参考文献。潜在的距离d（i，X）是未知的，但与大多数以前的工作不同，我们假设备选方案之间的距离是给定的。两个备选方案X和Y之间的距离由4（X，Y）表示。度量成本d自然会产生偏好概况。我们说d与σ相容，如果我、X为oh，如果d（i，X）iX，则d（i，X）≥d（X，W） [参考文献5][4]]。算法1：社会总成本最小化算法。输入：代理= 1，2，.，n，备选项=F1，F2，.，Fm，每个代理i的最佳选择方案，备选方案之间的距离，即，4（Y，Z），Y，Z输出：获胜的备选方案W。生成代理i的投影集合：对于每个代理i，在度量空间中交替地在i的最佳选择的位置处创建代理i，并且指定新代理i的集合i=1i，2i，. . ，n. 对于每个备选方案X，通过选择X来计算总的社会成本，即， SC（X，λ）=λxrd（i）=最终输出：返回具有最小社会成本SC（W，A）的方案W。在算法1中，我们生成一组投影代理，如下所示：和偏好曲线σ，对于每个代理i，表示备选方案X作为i然后，我们在度量空间中的X i的位置处创建一个新的agent i，如图1（a）所示;因此，对于每个Y∈F，d（i，Y）=d（Xi，Y）。将新函数的集合定义为A={1，2，. . ，n}。对于任何与4一致的度量d，d（i，Y）=d（Xi，Y）=4（Xi，Y），因此A中的主体与F中的替代物之间的距离是已知的，而不像A与F之间的真实距离。九：8E. Anshelevich和W.朱ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月A...∈A∈A≤∈ASC. （W，A）=.i∈Ad（i，W）=.i∈Ad（i≠，W）≤1.（=i∈Ad（ i， i∈D）.i∈Ad（i，X）+i ∈A d（i ∈，W）.（二）.i∈Ad（i，X）id（i，X）i图1.一、（a）对于每个代理，在其首选备选方案的位置生成一个预计代理（b）一幅图，展示了用于证明定理2.2的代理人i、i的最佳选择方案Y、i的位于Y的投影代理人i、获胜者W和最佳方案X。第2.2节. 算法1在A上的最小社会总成本的失真最多为3。P屋顶。 让W表示获胜的选择。W在代理集如果您有任何其他选择，SC. （Y，A）.i<$∈A<$d（i<$，Y）.i∈Ad（i∈Y）令X表示的真正的最优方案。我们想通过上界W相对于X的成本来得到dist（W，σ，l）：SC. （W，A）=SC. （X，A）≤i∈Ad（i，W）id（i，X）i∈A（d（i，i∈）+d（i∈，W））..i∈Ad（i，X）不等式d（i，W）d（i，i）+d（i，W）是三角不等式的结果，因为d是一个度量，如图1（b）所示。i，我们知道i的位置是ii和i之间的距离必须小于（或等于）i和任何备选项之间的距离;因此，d（i，i∈ X）≤d（i，X）. 对所有i∈A求和，我们得到。.i∈Ad（i，i∈ D） ≤1。对于任何代理i，使得X不d（i，X）=d（X，Y）.根据引理2.1，d（i，X）≥d（X，Y），因此d（i，X）≥d（i，X）。对于所有的i，社会选择和其他问题的序近似九：9ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月2X是i2˜2choice，d（i≠，X）= 0，所以不等式d（i，X）≥ d（i，X）对所有i ∈ A成立。与不等式1九：10E. Anshelevich和W.朱ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月2SC. （W，A）≤1+。i∈Ad（i∈，W）=1+2.i∈Ad（i∈，W）≤3.□A∈AA图二、 例如，随着代理人的首选和替代品之间的距离，中位数目标的失真为5。和2，SC. （X，A）.i∈Ad（i，X）2.i∈Ad（i∈X）2.2社会成本中位数的扭曲在本节中，我们研究了中位数目标函数，并提供了一个确定性机制，使失真最多为3。回想一下，我们将替代方案X的社会成本中位数定义为SCmed（X，）=medi（d（i，X））。我们将其称为med（X），当d和都是固定的如果n是偶数，那么我们将中位数定义为距离的第（n+1）注意，没有一个只知道顺序偏好的确定性机制可以具有优于5的最坏情况失真（参考文献[4]中的定理25）。在已知候选者之间的距离的情况下，我们能够提供失真为3的自然社会选择函数，这也可以证明是我们设置中最好的可能失真（再次考虑参考文献[4]中定理4的例子）。此外，我们的社会选择函数只使用关于备选方案的序数信息，而不是完整的距离4;特别是，只要我们有每个备选方案对其他备选方案的序数偏好（因此，每个备选方案到其他备选方案的距离的总顺序），那么我们的机制将正常工作这样的顺序信息可能比完整距离4更容易获得;例如，候选人可以对所有其他候选人进行排名。特别是，给定具有顺序偏好的代理，使得候选人是代理的子集，即使我们不知道距离4，我们的机制也总是会形成具有小失真的结果。请注意，仅使用代理人考虑图2中的以下示例：对于W，X，Y，Z，它们之间的距离为：d（W，Y）=d（Y，X）=d（X，Z）=d（Z，W）=2和d（W，X）=d（Y，Z）=4。假设W是代理1和2的最佳选择，X是代理3和4的最佳选择，Y是代理5和6的最佳选择，Z是代理7和8的最佳选择这图是对称的，所以我们选择一个任意的替代品作为赢家。假设我们选择W作为获胜者，代理人和候选人之间的距离是：代理人1，2到W的距离都是100，代理人1，2到X，Y，Z的距离都是102。从代理5、6到Y、X的距离都是1，从代理5、6到W、Z的距离都是3。从代理7、8到Z、X的距离都是1，并且从代理7、8到Y、W的距离都是3。从代理3、4到X的距离都是1，从3、4到Y、Z的距离都是3，并且从3、4到W的距离都是社会选择和其他问题的序近似九：11ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月≤22∈F≤∈≤≤≤≤ ≤ ≤ · ··≤≤≥ ≥ ≥···≥≥5. 在这个例子中，中位数是从第五最近的代理到获胜的替代方案的距离X是med（W）= 1时的最佳选择，而med（W）= 5时的失真为5。我们将使用参考文献[4]中的以下引理来证明我们的算法（为了完整性，证明包含在附录中）：2.3. 对于任意两个备选方案W和Y，我们有med（W）med（Y）+d（Y，W）。[引理23]2.4. 对于任意两个备选方案Y和P，如果P两两击败（或两两平手）Y，则med（Y）≥ d（Y，P）。[在参考文献[4]中的定理24LEMMA2.5. 设W，Y是F中的两个备选项，若W两两击败（或两两平手）Y，则med（W）≤3med（Y）. [在参考文献[4]中的定理24中证明]我们在形成算法时使用的主要简单见解来自以下引理。2.6. 对于任意三个备选方案W、 Y和 P，如果 P两两击败（或两两平局） Y，并且d（Y，W）≤ d（Y，P），则med（W）≤ 3med（Y）.P屋顶。根据引理2.3，med（W）≤ med（Y）+d（Y，W）。 根据引理2.4，med（Y）≥ d（Y，P）.我们已知d（Y，P）≥d（Y，W），因此med（W）≤ med（Y）+d（Y，W）≤med（Y）+d（Y，P）≤中位（Y）+2中位（Y）≤3med（Y）。□我们使用一个自然的康多塞一致性算法来近似最小的社会成本中位数与代理首先，创建多数图G=（，E），即，一个图的顶点和边（Y，Z）E的替代品，如果Y两两击败或两两领带Z。如果孔多塞冠军（即，一个成对击败所有其他选项的选项）存在，那么我们立即返回它否则，我们考虑每一对备选方案。根据引理2.5，如果边（W，Y）E，则med（W） 3med（Y）。当考虑备选对W，Y时，如果（W，Y）gE并且我们知道存在满足引理2.6的条件的另一备选P，则我们将边（W，Y）添加到G。不难看出，只要边（W，Y）在我们的图中，这意味着med（W） 3med（Y）。正如我们在下面证明的，在这个过程的最后，总是存在至少一个替代方案，它具有所有其他替代方案的边缘，因此选择它所获得的失真最多为3，无论哪个替代方案是真正的最优方案。请注意，从选项之间的顺序偏好，我们可以得到选项之间距离的偏序。将此偏序表示为，也就是，我们说d（W，Y）d（W，Z），如果我们知道W更喜欢Y而不是Z（我们没有关于严格偏好的信息）。这是我们手头上的信息：我们只知道共享一个共同选择的然而，请注意，如果在该偏序中存在循环，即，d（Y1，Y2）d（Y2，Y3）d（Y3，Y4）d（Yk，Y1）d（Y1，Y2），则这意味着循环中的所有距离实际上都是相等的，因此我们还可以添加关系d（Y1，Y2）d（Y2，Y3） d（Y3，Y4）d（Yk，Y1） d（Y1，Y2）。这样的循环易于检测（例如，通过形成一个图，每个替代对都有一个节点，然后搜索循环），因此我们可以假设，只要在我们的偏序中存在一个循环，那么对于每对距离d（W，Y）和d（W，Z），则有d（W，Y）≤d（W，Z）和d（W，Y）≥d（W，Z）.九：12E. Anshelevich和W.朱ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月F≤F{}A{}≤∈−≤≥≤算法2：最小中值社会成本算法。输入：代理= 1，2，.，n，备选项=F1，F2，.，Fm，多数图G=（，E），每个方案相对于其他方案的顺序偏好，方案之间距离的偏序。输出：获胜的备选方案W。如果有孔多塞获胜者W，则返回W作为获胜者。对于所有替代对W，Y，如果（W，Y）gE或（Y，W）gE，则假设（Y，W）存在，但（W，Y）不存在。如果存在一个替代P，使得我们在偏序信息中有d（Y，W）d（Y，P），并且P成对击败（或平局） Y，则将edge（W，Y）添加到E;继续;端端端必须存在一个备选W，使得<$Y ∈ F − {W}，（W，Y）∈E。返回W作为获胜者。2.7. 考虑在算法2期间的任何点处的修改的多数图G=（F，E）。对于任意边（W，Y）∈E，我们有med（W）≤3med（Y）.P屋顶。根据引理2.5，对原多数图中的任意边（W，Y），med（W）3med（Y）。现在考虑在处理备选对W，Y时添加到E的边（W，Y）。必须存在一个备选P，使得d（Y，W）≤d（Y，P），并且P两两击败（或追平）Y。根据引理2.6，med（W）≤ 3med（Y）。□2.8. 在算法2的结尾，必须存在一个备选W，使得f ∈Y∈ F-{W}，（W，Y）∈ E.P屋顶。我们用反证法证明了这个引理。假设不存在这样的替代方案W。则对于每个备选Y，至少有一个备选Z，使得只有（Z，Y）E和（Y，Z）gE。这是因为我们从多数图开始，所以每个图之间总是至少存在一条边。汇率我们创建另一个有向图GJ=（JF，EJ），其中EJ是所有边（Z，Y），使得（Y，Z）gE. 因此，G中的任何一对备选项之间至多有一个方向的边。根据我们的假设，每个备选方案Y在GJ中至少有一个输入边。由于GJ中每个节点的入度至少为1，因此GJ中至少有一个圈。为了看到这一点，例如，可以取进入Y1的边（Y2，Y1），然后取进入Y2的边（Y3，Y2），并以这种方式进行，直到形成一个循环。注意，GJ中的每条边必须在原始多数图中，因为如果我们在算法中处理一对备选项时添加一条边，则该对必须在两个方向上都有边。考虑由边（Y1，Y2），（Y2，Y3），.，（Yk1，Yk），（Yk，Y1）.在算法2中处理备选对Y2，Y3时，我们没有将边（Y3，Y2）加到E上，所以必然是不存在备选P使得d（Y2，Y3）d（Y2，P）和P成对击败（或追平）Y2的情况。但是我们知道Y1两两击败（或平局）Y2，因为边（Y1，Y2）在原始多数图中。那么唯一的可能性是我们不知道d（Y2，Y3）d（Y1，Y2），即，或者d（Y2，Y3）和d（Y1，Y2）在我们的偏序中是不可比较的，或者我们只知道d（Y2，Y3）d（Y1，Y2）.它们不可能是不可比的，因为我们有Y2对Y1和Y3的序数偏好，因此我们的偏序必须社会选择和其他问题的序近似九：13ACM Transactions on Economics and Computation，卷。号92、第九条。出版日期：2021年1月≤···−{∈ A}· · ·≤ ≤≤−≤≤−≥≥ ≥···≥ ≥≥−≤ ≤···≤ ≤≤−22 ≤≤≥23说明d（Y2，Y3）d（Y1，Y2），即，Y2比Y3更喜欢Y1。通过同样的推理，我们还得到Y3比Y4更喜欢Y2，更一般地说，对于所有i，Yi比Yi+1更喜欢Yi1，其中Y0=Yk，Yk+1=Y1，因为它是一个循环。这意味着在我们的偏序中，我们有d（Y1，Y2）d（Y2，Y3）d（Y k1，Y k）d（Y k，Y1）d（Y1，Y2）.然而，回想一下，这意味着我们知道d（Y1，Y2）=d（Y2，Y3）= =d（Yk1，Yk）=d（Yk，Y1），并且在运行算法2之前，我们检测交替距离的偏序中的循环，并且将等式信息添加到偏序。这意味着，每当d（Y1，Y2）d（Y2，Y3）d（Yk1，Yk）d（Yk，Y1）d（Y1，Y2）存在于我们的偏序中，我们也有d（Y1，Y2）d（Y2，Y3）d（Yk1，Yk）d（Yk，Y1）d（Y1，Y2）也是偏序的.但是这给了我们一个矛盾，因为在偏序中有d（Y2，Y3）d（Y1，Y2），结合Y1成对击败Y2的事实，会导致我们在算法中添加边（Y3，Y2），这与只有边（Y2，Y3）在算法产生的最终图中而不是（Y3，Y2）的陈述相矛盾。因此，必须存在至少一个备选方案，从它到所有其他备选方案都有边。□第2.9章.最小社会成本中位数算法2的失真最多为3。P屋顶。如果存在孔多塞优胜者，则根据引理2.5，失真最多为3。否则，根据引理2.8，算法总是返回赢家。假设它返回alternative根据引理2.7，W的失真最多为3，任何备选方案X都是最优解。□2.2.1广义中位数：百分位失真。 除了考虑中位数目标，我们还考虑了一个更普遍的目标：α百分位社会成本。令α-PC（Y）表示来自集合d（i，Y）：i的值，该值的α分数低于α-PC（Y）。因此，median是α=1，med（Y）=1-PC（Y）的特殊情况。文献[4]定理282 2当α∈[0，1）时，在该设置中的最坏情况下的失真（仅具有代理21在我们的设置中，α1∈[0，2）是无界的，同一个例子表明α1∈[0，2）是也是无界的。然而，在本文中，我们能够给出α∈[2，1]的畸变为3，而对于文献[4]中的设置，当α∈[1，2]时畸变的下限为5。原因是在我们的环境中，选择之间的顺序偏好也是可用的我们将展示算法2不仅对中位数目标而且对一般α-百分位数目标给出了至多3的失真，因为我们用来证明中位数目标结论的所有引理都可以推广到α-百分位数。我们在算法的证明中使用参考文献[42.10. 对于任意两个备选方案W和Y，我们有α-PC（W）≤α-PC（Y）+d（Y，W）.[参考文献[4]的引理29我们可以将引理2.6推广到下面的引理，并且在引理2.6的证明中使用引理2.10代替引理2.3，2.11. 对于任意三个备选方案W、 Y和 P，如果 P两两击败（或两两平局） Y，并且d（Y，W）≤ d（Y，P），则α-PC（W）≤ 3 α-PC（Y）.第2.12章. 算法2对于α-PC客观社会成本（1≤α≤1）的失真为：最多3。P屋顶。注意，引理2.10实际上是引理2.3