离散异构两设施选址问题研究

+v：mala2277获取更多论文1离散型真异质两设施选址问题研究作者：Panagiotis Kanellopoulos，Alexandros A.计算机科学与电子工程英国埃塞克斯大学摘要我们重新审视离散异构两个设施的位置问题，其中有一组代理人，占据节点的线图，并有私人批准的偏好超过两个设施。当设施位于线路的某些节点时，每个代理获得的成本等于她与她批准的设施的总距离我们的目标是决定在哪里找到这两个设施，以便（a）激励代理人如实报告他们的喜好，（b）实现一个很好的近似的最小总（社会）成本或最大成本之间的所有代理人。对于这两个目标，我们设计了确定性的防策略机制，其近似比明显优于最先进的水平，并用（几乎）严格的下限补充这些结果1介绍在经典的真实单设施选址问题中，有一组在实数线上具有私人位置的代理，以及一个公共设施（如图书馆或公园），我们需要决定其位置。这个决定必须做出，以便（a）激励代理人如实地透露他们的位置（如果这导致设施位于更接近她的真实位置，代理人将愿意撒谎），以及（b）优化社会目标（例如代理人与设施位置的总距离，或最大距离）。自Procaccia和Tennenholtz[2013]的著名论文以来，这个问题及其许多变体在没有金钱的近似机构设计文献中得到了广泛的研究。为了全面介绍多年来一直在考虑的各种不同的设施选址模型，我们请感兴趣的读者参阅Chan等人最近的调查。[2021年]。最近的一系列论文集中在异构设施选址问题上，其中多个设施（通常为两个）在性质上是不同的（例如，学校和酒吧）。因此，智能体关心设施的位置和类型，旨在使他们最喜欢的设施尽可能靠近他们的位置举个例子，一个家庭希望离学校比离酒吧近已经提出了许多设置来模拟代理可能对设施的不同偏好（参见相关工作中的讨论）。除了少数例外，所有这些模型都假设两个设施可以放置在实线的任何一点，甚至在同一点。Sera finno和Zerie[2016]偏离了这些假设，研究了问题的离散版本，其中线是离散图，代理人占据线的节点（这是常识），并且对两个设施具有批准偏好，这两个设施只能放置在线的不同给定设施位置，代理人的成本被定义为与她批准的设施的总距离。arXiv：2109.04234v1 [cs.GT] 2021年9+v：mala2277获取更多论文2Sera fino和Sera fere提出了确定性和随机机制在两个社会目标方面的近似比的界限。特别是，对于社会成本，他们表明，确定性机制的最佳可能近似比在9/8和n-1之间，其中n是代理人的数量。 相反，他们设计了一种随机机制，以最小的预期社会成本来解决问题。对于最大成本目标，他们表明确定性机制的最佳可能近似比在3/2和3之间，而随机机制的最佳可能近似比在4/3和3/2之间。在本文中，我们专注于确定性机制，并改进了社会和最大成本的Serafinno和sera fine的界限1.1我们的贡献Sera finno和Sélane给出的社会成本和最大成本的上限都遵循相同的确定性机制，称为TwoExtremes ， 它 与 Procaccia 和 Tennenholtz[2013] 考 虑 的 同 质 2设 施 位 置 的 机 制 类 似TwoExtremes在批准它的代理中最左边的代理所占用的节点处定位其中一个设施，并且在批准它的代理中最右边的代理所占用的节点处定位另一个设施;如果发生冲突，其中一个设施将向左或向右移动一个节点。TwoExtremes的缺陷主要有两个原因：（i）批准设施的边界代理（最左边和最右边）可能远离中间代理，其节点将是设施的理想位置，以及（ii）它没有以任何方式利用有关代理位置的可用信息。我们改进的机制照顾到这两个原因：我们把设施更接近中间代理（不破坏战略性），并利用代理的代理位置的信息。对于局部成本，我们设计具有至多17 / 4 = 4的近似比的FixeD-或MeDiu-Neirest-EmPty（FMNE）mechan。二十五该机制根据线路的结构在两种情况之间切换：如果没有空节点，它将设施的位置固定为线路的两个中心节点;否则，如果有空节点，它将其中一个设施定位在批准它的中间代理的位置，另一个设施定位在批准它的中间代理最近的空节点之一。我们对所有机制的近似比进行了改进的下界4/3，随后是两个只有三个代理并且没有空节点的实例。 受此下限构造的启发，我们将重点放在与三个数据集的交互上，并定义了三个数据集的多维多媒体数据集。最好的边界是4/3为了最大化成本，我们设计了一个参数化的机构类α-LeFT-RI cht（α-LR），它的每个成员将线路分成两部分，从第一个节点到节点α，以及从节点α+1到最后一个节点。然后，关于设施的位置的决定是基于包括在两个部分中的代理我们证明了该类的所有机制都是防策略的，存在近似比至多为2的成员。特别地，当线的大小m是偶数时，通过m/2-LR实现界限，并且当m是奇数时，通过（m+1）/2-LR实现界限最后，我们展示了所有防策略机制的近似比的一个紧下界2，使用一个包含五个实例的序列的构造，其中有三个代理，没有空节点。表1给出了我们的边界的概览，以及它们与Sera fino和Zerie[2016]所示的先前最佳边界的比较。1.2相关工作如上所述，Chan et al. [2021]很好地讨论了许多不同的设施模型，这些模型多年来一直在文献中考虑的近似机制设计没有钱。在这里，我们将主要讨论异构设施选址模型的论文，+v：mala2277获取更多论文3下限上限社会成本最大成本4/3（9/8）17/4（n −1）2（3/2）2（3）表1：我们对社会成本和最大成本的确定性防策略机制的近似比的界限的概述括号中的界限是Serafino和Zerie[2016]所示的以前最知名的界限对于有三个代理的例子，用一个符号标记的4/3的下界是紧的与我们的密切相关。除了Sera fino和Zerie [2016]的工作之外，我们的论文在这里，一些关于离散线路，周期中的单设施选址问题的防策略机制的特征[Dokow et al. ，2012年]和树[Filimonov和Meir，2021年]，以及一些与线度量上的真实单一获胜者投票相关的算法（例如， [Feldmanet al. ，2016年，Filos-Ratsikas和Aldouris，2021年]），相关文献主要集中在连续设置上，其中设施可以位于线路的任何点，甚至是同一点。第一个异构设施选址模型，结合了经典的单一设施选址问题和令人讨厌的单一设施选址问题的元素[Cheng et al. ，2011，2013]，由Feigenbaum和Sethuraman[2015]以及Zou和Li[2015]独立提出和研究在此设置中，有两个设施位于实际线路上，并且座席对设施具有双重偏好;即，座席喜欢或不喜欢设施。作者给出了不同情况下确定性和随机化防策略机制的近似比的界限，这取决于代理人的位置或偏好是否是他们的私人信息（因此可以撒谎）。Kyropoulou等人[2019]考虑了该模型的扩展，其中两个设施的位置空间是欧几里得空间的约束区域。Chen et al.[2020]研究了一种具有对设施具有可选（或批准）偏好的智能体的设置;也就是说，智能体要么喜欢设施，要么对设施不感兴趣。作者考虑了智能体的两个不同成本函数，一个等于智能体批准的最近设施的距离，另一个等于距离最远设施的距离。Li等人 [2020]研究了在更一般的指标（超出线）中扩展此设置，并设计了改进Chen等人的一些结果的机制。.Deligkas等人[2021]考虑了一个类似的偏好模型，但不同的是，目标是只定位其中一个设施（更一般地说，是m中的k），而不是所有设施。Anastasiadis和Deligkas[2018]考虑了一种结合双重和可选偏好的模型Fong et al.[2018]研究了具有分数偏好的设置，其中每个智能体对每个设施都有[0，1]的权重，表明她有多喜欢它。最后，Xu et al.[2021]关注两个设施的位置的位置必须满足最小距离要求的问题。2预赛我们考虑离散两设施选址问题。这个问题的一个实例I由n ≥ 2个代理的集合N、两个设施和一个具有m ≥ n个节点的线图组成。每个代理占用线的节点xi，使得不同的代理占用不同的节点。我们用x表示位置分布，由所有代理的位置组成（即，它们占据的节点）以及可能的空节点的位置;位置轮廓被假定为是公知的。每个代理i也有一个私人的批准偏好ti∈{0，1}2：如果tij=1，代理i∈N批准设施j∈{1，2};否则，她不批准它。通过t=（ti）i∈N，我们表示由所有代理人的偏好组成的偏好分布用Nj表示批准设施j∈{1，2}的代理的集合将是有用的。显然，如果存在批准两种设施的代理，则两个集合N1和N2不需要是不相交的由于x和t隐含地包含了与一个实例相关的所有信息，我们记为I=（x，t）。+v：mala2277获取更多论文4我我可行解z=（z1，z2）确定每个设施j∈{1，2}所在的节点zj，使得z1/=z2。给定一个可行解z，在实例I中任何代理i的成本是她到她所批准的设施的总距离，即，Σc o sti（z|I）=j∈{1，2}tij· d（ i，j），whered（i，j）=|xi−zj|这是一个由两个字母组成的数字。一个机制将一个实例作为输入，并输出一个可行的解决方案。机构M被称为是防策略的，如果当给定实例I =（x，t）作为输入时，它计算的解M（I）是这样的，即没有代理i有动机报告错误的偏好t′i= ti以降低她的成本，即，costi（M（I））|I）≤costi（M（x，（t′，t−i））|I），其中（t′，t−i）是代理i的偏好是t ′的偏好分布我我任何其它试剂的存在与t中相同。我们考虑两个著名的社会目标，这是可行的解决方案的功能给定实例I，可行解z的社会成本是所有代理的总成本，即，ΣS C（z|I）= co sti（z|（一）。i∈Nz的最大成本是所有代理中的最大成本，即，M C（z|I）=maxcosti（z|（一）。i∈N设SC_i（I）= minzSC（z|I）是任何可行的解决方案所能达到的最小可能的社会成本，例如I。类似地，令MC（I）= minzMC（z|I）是I的最小可能最大成本。对于任何社会目标f∈ {SC， MC}，机制M的f-逼近比是最差的由M计算的解决方案的目标值与所有可行解中的最小可能目标值，即，ρ（M）= sup我f（M（I））|第一章）f（I）.我们的目标是设计具有尽可能低的f-近似比（接近1）的防策略机制3一种社会成本的常数近似防策略机制我们从社会成本目标开始 对于具有n个代理的一般情况，我们设计了策略防护机制，即FixeD-or-MeDiiu-Neirest-EmPty（FMNE），其中proxi m anratio17/4，从而大大改善了Sera fino和Sere e [2016]的先前n − 1界。我们的机制利用了已知的位置信息，并根据给定的实例是否包含空节点来区分两种情况。 如果没有空节点，FMNE将设施定位在线路的中心节点处（特别是，节点n/2 n +1和n/2 n+1）;这是该机制的F I xeD部分。 如果存在空节点，FMNE将设施1定位在批准设施1的那些中间代理所占据的节点处，并且将设施2定位在批准设施2的那些中间代理所占据的节点处，该空节点最接近于由中间代理所占据的节点;这是该中间代理的MeDIiu-Neirest-EmPtypa r。 SeeMechanis m 1.+v：mala2277获取更多论文511122222222Mechanism1：FIxeD-or-MeDIiu -Neirest-EmPty（FMNE）输入：具有n个代理的实例I;输出：可行解z=（z1，z2）;如果没有空节点，则//FI xeD部分z1←n/2 n;z2←n/2 <$+1;else//MeDIiu-Neirest -EmPtypart对于j∈{1，2}，yj←Nj中 的最小存储量的position;z1←y1;z2←离y2最近的空节点，打破束缚，支持最右边的空节点;Reorem 3.1. FMNE是防策略的。证据 考虑一个任意的例子I。如果I中没有空节点，则该机制显然是防策略的，因为设施的位置是固定的，并且独立于代理人的偏好所以，我们仍然要考虑I包含空节点的情况。让我成为一个任意的代理人。我们在以下三种情况之间切换：代理i只批准设施1（i ∈ N1\N2）。 不失一般性地假设xi≤ y1。代理i的任何误报只能导致批准设施1的代理中的中值y′，离xi更远。特别地，如果i误报她只批准了设施2，则y′≥y1，而如果我误报她批准了这两项贷款，那么y ′= y1。代理i只批准设施2（i ∈ N2\N1）。 在不失一般性的情况下，假设设施2位于某个空节点e处，其中x e>y2。用y′表示代理占据的中间节点批准了2号设施• 如果代理i误报她批准了这两个设施，那么y′=y2，因此，设施2以及代理I的成本保持不变。• 如果xi≤y2且代理i误报她只批准设施1，则y′≥y2。 因此，在本发明中，或者e继续是离y′最近的空节点，并且i的成本保持完全相同，或者另一个空节点e′成为离y′最近的空节点，并且i严格增加。• 如果xi>y2并且代理i误报她只批准设施1，则y′≤y2。 因此，在本发明中，要么e继续是离y ′最近的空节点，要么另一个空节点e（x e′ 3的x，y的值上，即， 对这些x，y，使得−x2+ 4xy+2y+3> 2。 通过重新排列，我们得到−x2+4xy+2y+3>2x2+2y2−4，因此−x2+2y+7>2（x-y）2。设y=x+k，其中k为整数，并将最后一个不等式改写为−x2+2x+7>2（k2−k）。显然，对于x≥4，不等式永远不成立，因为左边项是负的，右边项总是非负的。因此，我们得到f（x≥4，y）13/4。<对于x的其余值，即， 当x∈ {0，1，2，3}时，回想一下x + y ≥ 6，即， 2x +k ≥ 6。当x=0时，它必须是k≥6，并且不等式不成立，如760。<当x=1时，我们有k≥4，同样，不等式不成立，为824。<当x=2时，我们得到k≥2，不等式变为7>2（k2−k），仅当k=2时成立;在这种情况下，f（2，4）=19/613/4。<最后，对于x=3，我们有k≥0，不等式变成4>2（k2−k），这对k∈{0，1}成立。证明如下注意max{f（3，3），f（3，4）}= max{13/4，73/23} ≤ 13/4。现在我们准备证明具有空节点的实例的界+v：mala2277获取更多论文8Reorem 3.5. 对于n≥6且至少有一个空节点的任何实例，FMNE的SC-近似比至多为17/4。+v：mala2277获取更多论文9证据 考虑任何实例I. 我们首先讨论一下I的最优社会成本。最小化社会成本的解决方案将每个设施j ∈ {1，2}定位到Nj中的中值代理所占据的节点y j。 然而，如果y1=y2，则这种选择不可能是可行的，并且这种选择的成本可能会更大。我们有这个Σ ΣSC_n（I）≥ d（xi，y1）+ d（xi，y2）.（一）i∈N1 i∈N2现在，让我们关注由该机制计算的解决方案z的社会成本设e是设施2所在的空节点;不失一般性，我们可以假设xe>y2。结合设施1位于y1的事实，我们得到z=（y1，xe），并且Σ ΣSC（z|I）= d（xi，yi）+d（xi，xe）。i∈N1 i∈N2第一项出现在由不等式（1）给出的最优社会成本的下界中，因此我们所需要做的就是约束上述表达式的第二项。我们根据智能体在N2中的位置将N2划分为三个集合L、M和R与y2和xe相比，如下所示：• L={i∈N2：xi≤y2};• M={i∈N2：xi∈（y2，xe）};• R={i∈N2：xi>xe}.根据媒体的定义，|L|≥|M|+|R|;在本例中，如果n2=|N2|是偶数，如果n 2是奇数，则是严格不等式（因为L在这种情况下也包括中值代理）。观察到• 对于每个代理i∈M，在j∈L中存在唯一代理，使得d（ xj，xe）= d（ xj，xi）+ d（ xi，xe）= d（ xj，y2）+ d（ xi，y2）+ d（ xi，xe）.• 对于每个代理i∈R，存在唯一的代理j∈L，使得d（xj，xe）+d（xi，xe）=d（xj，y2）+d（y2，xe）+d（xi，xe）=d（xj，y2）+d（xi，y2）.因此，我们有，Σd（ xi，xe）=i∈N2Σi∈Ld（ xi，xe）+Σi∈M d（ xi，xe）+Σi∈Rd（ xi，xe）Σ≤i∈N2d（xi，y2）+d（y2，xe）1{n2odd}+ 2·Σi∈Md（x i，x e）.接下来，我们将约束上述表达式的第二项和第三由于每个智能体占据不同的节点，我们可以将M中智能体的总距离上限如下：Σd（y2，xe）1{n2odd}+ 2·d（xi，xe）i∈M。≤d（y2，xe）1{n2odd}+2·Σd（y 2，x e）− 1 + d（y 2，x e）− 2 +. . . +d（y 2，x+v：mala2277获取更多论文10e）− |M|=−|M|2+（2d（y2，xe）−1）|M|+d（y2，xe）1{n2o d d}。+v：mala2277获取更多论文112222≤1 +2。现在观察d（y2，x e）> |M|（因为M中的所有代理都在y2和e之间）;因此，上述推导中的最后一个表达式是关于|M|. 它显然也是一个关于d（y2，x e）的递增函数。 以来|M|≤1（n2− 1 {n2odd}）且d（y2，x e）≤ n1+ 1 + |M|≤ n1+ 1 +1（n2− 1 {n2odd}），通过计算并利用1 {n2odd} ≤ 1的事实，我们得到：d（y2，xe）1{n2odd}+ 2·Σi∈Md（ xi，xe）≤.Σn2+ 4n1n2+ 2n2+ 1。4把所有的东西放在一起，1.ΣSC（z|I）≤ i∈N1d（xi，y1）+.i∈N2d（xi，y2）+4n2+ 4n1n2+ 2n2+ 1Σ≤SC n（I）+1 n2+ 4n n+ 2n+ 1。421 2 2根据引理3.2，我们有SC（I）≥1。 22Σ4 n1+n2−2，因此近似比由下式限定：SC（z|I）SC（I）n2+ 4n1n2+ 2n2+1n2+n2−21 2通过应用引理3.4（x = n1，y = n2），可以得出17 / 4的界。我们通过证明我们对FMNE的近似比的分析是严密的来结束这一节我是3号。六、什么？在n≥5且没有空节点的情况下，存在一个新的实例，使得FMNE的SC-近似比至少为3，并且存在一个n ≥ 6且至少有一个空节点的实例，使得FMNE的SC-近似比至少为17/4。证据对于FMNE的FI xeD部分，考虑具有5个代理并且没有空节点的以下实例I1前两个代理仅批准设施2，最后三个代理仅批准设施1。该机制输出解（2，3），即，它将设施1定位在第二节点，将设施2定位在第三节点。这两个问题的局部代价是SC（（2，3））。|I1）=9。然而，当社会成本SC_n（I_1）=3时，最优解为（4，2），导致近似比为3。对于F M N E C的MEDIiu-Neirest-EmPypartirt i r t ineinceI2，其具有6个agent和一个空节点。前三个节点由仅批准设施2的代理占用，接下来的三个节点由仅批准设施1的代理占用，最后一个节点为空。该机制输出解（5，7），即它将设施1定位在节点5处，将设施2定位在空节点处。 这是一个简单的问题，它有一个简单的成本SC（（5，7））|I2）=17. 在比较中，当SC_n（12）= 4时，非最优解是S（5，2），导致近似比为17/4。4对于具有三个代理的在本节中，我们仅限于具有三个代理（可能还有许多空节点）的实例。我们证明了防策略机制的近似比为4/3的紧界。特别是，我们提出了一个没有空节点的相当简单的例子，表明任何防策略机制的近似比至少为4/3;这改进了Sera fino和Zerie[2016]所示的9 / 8的下限。我们通过设计一种机制来补充这一结果，该机制在输入任何具有三个代理的实例时实现了4/34. 1 .一、什么？eSC-一个简单的系统结构的proxmationratioofmechanismisat4/3。1+v：mala2277获取更多论文12Mechanism2：PrIorIty-DIctitorshIP输入：实例I，具有三个代理，c和r，使得x=x xcxr;<<输出：可行解z;如果c∈N1\N2，则如果r∈N2，则intx（x，x）;其他（x，x，y，y）;否则如果c∈N2\N1那么如果r∈N1那么intx（x，x）;其他（x =0，x = 0，x= 0）;其他若r∈N2，则intx（x，x）;其他（xc+1，xc）;证据我们考虑两个实例，三个代理，没有空节点。在第一种情况下，所有代理人都批准两种贷款。显然，任何机制都必须将设施定位到第一个或第三个节点（或者，两者都有）。不失一般性，假设该机制将设施2定位在第三节点处。在第二个例子I2中，前两个代理人批准了两种贷款，而第三个代理人只批准了贷款2（也就是说，I1和I2之间唯一的区别是第三个代理人的偏好）。由于设施2位于I1中的第三个节点，因此同样的情况也必须发生在I2中;否则，代理3在I2中的成本至少为1，并且有动机误报她批准了两个设施，从而将I2更改为I1，并将她的成本降低到0。然而，两个可能的可行解z1=（1，3）和z2=（2，3）在I2中的社会成本都是4，而最优解（例如z =（1，2））的社会成本是3;定理如下。因此，我们设计了3-a-d-D-P或H-P，其具有最大4/3的近似比，并且具有最大4/3的近似比。考虑任何有三个代理的实例;为了方便起见，我们称代理为x，c和r，并设x x

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