没有合适的资源?快使用搜索试试~ 我知道了~
ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月单调子模赋值POOYA JALALY,Google LLC埃瓦·塔尔多斯,康奈尔大学我们研究的问题,预算有限的买家谁想要购买一套物品,每一个从不同的卖家,以最大限度地提高她的价值。预算可行机制设计问题要求设计一种机制,激励卖方如实报告其成本,并最大化买方的价值,同时保证总付款不超过她的预算。这种预算可行的机制可以模拟在众包市场中有兴趣招募一组工人(卖家)来完成她的任务的买家。这个预算可行的机制设计问题是由Singer在2010年提出的我们考虑一般情况下,买方的估值是一个有许多诚实的机械主义者都知道这个问题。我们为简单的机制提供了两个通用框架,通过结合这些框架,我们显着改善了最知名的结果,同时也简化了分析。例如,我们将一般单调子模情形的近似保证从7.91提高到5,并将大市场情形(其中每个单独项目的值可以忽略不计)的近似保证从3提高到2.58。更一般来说,对于最优化问题(忽略激励),给定一个r近似算法,我们的机制对于大市场是一个r+1近似机制,这是对2r2的改进。我们还提供了一个没有大市场假设的机制,在那里我们实现了4r+ 1近似保证。我们还展示了我们的研究结果如何可以用于在众包市场中选择一组受总预算约束的任务的主要招聘问题。CCS概念:·计算理论→动力学机构设计附加关键词和短语:预算可行机制,子模块估值,算法机制设计,算法博弈论ACM参考格式:Pooya Jalaly和Eva Tardos。2021年单调子模估值的简单有效的预算可行机制ACM跨经济计算9,1,第4条(2021年1月),20页。https://doi.org/10.1145/3434421P. Jalaly在康奈尔大学完成了这篇论文的工作,部分得到了NSF基金CCF-1563714、ONR基金N 00014 -08-1-0031和Google研究基金的支持。- 是的Tardos的工作部分得到了NSF资助CCF-1563714和CCF-1422102,ONR资助N 00014-08-1-0031和Google研究资助。作者pooyaj@google.com塔尔多斯,康奈尔大学,计算机科学系,316盖茨大厅,康奈尔大学,伊萨卡,纽约14853;电子邮件:eva@cs.cornell.edu。允许免费制作本作品的全部或部分的数字或硬拷贝,以供个人或课堂使用,前提是制作或分发副本的目的不是为了盈利或商业利益,并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有,必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表,需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2021计算机协会。2167-8375/2021/01-ART4 $15.00https://doi.org/10.1145/34344214ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月四:2P. Jalaly和Jaly。Tardos∈−∈⊆1介绍我们研究了无先验预算的可行机制设计问题,其中一个单一的买家的目标是购买一组项目,每个从不同的卖方。预算可行性机制设计的重点是最大化的价值,买方,同时保持总付款低于预算。这是由Singer [13]引入的,并模拟了各种实际问题。例如,它可以被一个在众包平台上采购工人的负责人使用,比如亚马逊的Mechanical Turk。负责人希望采购一组工人来完成一组任务。每个工人都有自己的服务成本。我们提供普遍真实的机制(即,它们要么是真实的,要么是决定性的,或者是在决定性真实机制上的分布),对于这个问题具有良好的近似保证,这激励工人报告他们的真实成本并找到具有接近最优值的一组工人。我们专注于简单的参数化机制,假设买方的估值是一个一般的单调(非递减)次模函数。子模性捕捉了增加项的收益递减特性,使得单调子模函数得到了广泛的应用。次模值函数是最一般的一类函数,其中优化问题(不考虑激励)可以使用值预言器在多项式时间内近似求解[15]。我们引入新的简单的参数化机制,这一问题,参数化和改进的一些以前已知的机制的分析。我们的主要结果是显示如何将这些简单的参数化机制可以结合的情况下,大的市场,其中每个项目单独没有一个显着的价值相比,最佳的。我们还展示了我们的结果如何可以用于众包市场中的主要招聘问题,根据总预算,选择一组任务和代理来完成这些任务我们的模型。我们考虑的问题,一个单一的买家与预算B面对一组多个卖家A。我们假设每个卖家i A都有一个不可分割的物品,并且有一个私人成本c i买方事先并不知道该物品的私人成本。卖方出售其物品并收到付款的效用为pici。我们只研究普遍真理的机制,即,卖方如实报告其成本的机制,并且在任何随机性结果中没有误报的动机。由于每个卖家i A只有一个物品,我们可以互换使用i来表示卖家或她的物品。我们假设v(S),购买者对于物品S A的子集的价值,是单调(非减)子模函数。预算可行性约束要求向卖方支付的总款项不得超过预算。本文的目标是设计简单,普遍真实,预算可行的机制,大约最大限度地提高买方的价值我们将我们的机制的性能与真正的最优值进行比较,没有计算或激励限制:最大化价值,以保持总成本低于预算。考虑到这种比较,不考虑计算限制的激励兼容机制也有一定的意义。我们还考虑了一个变种的问题建模的二分图,其中一边的图形是代理与私人成本和其他方面的任务,每个值的主要。边(a,t)表示代理a可以执行任务t。在这个由Goel提出的模型中,在众包市场的激励下,每个代理(由节点表示)都有固定的私人成本,可以完成任务的子集,并且每个任务对委托人都有固定的价值。我们的贡献。我们提供了两类参数化的机制。我们在第5节中的文章的主要结果以一种令人惊讶的方式结合了这两种机制,为大型市场提供了一种新的改进机制。在第4.1节中,我们研究了一类参数化阈值机制,该机制基于每个项单调子模赋值的简单有效预算可行机制四:3ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月≥表1. 最上面的数字是以前已知的最佳保证,r1是该机制使用的预言的近似比率,并且r2表示该机制具有指数运行时间兰德兰德公司DetDet,LM兰德,甲骨文Det,Oracle,LM以前的工作7.91 [7]7.91 [7]8.34 [7][3]第三章−[3]第二节我们的结果544.562.584r或4r+ 11+RRand和Det表示随机和确定性机制,LM表示大市场假设。4r保证需要对预言机做一个额外的假设,如果没有这个假设,界限是4r+ 1。项目超过其成本(每美元爆炸),使用参数γ。在第4.2节中,我们考虑另一个参数化的类,称为预言机机制,它以每一美元爆炸的递减顺序添加项目,直到达到真正最优值的α在第四节中,我们分析了这两个参数化机制的一般单调子模赋值。 在第5节中,我们将这两种机制结合起来,以获得大型市场的改进结果。我们对一般问题的结果总结见表1。在第6节中,我们重点讨论了具有异质任务的市场问题的应用[7,10]。在第4.1节中,我们考虑阈值机制GREEDY-TM和R and dom- TM,其在最高值的单个项目和GREEDY- TM的输出之间随机选择。该框架是参考文献[7,13,14]中提出的机制以及Anari等人[3]使用γ= 0的一些机制的直接推广。5.我们证明了对于单调子模赋值,在参数γ相同的情况下,随机阈值机制是普遍真实的,预算可行的,并且可以达到最优值的5近似值.这改善了以前的最佳界限7.91由于陈等人。[7]的文件。在4.2节中,我们介绍了另一类参数化机制,R andDOM-OM,称为预言机机制,它以bang per buck的顺序添加项,直到获得参数α的最佳值的α分数。我们还包括它们的指数 时 间 对 应 物 R 和 DOM-EOM 和 D eterminI sTI c-EOM 。 机 制 R andDOM-E0 M 和DETERMINISTIC-E0 M使用真正的最优值(并且因此在指数时间中运行),而RandDOM-OM使用多项式时间近似。我们表明,保持获胜集的总价值至多是最优保证的一小部分,该机制在预算上是可行的。R andDOM-EOM和DETERMINISTIC-EOM使用Anari等人[3]的指数时间预言机制的参数化版本,我们称之为GREEDY-EOM,作为子例程。对于该机制可以访问计算真正最优值的预言机的情况,我们证明了我们的预言机机制R andDOM-EOM是普遍真实的和预算可行的,并且通过正确选择α来实现最优值的4近似,改进了Chen等人的7.91的界[7]的文件。对于DETERMINISTIC-EOM,我们使用了一种去随机化的思想,这与Chen等人的思想类似。[7],并表明它实现了最优解的4.56近似,改进了Chen等人的8.34界。[7]。我们的机制与Chen等人的机制之间的主要区别。[7]是他们的机制仅在其去随机化阶段使用最优值,并且他们的贪婪子例程不利用访问最优值,但是我们的机制使用最优值进行去随机化和创建选择项的简单贪婪子例程(称为GREEDY-EOM)。机制R和DOM-OM通过使用r-近似预言机作为子例程而不是最优子例程在多项式时间内运行。我们注意到,使用GREEDY-EOM,··四:4P. Jalaly和Jaly。TardosACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月+ e 1美元。图1.一、边缘显示的是作为其他子程序使用的机制左边和右边的机制分别运行多项式和指数时间 Oracle是一个多项式时间算法,近似解决单调子模赋值的预算优化问题。一个次优的预言机打破了单调性;我们的RA nD oM-OM机制保证了与任何预言的单调性。我们证明了在α,R和DOM-OM是普遍真实的和预算可行的,并且实现了最优的4R+1近似(当所使用的预言机是贪婪算法时,其改进为4R我们在第5节中给出了本文的主要结果,其中我们通过运行两个参数化机制并将两个集合的交集中的卖家声明为赢家来组合这两个参数化机制。我们的CAUTIOUSS-BUYER机制采用两种机制中获胜者的交集,以使用较大的参数γ和α值,并保持机制预算可行。我们证明,对于α和γ的正确选择,我们的机制是决定性的,真实的,预算可行的,并且具有1 + r的近似保证,改进了Anari等人[3]1(其中r是所使用的预言机的近似保证)声称的界限2 r 2。使用Sviridenko [15]的贪婪算法(Khuller等人[11]也分析了预算最大覆盖问题的特殊情况),近似我们机制的保证是1 +ee1 2002年。58.在图1中,我们展示了我们的机制,他们的子程序。−在第6节中,我们展示了我们的子模块估值结果如何用于Goel等人的具有异质任务的众包市场问题。这意味着我们在第5节中的大市场机制是确定性的,真实的,预算可行的1e 2 58近似保证的机制。由此产生的确定性机制与随机真实性的近似保证相匹配(in Goel et al. [10]对这个问题的预期)机制。2相关工作Singer [13]已经引入了用于购买一组物品的先前的自由预算可行机制设计,每个物品来自不同的对于单调子模赋值,这是我们的文章的重点,陈等人。[7]改进了Singer [13]的机制及其分析,以实现7.91的Amanatidis等人。[1]表明,给定多项式时间内该问题的整数规划(IP)的线性规划(LP)松弛,该机制可以去随机化。它们的近似保证取决于输入IP及其LP松弛的一些参数,但并没有改善8.34保证。2Singla和Krause [14]考虑了社区感知应用中的问题,并给出了一种机制,该机制对大型市场具有4.75的近似保证Anari等人[3]改善1Anari et al.[3]通过用R-近似算法替换在它们的指数机制中计算最优解的子例程来实现所要求保护的2R2不幸的是,正如我们在4.2节中指出的,这似乎破坏了该机制的真实性。2相同的作者在参考文献[2]中使用我们对早期版本的分析对这个界限进行了一些文章,但改进的边界至少是5.45。··单调子模赋值的简单有效预算可行机制四:5ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月+100。≈−1−1log logn−1Singla和Krause [14]的结果实现了具有多项式时间机制的大型市场的3近似保证和具有指数时间机制的2近似保证。Anari等人。[3]还提出了一种机制,对于单调子模函数的预算值最大化问题给出r近似预言,具有2r2近似保证,然而,他们的机制使用优化算法作为预言,并且在使用贪婪算法时失去单调性(因此失去真实性)(更多细节请参见第4.2节)。我们克服了这个困难(除了提高边界),允许获胜的项目集,不再是连续的顺序,他们的边际爆炸每美元。预算可行性机制设计也被认为具有特殊的评估功能,更好的边界是已知的。例如,对于加法估值,由于Chen等人的研究,最著名的机制分别用确定性和随机化机制实现了2×[7],谁也给了一个1+102二、41下限在这种情况下,任何真实的预算可行机制的近似比率在大型市场与添加剂估值,Anari et al.[3]改进了这些结果,并给出了一个预算可行的机制。具有匹配下界的ee的近似保证的Anism。Singer [13]还介绍了二分图上匹配的可行机制设计问题:要求委托人选择二分图的匹配,其中每个单独的边缘是具有私人成本和公共价值的代理Chen等人[7]考虑具有异质项的背包问题,这是该问题的特殊情况,其中二分图是一组不相交的星。他们的近似界上面提到的附加项目的价值,具有确定性和随机性机制的2+1/2和3也推广到这种情况。Goel等人[10]考虑了由众包市场激励的问题的变体,如上所述,其中图的一侧是具有私人成本的代理,另一侧是任务,每个任务都有一个值。他们给出了一个随机的真实(期望)机制,具有1+ee大市场假设下的近似保证我们认为这第6节中的匹配问题的版本。即使增加了硬约束,即获胜集应该是匹配的破坏了赋值函数的子模性(参见参考文献[1,7,10]),我们表明我们的机制对于单调子模赋值的情况仍然可以用于这种情况,与Goel等人的近似保证相[10]具有确定性机制。先前的自由预算可行机制也被研究用于更一般的估值函数。单调子模赋值是最一般的一类赋值函数,已知其具有多项式时间(具有值预言)的常数因子近似保证,真实和预算可行的机制Dobzinski et al.[8]引入了一种使用需求Oracle的机制(比我们使用的值Oracle更强大)。由于Bei等人[5],当前最佳界是O(logn)Bei等人[5]还给出了一种随机化机制,该机制实现了恒定(768)近似保证,分数次加性(XOS)的估值,使用的需求预言,并证明了存在一个常数近似一般次加性函数的贝叶斯框架。一些论文考虑贝叶斯设置,每个代理的成本来自已知的独立分布。Bei等人[5]给出了一个恒竞争机制,估值(具有非常大的常数)。 Rumanski和Hartline [4]给出了一个(ee)2-竞争性大市场单调子模块估值的公布定价机制,使用成本定义市场规模的版本。参考文献[4]中使用的基准是最优贝叶斯激励相容机制的结果,而其他人(包括我们)使用了相对于预算纯优化问题的显著更高的最优值作为他们的基准。有趣的是,将我们对大型市场的结果与近似值进行比较,四:6P. Jalaly和Jaly。TardosACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月()第1章−1·⊆∈≤ ⊆ ≥ ∪∩.«∈选择(A)≈∈–e保证22 5的机制在参考文献[4]。 虽然这个界限好了0.08比我们的界限,-他们的基准,最佳贝叶斯激励兼容机制,可以是a因子ee低于我们忽 略 激 励 的最优基 准 [3]。即使销售商的成本来自一个不一致的差异,每个项目的价值为1,两个基准之间的差异是2.3预赛我们考虑的问题,一个单一的买家与预算B面对一组多个卖家A,每个销售一个单一的项目。我们让n表示卖家的数量,我们假设A=[n]。 我们假设购买者对一组物品S的价值v(S)是一个(非减)次模函数,即它满足v(S)v(T)对于每个ST和v(S)+v(T)v(ST)+v(S T),对于每个集合S,TA.对于每个iA和SA,我们定义mi(S)=v(S(一)v(S),即,i相对于子集S的边际值。注意v()是单调次模的当且仅当对于每个S,T A,我们有:v(T)≤ v(S)+ mi(S).i∈ T\ S大市场的假设。 在第5节中,我们考虑大市场,假设每个代理人的价值与最优值相比都很小,即,v(i)opt(A)for alli [n]. 为了简单起见,我们陈述了我们对于大市场的近似边界,其中每个项目的价值与最优值相比可以忽略不计,假设θ= max i[n]v(i)0。在买方预算约束下选择一组卖方使买方价值最大化的机制设计问题我们设计真实的、确定性的和个体理性的机制,以及普遍真实的和个体理性的随机机制。一个随机化机制是普遍真实的,如果它是确定性机制中的一个随机化,每个确定性机制都是真实的。我们使用迈尔森根据迈尔森的特征,获胜集合中每个项目的阈值支付可以通过找到该项目可以声明并且仍然在获胜集合中要证明一个机制是普遍真实的和预算可行的,只需证明分配是单调的,总支付等于阈值支付之和。不超过预算。与参考文献[5,7,8,14]类似,我们假设支付是阈值支付,并且仅指定分配规则。在每一节的最后,我们简要解释如何计算该节中机制的支付规则。在我们的所有机制中,如果卖方出价的成本超过B,他将不会被选入获胜集合,因此效用为0。这与我们所有的机制都是真实的这一事实相结合,意味着个人理性,即,在我们的所有机制中,卖方的效用是非负的。4亚模赋值在本节中,我们将介绍两种简单的参数化机制。我们表明,这些参数化机制提供了良好的近似保证,是单调的,因此可以[3]通过θ-大市场假设,我们的大市场机制的近似保证增加了(1cθ)−1倍,其中c(0, 4)是一个常数,对于每个机制都是不同的。我们省略了确切的说明。 c值分别为每种机制单调子模赋值的简单有效预算可行机制四:7ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月CJ∈R和D o M-TM,其中12 e−4γ= 0。γ∈γγ变成了真实的机制,并适当地定义了付款我们分析了在大市场假设和非大市场假设下这些机制的近似保证,并给出了使这些机制预算可行的条件。设S0= ,并且对于每个i [n],递归地定义Si=Si-1arg max具有最大边际价值与成本比的项目,以j∈A\Si−1 (mj(Si−1))},加上不失一般性,S i−1。为了简化符号,我们假设{i}=Si\Si−1。我们所有的机制都是按降序在开始时考虑每美元的边际冲击的顺序,并按此顺序考虑项目4.1门槛机制我们的阈值机制概括了Singer [13]和Chen等人的机制。[7]。我们按照成本对边际价值递增的顺序来考虑项目,如上所述我们的贪婪阈值机制,GREEDY-TM,为项目的成本与边际价值比率设置阈值,与预算与所选集合的总价值的比率相比。使用参数γ,该机制添加项目,而它们与迄今为止的总数相比相对便宜。该GREEDY-TM机制工程以及为大型市场,其中每个单独的项目有小的价值相比,最佳。在一般情况下,我们将随机选择之间的选择,只是选择最大的个人价值和成本低于预算的项目,或运行GREEDY-TM。我们称由此产生的随机化机制为R和M-TM(γ,A,B)。GREEDY-TM(γ,A,B)(贪婪阈值机制)设k=1当k≤|一|和ckBmk( Sk−1)≤γ v( Sk)doK=k+1端returnSk−1R和M-TM(γ,A,B)(随机阈值机制)设A={i:ci≤B}设i∈[n](v(i))概率为γ+1γ+2returnGREEDY-TM(γ,A,B)停止返回Singer [13]的次模函数的随机化机制类似于参数γ=e−1的RandDOM- TM和Chen等人的改进机制[7]相当于5.这个机制的单调性很容易看出:如果某个卖家没有被选中,那么他就不能通过增加成本(减少每一美元的边际收益)而被选中。这意味着,根据Myerson4.1. blog 对于每个固定的γ ∈(0,1],Gr EEDY-TM(γ,A,B)是单调的.我们证明了对于每一个固定的γ(0, 1],R和dom- TM(γ,A,B)都达到最优解的1+2近似,从而改进了Chen等人的界[7]的文件。关键的区别是,我们直接将GREEDY-TM的输出与真正的最优值进行比较,而不是分数贪婪解决方案。这样做不仅提高了近似因子,而且简化了分析。我们在下面的技术引理的证明中使用这个想法,这是证明我们的机制的近似保证的主要成分4.2. blog 对于每个固定的γ∈(0, 1],如果Sk−1=GrEEDY-TM(γ,A,B),则.1+1v(Sk−1)+1v(i)≥opt(A),(1)其中,i是成本低于预算B的最有价值的项目。四:8P. Jalaly和Jaly。TardosACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月..近似比为21+。γ««–Ci2 2ϵCkγBγγγγγγγi∈S<$\Sk−1PR oF. 设S为最优。利用v(. ),我们有v(S)−v(Sk−1)≤v(SSk−1)−v(Sk−1)≤i∈S<$\Sk−1mi(Sk−1)=i∈S<$\Sk−1cim i(Sk−1).Ci利用k∈arg maxi∈A\Smi(Sk−1)的事实,我们得到mi(Sk−1)≤mk(Sk−1)。因为k不在决胜盘ckBk−1cicickmk(Sk−1)>γv(Sk)。利用这些,.c imi(Sk−1)≤ c(S\S k−1)mk(Sk−1)41−1,因此没有其他项目在获胜的G REEDY-TM(0)集合中。5,A, 4)。−单调子模赋值的简单有效预算可行机制四:9ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月−r=0。opt(A,B)e1≥≥αα端返回G REEDY-EOM(0. 5、A、B)其他−3∗17√∗返回i4设v=opt(A\{i},B)如果v( i)≥v,则设i∈[n](v(i))设A={i:ci≤B}Det. exp.时间预言机制)返回GREEDY-EOM(α,A,B)停止返回2概率为1设i∈[n](v(i))设A={i:ci≤B}R andDOM-EOM(α,A,B)端returnSk−1K=k+1当v(Sk)≤ αv≠0时GREEDY-EOM(α,A,B)(exp.时间预言机制)设v_i=opt(A,B)设k=1因此,G REEDY-TM(0. 5,A,4)以及R和m的值-TM(0. 5,A, 4)为1。然而,最佳可以选择所有的项目,并获得价值5 4美分。由于R可以任意小,因此R和M = TM(0. 5,A,B)至多是5-近似。注意,我们需要γ = 0。5得到上述推论;然而,在第5节中,我们使用这个机制-具有较大的γ值。对于本节中的阈值机制,获胜集合中的每个代理i的阈值支付可以通过增加i要在多项式时间内计算这个数字,只需确定其他代理GREEDY-TM(γ,A,B)不等式仍然适用于她。[13]这一点与辛格的观点类似4.2Oracle机制在这里,我们提供了一种不同的参数化机制。这类机制需要一个r-近似的Oracle(A,B),它返回一组项目A和预算B的问题的值,该值在最大值的因子r内。当r= 1时,我们使用opt(A,B),因此,一般来说,rOracle(A,B)选择(A,B)Oracle(A,B).例如,Sviridenko [15]可以用作Oracle,e一百五十八。由于在多项式时间P=N P[9]中不可能计算,因此我们可以使用所有使用最佳值的机制,指数时间预言机制。由预言机返回的值也可以被操纵-原则上-由卖方申报其费用。因此,从博弈论(“激励”)的角度来看指数时间预言机。 我们从一个简单的指数时间预言机制GREEDY-EOM开始,使用最优解值opt(A,B)作为预言。最优值更容易使用,因为它在代理成本中是单调的。4稍后,我们展示了如何使用多项式时间近似预言机而不是opt(A,B),在近似比上有小的牺牲,同时保持机制的真实性和预算的可行性。在这一小节中,我们的机制还按照bang-per-buck的降序对项目进行排序,如第4节开头所述。4.5. 对任意固定的α ∈(0,1],Gr EEDY-EOM(α,A,B)是单调的,若Sk−1= Gr EEDY-EOM(α,A,B),则1v(Sk−1)+1v(i)≥ opt(A,B).[4]对于大型市场,Anari等人[3]使用了一个指数时间机制,等价于G REEDY-EOM(0. 5,A,B)。四:10P. Jalaly和Jaly。TardosACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月∈−αSk−1v( Sk−v( Sk−−k−1−αααJJJMt(Sj·Tz−1)PR oF.我们首先认为,该机制是单调的。设i A和igSk1。如果i增加她的成本,那么它不能增加v=opt(A,B)的值。此外,通过增加i单调为了看到近似界,只需注意,根据机制的定义,我们有v(Sk)>αv. 所以v(S k−1)+v(i)> v(S k−1)+v(k)> αv。□通过使用引理4.5,很容易证明下面的定理。4.6. 对每个固定的α∈(0, 1],R和M-EOM(α,A,B)是普适真的,如果S=R ANDOM-EOM(α,A,B),则2E[v(S)] ≥ opt(A).PR oF.通过使用引理4.5和定理4.3中的真实性证明的类似论证,很容易看出该机制是普遍真实的。通过定义R和M-EOM(α,A,B),我们有E[v(S)]=1v(S)+1v(i)2 2E[v(s)]= 1v(S)+1v(i)。通过使用引理4.5,证明是完整的。□现在我们证明,对于α= 0的选择。5,G REEDY-EOM(0. 5,A,B)是预算可行的,因此R和M-EOM(0. 5,A,B)是普遍真实的,预算可行的,和4近似最优。4.7. blog 通过使用阈值支付,Gr EEDY-EOM(0。5、A、B)预算可行。PR oF. 设pi为代理人i的支付阈值。设S k−1= G REEDY-EOM(0. 5,A,B)。对于ev-ery i∈S k−1,我们证明了如果i偏离到bi>mi(S i−1)v(B),他不能被选中,im-假设支付阈值p i≤m i(S i−1)B。 通过证明这一点,我们得到了。i∈Sk−1 pi≤.i∈Sk−1 mi(Si−1)B =B,其中最后一个不等式通过回忆mi(Si−1)=v(Si)−v(S i1),所以总和伸缩。因此,该机制在预算上是可行的。我们用反证法证明了上述不等式:假设i偏离到bi>m i(S i−1)v(B) 而且仍然是赢家设b为新的成本向量,i投标Sb i和所有其他代理人出价他们的真实成本。请注意,考虑项目的顺序第i项之后的第1项也受到i现在设j是机制中的步骤,其中i在偏离到bi之后被添加到获胜集合,Sj·是该步骤p之后的获胜集合,其中对于z∈[n],Sz·被类似地定义为Sz,但是成本向量b而不是c。LetS是v(S)=v的最优解。令S|S j·={t1,t2,.,tq},T0= π,Tz={tl:l∈ [z]}。由于i是唯一增加他的成本的项目,并且i∈Sj·,我们有c(S)≥ b(SS·)− b(S·)=.M t(S·T z−1)btz.z通过子模块性和该机制选择在po中具有项i的排序的事实在条件j(成本为b)下,我们有mtz(Sj·<$Tz−1)≤mtz(Sj·1)且btz/mtz(Sj·1)≥bi/mi(Sj·1)。–z∈[q]z单调子模赋值的简单有效预算可行机制四:11ACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月−1−1−1−1−−1联系我们Σ−42JMt(Sj·Tz−1)zJMt(Sj·)zJmi( Sj·)z∈[q]利用这两个不等式,我们得到.Mt(S·Tz−1)btzz≥。m t(S·T z−1)btz≥.m t(S·T z−1)biz=bi(v(S S·)− v(S·))≥bi(v(S)− v(S·))。mi(Sj·)j jmi(Sj·)j现在,通过使用矛盾假设,以及Si−1<$Sj·1的事实,我们得到bi(v(S)− v(S·))> Bv(S)− v(Sj·)。mi( Sj·)jv(Sk−1)通过组合上述不等式并利用v(S j·),v(S k−1)<αv和α = 0的事实。5、存在c(S)>B,这是一个矛盾,所以该机制是预算可行的。□对比4.8。通过使用阈值支付,R and D o M-EOM(0. 5,A,B)是普遍真实的,预算可行的,和最佳的4近似值。接下来,我们提供了一个简单的确定性版本的这种机制,一个显着更好的近似因子,改善以前已知的确定性8.34近似指数时间机制的陈等人。[7]保证金为4.56。为了去随机化RandD oM-EOM,我们将我喜欢检查最优值是否比最优值大。为了保持机制的单调性,我们将比较最高值项i的值与删除项i后的最优值。他的眼睛4.9。 通过使用阈值支付,D ETE r min I s TI c-EOM是真实的和预算可行的,并且具有4.56的近似比。PR oF. i不能改变opt(A i,B),因此由于G REEDY-EOM(0. 5,A,B)是单调的,且在预算上是可行的,D-末端-EOM是真实的,且在预算上是可行的。为了证明近似比,我们考虑两种情况:情况1:v(i)≥17−3v=17−3opt(A\ {i},B):在这种情况下,算法返回i,我们有44√173√4+1 v(i)≥ opt(A\{i},B)+v(i)≥ opt(A,B).√情形2:v(i)<17−3v≤17−3opt(A,B):令S k−1= G REEDY-EOM(0. 5,A,B)。在这种情况下,由4引理4.5,我们有42v(Sk−1)+ 2v(i)≥opt(A)102v(Sk−1)+2。17 − 32<$1 −<$17−3v(S k−1)≥ opt(A)。42因此,在任何情况下,近似比都是1− 17−3+ 1 =1−17−3− 4。五十六□多项式时间预言机。在这里,我们提供了一个预言机机制,使用一个或- acle代替最优值opt(A,B),因为在背包约束下找到单调子模最大化的最优值不能在多项式时间内完成。在我们的指数时间预言机制中,天真地使用次优预言的结果而不是最优预言的结果.z2z∈[q]z∈[q]四:12P. Jalaly和Jaly。TardosACM Transactions on Economics and Computation,卷。号91、第四条。出版日期:2021年1月GREEDY-OM(α,A,B)(贪婪的预言机机制)对于i=1到n,设S=然后如果v(Si)≤ αOracle( A\{ i}, B)端S= S{ i}终端返回S联系我们{}\−(S(S.i∈Smi(Si−1<$S)B/v(S)=B,因此该机制是预算可行的。∈iii−五)α..αRR随机预言机制(RandomOracle Mechanism)设A={i:ci≤B}概率为αr2rdo设i∈[n](v(i))returnGREEDY-OM(α,A,B)+停止返回可以打破单调性,如在许多上下文中众所周知的,例如参见参考文献[6]。要看到这一点,请注意,如果卖方增加其成本,她不能增加opt(A,B)的值。然而,如果我们用次优预言的结果(例如,贪婪算法)替换opt(A,B),这不再正确:如果增加不在最优集中的所有项的成本,要超过预算,那么任何合理的子模极大化近似算法(例如,参考文献[15]中的贪婪算法)都可以检测并选择最优集中的所有项。现在,如果物品i增加了她的成本,这增加了近似算法的结果与opt(A,B)相比,则这使得该机制通过增加该机制的选择规则中的αv的值来获取更多的项目,可能包括项目i为了使我们的机制单调,我们在调用oracle来决定是否应该将i添加到集合S之前删除i,使所选择的项不再按照我们考虑它们的顺序连续其次,证明了GREEDY-OM(α,A,B)是单调的,并给出了它的逼近比.LEMMA4.10. 对任意固定的α∈(0,1],Gr EEDY-OM(α,A,B)是单调的.如果S=天啊-OM(α,A,B),则k∈ [n]是最大整数,使得S k−1<$S,i 是具有最大值单个值,并假设OrA clE是最优值的rrv(S k−1)+.1+ rv(i)≥ opt(A)。PR oF.该机制的单调性来自通常的论点,增加ci不会影响ORA cLE(A i,B),并且在任何步骤中都会减少项目为了显示近似因子,回想一下k=Sk Sk1。由于k不是由我们所知αv(Sk−1)+v(k)≥v(Sk)>αOracle(A k)≥ropt(Ak)≥α(opt(A)− v(k))≥ α(opt(A)−v(i))。下一个引理表明G REEDY-OM(0. 5、A、B)预算可行。□第4.11章. 通过使用阈值支付,G
下载后可阅读完整内容,剩余1页未读,立即下载
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![m](https://img-home.csdnimg.cn/images/20210720083646.png)
![m](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 基于Springboot的医院信管系统
- 基于Springboot的冬奥会科普平台
- 基于Springboot的社区医院管理服务系统
- 基于Springboot的实习管理系统
- TI-TCAN1146.pdf
- 基于Springboot的留守儿童爱心网站
- S32K3XXRM.pdf
- Ansible Automation Platform 快速安装指南 v3.8.1
- Ansible Tower 发行注记 v3.8.1-76页
- C语言笔记-考研版(进阶)
- Design_of_Analog_CMOS_Integrated_Circuit20200602-85440-9wt61m-with-cover-page-v2 (1).pdf
- Ansible Automation Platform 安装和参考指南 v3.8.1-59页
- 浅析5G技术在工业互联网领域的应用研究
- 查重17 岑彩谊-基于otn技术的本地承载网-二稿 .docx
- 自考计算机应用基础知识点.doc
- 数据库系统安全、技术操作规程.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)