降价最优地协调搜索

引理2、定理2和推论2在具有多个检验阶段的模型中成立，具有适当定义的履约价格和涵盖的看涨期权的广义概念。非正式地说，履约价格的泛化是一个（随机）价格序列，每个检验阶段一个，每个代表看涨期权的履约价格，鉴于决策者已经达到给定的检验阶段并投入了相应的成本，其公允价值将完全覆盖决策者的预期剩余检验成本。然后将广义覆盖赎回价值定义为该履约价格序列的最小值。直觉这是个人在检查前的每个检查阶段出售相关看涨期权以资助未来信息获取的价值。我们将正式定义留给附录，因为它有些复杂。但是，正如第4节所述，它保留了所有相关的福利数量，其实质意义与单一检查阶段的情况相同。为了只对一定数量的阶段进行建模，所有后续阶段都不需要额外成本，也不需要披露任何信息。6.2许多对象基线分析侧重于单个对象的情况，但我们的基本见解延伸到包含多个项目的上下文。在这种情况下，我们需要一种拍卖形式，在不同的物品之间有一个统一的降价，这对我们来说是新奇的。一组M个不同的物品出售给一组N个投标人。投标单位需求；每个人最多想要获得一件物品。在我们的基线模型中，我们将用i表示一般投标人。我们将使用符号j表示一般项目。

在基线模型中，投标人被赋予了一个θi类型，该类型确定了成本向量ci（θi），典型元素cij（我们从中删除了辩论）表示投标人i检查对象j的成本。每个投标人根据任意联合分布绘制的θi类型。给定θi，根据分布Fθi，j定义6，在i和j之间独立绘制投标人i对对象j的价值vjj。统一降序拍卖是一种按如下方式进行的销售程序。时钟从两点开始∞ 并不断减少库存，维护一套可用的项目；两者都公开展示。在任何时候，任何投标人都可以在投标时要求任何可用的项目，此时，投标人和投标人都可以立即删除该项目。然后时钟继续下降，直到达到0。就我们所知，即使在没有信息获取的情况下，之前的文献中也没有分析过这种机制的均衡。当信息获取被纳入模型时，没有已知的计算可处理程序可以保证实现超过一半的最优分配福利，让人们难以想象完全的效率是一个容易实现的目标。因此，在这种情况下，对Theorem2的模拟意义不大。相反，我们证明了推论2第二点的类似物，即任何均衡都将非常紧密地近似于福利保障。实际上，我们的基线分析也仅在证明中进行了小的修改，适用于固定数量的相同项目用于福利保障的情况，或者更一般地，对于某些代理子集可能被选为一个联盟的赢家的情况，这些可行的赢家集合c构成一个拟阵，而virepresents代理i的赢家值。

对拍卖进行了修改，以便：（i）代理人可以通过计算当前时钟值，随时加入赢家组；（ii）代理人不属于当前赢家组的任何可行超集时，从拍卖中被淘汰；（iii）当每个代理人都被包括在赢家组中或被淘汰时，拍卖结束。经纪人被淘汰时会被告知，但当其他经纪人加入赢家时，他们不会被告知。该机制的一项专利正在申请中，其美国专利和商标名为“与信息共享匹配的递减计数器值”。在我们所知道的最佳可处理分配协议中，在完全了解所有事先已知信息的情况下，即保证实现一半最优福利的贪婪匹配算法。我们在附录中的论点大量借鉴了计算机制设计中的光滑性文献（Lucier和Borodin，2010；Roughgarden，2012；Syrgkanis，2012；Syrgkanis和Tardos，2013；Chawla和Hartline，201 3），这些文献用于推导这种形式的近似效率结果。定理3。在均匀下降拍卖的任何Bayes-Nash均衡中，expec te dwelfare至少为（1）- E-2) ≈ 0.43的最佳成绩。因此，我们在单品情况下得出的结果背后的基本直觉，即保证合理的性能，会延续到有许多待售物品的环境中。6.3近似最佳响应在我们的环境中，确定最佳响应可能很困难，尤其是在上一小节的扩展中，因为决定何时调查哪个对象以及在调查后投标什么，需要对其他代理的可能行为进行丰富的战略计算。幸运的是，我们的结果并没有敏感地依赖于经纪人能够做出完美的最佳反应。

