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

载Vincent Conitzer，Dirk Bergemann和Yiling Chen，编辑，《2016年ACM经济与计算会议论文集》，EC\'16，第251-267页。ACM，2016年。胡服，罗伯特·克莱因伯格，罗恩·拉维。条件均衡结果通过上升的价格过程与应用到组合拍卖与项目投标。Boi Faltings、KevinLeyton-Brown和Panos Ipeirotis编辑，《第13届ACM电子商务会议论文集》，EC2012,第586页。ACM，2012年。杰森·D·哈特林、达雷尔·霍伊和萨姆·塔格特。拍卖收入的无政府状态价格。Moshebabaio,Vincent Conitzer和David A.Easley,编辑，ACM经济与计算会议，EC\'14,第693-710页。ACM，2014年。Avinatan Hassidim、Haim Kaplan、Yishay Mansour和Noam Nisan。离散商品市场的非价格均衡。在Yoav Shoham，Yan Chen和Tim Roughgarden，编辑，第12届ACM电子商务会议(EC-2011)，第295-296页。ACM，2011年。Darrell Hoy，Samuel Taggart和Zihe Wang。对价格拍卖的更严格的福利保障。Ilias Diakonikolas、David Kempe和Monika Henzinger编辑，《第50届ACM SIGACT计算理论研讨会论文集》，STOC2018，第132-137页。2018年，ACM。妮可·伊莫利卡、萨希尔·辛格拉和博·瓦格纳。具有线性相关和增广的预言家不等式。CoRR，ABS/2001.10600，2020年。Takayuki Ito和David C.Parkes。实例化真实相互依赖价值拍卖的或有出价模型。在Hideyuki Nakashima，Michael P.Wellman，Gerhard Weiss和PeterStone，编辑，第5届自治代理和多代理系统国际联合会议(AAMAS2006)，第1151-1158页。ACM，2006年，Philippe Jehiel和Benny Moldovanu。具有相互依赖的估值的设计。经济计量学，69(5):1237-1259，2001。金耀南，李维安，齐齐。关于MHR分布的简单机制的逼近性。Ioannis Caragiannis，Vahab S.Mirrokni和Evdokia Nikolova，编辑，《网络与互联网经济-第15届国际会议，葡萄酒2019》，第11920卷，第228-240,201 9页。Paul Klemperer。几乎具有共同价值的拍卖：“钱包游戏”及其应用。《欧洲经济评论》,42（3-5）：757-769,1998.维杰·克里希纳。拍卖理论。学术出版社，2009.李胜武。显然是策略证明机制。《美国经济评论》,107（11）：3257-87,201 7A.李玉南。具有相互依赖值的机构设计中的近似。游戏经济学。Behav.，103:225-253，2017b.Brendan Lucier和Renato Paes Leme。具有相关类型的普惠制拍卖。载于Yoav Shoham，Yan Chen和Tim Roughgarden，编辑，《第12届ACM电子商务会议论文集》，EC2011，第71-80页。ACM，2011。Eric S Maskin。拍卖和私有化。第433-453页。1996.保罗·米尔格罗姆。使拍卖理论发挥作用。剑桥大学出版社，2004年。保罗·米尔格罗姆和罗伯特·韦伯。拍卖和竞标理论。计量经济学：计量经济学会学报，50(5):1089-1122，1982。最优拍卖设计。运筹学的数学，6(1):58-73，1981。瓦伦丁·罗布，大卫·C·巴夏礼，高行·伊藤，和尼古拉斯·R·詹宁斯。具有单一投标人的相互依赖的价值组合拍卖。载于Francesca Rossi，编辑，IJCAI，2013年，《第23届国际艺术情报联合会议论文集》，第339-345页。IJCAI/AAAI，2013年。Tim Roughgarden。机械设计前沿讲义，2014年。第14-17讲。蒂姆·劳格花园。无政府状态代价的内在稳健性。J.ACM,62（5）：32：1-32：42,2015a.Tim Roughgarden.不完全信息博弈中无政府状态的代价。ACM反式。《经济学与科学》，3(1):6:1-6:20,2015b.Tim Roughgarden和Inbal Talgam-Cohen.具有相互依赖价值的最优稳健机构设计。ACM反式。经济学和Comput。，2016年，4(3):18:1-18:34。蒂姆·劳格加登，瓦西里丝·西格卡尼斯，和伊娃·塔多斯。无政府状态在拍卖中的价格。J.Artifi.Intell。

