降价最优地协调搜索

在步骤t中，她的优先级σki大于或等于所有其他投标人的优先级，并且因为σki<infl>k{σli} 因此，从t+1到shereached检查阶段的每一步，r的优先级都严格高于所有其他投标人的优先级∞. 因此，在当前步骤中，投标人i是唯一活跃的投标人。此外，包括i在内的所有投标人的最小优先级与步骤t中的相同，这意味着投标人i的最小优先级大于或等于所有其他投标人的最小优先级，如所述。定理3。通过降序优先程序获得的预期福利等于[最大值κ+i]。没有其他程序可以获得更高的预期福利。证据根据引理13，对于任何程序，投标人i的预期净效用是tmost E[Aiκi]，其中，Ai是该项目被授予i的事件的指示器。对投标人进行求和，任何程序的预期福利最多为E[PiAiκi]，而这反过来又以E[maxi（κi）+]为界。为了确保降序优先程序达到这个上限，我们将证明它为每个投标人引入了一个非公开检查政策，并且它总是将项目授予arg maxi{κi}中的投标人i，除非κi<0，在这种情况下，项目没有分配。从这两个事实来看，引理13意味着递减优先级过程的预期福利等于E[maxi（κi）+]，这与定理1的证明完全相同。考虑优先级递减过程中的任何一个步骤，并假设它们都是1。k（i）<∞ σk（i）i>κk（i）i，or2。k（i）=∞ 和vi>κi。在这两种情况下，投标人i的优先级严格大于r min优先级。这意味着我是唯一一个拥有最高优先权的投标人。在第一种情况下，这意味着她将被选中进行另一阶段的检查。在第二种情况下，这意味着该项目将授予她。

因此，当投标人处于σk（i）i>κk（i）i的阶段时，下降优先级程序从未停止检查投标人i，并且它从未失败地将项目授予完成所有检查阶段并发现vi>κi的投标人。这证明该政策是不公开的。最后，我们必须证明，程序总是将项目授予r g maxi{κi}中的Abider i，除非ssκi<0，在这种情况下，项目没有分配。如果程序通过将项目授予i而终止，则k（i）=∞, 因此，投标人i的最小优先权是κi。通过引理14，这大于或等于每个其他投标人的最小优先权r i′，这反过来是κi′的上界，因此我是具有最大覆盖调用值的投标人。此外，对于任何k，σki都不可能小于0∈ N-否则，程序将不会使投标人i超过检查阶段k-也不会出现vi<0的情况，因为程序不会将项目授予具有负值的投标人。因此，κi≥ 如前所述为0。需要考虑的一个悬而未决的情况是，该程序在不将项目授予任何投标人的情况下终止。如果每个投标人的优先权都严格为负，这种情况就会发生。由于每个投标人的优先权是其最小优先权的上限，而最小优先权又是其覆盖调用值的上限，这意味着所有覆盖调用值都是严格负的。G.5荷兰拍卖分析的应用我们现在概述我们关于荷兰拍卖分析的主要结果（正文引理2、定理2和推论2）如何扩展到多级检验的设置，如正文第6.1小节所述。

由于我们正在考虑对单个物品进行荷兰式拍卖，我们可以从σ-字段中删除下标j，并用Fk，τi表示它们。在荷兰式拍卖中，我们将假设下降价格由一个连续的非递增函数t给出，t（τ）表示时钟时间为τ时的价格。由投标人i的私有类型θi生成的σ-场Fk，τiis，前k个检验阶段的结果，以及描述时钟时间τ拍卖状态的随机变量s（τ）；如果某个投标人i′在τ′<τ时被分配了项目，则该状态变量s（τ）取值（i′，τ′），否则取空值⊥.投标人i的策略由检验政策si给出，受制于可行性约束，即如果该项目已经分配给另一个投标人，投标人不能尝试获取该项目：Asi（ω，τ）=0，除非s（τ）=⊥. 我们将使用*i（ω，τ）表示项目在τ或earlier时分配给投标人i的事件的指标随机变量。只有在这种情况下*i（ω，τ）可能与Asi（ω，τ）不同，Asi（ω，τ）是指两个或多个投标人试图在τ时间获得该项目，在这种情况下，通过随机平局决定胜出者。投标价格（ω）=如果是*i（ω，τ）=0τsup{t（τ）|A*i（ω，τ）=1}否则。投标人i的覆盖副本是一个投标人（编号为i+n，如正文第4节所示），其检查成本基本为零，其值等于随机变量κi，即投标人r i的广义覆盖调用值。