这是近似参数的一个吸引性质，就像我们用来建立定理3（Roughgarden，2015）的近似参数一样。特别是，我们会说，如果投标人至少得到一个分数α，那么他们的反应最好≤ 他们可以通过任何策略实现的最大效用之一。我们的界限在α中不断下降。提议5。在荷兰单品拍卖中，如果所有买家α-反应最好，那么预期福利至少是一个因素1- E-α是最优的。在具有多个项目的统一降价拍卖中，如果所有投标人α-最佳响应，那么预期福利至少是一个因素（1）- E-2α）的最佳值。对于相当大的α来说，这种衰减确实是相当缓慢的。例如，当α=0.7时，与近似保证值1相比，荷兰拍卖单品的预期价格至少是最优价格的一半-E≈ 63%的人对彼此的反应最好。当α=0.7时，与近似保证为1相比，多个物品的统一拍卖的预期福利至少是最优的37%-E≈43%的玩家对彼此的反应最好。6.4共同价值从a和We ber（1982）的研究中可以看出，在没有信息获取成本的情况下，如果个人拥有共同的价值，即物品的真实但未知的价值在所有拥有物品价值信号的个人中都是共同的，那么升价拍卖通常比降价拍卖带来更大的收入。这就提出了一个问题，即在我们模型的commonvalues版本中，上升价格机制是否会胜过下降价格机制。

在这一小节中，我们表明，与此相反，升序定价机制的不良潜在性能和降序定价机制的良好保证性能扩展到了一个简单的公共价值背景。考虑我们的基准环境，对价值和信息结构进行以下修改。每个人都有一个共同的先验知识，即物体的真实价值，以及确定这个共同价值的个人特定成本，即私人知识。为了获得上述项目，需要花费该成本。由于目标对所有个人都具有同等价值，因此效率的唯一范围是确保调查目标的个人拥有尽可能低的成本。正如Bergemann和V"alim"aki（2002）所证明的那样，在上升或同时进行的二次价格拍卖中，总是存在一个均衡来实现这种效率。然而，正如Maskin和Tomoeda（20 16）所显示的，通常存在非常不充分的平衡。在我们的例子中，这是特别容易的。假设所有成本都已知，并且有两个投标人，爱丽丝和鲍勃。爱丽丝花了很多钱- Bob有成本，其中E[v]>>  > 0. 最好的福利是E[v]- 并在均衡状态下实现，在提交E[v]出价且无竞争对手后，Alice相信Bob将以0的价格查询并索赔该物品。然而，假设Bob belie ves Alice肯定会提出质疑，然后提交v的报价。Bob没有动机出价高于0，因为如果他提出质疑，他无法避免遭受损失。在这种情况下，Alice对做出了积极的贡献，如果不努力，就会失去这些。因此，这种状态构成了不平衡。

如→ 在这个例子中，无ZF状态的代价是任意的。相反，下面的定理表明，在这种情况下，下降过程非常有效。提议6。在本节所述的共同价值环境中，降价单品拍卖至少达到1-是社会福利的最佳选择。这表明，将我们的结果扩展到更丰富的公共价值环境中是可能的，例如，投标人有私人的估值信号，或者同时具有公共和私人价值成分。这是未来研究的一个有趣方向。6.5可选检查在我们的基线模型检查中，个人必须使用某个对象。在许多情况下，这似乎是真实的：在收购一家公司时，法律通常规定尽职调查是完整的，购买一套房子通常需要检查和评估，在学术界招聘就业市场候选人时，如果没有校园面试，几乎是不可能的。然而，在某些情况下，比如买车，在消费前检查可能是可选的。这种可能性为降价机制带来了有趣的挑战。虽然知道物品的价格不是太高（从上面包围它）可能对决定是否检查或完全放弃物品（在“否”和“ma ybe”之间决定）至关重要，但只有当物品的价格非常低时，在不费心检查的情况下消费它才是最佳选择。例如，假设有两个投标人。投标人A的检验成本等于1，概率p>1/v的检验成本等于v，剩余概率的检验成本等于0。B id d er B没有检验成本，从分配中采样的值w将完全支持[0，∞).

由于检查B的值w是免费的，因此第一个最佳程序从这样做开始。如果w大于投标人A的履约价格（即v-1/p），则只将项目授予B是最佳选择。如果w充分接近于0，则将项目授予A是最佳选择，而无需花费检查A价值的成本。如果w位于这两个极端之间的非空区间，则最好先确定a的价值，然后将该项目授予价值较高的投标人。因此，为了实施最佳程序，在A决定检查其值之前，有必要了解B值的下限和上限。虽然我们给读者留出了一个平衡结构，但应该注意的是，在下降过程中，B的值将无法发出信号，表明B的值高于在第一最佳过程中刺激a检查所需的阈值。更一般地说，对于投标人来说，在检查和即时购买之间进行选择（在“可能”和“是”之间做出决定），关键是要知道物品的价格不会太低（从下方限定）。因此，似乎有理由认为，最大的效率可能不是通过一种上升或下降的价格机制实现的，而是通过一种潜在价格从两端汇聚的混合机制实现的。另一方面，在这种情况下，没有已知的计算可处理的算法来实现第一个最佳（Doval，201 4）。然而，至少在检查发生在单个阶段且存在单个对象的情况下，由于检查而产生的效率不能像根本不考虑对象而产生的效率那样“复合”。直觉上的原因是，一旦一个人认领了物品，其他任何人都不可能有其他效率损失。