Res.59:59-101，2017。Vasileios Syrgkanis。复杂市场中的机制。康奈尔大学博士论文，2014年。Vasilis Syrgkanis和Eva Tardos。可组合和e-cient机制。在计算理论研讨会上，STOC\'13，第211-220页。ACM，2013年。罗伯特·威尔逊。信息完全不同的竞标。管理科学，15(7):446-452,1969。第1A节附录。1不纯平衡例题A.1。存在一个具有c-SC相互依赖的单物品2代理环境，使得每一个将物品分配给价值最高的竞拍者并按mosther报告价值收费的拍卖，在无超额出价假设下不存在纯Nash均衡。推论a.2。存在一个具有c-SC相互依赖的单品2代理环境，使得第二价格拍卖和广义Vickrey拍卖在不出价假设下都不承认纯Nashequilibribrium。命题a.1的证明。设M=(x，p)是一个单物品拍卖，它将物品分配给报告价值最高的竞拍者，并至多收取报告价值的费用。考虑信号空间s=s=[0,3π]和以下估值（如图2所示为s+s的asa函数）:v(s)=sin(s+s)+2(s+s)和v(s)=sin(s+s+π)+2(s+s)。我们可以很容易地验证这些估值在两个信号中都是单调的，对于c=3的c-SC。我们声称，对于s=(2π,2π)的信号，不存在满足不出价的纯Nashequilibrium。错误地假设存在b≤s，使得b是纯纳什均衡。我们证明了对于中标代理的每一个出价，落败代理都有一定的偏差。假设b是这样的，代理1赢得了该项目。在不出价过高的情况下，B≤S=2π。我们声称代理2有一个偏差，使她具有严格的正效用。我们证明存在B≤S=2π，使得代理2赢得该项目。的确，存在k∈{1,2}，因此对于满足b+b=2πk-π/2的b，它认为v(b，b)=2(2πk-π/2)+1>2(2πk-π/2)-1=v(b，b)。根据分配规则，代理2赢得项目。此外，通过对支付的假设，p(b，b)≤v(b，b)。因此，u((b，b)；s)=v(s)-p(b，b)≥v(s)-v(b，b)=8π-(2(2πK-π/2)+1)≥π-1>0。因此，代理2获得了正效用。类似地，如果b是使投标人2赢得该项目，则投标人1有一个偏差b≤st，该偏差使其具有正效用（即存在k∈{0,1}，使得对于满足b+b=2πk+π/2的b+b=2πk+π/2的b+b=2πk+π/2的b+b=2πk+π/2的b+b=2πk+π/2的bidder1具有严格的正效用）。图2：作为S+S函数的代理1和代理2的估值。对于一个代理人的每一个投标，另一个代理人有一个中标者。a.2“挑战”的附录包含ectionProposition（命题1.2的正式陈述）。存在一个满足单交叉的单项目n-biddersetting,使得每一个将项目分配给最高值竞拍者的拍卖的EP-PoA为Ω(n)（即使在无出价过高的情况下）。命题1.2的证明。考虑一个具有n个投标人的单项目设置，信号空间S={1},S={1}和si=[0,1]，对于每i≥3,并且下面的估价结果:V=XI∈[n]si+,V=2(S+),且i≥3:VI=si,(19)，其中>0是任意小的。观察到估值结果在信号上存在单交叉和次模块性[Eden et al.，2019]。我们认为，当i≥3时，σ(s)=1,σ(s)=1,σi(si)=0时，σ(s)=0是一个事后均衡(EPE)：给定这些信号，我们有v(σ(s))=2+,v(σ(s))=2+2,vi(σ(s))=0。投标者2赢得该项目。投标者1、2不能偏离，因为他们的信号空间是单一的，而投标人i≥3可以通过偏离而获胜，因为每一次投标都是v(b)>vi(b)。如果真值为s=(1,....,1）,则最优福利为n+，而在EPEσ下获得的福利为2+2，完成了证明命题（命题1.4的形式陈述）。