投标人i+n的验收策略是一种适用于过滤{Fk，τi}的检验政策，受制于上述相同的可行性约束：如果该项目已被授予另一投标人，投标人i+n不得试图获取该项目。通过允许策略si+适应过滤{Fk，τi}，我们隐含地认为投标人i+n被授予了解投标人i的所有检查成本和结果，以及其获取项目的价值。该假设的证明与定理2证明第一段及其随附脚注中给出的证明相同。如正文第4节所示，我们将使用P表示n个投标人的类型分布（可能相关），以及Po表示其覆盖副本的分布。引理16（引理2重述）。根据P分配类型的任何程序所能实现的最高预期福利，相当于当投标人被替换为其所涵盖的部分时所能实现的最高预期福利，这些部分无需支付检查费用，且类型根据P分配o.证据当代理人的类型根据P共同分配时，可实现的最高预期福利o是E[maxi（κi）+]，例如通过运行二次价格拍卖来实现。我们已经在定理M3的证明中看到，当代理的类型a根据P重新联合分布时，这也是第一个最佳程序的预期福利。

实现这一最佳福利的机制是动态VCG机制，在该机制中，每个投标人在拍卖开始时披露其所有私人信息，并在每次进行新阶段的检查时更新其私人信息；该机制指导各投标人按照放弃优先权程序规定的顺序进行检查，按照该程序规定分配物品，并向中标人收取一个价格，其预期价值等于中标人通过参与拍卖对其他投标人施加的负外部性。为了节省空间，我们没有重复定理2的完整证明——我们模型中的荷兰引进均衡与投标人被覆盖的对等物替换时的均衡之间的对应关系——我们只是简单地描述了如何将证明修改为多阶段检验的设置。首先，为了陈述该定理，必须将功能对等的定义推广到多阶段检查的设置中。定义13。如果两个拍卖结果以相同的价格将物品交付给同一个投标人，并且每个投标人在两个拍卖结果中承担相同的检查成本，则称两个拍卖结果在功能上等同。投标人的两种策略在功能上是等效的（相对于对手策略的给定比例），如果它们总是导致功能上等效的结果。两个平衡点在功能上是等价的，如果它们对每种类型的结果在功能上是等价的。定理5。在我们的模型中，荷兰式拍卖的平衡点按照P的形式分布，而荷兰式拍卖的平衡点按照P的形式分布o投标人未经检查就知道其价值。

该映射保持了双数据预期效用和拍卖商预期收益，并引入了双射函数等价类均衡。回想一下，定理2的证明的关键是一对映射，u和λ，从投标者i的策略到其覆盖对手投标者i+n的规范化策略，反之亦然。与之前一样，我们可以将bidderi+n的策略u（s）定义为投标人i执行的检验政策的模拟。事实上，由于我们的惯例，投标人i+n的策略是根据投标人i的过滤{Fk，τi}调整的检验政策，我们可以将u定义为identityfunctionu（s）=s：对于投标方r i+n，模拟s和执行s之间没有区别。对于被覆盖的对等投标方，标准化策略的定义以一种显而易见的方式概括：投标方r i+n的策略s是标准化的if1。它总是在尽可能早的时刻执行所有阶段的操作，即s（ω，0）=∞ 对于所有ω；2.其试图获取物品的价格（如果另一投标人尚未提出索赔）由函数b（vi）给出，其价值仅取决于vi；而不是检查中间阶段的结果；3.函数b（vi）是非递减的。如果b是投标人i+n的标准化策略，那么我们可以定义λ（b）为投标人i的策略，其操作如下：如果当前检查阶段为k<∞, 当价格为b（κki）时，λ（b）进入下一个检验阶段；如果当前检查阶段为k=∞ 当价格为b（κi）时，λ（b）索赔。该政策λ（b）是不公开的：如果σki>κk，则立即进入下一个检查阶段，而不等待价格进一步下降，如果k=∞vi>κi它立即获得物品。定理m 2的证明依赖于四种主张。

权利要求1、3、4的证据除符号和术语发生变化外均未发生变化；例如，当我们从一个检查阶段概括到多个检查阶段时，“几乎可以肯定的是在金钱中锻炼”变为“不暴露”。在权利要求2中，bi+nandu（λ（bi+n））在功能上等价的证明没有改变，但biandλ（u（bi））的证明需要一个非平凡的推广。在权利要求2的原始证明中出现的单阈值BINSPI（θi）中，投标人的策略定义了一系列随机变量bki，每个变量表示如果没有其他投标人声称该项目，SIP将在该时间段进行第k阶段的检验。更正式地说，bki=t（τki），其中τki=inf{τ| si（ω，τ）≥ k} 仅限于样本点集，其中s（τki）=⊥, τki（和hencealso bki）的值必须为Fk-1,0-可测量，因为我们假设事件si（ω，τ）≥k是可测量的，与i的私人类型her Firstk生成的σ-场有关- 1检验结果和s（τ）。现在，正如在权利要求2的证明中，我们推断投标人（i+n）的标准化策略u（si）由满足b（κki）=bki的投标函数b指定，因此λ（u（si））在p rice bki精确地进入K检验阶段，除非该项目已经准备好分配，就像策略si一样。类似地，这两种策略都以b（κi）的价格获得该商品，除非它已经被定位。这就证明了它们在功能上是等价的。正如在权利要求2的原始证明中，标准化策略si+nandu（λ（si+n））的功能等价性是投标人i+n没有检查成本这一事实的简单结果。

感谢分享