具有相互依赖价值的简单拍卖的无ZF状态价格

（1）我们区分以下两种情况：情况1：投标人i没有赢得投标程序(si，B-I)下的项目。因此，她的效用为0。此外，存在一个投标人j6=i，使得vj(si,b-i)≥vi(si,b-i)。由于投标人w(b)赢得atb，所以vw(b)(b)≥vj(b)。通过引理3.6（使用d=max{γ，c}），max{γ，c}vw(b)(si,b-i)≥vj(si,b-i)≥vi(si,b-i).再次应用引理3.6，我们得到max{γ，c}vw(b)(s)≥vi(s).因此ui（（si,b-i）；s)=0≥vi(s)-max{γ，c}vw(b)(s).情况2：投标人i赢得了投标程序（si,b-i)下的项目。设b*i≤sibe i的临界bidgen b-i。ui（（si,b-i）；s)=vi(s)-vi(B*i,b-i)。如果w(b)=i，ui((si,b-i)；s)≥0≥vi(s)-max{γ,c}vw(b)(s)，否则，w(b)6=i。设bi≥bibe为最低信号，使得vi(bi，B-I)∈argmaxkvk(bi，B-I)，存在这样的bi≤sisince i在投标方案b下不获胜，但在投标方案（si，B-I)下获胜。根据相同的论元和估值的连续性，存在J6=i使得vj(bi，b-i)∈argmaxkvk(bi，b-i)。根据推论3.6，max{γ，c}vw(b)(bi，b-i)≥vj(bi，b-i)=vi(bi，b-i)≥vi(b*i，b-i)，其中最后一个不等式是由临界出价决定的。因此，ui((si,b-i）；s)≥vi(s)-max{γ,c}vw(b)(bi,b-i)≥vi(s)-max{γ,c}vw(b)(s)，其中最后一个不等式后面是b≤s和估值的单调性。这就得到了（1）的证明，我们现在可以建立B-POA上的界：设σ=(σ，..，σn)是满足nob的BNE；即对于σ(s)支持下的任何b，b≤s。设Ii(s)为eventi=argmaxjvj(s)的指示变量（任意断开联系）。回想一下，Eq(σ)表示均衡σ中的福利。我们得到:Eq(σ)≥EshXiui(σ(s)；s)i(2)≥xies[ui(si,σ-i(s-i)）；s)](3)≥xies[ii(s)·(vi(s)-max{γ,c}vw(σ(s))(s))](4)=EshXiIi(vi(s))i-max{γ,c}EshXiIi(s)vw(σ(s))(s)i=es[maxivi(s)]-max{γ,c}es[vw(σ(s))]=opt-max{γ,c}Eq(σ),其中（2）成立，因为效用的总和是由福利支配的。（3）均衡假设（和期望线性）成立。（4）由（1）持有。在精确SC（即c=1)下，该界进一步提高到γ（见命题c.1)。定理3.4的证明。病例1：NE-PoA为C。考虑信号空间s=s=s=[0,1]和以下估值:V=βs+1V=Cβs+SV=Cβs+s，其中接近于0。设实信号为s=1。我们声称出价向量（0,1,1）是一个均衡；代理1赢了，并且在广义Vickrey中支付1（临界出价支付），并且她不能通过增加出价来增加她的效用（她的支付相对于b-1是最小的）。在无出价条件下，其他代理人不能提高出价，也不能通过降低出价而获胜，因此双方都不存在收益偏差。在此均衡条件下，实现的福利为β+1，但最大福利为Cβ+。当β任意大时，NE-PoA任意接近C。情况2：NE-PoA为γ。考虑信号空间s=s=s=[0,1]和以下值:V=γβSV=βs+SV=γβs+s，其中接近于0。设实信号为s=1。我们声称出价向量（0,1,1）是一个均衡；代理2 winsand支付，在她不能增加她的出价来增加她的效用（她的支付相对于B-2是最小的）。Agent 1不能通过增加出价来获胜，因为Agent 3每发送一个出价，其价值就比Agent 3大，而且Agent 3的出价在其信号空间中很小，所以Agent 1不能降低其出价；此外，代理3由于其信号空间中的最大值而不能提高其出价，也不能通过降低出价来赢得该项目。因此，两个代理人都没有收益偏差，在这个均衡中，实现的福利是β+1，但最大福利是γβ+。当β可以任意大时，NE-PoA任意接近于γ.4多项：一个正结果在本节中，我们研究多项和单位需求代理的设置。