存在一个满足单交叉的单项目N投标人设置，使得每一确定性后置IC-IR机制的EP-PoA均为Ω(√n)（即使在无过竞价情况下）。考虑一个具有n个投标人的单项目设置，信号空间si=[0,1]，对于每i,并且有以下估价规则:v=xi∈[n]si+,v=√ns,且i≥3:vi=si,(20)，其中>0是任意小的。观察到估值结果在信号上存在单交叉和次模块性[Eden et al.，2019]。我们认为，当i≥3时，σ(s)=s,σ(s)=s，σ(s)=0时，σ(si)=0的投标策略是一个无超额报价下的EPE:≥3的投标人不可能因偏离而获胜，因为每个投标条件为b时，v(b)>vi(b)。投标者i=1,2如果是真实的，就不能提高他们的出价（没有过高的出价）。中标者不能通过降低出价而获益。她要么失去该项目，在这种情况下，她的效用为0，而在偏差前的效用为非负的无过竞价和前postir属性；或者仍然赢得项目，在这种情况下，她的付款根据支付规则Ofex-post IC-IR机制是相同的，她的功利也是一样的。失败的投标人不能通过降低投标来赢得项目，因为估价过程是交叉的，并且由于post IC-IR机制的特征是单调的。因此σ是一个EPE，假设真信号profirele是S=(1，1，0，..，0)。惟一的非零值是v(s)=2+，v(s)=√n。如果所有投标人都如实报告，这是一个事后平衡，因为mechanismis事后IC。如果项目分配给除2以外的任何投标人，则命题陈述如下。因此，假设给定的投标profielle机制分配给投标人2。现在假设真信号profielle是S=(1，..，1)。由于σ是一个EPE，如果代理人投标符合σ，他们投标σ(s)=s，所以投标人2是赢家。得到的福利为v(s)=√n，而最优福利为v(s)=n+。这就完成了证明。B第2B.1节附录“POA背景”子节附录观察2.8的证明。首先假设σ是EPE。通过认识，对于每一个i和s-i，我们得到σi（si）最大化ui(σ(si,s-i）；（si,s-i））。特别是对于S-I来说，这是成立的。因此，σ是相对于s的PNEwith。现在假设σ是一个PNE（不一定是EPE）。考虑一个概率为1的点质量分布F。注意到σ是这个贝叶斯分析的BNE。C附录第3节（单项目）C.1改进的广义Vickrey拍卖命题C.1（改进的界）的PoA界。考虑一个具有γ-异构、单交叉、连续估值的单项目设置。广义Vickrey拍卖的B-PoA至多为γ.为了证明命题C.1，我们建立了以下主张。主张C.2。设σ为单交叉、γ-异构、连续估值的单品广义Vickrey拍卖的BNE,满足无出价条件。对于每一个séFand béσ(s)，分别设isand ibbe一些在s和b下具有最高值的棋子。则γvib(s)≥vis(s)。证明。对于某些sèF，设b是σ(s)支持的一些bid profemile。如果is=ibthe主张istrivial，那么考虑isis不在B中分配的情况是必要的。假设isis不在b中，因此，uis(b)=0。首先，我们证明uis(sis，b-is)=0。相反地假设情况并非如此，我们为isσis(ti)=(σis(tis)tis6=sissistis=sis设计了一个新的策略方案。注意，对于所有的信号方案，在新的策略方案下agent的isbid只能相对于她在旧的策略方案下的出价增加，因此如果agent在σ(s)下获胜，那么通过单交叉，她仍然是赢家。此外，根据临界支付规则，她的支付保持不变，因此她的效用保持不变。如果agent在σ(s)下没有获胜，那么她的效用为0。

当将her策略改为σis时，通过无超额出价、分配规则和支付规则，其效用是非负的，因而不会降低。而且，当s=s时，她的效用严格增加。因此，与σ是一个BNE相反，esèf[uis(σis(s),σ-is(s))]>esèf[uis(σ(s))]，我们继续我们的主要证明。考虑两种情况：1。Isdons不赢得（sis,b-is）项下的项目。存在一个代理J6=ISS.T。vj（sis,B-IS)≥VIS（sis,B-IS)；根据推论3.6我们得到γvib(sis，b-is)≥vj(sis，b-is)≥vis(sis，b-is)，(ib，j6=is，bis≤sis)，再次应用推论3.6，我们得到γvib(s)≥vis(s)。iswins（sis,b-is）下的项。由于is的效用为0，那么vis(s)=pis(sis，b-is)=vis(b*is,b-is)，其中b*is是她的临界出价。由于估值函数是连续的，且在b下不赢，所以存在一个代理J6=i，使得vj(B_is,B_is)=vis(B_is,B_is).通过与上述相同的论证，γVIB(B_is,B_is)≥vj(B_is,B_is)=vis(s)。利用赋值函数的单调性，得到γvib(s)≥vis(s)。这就结束了证明。我们现在准备证明命题C.1。命题C.1的证明。设σ是具有上述性质的广义Vickrey拍卖的BNE。表示F在代理信号上的分布；对于每一个信号，proformileSF和bidformileBσ(s)分别表示在s和b下具有最高值的isand IB，根据权利要求C.2，γvib(s)≥vis(s)。本文认为:opt=esèf[OP T(s)]=esèf[vis(s)]=esèf[ebèσ(s)[vis(s)]]≤esèf[ebèσ(s)[γvib(s)]]=γesèf[ebèσ(s)[vib(s)]](21)=γesèf[sw(σ，s)]=γeq,c2 PoA二价拍卖的界我们现在从定理3.3中证明了关于相互依赖的二价拍卖的相同的一般上界：定理c3。考虑一个具有γ-异构，c-SC估值的单项目设置。在无出价条件下，具有相互依存价值的广义二价拍卖的B-POAA受1+max{γ,c}的约束。证明。注意，二价拍卖和广义Vickrey拍卖的分配规则是相同的，它们只在支付规则中存在。另外，在定理3.3的证明中，我们唯一使用付款规则的部分是在情形2中，因此，用第二价格付款规则证明情形2是SU-CE,该证明对该定理也成立。情形2：投标人i在投标程序（si,b-i）下赢得了该项目。设j∈Argmaxl6=i{vl(si,b-i）}。投标人i的效用是ui（s；（si,b-i））=vi(s)-vj(si,b-i）。由于w(b)在b获胜，所以已知vw(b)(b)≥vj(b)，通过应用推论3.6，我们得到max{γ,c}vw(b)(si,b-i)≥vi(s)-max{γ,c}vw(b)(si,b-i)≥vi(s)-max{γ,c}vw(b)(si,b-i)≥vi(s)-max{γ,c}vw(b)(si,b-i)≥vi(s)-max{因此，定理3.3的证明成立。这就结束了我们的证明。接下来我们证明定理C.3几乎是紧的。定理C.4。存在满足γ-异质性和c-SC的单项目设置，使得相互依赖的二次价格的then-POA任意接近于max{c,γ}，即使在没有出价的情况下也是如此。证明。与定理3.4的证明相同的论点在这种情况下成立，唯一的变化是在情况1中，代理人1的付款代替了第4节的附录1（多项：肯定的结果）D.1参与的必要性假设命题D.1。存在一个多项目，n个单位需求的竞拍者设定，满足单交叉和γ-齐性，使得每一次将每一个项目分别分配给最高价值的竞拍者的拍卖的PoA为Ω(m)。证明。考虑一个具有n个单位需求代理和信号空间si=[0,1]的设置。对于每一项`∈[m]，设v1`=pj∈[n]sj+1,对于每一个i≥2,设vi`=pj∈[n]sj+。Anyauction将每件物品单独分配给价值最高的出价者，将所有物品分配给agent1，而不管所有出价。

此外，投标人6=1是他们的出价，所以他们不妨出价他们的真实信号。在这种情况下，PoA为Ω(m)。命题4.4。在例4.3中，对于su大n,(1+e)gOpt≥opt.证明。给定一个信号，表示项目\'by s(1)\'的最高信号，第二高信号by s(2)\'，以此类推。对于每一个信号，考虑福利最大化匹配；我们把它的总价值Ep(i，`)∈μVi`(s)分成两个分量:p(i，`)∈μ～Vi`(s)和p(i，`)∈μβmaxj6=i{sj`}。该分量是上界的byP(i，`)∈em(s)～Vi`(s)（其中从知识4.2中回忆，em(s)是关于截断值的最大匹配），所以在对s的期望中，它是最大的。第二个分量P(i,`)∈μβmaxj6=i{sj`}仍然是有界的。为此，我们将分别研究每一项。对于每个项`，它认为maxj6=i{sj`}≤maxj{sj`}。现在考虑一个单项设置，其中每个代理的值是她的信号。在这种设置下，上述正是社会福利的最大值。此外，众所周知，当从MHR分布中提取价值时，最优福利位于OptimalCency的因子e内[Dhangwatnotai et al.，2015，引理3.10]。而且，Jin等人。[2019]表明，在这种情况下，第二价格拍卖与最优收入的近似值为1-（1-E）n-1。注意，第二次价格拍卖的收入正好是s(2)`。即使在信号的子模块性的附加假设下，该定理也成立，更多信息请参考Eden等人。[2019]综合上述结果，得到βes[P(i，`)∈μmaxj6=i{sj`}]≤e(1-(1-e)n-1)βes[P`s(2)`]。当agent数至少为2时，我们得到Es[p(i，`)∈μβmaxj6=i{sj`}]≤eβes[p`s(2)`]。注意对于每个信号序列s，对于每个agent i和项`，截断值~vi，`(s)至少为βpj≥2s(j)`≥β·s(2)`。因此，em(s)的总和至少是与项`相邻的所有边相对于边权β·s(2)`的最大匹配的总和。对于这样的边权值，每一个完美匹配都是最大的，并且具有总权值βP\'s(2)\'。取s上的期望，我们得到Gopt≥βEs[X`s(2)`]。（22）我们得到的结论是:opt=x(i,`)∈μ～vi`(s)+x(i,`)∈μβmaxj6=i{sj`}≤gopt+eβes[x`s(2)`]≤(1+e)gopt。（23）随着主体数的增加，1-(1-e)n-1任意接近于1，近似任意接近于(1+e)。命题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的证明。考虑示例4.5中所示的设置，其中f=u[0,1]，以及以下策略Profile(b，a):B1`(s)=msfor earch`，a(s)=(1，..，1)和Bi`(si)=0for earch`，ai(si)=(0，..，0)for earch`，i≥2。即agent 1是每个项目的唯一参与者。我们认为(b，a)是一个后置均衡。首先，注意投标人1的信号的分布是连续的，因此在0处没有点质量。这意味着概率为1的S>0，而投标人1策略的B>0。此外，智能体i≥2的信号空间是单例的，这意味着它们的出价不能大于0。考虑到这一点，对于每一个项目`，在机制看来，投标人1的价值支配着所有其他投标人的价值（对于每一个b>0；h1`(b)≥h1`(b，0-1)=v1`(b，0-1)=v1`(b)>vi`(b)≥hi`(b))。根据分配规则，如果竞买人1参与一个项目的拍卖，没有其他代理可以通过参与而获胜。这意味着对于每个代理i≥2没有改进偏差。对于代理1，她是每个项目的唯一参与者，根据支付规则，她为每个项目支付0。

而且，她赢得了所有的项目，因此，她的效用最大化。最后，SW(b，a)=s，而Opt≥m(1-)s。这就给出了随机化机制的证明。本文主要研究简单的确定性机制。人们可能希望在更广泛（但更复杂）的随机机制家族方面得到更好的界限。这一节对这个问题有很大的启发。命题E.1解决了伊甸园等人的随机抽样Vickrey拍卖。[2019]-一种expost IC-IR机制，该机制将投标人随机划分为两个集合A、B，然后将该项目分配给集合B中“归零”值最高的投标人，其中投标人i∈B的归零超值为vi(sA,si,0B\\{i}）。除了简单之外，在价值相互依赖的情况下，随机抽样Vickrey拍卖相对于其他拍卖形式的一大优势是，只要SoS属性保持不变，即使没有SC假设，也能实现良好的福利保障。据我们所知，这是迄今为止唯一已知的此类机制。不幸的是，当我们考虑所有均衡时，这些保证不再成立，而不仅仅是讲真话的均衡。事实上，即使我们只考虑无过度出价均衡，它也不再成立，如下命题所示。命题E.1。存在一个具有SoS的、相互依赖的估价（不满足SC）的单项目N-代理环境，其中随机抽样Vickrey拍卖的EP-PoA为Ω(2n)，即使在无超额出价的情况下。证明。考虑一个单项目设置，有n个投标人，信号空间Si=[0,1]，对于每个i，并且有以下估价规则:v=s+cnxi=2si，且i≥2:vi=si+2i，(24)，其中c是一个su_ciently大标量，将在下面确定。请注意，估值表包含SOS。我们认为，当b(s)=sand,bi(si)=0时，投标策略是一个后置均衡。对于每一个出价亲带，每一个随机分区A,B通过随机抽样Vickrey拍卖选择的竞投者，如果B包含指数较高的投标人，i≥2的投标人永远不会获胜，通过下面的不等式链:I，j∈B,2≤i<j:vi(bA,bi,0b-i)=bi+2i≤1+2i<2(i+1)≤2j≤bj+2j=vj(bA,bj,0b-j)。在投标策略亲b-1时，对于每个分区A,B的每个报告带，投标人1获胜当且仅当她是B中唯一的投标人。实际上，假设投标人1∈B:±i∈B，i≥2:v(0A,B,0b-1)=s<2i≤vi(0A,0B).因此，投标人1是否获胜并不取决于她的出价。我们得出结论：在b下，该项目被分配给集合b中索引最高的投标人，任何失败的投标人都不能通过偏离而成为赢家。此外，在事后IC-IR机制中，根据已知特征，获胜者的付款不取决于她的出价（见1.1节）。因此b是事后平衡。另外，b清楚地表明了对任何真实信号的不出价。现在假设真实信号的出价是s=(1，..，1)。在b下，投标人1赢得该项目的概率是在集合b中的所有n个投标人中准确地选择投标人1的概率，即n。还可以观察到，在所有投标人i≥2中，投标人n的值最高。因此，b下的期望福利为最小NV(s)+(1-n)vn(s)=n(1+c(n-1))+(1-n)(2n+1)，而总是将物品分配给竞买人1所得到的最优福利为1+c(n-1)。对于一个非常大的c，例如c≥2·2n，我们得到EP-PoA=Ω(2n)，完成了证明。在命题E.1中，我们建立了一个简单随机拍卖的下界，它满足了IC-IR的事后要求。下一个结果（命题E.2)表明，我们不能期望对所有随机化的事后IC-IR拍卖都有一个普遍的下限（与确定性的这种机制相反--召回命题1.4）。

然而，我们的结果可能表明，为了获得良好的PoA保证，人们必须求助于类似下一个命题中构造的相当不自然的机制。如果随机化机制是确定性后IC-IR机制上的分布，则称为普遍后IC-IR。在非正式的情况下，命题E.2表明，在无超额假设下，对于任意小的情况，每个α近似普遍的后置IC-IR机制都可以转化为NE-PoA至多α1-的随机机制。由于普遍存在对SoS估值具有恒定近似福利保证的事后IC-IR机制（如Eden et al.[2019])，命题E.2排除了随机化机制EP-POA的下界。该命题利用了一个比例分配机制，如下所示：给定出价条件b，该项目以概率BIPJBJ+1分配给出价人i。命题E.2。设M是一个福利最大化的α近似，普遍的事后IC-机制。对于每>0，随机机制M，运行概率为1-的M和运行概率为1-的比例分配机制，在nooverbidding下具有NE-PoA≤α1-。在证明命题E.2之前，我们证明了下面的声明。声明E.3。如果一个机制M是普遍的后IC-IR并且满足无出价假设，那么M是DSIC。证明。由于每个普遍的事后IC-IR机制都是确定性事后IC-IR机制上的概率分布，因此有必要证明确定性M.LetM=(x，p)是确定性事后IC-IR机制的引理。请记住，x是单调的，支付规则p是唯一的，并与关键支付规则相一致，关键支付规则仅由竞争投标人的出价决定（更多细节见1.1节中的事后IC-IR机制的特征）。设b为出价表。对于每一个出价者i，用pi（b-i）表示她根据toba支付的款项。考虑两种情况：1。i在b下获胜，即xi(b)=1。通过单调性和无出价性，xi(si,b-i)=1。它保持ui（（si,b-i）；s)=vi(s)-pi(~b-i)=ui（（bi,b-i）；s）。i在b下亏损，即xi(b)=0。如果xi（si,b-i)=0，则ui（（si,b-i）；s)=0=ui（b；s）。因此，itsu和ces需要考虑xi(si,b-i)=1的场景。通过x的单调性、criticalpayment规则和估值的单调性，我们得到vi(si,b-i)≥vi(B*i,b-i)=Pi(si,b-i)。因此，ui((si,b-i）；s)=vi(si,b-i)-vi(b*i,b-i)≥0=ui（b；s）。在这两种情况下，ui((si,b-i）；s)≥ui（b；s）。命题E.2的证明。设M是一个普遍的后置IC-IR机制。根据E.3的说法，M在没有过高出价的情况下，实际上是DSIC。我们证明了在M中，说实话是唯一的无出价PNE。对于每个投标人i、信号profirele s和出价profirele b-i，出价bi=sii是无超额出价下的最佳响应，而任何出价bi<sii不是最佳响应:uMi((bi，b-i)；s)=(1-)uMi((bi，b-i)；s)+bipjbj+1vi(s)≤(1-)uMi((si，b-i)；s)+bipjbj+1vi(s)(25)<(1-)uMi(si，b-i)；s)+sipj6=ibj+si+1vi(s)=uMi(si，b-i)；其中M后面的不等式（25）是DSIC。真实的PNE至少产生最优福利(1-)/α，因此NE-PoA≤α1-。