任何一个给定的个体，只要选择忽略两个选项中的一个，就永远不会失去超过一个最优策略所能实现的自我。更正式地考虑我们的baseli-ne模型，唯一的修改是，投标人现在可以选择在不进行首次检查的情况下索赔和接收Eθi[vi]。提议7。在可选检验模型中，任意一个检验的Bayes-Nash均衡至少达到-2.最优秀的人的福利。因此，在这种情况下，降价过程至少近似于最优性。6.6公布的价格我们的结果背后的基本直觉是，为了表现良好，一种机制必须允许投标者通过保证他们在他们必须决定的检查点上，能够以有上限的价格获得物品，从而在资金中行使。这种机制在某些方面甚至比我们的更简单，并且允许这样做，即与投标人接洽，并向他们提供标价。这显然需要卖家知道一个合理的价格。当投标人的类型是独立的，且卖方知道其分布时，可以计算出一个近似最优福利的价格。定理4（“先知不等式”，Krengel和Sucheston（1978年）；塞缪尔·卡恩（1984）。让X，Xnbe独立非负随机变量。假设随机变量X的分布*= maxixih没有点质量，让π是这个分布的中间点。设Z等于超过π的最低指数xit，如果没有，则为0。ThenE Z≥E X*.推论3。当投标者完全独立时，将价格π设置为最大覆盖看涨值分布的中位数的顺序标价程序将获得最佳预期福利。备注1。

以随机顺序排列投标人并按顺序提供投标人特定标价的不同程序可以显示为至少获得1-利用Esfandiari等人（2015年）的“预言家秘书长素质”，对最佳预期福利进行预测。在避免标准程序的极端失败的同时，顺序公布价格机制牺牲了拍卖的价格发现效益。与下降过程不同，即使在对称和没有信息采集的情况下，它也不是完全有效的。任何标价都将排除某些投标人，这些投标人可能在任何给定样本中价值最高，或将利润分配给某些投标人，而这些投标人在给定样本中价值不最高。降价拍卖保留了交易的价格发现功能，同时提供了必要的担保，以确保资金的行使。7除拍卖外，我们所有的正式结果都与拍卖有关，即可转让的公用事业环境。在这种环境中，投标人对物品的估价与投标人获得的物品无关。然而，近年来关于“市场设计”的大量文献将拍卖的见解与市场双方将代理人配对与偏好匹配的机制，以及无法进行转移的分配问题联系起来。例如，Hat Fiield和Milgrom（2005）表明，价格上涨的潜在结构与Crawford和Knore（1981）和Kelso和Crawford（1982）提出的可转移效用匹配的上升匹配值（最低值匹配ma d e First）程序以及Gale和Shapley（1962）的延迟接受算法密切相关。

由于双边垄断问题（Myerson and Satterthwaite，1981）和缺乏转移支付，不完全信息环境中的定量福利保障在这些替代环境中往往不可用。然而，拍卖和匹配机制之间的结构联系被用来表明常用匹配程序的吸引力，反之亦然。这表明，我们的研究结果中关于拍卖的一些见解可能与匹配环境中的情况类似。在本节中，我们简要地非正式地推测了这些设置。我们希望未来的研究能更正式地量化这些提案的福利性质。7.1双边匹配和马沙利匹配经济学者倡导的大多数集中匹配程序（Roth，2015）涉及参与者同时提交偏好列表。这可能会导致更大的福利损失，原因与我们在拍卖中强调的类似。例如，进入全国居民匹配项目的医学生必须在明确自己选择的医院之前提交他们可能匹配的所有医院的偏好。这类学生可能很难知道哪些医院值得更深入地调查，从而导致潜在的巨大福利损失。事实上，在许多不是由集中匹配组织的市场中，双边匹配似乎具有降价拍卖的特点；也就是说，从高值匹配到低值匹配顺序明确，在信息获取过程之前，参与者在不同的时间点获得关于其选择的“保证”。有两个例子可以说明问题。首先，在大学招生中，学生们通常会“提前申请”放弃自己的选择，因此他们的申请会得到更彻底的审查。