一个简单的机制为预算有限的买家

ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月一个简单的机制，为预算有限的买家YU CHENG，杜克大学NICK GRAVIN，上海财经大学，中国KAMESH MUNAGALA和KANGNING WANG，杜克大学研究了在预算存在的情况下，一个添加剂购买者垄断问题的经典贝叶斯机制设计。在这种情况下，一个拥有m个不同商品的垄断卖方面对一个单一的买方，并寻求最大化她的收入。买方有一个独立的预算和附加估值 对于来自（不相同）分布的每个项目。我们表明，当买方的预算是公开的，最好是分别出售每一个项目;出售大的捆绑提取恒定的最佳收入的一部分。当预算是私人的，我们考虑一个标准的贝叶斯设置，其中买方我们证明了，如果b是独立的估值（这是必要的）和分布B满足单调风险率条件，那么单独出售或在一个大捆绑仍然是近似最优的。CCS概念：·计算理论→竞争机制设计;计算定价和拍卖;竞争博弈论;其他关键词和短语：拍卖，收入最大化，预算，简单的机制ACM参考格式：Yu Cheng，Nick Gravin，Kamesh Munagala，and Kangning Wang. 2020.一个简单的机制，为预算有限的买家.ACM跨经济计算9，2，第10条（2021年1月），25页。https://doi.org/10.1145/34344191介绍收益最大化是拍卖理论中的基本问题之一。迈尔森（Myerson，1981）的著名结果描述了只有一件商品出售时的收入最大化机制。具体来说，在单一买家的情况下，最佳解决方案是发布一个接受或放弃的价格。自Myerson的工作以来2012 a，2012 b，2013 a，2013 b;Daskalakis2015]。找到最优拍卖的问题比单一物品拍卖的问题要复杂得多不像迈尔森家Yu Cheng获得了NSF资助CCF-1527084、CCF-1535972、CCF-1637397、CCF-1704656、IIS-1447554和NSF CA-REER奖CCF-1750140。 Kamesh Munagala获得了NSF基金CCF-1408784、CCF-1637397和IIS-1447554以及Adobe数据科学研究奖的支持。Kangning Wang得到了NSF资助CCF-1408784和CCF-1637397的支持作者地址：Y。程，SEO416，851 S摩根街，芝加哥，IL 60607;电子邮件：yucheng@cs.duke.edu; N。上海市杨浦区武东路100号信息管理与工程学院; nikolai@mail.shufe.edu.cnMunagala，D205 LSRC，308 Research Drive，Durham，NC 27708;电子邮件：kamesh@cs.duke.edu;K. 王，D206 LSRC，308研究驱动器，达勒姆，NC 27708;电子邮件：knwang@cs.duke.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020计算机协会。2167-8375/2020/01-ART10 $15.00https://doi.org/10.1145/343441910ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月10点整：2Y. Cheng等人拍卖，最优可以使用随机分配和价格捆绑的项目已经为两件物品和一个买家还已知的是，最优随机化和最优确定性机制的收益之间的差距可以任意大[Briest等人，2010;Hartand Nisan2013];最优机制可能需要一个具有无限多选项的菜单[Daskalakis et al.2017; Manelliand Vincent2007]，当买家的估值分布向上移动时，最优拍卖的收入可能会减少鉴于最优拍卖设计的这些负面结果，最近的许多论文集中在近似最优的简单机制的设计其中一项著名的工作由Hart和Nisan [2017]发起的关于买方垄断问题的基本和自然设置，其物品价值独立于给定的分布D1，... ，Dm ，并且其对项目集合的赋值是加性1（线性的）。Babaioff etal.[2014年]结果表明，单独销售商品或销售大捆绑的更好机制至少提取了最佳收入的（1/ 6）部分。还观察到[Babaioff et al.2014; Hart and Nisan2013; Rubinstein and Weinberg2015]，对项目的独立性假设基本上是必要的，没有它，任何简单的（确定性）机制都不能近似最优。预算约束下的拍卖设计是一个更难的问题。由于买方的效用不再是准线性的，许多标准概念不再延续。2例如，即使对于一个购买者和一个物品，当预算为公共[Chawla etal.2011]，当预算是私人的时，可能需要指数大小的菜单（可能预算的数量呈指数级）[Devanur and Weinberg2017]。尽管做出了许多努力[Abrams2006; Bei et al.2012; Bhattacharya等 人 2010 a ， 2010 b; Borgs 等 人 2005; Chakrabarty 和 Goel2010; Chawla 等 人 2011; Che 和Gale2000; Chen et al.2011; Daskalakis 等 人 2015; Devanur et al.2013; Devanur andWeinberg2017; Dobzinski et al.2012; Goel et al.2015; Goldberg et al.2001; Laffont andRobert1996; Singer2010]，有预算的最优拍卖设计理论仍然远远落后于无预算的理论。在这篇文章中，我们调查的有效性，简单的机制存在的预算。我们的工作是由以下问题驱动的：在有预算的情况下，简单的机制有多强大？特别是，是否有一个简单的机制，是近似最优的一个独立的估值约束的买家？为此，我们考虑一个最基本的和自然的设置，广泛研究的monopoly问题的添加剂买家。在这种情况下，一个垄断的卖方出售m个项目给一个单一的买家。买方从任意（不相同）分布中独立地为每个项目得出附加估值。我们研究两种不同的预算设置：公共预算的情况下，买方有一个固定的预算已知的卖方，和私人预算的情况下，买方的预算是从分布。卖方希望通过设计一个受个人理性、激励相容性和预算约束的拍卖来最大化其收益。我们考虑贝叶斯设置，其中买方知道他的预算和他的价值为每一个项目，但卖方只知道先验分布。[1]如果买方对一组物品的价值等于他对该组物品的价值之和，则买方具有附加价值2例如，经典的VCG机制可能无法实现，在预算设置中可能无法实现社会效率[Singer2010]。一个简单的机制，为预算有限的买家10点整：3ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月Vweaklycorrelatedˆˆ∼ˆ|.i≤∼1.1我们的成果和技术我们的第一个结果是，简单的机制仍然是近似最优的，当买方有一个公共预算。THEOREM 1.1. 对于一个拥有已知公共预算和独立估值的附加买家来说，单独出售每件商品和出售大捆绑的更好方法可以提取最佳收入的恒定部分。定理1.1是在有限约束条件下对任意分布成立的少数几个正结果之一在我们的工作之前，不清楚任何提取最优收入的恒定部分的机制可以在多项式时间内计算在第3节和第4节中，我们提出了两种不同的方法来证明定理1.1。这两种方法都根据预算b（以不同的方式）截断估值分布V第一种方法以黑盒方式使用Babaioff等人[2014]的主要结果，第二种方法采用Cait等人[2016]中开发的基于对偶的框架。值得指出的是，我们的许多结构引理也适用于相关估值。利用这些引理，我们可以推广定理1.1，使买方的估值弱相关.我们称之为分布，如果它是一个条件的结果，独立分布V关于v V之和至多为c：V=V（vc）（形式定义见定义2.1）。CORO llARY 1.2. 设V为弱相关分布。对于一个拥有公共预算和来自V的估值的附加买家来说，单独销售和销售大捆绑的更好方法可以提取最佳收入的恒定部分。在第五节中，我们考察了私人预算的设定。预算b不再是固定的，而是从分配B中提取的。卖方只知道先验分布B，而不知道b的值。我们首先表明，如果估值可以与预算相关，这个问题至少是困难的无约束机制设计与相关的估值，简单的机制是无效的。鉴于这一负面结果，我们将重点放在预算分配B独立于估值V的设置上。在这种情况下，我们表明，简单的机制是近似最优的预算分布满足单调风险率（MHR）条件。第1.3节.当预算分配B是MHR时，单独定价和销售大捆绑的更好机制可以实现最优收入的恒定部分。我们将证明，假设买方有一个公共预算b=EbB[b]就足够了。定理1.3的证明使用MHR条件，以及对于公共预算b，（无约束）最优收益在b中是不减的，但最优收益除以b在b中是不增的。1.2相关工作与我们关系最密切的是以下两个行业。简单的机制。在Hart和Nisan发起的一系列工作中[Babaioff et al.2014; Cai and Zhao2017;Chawla and Miller2016; Hart and Nisan2017; Li and Yao2013]，Babaioff et al. [2014]首先表明，对于具有独立估值的添加剂买家，单独出售或出售大捆绑提取了恒定的最佳收入比例这后来被10点整：4Y. Cheng等人ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月∈--.∈ {}扩展到多个买家[Yao2015]，以及具有更一般估值的买家（例如，次可加性[Rubinstein andWeinberg2015]，具有共同价值成分的估值[Bateni等2015]和补充估值[Eden等2017]）。其他人研究了拍卖的复杂性和近似比之间的权衡，以及各种设置中小菜单机制的设计[Babaioff et al.2017; Cheng et al.2015; Dughmi et al.2014; Hart 和 Nisan2013; Tang 和Wang2017]。为预算受限的买家拍卖 关于预算约束对机制设计的影响，已经做了大量的研究工作。大多数早期的工作都需要对估值分布进行额外的解释，如正则性或单调风险率[Bhattacharyaet al.2010 b; Che and Gale2000; Laffont and Robert1996; Pai and Vohra2014]。我们提到了一些适用于任意分布的结果。对于公共预算，Chawla等人。[2011]设计了几个单参数设置和多参数设置与单位需求买家（我们的文章涉及添加剂买家）的近似即时最优机制。对于私人预算，Devanur和Weinberg [2017]描述了一个项目和一个买家的最佳机制的结构Daskalakiset al. [2015]给出了一个常数因子近似的加法投标人，其私人预算可以与他们的价值相关。然而，它们要求明确给出买家的估值分布，在我们的设置中，这是指数级的。在无先验设置中也有近似和硬度结果[Abrams2006; Borgs et al.2005; Devanur et al.2013]，以及设计帕累托最优拍卖[Dobzinski et al.2012; Goel et al. 2015年]。其他相关工作。我们的工作涉及添加剂买家的收入最大化。文献中广泛研究的另一种自然和基本情景涉及具有单位需求偏好的买家[Chawla et al.2007，2010，2015]。研究了标准贝叶斯方法下可加预算购买者的垄断问题。在这个框架中，先验分布是卖方已知的，通常被假设为是独立的。与此框架并行，在一个新的鲁棒优化框架中研究了（预算）添加剂垄断问题[Carroll2017; Gravin and Lu2018]。另一组关于预算可行机制设计的论文[Bei etal.2012; Chen et al.2011; Singer2010; Singla and Krause2013]研究了不同的反向拍卖设置，并关注价值最大化。2预赛2.1最优机构设计我们研究了最优拍卖的设计，一个买家，一个卖家，和m个异质项目标记为[m]= 1，.，m.每一项都只有一个副本，并且这些项是不可分割的。买方具有可加估值（v（S）=j Sv（i），对于任何集合S[m]）和公开已知的预算b。3我们用vRm表示买方我们考虑贝叶斯设置的问题，其中买方的价值是从一个离散的4分布V。设T=supp（V）是V中所有可能的估值分布的集合。我们使用f（t）对于任意t∈T，表示V的概率质量函数：f（t）=Prv<$ V [v=t]。设Tj=supp（Vj）。我们说价值分布V在所有项目之间是独立的，如果它可以表示为V=×jVj。3本文主要研究公共预算案例。因此，我们定义符号，并讨论背景假设买家有一个公共预算。[4]与以前关于简单和近似最优机制的工作一样，我们的结果也扩展到了连续类型，由于我们可以离散化类型使得收入任意接近（参见，例如，Cai等人[2016]进行了更详细的讨论）。一个简单的机制，为预算有限的买家10点整：5ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月→→联系我们.∈≤ ∀ ∈≤ ≤ ∀ ∈∈i=1我们假设买方是风险中性的，并具有准线性效用时，支付不超过他的预算。设π：T[0，1] m和p：TR分别表示机制的分配规则和支付规则。也就是说，当买方报告类型t时，他收到物品j的概率是πj（t），他的预期支付是p（t）（在机制的随机性因此，如果买方具有类型t，则他的报告类型tJ的（预期）值正好是π（tJ）Tt，5，并且他的报告类型tJ的（预期）效用是π（tJ）Tt−p（tJ），如果p（tJ）≤b，以及- ∞否则。根据启示原则，考虑激励相容的机制就足够了（即，“真实”）。一个机制M=（π，p）是（临时）激励相容的（IC），如果买方被激励说实话（在机制的随机性上），并且（临时）个体理性的（IR），如果买方的期望效用是非负的，每当他如实报告。我们使用对于不参与拍卖的选项（π（π）= 0，p（π）= 0），设T+=T。然后，IC和IR约束可以统一如下：u（t，t）≥ u（t，TJ）<$t ∈ T，TJ∈ T +.总而言之，当卖方面对单个买方，预算b和估价来自V时，最优机制M=（π，p）是以下（指数大小）线性规划（LP）的最优解：maximizetTf（t）p（t）满足π（t J）Tt − p（t J）≤ π（t）Tt − p（t），τt ∈ T，t J∈ T +.0πj（t） 1，tT，j [m].p（t）b，tT.π（π）= 0，p（π）= 0。（一）如果相应的约束对所有可能的结果都成立，而不对机制中的随机性进行平均，则该机制分别被称为事后IC、事后IR或事后保序。我们将展示对每个项目单独定价和对大捆绑定价的更好方法，大捆绑是一种确定性的事后机制，可以从任何临时机制的收入中提取一个常数。2.2简单的机制对于估值分布为V的买方，我们在分析中经常使用以下符号-REV（V）：最优真实机制的收益。-SREV（V）：通过对每个项目单独定价可获得的最大收入。-BREV（V）：通过对大捆绑定价可获得的最大收入。-REVb（V）：当买方有预算b时，最优真实机制的收益。-SREVb（V）：当买方有公共预算b时，通过对每个项目单独定价可以提取的最大收入。-BREVb（V）：当买方具有公共预算b时，通过对大捆绑定价可以提取的最大收入。我们知道，SREV（V）是通过对每个物品分别运行Myerson最优拍卖得到的5我们使用x Ty=。M表示两个向量x和y的内积。.Ju（t，t）10点整：6Y. Cheng等人ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月∈ˆˆ∈◦◦|◦◦≤∼∼∼ ∼ ≤∈≥≥Pr[v=t]=Pr [v=t|[v<$1≤c]，[t∈sup（V）.≥ ≤→item.类似地，BREVb（V）也是一个单参数问题，只不过公布的价格最多为b。SREVb（V）的情况更复杂。例如，当类型tRm的预算购买者参与拍卖，每个物品j的标价为pj时，他将通过解决KnAP sA ck问题来最大化他的效用。存在提取SREVb（V）的恒定分数的多时间可计算机制（例如，参见Bhattacharya et al.[2010年a]）。然而，在这篇文章中，我们只需要一个温和的假设，即买方将购买最大子集的项目，如果买方价值的项目超过其价格，他仍然可以负担得起，那么他会买它。2.3弱相关分布如果导致相关性的唯一条件是其和的上限，则我们称V这样的分布为弱相关定义2.1. 对于m维独立分布V和阈值c> 0，我们重新移动任意tsupp（V）上的概率质量，使t1>c，并重新归一化。令V：=V（v1c）表示所得分布。从形式上讲，vVvV弱相关分布在我们的分析中自然出现。我们将证明，如果买方2.4一阶随机优势随机优势是随机变量之间的偏序。 一个具有supp（X）<$R（弱）一阶随机变量X优于另一个具有supp（Y）<$R的随机变量Y当且仅当对任意a ∈ R，Pr[X ≥ a] ≥ Pr[Y ≥ a]。这种随机优势的概念可以扩展到多维分布。在这篇文章中，我们使用坐标优势的概念。定义2.2. 给定两个m维分布D1和D2，我们说D1坐标方向的随机占优D2（D1D2或D2D1），如果存在一个随机映射f：supp（D1）supp（D2），使得当xD1时f（x）D2，且f（x）x坐标方向的概率为1。这个概念有助于我们表达在某些情况下最优收益的单调性。例如，我们可以证明当V1V2时，SREV（V1）SREV（V2）。映射f允许我们将v1V1和v2V2的抽奖结合起来，因此对于一组固定价格，如果买家在v2下购买物品，他也会在v1下购买。3公共预算在本节中，我们将重点放在公共预算的情况下，证明我们的主要结果（定理1.1）。买方有一个固定的预算b和估值来自一个独立的分布V。定理1.1. R EVb（V）≤ 8SR EVb（V）+23BR EVb（V）。一个简单的机制，为预算有限的买家10点整：7ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月∞31≤◦ ◦◦ ◦◦◦∞∼ ◦ ◦∈◦◦≥∞10101010因此，SREVb（V）和BREVb（V）中的较佳者至少为REVb（V）。6我们的方法概述。而不是采取拉格朗日对偶的LP（1）推导出一个上限的最佳目标值REVb（V），我们采用了一个更组合的方法。直觉上，我们提出了一个充电参数，它将REVb（V）拆分，并将每个部分充电到SREVb（V）或BREVb（V）。以下是证明大纲：首先，我们划分买家类型，supp（V）分为两组：高值类型， 不b和低值类型，其中t0且d0c时，我们通过预算b上限卖方 c，我们运行REVb（V）的最优机制。P屋顶的 LEMMA3.5. 让和 、和表示支持度和概率密度函数V和V分别。设M∈=（π∈，p∈）是获得REVb（V）的最优机制.回想一下，π和p是分配和支付规则，（π，p）是LP（1）对f和T的最优解。我们将最优收入分为两部分：R EVb（V）=.f（t）p（t）=.f（t）p∈（t）+.f（t）p（t）.因为p≠（t） b，第一项至多是bt>cf（t）=bPr[v1>c]（b/c）BRE Vb（V）be-因为我们可以以价格p = c出售大丛。第二项至多为REV，因为是LP的可行解。在关于MonV：REV（V）≥.t∈Tf（t）p（t）≥t∈T，.最大值1≤cf（t）p（t）≥t∈T，.最大值1≤cf（t）p（t）.结合上界，我们得到RE Vb（V）≤（b/c）BRE Vb（V）+RE V（V）。□3.2引理3.3的证明引理3.3指出，当v JV J的和通常很小时，预算对Vj并不太重要。直觉上，因为v JV J的每个坐标是独立的，并且由b限定上限，所以浓度不等式意味着和具有指数衰减的尾部。因此预算约束不太重要，因为购买者对大捆绑的价值不太可能◦t ◦1>c最大值1≤c一个简单的机制，为预算有限的买家10点整：9ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月◦ ◦J JVJ JVvJJV1010....≤≤.≤Jc=bV=V≤ˆˆ≤ ≤ˆˆc≠2cbSREV（V）≤max（1，）SREV（V）.ˆ≤ ≤BRE Vc（V）=ma x.p·Pr[nvnn1≥p]n≤ max.p·Pr[vvvv1≥p]v=BRE Vb（V）.B我们通过证明以下引理来形式化这种直觉，这与标准的尾界相似主要区别在于，我们不知道v J1的均值很小，而只知道BR EVb（V J）很小。3.6. blog 如果VJ是独立的，并且对于所有vJ∈VJ，v j∈∞≤c，则nPRvJvJ. vJ<$1≥x+y+c。≤vPr. vj·vPr. vj对于所有x，y>0。特别地，如果PrvJ<$VJ[<$vJ<$1≥c]≤q，则当f或所有整数k≥0时，PRvJvJ.n_v_J≥（2k+1）c.≤qkPr . n≥c. .我们将引理3.6的证明推迟到附录A，首先使用这个尾界来证明引理3.3。LEMMA3.3的概率。 L e tc=b且q=1。WeknowthatPr[nvJn1≥c]≤q fromthe p-BR EVb（VJ）≤b.首先证明了BRE Vb（VJ）=maxp≤b（p·Pr[vvJ<$1≥p]）. 如果我们把这一大捆东西定价为p米，其中，对于某个k≥0，（2k+ 1）cp≤（ 2k+ 3）c，根据引理3.6，收益至多为1>c的情况下扩展全部收入，并在以下情况下运行最优的收入约束机制来上限收入：vjSR E V（VJ）≤SR E Vc（VJ）+E 。vJ<$1≤SRE Vc（VJ）+。∞（2k+3）c·Pr.n_v_J≥（2k+1）c.SREVc（VJ）+∞（2k+ 3）qk BREVc（VJ）k=0≤SR EVc（V J）+4BR EVc（V J）。□3.3引理3.4的证明引理3.4指出SREVb（V）和BREVb（V）都是V中的单调（直到常数因子）。我们证明了一个更一般的版本的引理，不需要V是独立的。回想一下，V≤V意味着V是由V支配的坐标随机数。第3.7章. 固定b>0且d00。 LetV=V|（n ≤v≤1≤c）。WehaveREV（V）≤我们把引理4.1的证明推迟到附录C。我们首先利用这些引理证明定理1.1和推论1.2。□一个简单的机制，为预算有限的买家10点整：ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月VVVV∼◦ ◦≤|◦◦≤1◦ ◦∼bb<$REV（V）≤（b/c）·BREV（V）+REV（V）（引理a3. 第五章）ˆ≤≤|◦◦≤|◦◦≤11ˆˆˆ ˆˆ≤b≤（V）v≤b/>vV1◦◦≥∼V=Vc=b|（v≤c）1VVVVB1ˆ|◦◦≤T HEOREM1.1和COROllary1.2的P屋顶。 如果min vVv1b/2，那么卖方可以将大捆的价格定为atb/2，买方总是购买它。在这种情况下，R_ev_b（V）=b/2，2BREVb.因此，我们专注于更有趣的情况下，Pr [2] 0。7让 ：for/ 2.我们将重复使用第3节中的引理3.5和3.7。我们可以重复使用这两个引理，因为它们不要求或不要求是独立的，不修改V的小和部分，并且V≤V（此时我们将使用引理D.2inAp p e nominalD）.≤2BREVb（V）+ 5SREV（V）+ 4BREV（V）（引理4.1）=2BREVb（V）+ 5SREVc（V）+ 4BREVc（V）（V≤1≤c）≤2BR EVb（V）+5SR EVb（V）+4BR EVb（V）。（引理3.7）我们现在证明推论1.2。直觉上，推论1.2成立，因为简单的机制对弱相关估值很有效，而弱相关的概念在进一步的假设下是封闭的。最高限额设V=V（vc2）为输入分布。如果c2b，则我们可以去除预算约束，并应用Lemma4.1directctly。当c2>b时，新方法可以在c1=b/2处对V进行计算，得到一个弱的c或r分布.我们可以证明引理3.5和3.7仍然成立。和 引理4.1成立对于V.唯一的区别是，我们需要显示V（vc1） V（vc2） 对于C1 c2.我们将 在附录D中证明这个（引理D.1）。□5的私人预算在本节中，我们考虑预算b不再是固定的，而是从分布B中提取的情况。根据以下观察，我们假设B独立于V如果我们允许B和V相关，一个自然的模型是，买方在这种情况下，这个问题至少和在无风险设置下为任意相关的估值找到（近似）最优机制一样困难考虑一个例子，其中所有可能的预算都大于maxvVv1，因此它们是不相关的。然而，预算仍然可以用作信号（或相关设备）以产生相关估值。它众所周知，对于相关分布，单独销售和捆绑在一起的更好[Hart和Nisan2013]，甚至最好的基于分区的机制[Babaioff et al.2014]都不能提供恒定的近似值。另一个自然的模型是我们先画出v，V，i这也至少和相关估值的情况一样困难，因为我们可以如果我们希望v在相关分布中，则b=0，如果我们不希望v在相关分布中，则b>v1这些负面的观察促使我们研究私人预算设置时，预算分布B独立于估值分布V。5.1单调风险率预算我们关注的情况下，预算是独立的估值，它是从一个连续的8MHR的差异。Letд（·）和G（·）是概率密度函数和累积量分布函数 . MHR条件是<$（b）−G（b） 在B中不减少。7在整篇文章中，当我们考虑条件分布V：=V（v1c）时，我们将始终有c>minv∈supp（V）1，使得我们所假设的事件以非零概率发生[8]如果分布是离散的MHR分布，类似的结果仍然成立。对于离散分布，我们有Prb<$ B [b≥b] ≥e−1而不是fPrbB[b≥b] ≥e −1。10点整：Y. Cheng等人ACM Transactions on Economics and Computation，卷。号92、第十条。出版日期：2021年1月2e∼≥≥≥≥∼布≤2e≥∫∫b5.1. biggest 设b是MHR分布B的期望。 假设M是具有公共预算b的买方的最优机制。然后，在预期中，M*提取至少1-分数的预期最优收益时，买方有一个私人预算从B。P屋顶。设R（b，V）表示当买方有公共预算b和来自V的估值时M的预期收入。设R（B，V）=EbB[R（b，V）]表示当购买者的预算来自B时M的R（B，V）=B<$（b）R（b，V）db≥<$b≥b<$（b）R（b，V）db∗=b≥b <$（b）R（b，V）d b ≥ e−1·R（b，V）.倒数第二步使用R（b，V）=R（b，V）当bb时，因为M提供了一个分配/支付对的菜单供买家选择;预算为b的买家可以负