经过多项初步研究，我们确定了一个限制Agent之间知识不对称的条件，该条件可以用来适应正的PoA结果。然后我们用它证明了一个简单同时拍卖在n≥m条件下的PoA保证（定理4.7）。（对n m方案进行5.）4.1多项目预赛参与。类似于Syrgkanis和Tardos[2013]，我们假设代理可以向物品拍卖者传达他们是否希望参与和竞争被出售的物品（除了他们的信号报告之外）。agent i的总体报告为(bi，ai)，其中Bii是agent的m个信号的报告（出价）的向量，如果agent参与拍卖，则ai是ai=1的参与向量，否则ai=0。该代理的（混合）策略σi（si）给定她的信号向量，然后是一个分布在可能的报告(bi，ai)。在附录D中，我们认为如果代理人被要求参与所有的拍卖，这将导致一个糟糕的POA.标记和假设。设b（分别a）是n个信号报告bi（分别ai）的表达式，并用σ(s)表示给定信号表达式s的策略表达式，即(b，a)对上的分布。我们使用Xi(b，a)来表示由独立拍卖代理i分配的项目子集，给定投标和参与结果b，a。在本节中，我们陈述了我们的估价结果，以满足c-SC和γ-异质性。多个项目的标准NOB假设本质上限制了每个代理对子集X中项目的出价之和至多该代理对X的价值。我们现在在IDV：定义4.1（IDV的多项目NOB）中正式定义了这一概念。对于多项，如果对于具有信号siit的每个agent i持有-i:/f-i,(b，a)'Aσ(s)hx`∈Xi(b，a)Vi`(Bi`，s-i`)i≤ES-I:/f-i,(b，a)'Aσ(s)[Vi(Xi(b，a)；s)],则策略Profileσ=(σ，..,σn)满足NOB。（5）注意，如果估值是私有的，这与标准的NOB假设相一致。4.2有限知识不对称的条件我们提出了一个使我们的正PoA结果成立的条件。我们使用以下定义：定义4.2（截断值和福利）。对于每个代理i和项`，截断值～vi`给定信号profireles为～vi`(s)=～vi`(s\')=minj6=ivi`(S-J`,0J`)。截断最优匹配(s)是argmaxmatchingμ{P(i，`)∈μ～vi`(s)}中的匹配，（任意断开关系），期望截断福利isgOpt=es'Aflut(i，`)∈em(s)～vi`(s)。换句话说，截断值～vi`(s)是除i自己的最重要信号被归零后，i对项目的值；em(s)是一个分配，在给定s的情况下，相对于截断值，社会福利最大化；而GOPT是相对于截断值的最优社会福利。根据信号中值的单调性，gOpt≤opt。给定一个相互依赖的环境，有限知识不对称条件如下：存在一个常数d，使得ATD·gOpt≥opt。（6）直观地说，如果截断值Vi`(s)与真实值Vi`(s)相去甚远，这意味着agent I对item的值在很大程度上由单个agent所持有的信息决定，而这个agent本身并不是。这意味着我和知情代理人之间存在信息不对称。条件（6）排除了几乎所有福利都源于这种信息不对称的环境。在这样的极端环境下，所有形成价值的信息都可以追溯到一个单一的因素--就像威尔逊的早期和经过充分研究的“排水道”模型[Wilson,1969,Milgrom,2004]一样。我们现在给出两个相反的例子：一个自然的环境，其中（6）中的条件成立（例子4.3)，和一个极端的环境，其中一个主体拥有所有的信息（例子4.5）。对于第二个例子，我们给出了一个自然机械族的PoA的Ω(m)的下界。例子4.3（重提加权和值）。回想一下示例1.1中介绍的转售模型。

我们将此示例扩展到多个项：为了简单起见，假设n=m。对于每个单位需求主体i和项目`，当β≤1时，设Vi`(s)=Si`+βPJ6=ISJ`（其中对β的限制保持SC性质）。我们假设所有信号都是I.I.D.绘制的。从单调危险率(MHR)分布（如均匀、正态分布或指数分布）。命题4.4。在例4.3中，对于一个su大的n，(1+e)gOpt≥opt.命题4.4的证明出现在附录D中。例4.5（代理1包含几乎所有信息）。考虑n个具有单维信号的单位需求代理。.、sn和信号空间s=[0,1]表示代理1,si={0}表示每个代理6=1。对于每个项`∈[n]，代理具有以下值：代理1的值是v1`=s，对于每个代理i6=1，vi`=(1-)s。注意，这些估值是SC和γ-齐次的。在示例4.5中，截断的值为i6=1的~v1`=sand~vi`=0。我们得到了gopt=s，而Opt>n(1-)s，因此不存在（6）所代表的常数d。命题4.6。对于每个投标人，设Hi`(s)为单调函数，使s,Hi`(s)≤Vi`(s),且Hi`(si`,0-i`)=Vi`(si`,0-i`)。每一种机制，根据HI`(s)将每一个项目单独分配给价值最高的代理，如果没有其他人参与，则向代理收取零支付，即使在NOB下，其EP-PoA也为Ω(m)。特别地，通过hi\'(s)=vi\'(s)，我们得到了同时进行2Pa或GVA拍卖的thisholds。命题4.6的证明出现在附录D中，并使用了示例4.5。如下一节所示，上述命题对于我们开发和使用来获得好的poaguarantes的机制是成立的。4.3肯定结果:n≥m个方案我们给出了一个简单的同时报价机制，并证明它的每一个BNE都达到O(max{γ，c}）逼近。对于满足方程（6）的估值，它意味着OPT的anO(d max{γ,c}）-逼近。在SC的特殊情况下（即c=1),每个BNE都达到O(γ)-逼近，对于满足方程（6）的估值，它意味着O(dγ)-逼近。在介绍该机制之前，我们提供了一些直觉，帮助Shit lighton选择我们的机制及其分析。具体来说，我们强调了我们的分析是如何将ERent从平滑性框架中分离出来的，平滑性框架已经成为为简单拍卖建立POA结果的标准技术。平滑性范式的一个关键步骤是为每个参与者寻找一个适当的假设偏差，这样对于其他竞标者的任何出价，该偏差所实现的效用被参与者对最优福利的贡献的一部分所限制，更少一些误差术语。对于独立的私人价值和单位需求竞标者，Christodoulou等人。[2016B]证明了对项`进行全入的假设偏差给出了以下保证:ui((Vi`,0i-`),b-i)≥vi`-maxj6=ibj`,（7）不等式(7)su-ces给出了完全信息设置下的PoA界。此外，这个界也通过一个扩展定理适用于信息不完全的情况，如下文所述，即使agent不知道其他agent估值的实现，她也可以从其他agent的价值分布中取样，并对她在取样市场的optimalallocation中得到的项目进行“All-in”，从而有选择性地模拟该agent对最优分配的贡献（在（7）右边的firerst项）。这就是所谓的“二重身愤怒”技术。然后，通过将误差项与抽样均衡的分配绑定并使用NOB假设来限定误差项。不幸的是，将这种类型的分析推广到IDV有一些主要障碍。尽管人们可以导出光滑型不等式，但它的右手边表达式将采取γ～vi`(s)-maxj6=ivj`(bj`，s-j`)的形式。

利用这个不等式，我们可以得到完全信息博弈的PoA结果，但由于以下原因，这些界不能推广到不完全信息的情形：(a)分身技术不能直接应用。特工i只知道SI，而不知道S-I，这会影响她的估价。因此，对其他投标人的信号进行采样，并相应地进行全入，将模拟比desiredone更精确的值分布，因为投标只考虑SI，而不考虑SI.(b)Christodoulou等人中的误差项。[2016b]关键是只取决于其他投标人的投标，但在IDV中，误差项也取决于代理的真实信号，这阻止了他们的分析通过。(c)我们设置的基准应该是截断的最优分配，而不是真正的最优分配。对于同时进行的第二次价格拍卖。为项目出价她的真实价值VI，为所有其他项目出价0。我们不在手稿中包括这个推导，因为它无助于我们证明B-POO的一个界。下面的观察推动了我们的分析：由于代理人只能访问他们自己的信号，在考虑我们所说的私有化估值时，分身技术可以成功地应用；即，在i的私人信号下对代理人i的估值，同时将他人信号的贡献归零。然后，我们可以利用γ-异构条件来断言其他竞标者对两个独立代理的估价信号的E-ect大致相同。上述讨论激励了我们提出的机制设计，即关于私有化估价的同时第二价格项目拍卖（见图1）。为了便于分析，我们将基准分为两个术语。fiefrst项(SELF)解释了私有化估值，第二项(OTER)解释了其他投标人的信号对基准的贡献（见等式（8））。我们继续为每一项分别提供光滑型不等式（见引理4.10）。具体来说，对于每一个术语，我们都确定了适当的假设偏差，这样均衡状态下的预期福利就“覆盖”了它。我们先把上面给出的直觉形式化。私有化的价值观。给定一个（报告的）信号profectionle b`for item`,代理J的私有化值vj`for`是当其他代理的信号设置为零时的值:vj`(b`)=vj`(bj`,0-j`)。我们可以互换使用VJ`(b`)和VJ`(bj`，0-j`)。观察私有化值的上限为截断值VJ`(b`)≤～VJ`(b`)。本节所分析的机理，实质上是对私有化后的代理人进行价格拍卖。定理陈述。我们着重于图中描述的简单机制。1,包括同时私有化的二价拍卖。该机制通过对参与该项目的代理的私有化价值进行二次价格拍卖来单独分配每一个项目。本节的主要定理如下：同时进行的私有化二价拍卖：出价和参与过程b和a。产出：分配和支付。对于每一个项目`（同时进行）：1。对于每个代理j，计算私有化值VJ`(B`)=VJ`(BJ`,0-j`)；2。将项`分配给agent i∈argmax{vj`(b`)aj`=1}；3。收费代理人i a付款pi`(b`,a`)=max{0,maxj6=i{vj`(b`)aj`=1}}；图1：同时私有化的二价拍卖。定理4.7。考虑一个具有m个项目，n≥m个单位需求代理，γ-异构的c-SC估值的环境。若d·gopt≥Opt为常数d，则无出价条件下同时私有化二价拍卖（见图1）的B-PoA为O(d max{γ,c}）,定理4.7中d·gopt≥Opt为必要条件，如hi`(s)=vi`(Si`,0-i`),命题4.6对同时私有化二价拍卖也成立。本节的其余部分致力于证明定理4.7。

我们使用以下符号：让ui（（b,a）；s）表示agent I在投标程序（b,a）和信号程序（s）下的效用。设Pi`(B`，A`)为图中的结果。1.我们将福利按上述方式分解。回顾第4.2条，em(s)是相对于信号profirele处的截断值最大化社会福利的目标，我们将其分解如下:Gopt=ES X(i，`)∈em(s)～Vi`(s)=ES X(i，`)∈em(s)Vi`(s)-Vi`(Si`，0-i`){z}自身+ES X(i，`)∈em(s)～Vi`(Si`，0-i`){z}其他。（8）为了证明定理4.7，我们证明了平衡‘复盖’了上述分解中的两项。引理4.8和4.9表明了这一点，它们分别在4.3.2和4.3.3节中得到了证明。对于每个BNEσ，2eq(σ)≥self，引理4.9。对于每一个BNEσ，O(max{γ，c}）·Eq(σ)≥other，利用这些引理，我们证明了定理4.7。定理4.7的证明。将引理4.8和4.9与方程（8）和（6）相结合，对于每一个bneσ，我们有(2+max{γ,c}·(max{γ,c+1}+2))Eq(σ)≥SELF+OTHER=gopt≥opt/d。我们继续证明引理4.8和4.9，使用两个利用光滑型不等式的偏差（引理4.10)，如下文所述。4.3.1用于相互依赖的光滑型引理。在限定PoA的标准光滑性框架中（具有独立的privatevalues)，一种主要的证明技术利用了这样一个事实，即在平衡状态下，agent i不能通过对其中一项进行“全入”来提高它的效用。在相互依赖的设置中，代理并不完全知道自己的值，所以all-in意味着以下（在没有过度出价的情况下）：只参与项目`（即，对每个项目k6=`报告AI`=1和AIK=0)，并为该项目出价BI`=SI`（其他项目的出价可以是任意的）。为了形成下面的平滑型论证引理4.10，我们用(bi，ai)表示代理人i的全入报告，并让j`=j`(b，a)是私有化第二价格拍卖（图1）在出价表(b，a)下分配项目`的代理人。如果物品不是在(b，a)分配的（没有代理参与物品的拍卖），那么让J`(b，a)是一个对物品`具有常值0的虚拟代理。我们现在陈述引理：引理4.10。考虑代理i，投标报价(b，a)，项目`的全入报价(bi，ai)，以及真正的信号报价S。那么代理i的实用程序ui（（bi,b-i）,（ai,a-i）；s）从All-in for`至少是(i)vi`(s`)-maxj6=i:aj`=1{vj`(bj`,0-j`)}，(ii)vi`(s`)-max{γ,c+1}·vj``(bj``,s-j`)·ii6=j`-vj``(s`)·ii=j`。证明。我们从下界(i)开始，考虑两种情况：情况1：当进入all-in agent i时，没有分配项`（因此没有分配项）。在这种情况下，我们有maxj6=i:aj`=1{vj`(bj`,0-j`)}≥vi`(Si`,0-i`)=vi`(S`)，并且由于代理i的效用为0，下界(i)保持不变。因此，她的实用工具是vi`(S`)-pi`((bi，b-i)，(ai，a-i))≥vi`(S`)-maxj6=i:aj`=1{vj`(bj`，0-j`)}，并且(i)保持。我们现在进行下界(ii)。注意代理i的效用从全入出价是非负的（我最多支付她的价值`和不竞争其他项目）。考虑AgentJ`=J`(b，a)（如果代理人i报告(bi，ai)，而不是全力以赴，则在私有化的第二价格拍卖中，项目的获胜者）。如果J`实际上是代理i（所以ii=J`=1)，那么她的效用从全入isui(((bi，B-I)，(ai，A-I))；s)≥0=～Vi`(s)-～VJ`(s)≥～Vi`(s)-VJ`(s)。如果J`6=i，还有待于说明(ii)。我们再次考虑前面的两种情况：情况1：当进入all-in agent i时，没有分配项`。

我们有vj``(bj``,0-j``)≥vi`(si`,0-i`)。此外，通过c单交叉，我们有c vj``(bj``,si`,0-{ij`}`)-vj``(si`,0-i`)≥vi`(bj``,si`,0-{ij`}`)-vi`(si`,0-i`)。结合以上两个不等式，我们得到vi`(bj``,si`,0-{ij`}`)≤vj``(bj``,0-j``)+c vj``(bj``,si`\')+c vj``(bj``,si`,0-i```)-vj``(Si`,0-i`)≤(c+1)vj``(Bj``,si`,0-{ij`}`)，其中最后一个不等式是由于估值函数的单调性。通过应用推论3.6，我们得到max{γ,c+1}·vj``(bj``,s-j``)≥vi`(bj``,s-j``)≥～vi`(s)。由于我们在i没有得到项目的情况下，她的效用为0，并且(ii)保持。情况2：当进入all-in agent时，i被分配项目`。注意，在本例中，vj``(b`)=pi`((bi，b-i)，(a，a-i))（由于认识到pi`，并且j`具有最高的私有化值）。我们有thatui(((bi，b-i)，(ai，a-i))；s)=vi`(s)-pi`((bi，b-i)，(a，a-i))=vi`(s)-vj``(b\')≥～vi`(s)-vj``(bj``，s-j``)。因此，(ii)保持不变。有了这些不等式，我们现在继续证明引理4.8和4.9.4.3.2引理4.8的有界自证明。考虑以下对代理I均衡策略的偏离。Agent对一个替代信号进行ISAMONLE t(R)F，计算一个匹配的MI=em(si,T-I)，并对miishe在MI中匹配的项进行ALL-INS。如第4.3.1节所示，all-in报告为ai`=1，如果`=mii，否则为0，而bimii=simii。我们的目标是显示2eq(σ)≥self。我们注意到:eq≥xies(R)f(b，a)σ(s)[ui((b，a)；s)]≥xies，Tf(b，a)σ(s)mi=em(si,t-i)ui(bi,ai,b-i,a-i）；s^≥Xies,T^f(b，a)^σ(s)MI=em(si，T-I)“VIMII(simii,0-IMII)-MAXJ6=I:AJMII=1{vjmii(bjmii，0-JMII)}#。（9）在上面，不等式成立是因为福利大于效用，第二不等式成立是因为均衡假设，第三不等式来自下界(i)引理4.10。考虑EQ中的不等式项。(9):xies，téfmi=em(si,t-i)hvimii(simii，0-imii)i=xieséfmi=em(s)hvimii(simii，0-imii)i=esx(i，`)∈em(s)vi`(si`，0-i`)=SELF,（10）其中的等式是通过重命名的。至于eq中的第二项。(9)，筛选代理i,Es,t=f（b,a）=σ(s)mi=em（si,t-i）“maxj6=i:ajmii=1{vjmii(bjmii，0-jmii)}#=Es,t=f（b,a）=σ(si,t-i）mi=em(s)”maxj6=i:ajmii=1{vjmii(bjmii，0-jmii)}#=Es,t=f（b,a）=σ(t)mi=em(s)“maxj6=i:ajmii=1{vjmii(bjmii，0-jmii)}#≤Es,t=f a)'Aσ(t)mi=em(s)”maxj:ajmii=1{vjmii(bjmii，0-jmii)}#，其中的相等性是通过重命名的，第二个是因为该术语不使用（bi,ai）。回想一下，Xi(b，a)表示代理i在投标程序(b，a)下收到的项目子集。我们有xies,tèf(b，a)'Aσ(s)mi=em(si,t-i）“maxj6=i:ajmii=1{vjmii(bjmii，0-jmii)}#≤Es,tèf(b，a)'Aσ(t)mi=em(s)”ximaxj:ajmii=1{vjmii(b，a)'Aσ(t)xix`∈Xi(b，a)vi`(bi`，0-i`)≤etóf(b，a)'Aσ(t)“xivi(Xi(b，a)；t)#=Eq(σ)，(11)，其中，firerst等式是由同时私有化二价拍卖的分配规则导出的，而第二个不等式是由不出价假设导出的。将方程（9）-（11）结合起来，在自身上得到了期望的界。4.3.3在本节中，我们证明了引理4.9。为此，我们使用以下引理：引理4.11。对于每两个代理i和j，项`和信号profoile s,max{γ,c}·～vj`(s)≥～vi`(s)-vi`(Si`,0-i`)。证明。考虑代理j，设K6=j是某个代理，使得~vj`(s)=vj`(0k`，s(-k)`)。我们考虑了两种情况：情况K6=I:在这种情况下，～vj`(s)≥vj`(0k\'，S-K`)-VJ`(SI`，0-I`)≥(VI`(0k`)，s-k`)-vi`(Si`，0-i`))/max{γ，c}≥(～vi`(s)-vi`(Si`，0-i`))/max{γ，c}，其中第二个不等式来自引理3.5，第三个不等式来自截断值的确认。情况k=i:在这种情况下，～vj`(s)≥vj`(0i`，S-i`)-vj`(0)≥vi`(0i`，S-i`)-vi`(0))/max{γ，c}≥vi`(0i`，S-i`)-vi`(0))/max{γ，c}≥vi`-vi`(Si`，0-i`))/max{c}，其中第二个不等式来自引理3.5，第三个不等式来自他人信号中的Ubmodularity（定义2.2）。引理4.9的证明。

考虑以下偏离agent i的均衡策略的情况，其中iis是m个agent中的一个：agent i∈[m]为项目i全入。如果`=i，all-in报告为ai`=1，否则为0，bii=si.如果没有这个子模块化假设，这个声明是不成立的，如函数vj`(si,sj,sk)=vi`(si,sj,sk)=si·sj+si·skwith si=sj=sk=1所示。在这种情况下，γ=c=1,不等式的LHS为0,RHS为1。我们的目标是表示max{γ,c}·(max{γ,c+1}+2)·Eq(σ)≥other。回想一下，对于项目`，J`(b，a)是我们的机制在投标程序(b，a)下向其分配项目`的代理。我们注意到:eq≥mxi=1es'Af(b，a)'Aσ(s)[ui((b，a)；s)]≥mxi=1es'Af(b，a)'Aσ(s)选项ui(bi，ai，b-i，a-i)；s^≥mxi=1es^f(b，a)'Aσ(s)ji=ji(b，a)[～VII(s)-max{γ,c+1}·vjii(bjii，s-jii)·II6=ji-vjii(s)·II=ji]。（12）在上面，不等式成立是因为福利大于效用，第二不等式成立是因为均衡假设，第三不等式来自下界(ii)引理4.10。考虑EQ中的不等式项。(12):ES“MXI=1～VII(s)#≥ES X(i，`)∈em(s)～V``(s)≥ES X(i，`)∈em(s)～Vi`(s)-Vi`(Si`，0-i`)/max{γ，c}=Othere/max{γ，c}，(13)其中第二不等式从引理4.11中得出。至于EQ中的第二项。(12):mxi=1eséf(b，a)'Aσ(s)ji=ji(b，a)[max{γ,c+1}·vjii(bjii，s-jii)·ii6=ji+vjii(s)·ii=ji]≤max{γ,c+1}eséf(b，a)σ(s)ji=ji(b，a)“mxi=1vjii(b，a)σ(s)ji=ji(b，a)”mxi=1vjii(b，a)ji=ji(b，a)“mxi=1vii(s)ji=ji(b，a)”`(bi`,s-i`)+esíf(b，a)'Aσ(s)“mxi=1vii(s)·i∈Xi(b，a)#≤max{γ,c+1}esíf(b，a)'Aσ(s)”xivi(Xi(b，a)；s)#+Es'Af(b，a)'Aσ(s)″MXI=1VI(Xi(b，a)；s)#=(max{γ,c+1}+1)Eq(σ),(14)，其中第一个不等式是由于对ji(b，a)的认识而产生的，第二个不等式是由无出价假设产生的。将方程（12）-（14）结合起来，得到另一个方程的期望界。5多项：负结果在本节中，我们表明对于多项的情况，在少项和多项的情况之间存在分离；也就是说，当项目比投标人多得多时，即使在非常简单的(a)公共值（这意味着γ=c=1)的情况下，也不能指望有一个独立于n的界；(b)对称估值：描述每个项目的估值函数是相同的，每个代理人/项目信号是I.I.D.绘制的；(c)gopt/opt-→1随着n的增加。在我们的设置中，每个代理i对于每个项目都有一个信号si`，它根据si`=(1W.P.1/N0水渍险。1-1/n，独立于（和相同地）其他项目。在定理5.1中，我们建立了最优福利与均衡福利之间的一个缺口，它是n的函数。在给出结果之前，我们先提供一个高层次的描述，并提供一些直觉。o考虑一个任意的n项集合。在这个集合中，大约有n个高信号分布在项目上，大致均匀。我们可以使用balls-and-bins类型分析来表明，在这个集合中，价值最高的项目的价值大致为ln n/ln ln n，直到常数（见索赔5.2）。因此，如果我们任意地将nitems划分为n个大小为n的集合，并将每个集合中价值最高的项目分配给一个独立的代理（由于有共同的价值，这个分配可以是任意的），那么得到的福利大致为n ln n/ln ln n。接下来，我们通过应用不出价假设来限制一个代理出价的项目数量。假设一个代理对一组大小为k的项目出价。由于每个项目的价值至少为1，代理的出价之和至少为k。另一方面，任何一组项的值都以大束的值为上限，大束的值大致为ln n/ln ln n（根据balls-andbins类型分析，这大致是大束中最高值项的值）（见索赔5.3）。

因此，不出价假设意味着代理人出价的预期项目数为O（ln n/ln ln n）（见等式（18））。o最后，由于代理人对有价值的项目有一个非常模糊的概念（她只知道+1她的信号可能有助于某些项目），代理人的出价基本上是“暗中的一击”。再次使用balls-and-bins类型分析，我们证明anagent从她出价的项目中得到的期望值是O（ln ln n/ln ln ln n）（见权利要求5.4)，这意味着ateq=O（n ln ln n/ln ln ln n)，它得到的下限是~Ω（ln n）。本节的主要定理如下：定理5.1。存在一个具有n个单位需求代理和nitems的实例，γ=c=1,Gopt≈Opt,其中在无超额出价假设下，对于每个项目出价机制和均衡σ，Opt/eq(σ)=Ω(ln n ln ln ln n/ln lnn）,在证明定理之前，我们给出了一些有用的主张。我们将建立一个较低的边界选择。此外，估值满足边际递减，定义2.2。在这里，～Ω隐藏了o（ln n）项。索赔5.2。Opt=Ω（n ln n/ln ln n）。我们将项目划分为n个项目的n个集合。本文证明了在每一个集合中，ES[max`∈[n]vi`(s)]=Ω（log n/log log n)，因为我们可以将每一个集合中的最优项分配给一个di[vi`(s)≥k+1]=prs xi∈[n]si`≥k≥prs xi∈[n]si`=k=nknk1-nk≥nkk=ekk。（15）设k=ln n3 ln ln n，则kk≤ln nln n3 ln ln n=eln n=n1/3。因此，PRS VI`(s)≥ln n3 ln ln n+1≥en1/3。设X`表示项目值大于ln n3 ln ln n的事件，X表示在n个项目集合中该项目的个数。我们知道μ=es[X]≥n·en1/3=n2/3/E.通过Chebychev不等式，我们得到prs max`∈[n]X`≤lnn3lnlnn+1≤prs[x-μ≥μ]≤Var(X)μ≤e·pn`=1(Var(X`))+p`6=jcov(X`，Xj)n4/3。对于每个`，Var(X`)≤e[X`]=en2/3，由于X`和Xj对于每个`6=j是独立的，所以对于每个`6=j我们也得到Cov(X`，Xj)=0。因此，我们得到了prsmax`∈[n]x`≤lnn3lnlnn+1≤1/n，这意味着es[max`∈[n]vi`(s)]=Ω（lnn/lnlnn)。这就结束了索赔的证明。下面的索赔用于限定最大项目的期望值，从而限定一个代理人投标的项目的数目。索赔5.3。对于任何i，以及对于Si=(si1,...,sim)的任何实现，es-i max`Vi`(s)Si≤4ln n/ln ln n+3。证明。考虑一个投标人。我们有prs-i max`vi`(s)≥k+2si=prs-i max`{1+xj∈[n]sj`}≥k+2si≤prs-i max`{xj6=isj`}≥k=prs-i`:xj6=isj`≥k≤prs`:xj∈[n]sj`≥k≤n·prsxj∈[n]sj`≥k。(16)firerst不等式是因为信号是独立采样的，最好的情况是siis是所有的向量，最后一个不等式是通过应用并界。我们可以用balls和bins类型分析来确定pRshpj∈[n]Sj`≥Ki。也就是说，如果我们考虑anyk个代理，这些k个代理对项目`有高信号的概率是n-k。利用unionbound，我们得到了对于项目`存在k个具有高信号的代理人的概率最多为NK-N-k。因此，prsxj∈[n]sj`≥k≤nknk≤enkknk=ekk，其中第二不等式遵循Stirling近似。设k=4 ln n/ln ln n,则prs xj∈[n]sj`≥k≤e ln ln n4 ln n4 ln nn ln n≤exp4 ln nn ln n(ln ln n-ln ln n)=exp-4 ln n+4 ln n ln ln ln n，且对于n足够大的情况，prs xj∈[n]sj`≥k≤exp(-3 ln n)=n。因此，通过方程（16）,prs-i max`vi`(s)≥4 ln nln ln n+2 si≤1/n。（17）我们得到了-i max`Vi`(s)Si≤prs-i max`Vi`(s)<4ln nln ln n+2Si·4ln nln ln n+2+prs-i max`Vi`(s)≥4ln nln ln n+2Si·(n+1)≤(1-1/n)·4ln nln ln n+2+(n+1)/n≤4ln nln ln n+3。

如果代理i在一个最多lnn项的集合上出价，对于SI.propertion的任何实现，她对该集合的期望值最多为4 ln ln nn ln ln n+4。我们定义了agent看到价值大于4 ln ln nn ln ln n+2的项目的概率。注意，一个agent选择一组项目进行投标，而不知道其他投标人信号的实现。也就是，如果是i出价的项集，prs-i max`∈Sivi`(s)≥k+2si≤prs-i max`∈Sixj6=isj`≥k≤siprs xjsj`≥k≤lnn·prs xjsj`≥k，其中导子类似于权利要求5.3中的导子。使用k=4 ln ln nln ln ln n，与权利要求5.3类似的级数表明:prsxjsj`≥4ln ln nln ln ln n≤ln-3n,其结果为:prs-i max`∈Sivi`(s)≥4ln ln nn ln ln n+2si≤prs-i max`∈Sivi`(s)≤4ln ln nn ln n+2i·4ln ln ln ln n+2+prs-i4ln ln ln ln n+2≤max`∈Sivi`(s)≤4ln ln ln ln n+2≤ln ln ln ln n+2≤ln ln ln ln n+2≤ln ln ln ln n+2≤ln nln ln n+2Si·4ln nln ln n+2+prs-i max`∈Sivi`(s)≥4ln nln ln n+2Si·(n+1)≤4ln ln nn nln ln n+2+ln n4ln nln ln n+2+n(n)+1)≤4ln ln nn nn ln nn n+2+4/ln ln n+2/ln n+1+1/n≤4ln ln nn nn ln n+4，完成了证明。有了这些要求，我们准备建立定理5.1的证明。定理5.1的证明。让Sibe代理i出价的随机项目集。对于每一个Sibye[Si Si]≤es-i'Af-i(bi,ai)→σi(Si)x`:ai`=1vi`(bi`,s-i)≤es-i'Af-i[vi（Si；s)]≤4ln nln ln n+3,我们可以确定Siby[Si；s)]≤4ln nln ln n+3。（18）在（18）中的不等式后面是这样一个事实，即对于每个项目和代理，该值至少为1，第二个不等式后面是无超额出价，第三个不等式后面是权利要求5.3。通过马尔可夫不等式和方程(18)，我们对每个si,prπsi>lnn si<4 ln nln ln n+3lnn=O(1/ln n ln ln n)，我们现在对每个Sies-i,si[vi(si；s)si]≤prsi≤lnn si4lnlnnlnlnn+4+prsi>lnn si·4ln nlnlnn+3=o ln lnnnnlnn+o ln nlnlnlnnn=o ln lnlnnnlnnn，其中不等式由权利要求5.3和5.4所示。因此，代理i出价的项目集的期望值为Es,si[vi(si；s)]=O ln ln nln ln ln n n.由于这是agent赢得的项目价值的一个上界，所以每个agent在一个均衡中都得到一个O ln ln nln ln ln n，因此Eq(σ)=O(n ln ln n/ln ln ln n)。由于Opt=Ω（n ln n/ln ln n）（根据权利要求5.2)，我们得出Opt/eq=Ω（ln n ln ln ln n/ln lnn）。这就得出了证明定理5.1。确认。我们深深感谢大卫·帕克斯的有益讨论。劳伦斯·M·奥苏贝尔，保罗·米尔格罗姆，等人。可爱但孤独的vickrey拍卖会。组合拍卖，17:22-26，2006年。劳伦斯·M·奥苏贝尔等人。广义的vickrey拍卖。《计量经济学学会世界大会》，2000年，尤西·阿扎尔、迈克尔·费尔德曼、尼克·格拉文和艾伦·罗伊特曼。无政府状态的流动价格。在VittorioBil`o和Michele Flammini，编辑，《算法博弈论-第10届国际研讨会》，SAGT 2017年，计算机科学课堂讲稿第10504卷，第3-15页，2017年。Moshe Babaio，Brendan Lucier，Noam Nisan和Renato Paes Leme。论瓦尔拉亚机制的存在性。在Moshe Babaio,Vincent Conitzer和David A.Easley,编辑，ACMConference on Economics and Computation，EC\'14。ACM，2014年。MohammadHossein Bateni、Sina Dehghani、MohammadTaghi Hajiaghayi和Saeed Seddighin。销售多种相关商品的收入最大化。在Nikhil Bansal和Irene Finocchi，编辑，算法-ESA 2015-第23届年度欧洲研讨会，第9294卷计算机科学讲座，第95-105页，2015。Dirk Bergemann和Stephen Morris。不完全信息博弈中的稳健预测。《经济经济学》，81(4):1251-1308，2013。Kshipra Bhawalkar和Tim Roughgarden。带项目竞价的组合拍卖的福利保障。

在Dana Randall编辑，22年度ACM-SIAM研讨会关于离散算法的论文集，SODA 2011,第700-709页。暹罗，2011年。Mark Braverman，Jeeming Mao和S.Matthew Weinberg。组合拍卖的真实和非真实机制之间的插值。载于Robert Krauthgamer，编辑，《第二十七届ACM-SIAM离散算法年会论文集》，SODA 2016,第1444-1457页。暹罗，2016年。Ioannis Caragiannis、Christos Kaklamanis、Panagiotis Kanellopoulos、Maria Kyropoulou、BrendanLucier、Renato Paes Leme和Eva Tardos。广义二次价格拍卖结果的边界。J.经济。《理论》，2015，156:343-388.舒奇·查拉，胡夫，安娜·R·卡林。在interdependentvalue设置中近似收益最大化。在ACM经济与计算会议上，EC\'14,第277-294页。ACM,2014。Shuchi Chawla,David L.Malec,和Balasubramanian Sivan。贝叶斯最优机构设计中的随机性。游戏经济学。行为。，91:297-317，2015年。乔治·克里斯托杜卢，安娜·阿里亚·科夫·ACS和迈克尔·沙皮拉。贝叶斯组合拍卖。ACM,63(2):11:1-11:19,2016a。乔治·克里斯托杜卢，安娜·阿里亚·科夫·ACS，阿尔克米尼·斯古里萨，和博·唐。同时拍卖的无政府状态价格的严格界限。ACM反式。《经济学与Comput》,EC\'16,4（2）：9：1-9:33,2016b.Florin Constantin,Takayuki Ito,David C.Parkes.价值相互依存的竞标者在线拍卖。Edmund H.Durfee，Makoto Yokoo，Michael N.Huhns和Onn Shehory，编辑，第六届自治代理和多代理系统国际联合会议(AAMAS2007)，第110页。IFAAMAS，2007年，Partha Dasgupta和Eric Maskin。电子拍卖。经济学季刊，115(2):341-388，2000。Bart de Keijzer,Evangelos Markakis,Guido Schéafer,Orestis Telelis。标准多单元拍卖协会。载Hans L.Bodlaender和Giuseppe F.Italiano，《编辑，算法-ESA2013-21年度欧洲研讨会》，《计算机科学课堂讲稿》第8125卷，第385-396页。斯普林格，2013年。Nikhil R.Devanur，Jamie Morgenstern，Vasilis Syrgkanis和S.Matthew Weinberg。具有简单策略的Simpleauctions。载Tim Roughgarden，Michal Feldman和Michael Schwarz，编辑，《第十六届ACM经济与计算会议论文集》，EC\'15，第305-322页。ACM，2015年。Peerapong Dhangwatnotai、Tim Roughgarden和Qiqi Yan。单一方案下的收入最大化。游戏经济学。Behav.，91:318-333，2015年。Shahar Dobzinski。具有次模估价的真实组合拍卖的一个不可能结果。载于Lance Fortnow和Salil P.Vadhan，编辑，《第43届ACM计算理论研讨会论文集》，STOC2011，第139-148页。ACM,2011。Alon Eden,Michal Feldman,Amos Fiat,Kira Goldner。相互依存的价值而不是单一的。摘自2018年ACM经济与计算会议录，第369页。ACM,2018。Alon Eden,Michal Feldman,Amos Fiat,Kira Goldner和Anna R.Karlin。估值相互依赖的组合拍卖：紧急救援。在2019年ACM经济和计算会议记录，EC2019，第19-20页。ACM，2019年。Uriel Feige、Michal Feldman、Nicole Immorlica、Rani Izsak、Brendan Lucier和Vasilis Syrgkanis。有补充和替代的统一估值体系。载Blai Bonet和SvenKoenig编辑，《第二十九届AAAI艺术情报会议论文集》，第872-878页。AAAI出版社，2015年。Michal Feldman,Hu Fu,Nick Gravin,Brendan Lucier。同时拍卖（几乎）是e-cient。Dan Boneh、Tim Roughgarden和Joan Feigenbaum，编辑，计算理论研讨会，STOC\'13,第201-210页。ACM，2013年。迈克尔·费尔德曼、奥菲尔·弗里德勒、杰米·摩根斯坦和盖伊·雷纳。具有补充的代理的简单机制。