近似有效的双边组合拍卖与代理人估值功能的机制设计

ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月近似有效的双边组合拍卖RICCARDO COLINI-BALDESCHI，Facebook核心数据科学，英国Paul W.GOLDBERG，英国牛津大学BART DE KEIJZER，埃塞克斯大学，荷兰STEFANO LEONARDI，Sapienza，罗马大学，意大利TIM ROUGHGARDEN，斯坦福大学，美国STEFANO TURCHETTA，NTT Data和英国牛津大学我们发展和扩展了双边市场机制设计的近期工作我们所考虑的一种机制是根据代理人对物品的估价而不是实际估价给出先验分布;因此，目标是在这些分布上最大化预期的社会福利。与以前的工作一样，我们感兴趣的是由真实机制实现的社会福利与可能的最佳社会福利之间的最坏情况比率。我们的主要结果是一个激励兼容和预算平衡的常数因子近似机制的设置，买方XOS估值和卖方这是第一个这样的近似机制的双边市场设置的代理组合的估值功能。为了实现这一结果，我们引入了一种更一般的需求查询，似乎需要在这种情况下。在简单的情况下，卖方有单位供应（每个只有一个项目出售），我们给出了一个新的机制，其福利保障改善了最近的文献。我们还介绍了一个更苛刻的版本的强大的预算平衡（SBB）标准，旨在排除某些我们表明，更强的版本是满意我们的机制。CCS概念：·计算理论→博弈论;博弈机制设计;计算定价和拍卖;计算广告理论;附加关键词和短语：机制设计，双边市场，公布价格机制，组合拍卖Tim Roughgarden得到了NSF Grant CCF-1524062的支持Stefano Leonardi的部分研究成果获得了Google FocusedAward的“大规模数据分析算法”、ERC Advanced Grant 788893 AMDROMA的“在线市场的数学和机制设计研究”以及MIUR PRIN项目ALGADIMAR的“算法、游戏和数字市场”的支持作者 Colini-Baldeschi， Facebook Core Data Science ，Facebook ， 1 Rathbone Place ， W1T 1FB ，London ， UK;email：rickuz@fb.com; P.W. Goldberg，University of Oxford，Room 255，Wolfson Building，Parks Road，OxfordOX1 3QD，United Kingdom; email：paul. cs.ox.ac.uk; B.de Keijzer，埃塞克斯大学，Wivenhoe Park，Colchester CO4 3SQ，阿姆斯特丹，荷兰;电子邮件：b. essex.ac.uk; S. Leonardi，计算机、控制和人机工程系Antonio Ruberti，罗马大学，Via Ariosto 25，00185 Roma，Italy; email：diag.uniroma1.it; T.Roughgarden，计算机科学系，哥伦比亚大学，500西120街，450室，MC 0401，纽约，纽约10027;电子邮件：tim@cs.stanford.edu; S。Turchetta，WolfsonBuilding，Parks Road，Oxford OX 1 3QD，United Kingdom;电子邮件：stefano. turchetta@cs.ox.ac.uk。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020计算机协会。2167-8375/2020/03-ART4 $15.00https://doi.org/10.1145/33815234ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月四：2R. Colini-Baldeschi等人ACM参考格式：放大图片作者：Paul W.Goldberg，Bart de Keijzer，Stefano Leonardi，Tim Roughgarden，and Ste- fanoTurchetta.2020年。近似有效的双边组合拍卖ACM Trans. 经济Comput. 8，1，第4条（2020年3月），29页。https://doi.org/10.1145/33815231介绍单边市场在经济学中已经研究了几十年，最近在计算机科学中也有研究。单边市场中的机制设计旨在找到一组物品到一组代理人的有效（高福利）分配，并且在这种设置中通常期望的属性是激励相容性，即，如实报告输入数据是代理商的最佳策略。机制设计中的基石方法是Vickrey-Clarke-Groves（VCG）机制[10，21，34]，该机制优化了社会福利，同时为讲真话提供了正确的激励：VCG机制是主导策略激励相容的（DSIC），并且在许多机制设计设置中，VCG也是个体理性的（IR）。IR要求要求参与该机制对任何代理都无害。DSIC的需求要求，如实地报告一个人最近，越来越多的注意力转向双边市场中出现的问题，其中代理人被划分为买家和卖家。与单边设置相反（在单边设置中，可以说机制本身最初持有物品），在双边设置中，物品最初由卖方持有，卖方对他们持有的物品有估价，并且被认为是理性和战略性的。该机制现在的任务是决定哪些买家和卖家应该交易，以及以什么价格交易。对双边市场日益增长的兴趣，它被用于各种重要的应用。相关的例子是在广告交易平台上销售显示广告，美国FCC频谱许可证重新分配和证券交易所。双边市场通常在贝叶斯环境中进行研究：存在概率分布的公共知识，每个买方和每个卖方各有一个概率分布，从中得出买方和卖方的估值。在双边市场中，另一个重要的要求是强预算平衡（SBB），即货币转移只发生在市场中的代理人之间，即，允许买方和卖方进行交易，而不给该机制留下任何支付份额，并且该机制不向市场增加资金。在文献中经常考虑的SBB的一个较弱版本是弱预算平衡（WBB），它只需要不向市场注入资金的机制。然而，从Myerson和Satterthwaite [27]的工作中可以知道，IR，BIC和WBB机制通常不可能在这样的市场中最大化社会福利，即使在双边贸易环境中，即，只有一个卖家和一个买家1.上述实际情况需要采用双边市场机制，可以在组合设置中工作，即，市场上有多种不同的商品以及代理对它们可能接收的项目子集具有可能复杂的估价。然而，我们不知道有任何这样的机制，既接近社会福利，又符合IR、DSIC和SBB的要求。本文的目的是提供满足这些要求的机制，并实现了O（1）-近似的社会福利为广泛的一类代理人事实上，我们设计的机制，[1] VCG机制也可以应用于双边市场;然而，在这种情况下，VCG要么不是IR，要么不满足WBB。近似有效的双边组合拍卖四：3ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月假设的估值是分数次加性（XOS），一个推广的次模函数，包含在类的次加性功能。我们的结果扩展和改进了以前的工作，针对一个重要的特殊情况，双边市场：每个卖家持有一件物品，物品是相同的，每个代理人只对持有一件物品感兴趣。在这种情况下，代理人的估值，从而给出一个数字，代表代理人持有物品的效用。这种设置的机制在文献中被称为双向拍卖。一些关于双重拍卖的研究[24，30，31]的目标是在激励相容性和预算平衡约束的强度下权衡可实现的社会福利。在我们目前的工作中，我们研究这个问题的更一般的组合双边市场。1.1模型如上所述，代理的集合被划分成卖方的集合和买方的集合，卖方的集合中的每一个最初被赋予异构项目的集合，买方的集合最初没有项目买家有钱可以用来支付项目。每个代理人都有自己的私人估价函数，它将项目的子集映射为数字，并且代理人被假设为优化其（准线性）效用，该效用由该机制分配给代理人的项目集的估价减去该机制从代理人收集的付款卖家通常会收到钱（而不是付款），我们将其视为负付款。对于每个代理，我们给出了一组估值函数的概率分布（公知），我们假设她的估值函数是从中得出的。该机制和其他代理人不知道第i个代理人的已实现价值函数，而只知道她的概率分布。2该机制的总体目标是重新分配物品，以最大限度地提高预期社会福利（代理人对最终分配的估值总和设OPT为物品最优分配的期望社会福利。注意这是一个明确定义的量，即使计算最优分配可能在计算上很难，即使可能不存在一个适当的机制（满足IR、SBB和DSIC），也可以保证总是输出最优分配（如Myerson和Satterthwaite [27]的不可能性结果所暗示的）。我们感兴趣的机制，满足IR，SBB，和DSIC（或者，如果没有，贝叶斯激励相容性（BIC）的较弱的概念），并重新分配的项目，以这样一种方式，预期的社会福利是在OPT的一些恒定的分数，其中预期是采取了给定的概率分布的代理人的估值，并在随机性的分配，该机制的与单边组合拍卖设计（其中的主要挑战是多项式时间可实现性）相比，对于双边情况，我们的主要目标是设计O（1）-近似OPTIR、SBB和DSIC/BIC机制（从而证明其存在性）。这些机制通过将最优社会福利的要求弱化为近似最优社会福利的要求（同时加强WBB对SBB的约束），从而规避了Myerson和Satterthwaite [271.2我们的结果及其意义本文首先展示了一个简单的技术技巧，可以将任何WBB机制转换为SBB机制，近似因子略有损失从技术上讲，人们可以，例如，将其应用于Blumrosen和Dobzinski [4]的组合交易市场的WBB机制;然而，该技巧在实践中并不令人满意，因为它基本上包括将剩余的钱交给随机代理人。这表明了一个弱点，[2]我们注意到，这些都是标准假设，尽管我们的DSIC结果并不需要知道主体的分布。四：4R. Colini-Baldeschi等人ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月表1.我们的成果摘要机制买家的估值卖方估值近似比IRICBBM1-供给XOS单位供电6事后IRDSICDSBBM加XOS添加剂6中期利率BICDSBBM加添加剂添加剂6事后IRDSICDSBBSBB的当前定义，这促使引入一个加强版本，我们称之直接贸易强劲预算平衡（DSBB）。让我们简单地阐述一下为什么要求（D）SBB机制而不是WBB机制是合理的在工业界遇到的许多双边市场中，经营这种机制的企业确实对赚取利润感兴趣然而，盈利的方式通常不是通过运行市场上买卖双方预算失衡过大的机制。相反，利润是通过入门费或订阅费（这种情况发生在，例如，在一个实施例中，证券交易所）或通过对所进行的每笔交易或交易量收取相对较低的佣金（这也发生在共享/接入经济中的一些证券交易所和许多双边市场平台中）。具有底层（D）SBB定价机制则比WBB机制更可取，因为前者机制可以以更透明的方式呈现给其客户，并且由市场平台获得的利润量现在在侧面容易描述和控制，而由WBB机制获得的利润量可能难以描述和控制，并且通常非常依赖于实例。如果剩余预算很小，这不一定是一个问题，但当盈余很大时，这就成了问题。因此，强加（D）SBB要求导致在许多实际机制设计挑战中捕获预期的主要目标的机制：在其客户之间直接进行商品货币交易，这本质上是商业双边市场平台主要打算向其客户提供的产品。然后，作为第二步，围绕这样一种机制来设计获利的方式。我们的目标是为组合双边市场设计个体理性的、激励相容的、直接交易的强预算平衡机制，以实现对最优社会福利的不断逼近。我们提出了两种机制，坚持这些限制的一般家庭的组合双边市场，总结在下表中。我们的M1供应机制处理的设置，所有卖方有一个单一的项目出售，和买方的分数次加性（XOS）估价功能的项目在市场上。我们的M添加机制可以处理更一般的情况下，卖方有多个项目出售，并有附加价值的项目，他们拥有的功能，虽然M添加满足较弱的IC和IR的概念比M1供应。更准确地说，Madd是卖方的DSIC和IR，BIC和BIM-IR站在买方一边。然而，对于买方具有附加价值函数的特殊情况，Madd确实满足买方和卖方的更强的IC和IR概念。在所有三种情况下，DSBB都得到了满足（SBB的强化变体），并且我们的机制实现了O（1）-近似的最优社会福利。据我们所知，这些是第一个机制，为组合双边市场，同时是IC，（D）SBB，IR，并近似最优社会福利的一个常数的因素。请注意，对于非单位供应的卖方，即使在WBB或标准SBB的上下文中，以前也不知道常数近似值3此外，我们注意到，[3]如果每个代理人的初始禀赋的大小受一个常数的限制，则参考文献[4]中提出的机制实现了对最优社会福利的常数近似;否则，近似因子是对数阶的。近似有效的双边组合拍卖四：5ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月不仅适用于比参考文献[12]更一般的设置（更多细节见1.3节），而且将双重拍卖的近似比从16提高到6。在M添加的情况下，买方需要回答一般类型的需求查询，其中该机制给出物品的价格，并询问买方如果对于每个卖方j，捆绑中的卖方j的物品将以概率1/2被接收，她想要哪个捆绑。虽然我们在这里不关心这个问题（我们也将代理建模为计算无界作为理性的），我们对这种查询的明显需求突出了代理人的计算限制如何影响可以实现的结果的一般问题41.3技术概述双边市场设计的主要挑战是找到刺激真实行为的价格，并适合具有不同利益的买家和卖家。其实即使在最简单的可以想象的设置-双边贸易-不可能设计一个社会有效的机制，满足IR，BIC和WBB [27]。第一个特点，我们所有的机制共享，以保证DSBB是一个广义版本的双边顺序公布价格机制（SPM）[12]的双重拍卖组合双边市场。这些机制为每个物品分配固定的、预先计算的价格，以便这些价格是物品可以交易的唯一价格这就产生了一系列双边交易，其中买方支付的金额等于卖方收到的金额。虽然单侧SPM免费提供IR和IC，但双侧SPM需要满足额外的条件在组合双边市场中，如果每一个商品的价格都是固定的，那么就不能保证买方所选择的一捆商品一定会被分配给她，因为在这一点上，相应的卖方还没有被询问她是否愿意出售该商品。对称地，当卖方将向SPM机制传达她愿意在给定提议的物品价格的情况下出售哪一捆物品时，则该机制不能向卖方保证在其还没有询问买方他们需要哪些物品集合的情况下该捆一定会被交易由于代理人的估价功能内的物品之间可能存在很强的相互依赖性，情况进一步复杂化因此，机制设计者在提出适合市场双方的价格时需要谨慎，在选择市场的一方首先进行处理时需要特别谨慎这里的机制所做的选择，关键取决于代理人的估值函数的类型事实上，我们两种机制的一个主要区别在于选择先处理哪一方的市场否则，本文中提出的所有机制都忽略了卖方和买方出现的顺序另外，为了实现一个机制，导致高社会福利，我们排除了贸易的一些项目，并引入随机性的机制。主要的想法是假设所有的物品都可供买方在单边拍卖，并计算预期边际贡献的一个项目的社会福利[19]在此假设下。然后，该机制将此贡献与卖家对该物品的价值进行比较因此，该机制只将预期价值相对较高的物品交易给市场的买方估计一个项目对社会福利的预期边际贡献，M1-供给和Madd使用算法A，给定买家4这个问题也适用于标准需求查询[18]，这可能在计算上难以回答，或者可能涉及高通信复杂性，这取决于所使用的计算模型和表示估值函数的方式四：6R. Colini-Baldeschi等人ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月−将物品分配给买家，而不考虑卖家及其估值。如果一个人如果对实现低运行时间不感兴趣，则可以将A视为输出最优分配的精确算法。或者，通过使用Feldman等人[19]的技术，可以对A采用多项式时间近似算法，并将其与从分布中采样足够大数量的估价简档相结合，以在多项式时间内准确地估计物品对社会福利的预期边际贡献。这产生多项式时间可实现的近似机制。特别是，在A是一个多项式时间的α-近似算法，它将在时间POLY（1/n，n，m）内运行，并在O（α）乘法因子和n +1加法项内近似最优社会福利，其中n +1是由抽样过程产生的参数。这种技术在参考文献[19]中有更详细的描述，适用于有界支持的分布。随机性的加入是为了确保每个卖家都以1/ 2的固定概率独立出售她的一捆商品;这是用来限制市场两边的社会福利损失不超过一个常数。总而言之，我们在本文中利用了参考文献[12]的双边顺序公布定价机制的隐含概括我们还利用参考文献[19]中介绍的公布定价技术和概念作为实现正确项目价格的一个重要组成部分，此外，我们（间接）利用使用概率分布中位数定价的基本思想，这一概念也是，例如，出现在参考文献[25]中，并已在其他著作中使用，如参考文献[4，12，25]。然后，我们结合各种新的见解提供的顺序，价格，概率和项目捆绑，以保持激励兼容性。因此，本文的技术贡献在于在定价过程的定义中使用的见解和技术，在捆绑的选择过程中，以及在结合和连接这些见解以建立所声称的近似边界的证明中。最后，在概念方面，我们引入了概率需求查询和直接交易SBB的概念，我们相信这是未来研究的有趣概念。1.4相关工作由于Myerson和Satterthwaite [27]的不可能性结果，即使在简单的双边贸易环境中，也没有双边机制可以同时实现最优社会福利并满足BIC，IR和WBB约束。因此，后续工作的重点是设计在这些属性之间权衡的机制。经济学文献的以下文章研究了当所有卖方和买方的估值分别独立地来自相同的正态分布，同时满足IR和WBB时，作为代理人数量的函数的最优社会福利Gresik和Satterthwaite[20]表明，用τ重复代理数量会导致其中最优IR、IC和WBB机制Rustichini等人。[28]和Satterthwaite和Williams [31]研究了一类非IC双重拍卖，并研究了这些双重拍卖中代理人误报其估值的低效率和程度。我们注意到，这些结果只适用于单位需求的买家和单位供应的卖家，相同的估值分布，这些渐近结果中的隐藏常数取决于特定的估值分布。相比之下，我们的兴趣是在寻找通用常数近似保证组合设置，不一定相同的分布。在McAfee [24]中，提出了IC，WBB和IR双重拍卖，其提取至少（1 1/4）从交易中获得的最大收益的分数，5其中4是最佳解决方案中的交易者数量[5]贸易收益（有时称为增量社会福利）代表相对于没有贸易发生的情况，在双边市场中，这是一个有意义的目标近似有效的双边组合拍卖四：7ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月在参考文献[3]中，对于空间分布市场的更一般模型，也得到了相同类型的近似保证，其中对于同一种商品，存在多个双边市场，并且可以以一定的成本在市场之间运输物品。Myerson [26]描述了最优收益最大化贝叶斯拍卖的特征，它提供了一个适用于单参数单边拍卖的优雅工具。随后的各种文章都涉及到推广这些结果。与我们的工作相关的是邓等人的工作。[13]，他们研究了贝叶斯双向拍卖中拍卖人收入的最大化。Deshmukh等人研究了相同的目的”[14]在《易经》中，在参考文献[32]中，提出了双边市场的一些特殊情况下的机制，这些机制通过随机抽样和随机序列独裁的组合来工作该机制是IR，SBB和DSIC和其收益的贸易接近最优时，市场是足够大的。许多其他文章研究了当机制是IC、IR和SBB或WBB时近似贸易收益的问题[1，7，8，11，25，33]。在参考文献[8]中，提出了一种机制，该机制保证在DSIC、IR和WBB-in-expectation下贸易收益的2-近似。这种近似保证是关于我们的替代基准的，称为第二最佳基准，其中该机制与最佳可能的BIC，IR，WBB预期机制进行比较。此外，参考文献[2]提出了一种机制，该机制被证明可以成功地实现对两个基准的近似保证：对第二好基准的恒定保证，而随着市场变得更大，他们的机制也接近完全效率。对于双边贸易的特殊情况，即，对于一个卖方、一个买方和一个物品，文献[5]表明，在IC、IR和SBB约束下，贸易收益不能近似于任何常数，文献[11]进一步描述了这种情况下的渐近近似因子。请注意，这意味着我们在本文中建立的常数近似因子主要依赖于将贸易收益与近似社会福利作为我们的目标函数，而不是贸易收益。从社会福利的角度来看，文献[4]中已经给出了双边贸易的IC、IR和SBB机制除此之外，作者还提出了一种适用于一般组合交易市场的WBB机制我们将使用这个结果来构建我们的初始机制。单边市场中的顺序公布价格机制（SPM）由Sandholm和Gilpin [29]引入，由于其简单性、对碰撞的鲁棒性以及在实际应用中的易实现性而受到关注。关于SPM的第一个理论结果之一是三种不同类型的单参数机构之间的渐近比较[6]。后来Chawla等人[9]为了实现收入最大化的目标对它们进行了研究。此外，Kleinberg和Weinberg [22]以及Dütting和Kleinberg [16]加强了这些结果进一步。与我们的工作非常相关的是Feldman等人的文章。[19]表明，如果一个项目的公布价格等于该项目对社会福利的预期附加贡献，则连续公布价格机制可以近似于XOS估值函数的1/最近的一系列工作解决了在WBB要求下，在双重拍卖中近似社会福利的问题和相关问题。Dütting等人。[17]确实提出了一种贪婪策略，该策略结合了单边VCG机制，独立应用于买方和卖方，以及McAfee的贸易减少机制[24]。他们获得IR，DSIC，和WBB机制具有良好的近似的社会福利，背包，匹配，和拟阵分配约束。最近，Colini-Baldeschi等人[12]提出了第一个因为即使没有交易发生，卖方也可能有正效用，仅仅因为他们拥有一些物品。因此，估算贸易收益比估算社会福利更难四：8R. Colini-Baldeschi等人ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月≥--j=1∈∈∀ ∈ ∀ ⊆∩≥⊆满足IR、DSIC和SBB，并将最优（预期）社会福利近似为常数因子的双向拍卖6这些结果适用于任意数量的买方和卖方，其估值具有任意的独立分布。该机制还扩展到设置有一个额外的拟阵约束的买家谁可以购买一个项目。我们在本文中研究的设置是更一般的双拍卖设置，考虑买家和卖家多个不同的项目和复杂的估价功能。最后，有一个替代的研究路线，其中，在满足IC，IR，SBB和效率（即，例如，在参考文献[23]中，针对交易市场提出了一种有效的迭代机制，当代理人如实出价时，该机制在所有非均衡支付规则的集合中产生最小化遗憾2预赛作为一般惯例，我们使用粗体符号表示向量，并使用[a]表示集合1，.，a.我们将使用I（X）来表示当且仅当事件/事实X成立时映射到1的指示符函数2.1市场双边市场由两种不同类型的代理人组成：最初持有待售物品的卖家和有兴趣购买卖家物品的买家。所有探员都拥有 单调和规范化的赋值函数，将项的子集映射到R0。7形式上，我们将双边市场表示为元组（n，m，k，I，G，F），其中[n]表示买家集合，[m]表示卖家集合，[k]表示所有待售商品的集合，I：=（I1，. ，Im）是被称为初始禀赋的（相互不相交的）项集合的向量，其中Ij是初始禀赋的项集合，由卖方j∈[m]持有。它认为MIj=[k]。向量G=（G1，.，Gn）和F=（F1，.，Fm）是概率分布的向量，假设从中得出买方（组合）交换市场是上述双边市场的更一般版本，其中代理人可以充当买方和卖方。因此，每个人最初都可以拥有物品，并且可以出售和购买物品。因此，在此设置中，我们覆盖了符号，使用n表示代理的总数形式上，交换市场是一个元组（n，k，I，F）。在本文中，我们保留使用字母i表示单个买家，字母j表示单个卖家，字母4表示单个项目。此外，我们用vi表示买方i在双边市场中，卖方被假设为只重视其初始捆绑中的物品，因此对从其他卖方购买不感兴趣，即，j[m]和S[k]，wj（S）=wj（S1，j）。相反，在外汇市场上，对估值函数不存在这样的限制。2.2机制设计目标下面的讨论是专门针对双边市场（本文的主要焦点），但这些概念可以直接扩展到组合交易所市场。在一个双边市场中，我们的目标是在代理人之间重新分配物品，以使社会福利（代理人的估值之和）最大化 双边市场（n，m，k，I，G，F）的分配是一对向量（X，Y）=（（X1，.，Xn），（Y1，.，Ym）），使得X1，.，Xn，Y1，.，Ym为[6]在双向拍卖中（遵循经典经济理论文献中的定义），物品是相同的，买方和卖方分别被假设有一个单位的需求和供应。7单调赋值函数v，我们的意思是v（S）v（T）对于所有的项目集合 TS。也就是说，不能降低代理商的整体估值。通过归一化，我们的意思是v（n）=0。近似有效的双边组合拍卖四：9ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月一∈×我我 我i，而对于卖方，[k]，和X1，...，Xn，Y1，.，Ym是互不相交的。注意，Yj表示在执行该机制之后保持在卖方占有中当讨论一个给定的双边市场时，我们将用该市场的所有分配的集合来表示。通过运行机制M来完成项目的重新分配。一种机制与代理交互并接收来自代理的输入，并输出结果，包括分配（X，Y）和支付向量（ρ B，ρ S）RnRm，其中ρB是指买方的支付向量，卖给卖家。因此，一个结果是一个元组（X，Y，ρB，ρS）。请注意，当代理人被收取负付款时，这应被解释为代理人收到钱。在一个合理的双边市场机制中，卖方的支付通常是负的，这也是本文所提出的机制的情况。代理人被假设为最大化其效用，其效用被定义为相对于分配向量，他们拥有的一捆物品的价值减去收取的费用的机制。特别地，买方i∈[n]的效用uB（vi，（X，Y，ρB，ρS）），其中val-评价函数v 是v（X）−ρB我j∈[m]，赋值函数为w是uS（wj，（X，Y，ρB，ρS））=wj（Yj）−ρS。J J此外，代理人被假定为完全理性的，所以他们将战略互动以达到效用最大化的目的。我们的目标是设计一种机制，使代理人有一个主导策略或贝叶斯-纳什均衡，该机制返回一个具有高社会福利的分配。对于分配（X，Y），社会福利SW（X，Y）定义为：SW（X，Y）=.vi（Xi）+.wj（Yj）.我们现在描述我们的机制必须满足的三个主要经济属性。对于这些约束中的每一个，我们首先引入最严格的版本，然后引入更宽松的版本。我们的目标是尽可能满足最严格的版本。激励相容性（IC）8-主导策略激励相容性（DSIC）： 每个代理人真诚地报告她的真实价值是一种主导策略也就是说，对于每个代理i和所有其他参与者的每个估值向量，代理i不可能通过误报她的估值来增加她的期望效用。-贝叶斯激励相容性（BIC）： 这是一个贝叶斯-纳什均衡（BNE）的代理人如实报告他们的估值的机制。也就是说，如果所有其他参与者也如实报告他们的估值，每个代理i通过如实报告她的估值来最大化个人理性（IR）-事后个人理性（事后IR）： 任何代理人参与该机制都是无害保证存在一种用于代理的策略，该策略产生代理的效用不小于其初始效用。(The捆绑销售者初始效用Ij是wj（Ij），买方的初始效用是vi（i j）=0。）- 临时个人理性（临时IR）：每个代理都有一个策略，她的期望效用不小于她的初始效用（在期望超过[8]从技术上讲，正如可以推断的那样，DSIC属性是为直接揭示机制保留的，即，其中买方仅与报告其估价功能的机制交互。众所周知，允许支配策略的机制可以转化为DSIC直接揭示机制，而具有贝叶斯-纳什均衡的机制可以转化为BIC直接揭示机制。这样一来，DSIC和BIC的定义就自然地延伸到了非直接披露机制。··Ji∈[n]j∈[m]四：10R. Colini-Baldeschi等人ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月≤·∈{∈ A}≥。∈机制的随机结果，由机制的内部随机性和代理采用的随机策略产生预算余额（BB）-强预算平衡（SBB）：该机制输出 的所有代理人的支付之和从概念上讲，这意味着没有钱最终流向外部方，也没有外部方需要补贴该机制。- 弱预算平衡（Weak Budget Balance，WBB）：所有支出之和至少为零。在双边市场中，这通常意味着买方的付款至少与卖方收到的付款一样大。任何外部方都不需要为该机制提供补贴。对于估值曲线（v，w），OPT（v，w）：=maxSW（X，Y）：（X，Y）表示最优社会福利。期望的最优社会福利值为OPT=Ev，w[OPT（v，w）]。我们说，当α>1时，机制Mα-近似于最优社会福利，当且仅当OPTαEv，w[SW（M（v，w））].我们的目标是找到在低α下，α近似于最优社会福利的机制，即DSIC（或BIC），SBB和事后IR（或临时IR）。2.3评估函数我们将考虑以下几类赋值函数的概率分布让v：2 [k]→R≥0是一个赋值函数。然后，• v是可加的当且仅当存在数α1，. αk∈ R0使得v（S）=jSαj，对所有S∈ [k].• v是分数次加性（或XOS），当且仅当存在一个加性函数a1，.，ad使得对于每个丛S<$[k]，v（S）= max i∈[d]ai（S）成立.• v是次可加的当且仅当对所有S，T<$[k]成立v（S<$T）≤v（S）+v（T）。很容易看出，每个加法函数都是一个XOS函数。此外，公知的是，子模函数类包含在XOS函数类中，并且XOS函数包含在子加函数类中。3初始机制和直接贸易强有力的预算平衡Blumrosen和Dobzinski [4]提出了一种具有次可加估值函数的交易所市场机制。它的工作原理是将代理集随机均匀地划分为两个集合A和B对于A中的代理人，代理人i得到的报酬等于他对整个捆绑的中间估价MEDiA的所有接受此付款的代理人都提交他们的项目，然后通过VCG拍卖将收集到的物品出售给B中的代理。然而，在运行该VCG拍卖时，目标函数被最大化，该目标函数是常规社会福利的修改版本，其中对于每个代理i减去H（ti）MEDi的量 A，其中ti是B中持有来自i的物品的代理的数量，并且H（）表示调和数。拍卖者可能会从A中的代理中拿走物品，这些物品在运行VCG机制后随后保持未分配。他们证明了这个机制，我们命名为Mbd。定理3.1（BLUMROsENAND D obz inskI [4]）。 机制Mbd是一种DSIC、WBB、事后IR随机化的直接揭示机制，它以4 H（s）-逼近具有次追加价值函数的组合交换市场（n，k，I，F）的最优社会福利，其中s=min{n，|我我|：i∈ [n]}是主体数量和主体初始禀赋中的项目数量的最小值。这种机制给了我们一个常数近似因子，如果代理人的起始项目的数量是由一个常数，特别是在单位供应的情况下。Mbd可能生成的预算不平衡可以任意高，并且高度依赖于实例。我们现在展示如何使用这种机制作为黑盒来获得SBB·近似有效的双边组合拍卖四：11ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月∈−−联系我们−i−ibdv，−i.−∈联系我们–∈v，−A.A.i∈[n]j∈[n]\{i}nH（s）i∈[n]j∈[n]\{i}vnH（s）[客n−vv只有一个稍微差的近似比机制如下定义机制Msbb当给定组合交易市场C=（n，k，I，F）作为输入时，(1) 在i[n]中随机均匀地选择一个代理(2) 在组合交易市场上运行Mbd机制C−i=（[n]\{i}，I −i=（I1，. ，Ii−1，Ii+1，. ，In），F −i=（F1，. ，Fi−1，Fi+1，... ，Fn））。令（X ，ρ ）是机制M输出的结果。(3) 设Xi=Ii且设pi=−j[n]ipj。输出分配（Xi，Xi）和支付向量（pi，ρ−i）。所以机制Msbb本质上运行机制Mbd，其中一个随机代理从市场中移除。该代理接收机制Mbd生成的剩余资金，并且不接收或丢失任何物品。请注意，如果我们希望确保在运行该机制后将所有项目分配给代理（因此不会在拍卖者处结束），那么我们可以将任何剩余项目额外分配给我们先验删除的代理。以下是机制Mbd的DSIC、WBB和事后IR性质的直接推论。第3.2节. 机制Msbb是一个DSIC，SBB和事后IR机制，用于具有次可加估值函数的交易所市场。其次，下面的定理表明，当n≥3时，该机制在近似比中只损失了一个因子2n/（n−1）≤3。9第3.3节.机制Msbb实现了一个8 nH（s）/（n 1）-近似的最优社会福利的交易所市场的次可加估值和至少有三个代理。P屋顶。 固定代理人的一个价值向量v，当代理人的价值为v时，设X v为局部财富最大化分配。对于代理i[n]，用Xi表示Ci的分配，其中re（X）j=（Xv）jIi为j[n]i，i。例如，当i被移除时，从Xv_n中获得ed的所有位置，并且i的所有项被移除。此外，设X_i是当局中人[n]i的估值函数向量固定为v_i时组合交易市场C_i的最优分配。机制Msbb均匀随机地选择i，因此根据定理3.1，期望机制Msbb的社会福利至少是41Ei .vj（X）≥41Ei.vj（X）H（s）n∈[n]\{i}v，−iH（s）1n∈[n]\{i}v，−i=4 nH（s）。 .vj（（Xv）j\Ii）=41。 .vi（（X）i\Ij）=41。 .[客：12（vi（（X）i\Ij）+vi（（X）i\IjJ））i∈n{j，jJ}j，jJ∈n\{i}J9对于n=2，存在实现良好近似比的替代机制。在这种情况下，可以例如限制到考虑将代理1的整个捆绑重新分配给代理2或反之亦然的机制。该机制随机选择两个备选方案中的一个，然后运行双边贸易设置的2-近似DSIC，SBB，IR机制（即，一个买方，一个卖方，一个项目的设置）[5]，其中销售代理的捆绑被视为单个项目。这产生了DSIC、SBB、IR机制，其中第一步中的随机选择向近似因子引入了附加因子2，使得我们得到总近似因子的上限4四：12R. Colini-Baldeschi等人ACM Transactions on Economics and Computation，卷。号81、第四条。出版日期：2020年3月.Σ––{}∈≥∈A∈--nH（s）[客：[客n−vi∈n{j，jJ}j，jJ∈n\{i}<$j<$jJ4nH（s）2v8nH（s）vi∈[n]=41。 .12vi（X）=1.一、 n −1vi（X）=n − 1。vi（X），其中第二个不等式由次可加性得出，倒数第二个等式是通过了解内求和项的数量为n-21而得到的=（n1）（n2）/2，当乘以系数1/（n）时，得到因子（n 1）/ 2 2）。这证明声明，因为上面对每个估值向量v都成立。□这产生了一个事后IR，SBB和DSIC机制，O（1）-近似的社会福利，如果最初拥有的项目数量由一个常数的限制。我们用来构建机制Msbb的原理可以更普遍地用于将任何WBB机制转换为SBB机制，同时保留DSIC和事后IR属性。这一原则还揭示了SBB概念的一个问题：它允许代理人在不参与任何贸易的情况下接受资金。这激