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

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
通过考虑具有相关值的设置，我们扩展了关于同时物品拍卖的无政府状态(PoA)价格的文献；我们通过相互依赖价值的基本经济模型(IDV)来做到这一点。众所周知，在具有私有值的多项设置中，相关值可能导致糟糕的PoA，其代理数可能是多项式大的$N$。在更一般的IDV模型中，我们证明了即使在单项目设置下PoA也可以是多项式大的。从积极的方面来看，我们发现了市场中信息分散的一个自然条件，称为$\\γ$-异质性，这使得良好的PoA保证成为可能。在此条件下，我们证明了对于单项设置，标准机制的PoA以$\\gamma$的形式优雅地下降。对于具有$M>1$items的设置，我们展示了两个域之间的分离：如果$N\\geq M$，我们设计了一个新的同时拍卖项目，在有限的信息不对称下具有良好的PoA（相对于$\\gamma$)。据我们所知，这是多项设置中相关值的第一个积极的PoA结果。建立这一结果的主要技术困难是，建立PoA结果的标准工具--平滑度框架--不适用于IDV设置，因此我们必须引入新的技术来应对这种设置带来的独特挑战。在$N\\llM$域中，我们建立了不可能的结果，即使是对于令人惊讶的简单场景也是如此。
---
英文标题：
《Price of Anarchy of Simple Auctions with Interdependent Values》
---
作者：
Alon Eden, Michal Feldman, Inbal Talgam-Cohen and Ori Zviran
---
最新提交年份：
2021
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  We expand the literature on the price of anarchy (PoA) of simultaneous item auctions by considering settings with correlated values; we do this via the fundamental economic model of interdependent values (IDV). It is well-known that in multi-item settings with private values, correlated values can lead to bad PoA, which can be polynomially large in the number of agents $n$. In the more general model of IDV, we show that the PoA can be polynomially large even in single-item settings. On the positive side, we identify a natural condition on information dispersion in the market, termed $\\gamma$-heterogeneity, which enables good PoA guarantees. Under this condition, we show that for single-item settings, the PoA of standard mechanisms degrades gracefully with $\\gamma$. For settings with $m>1$ items we show a separation between two domains: If $n \\geq m$, we devise a new simultaneous item auction with good PoA (with respect to $\\gamma$), under limited information asymmetry. To the best of our knowledge, this is the first positive PoA result for correlated values in multi-item settings. The main technical difficulty in establishing this result is that the standard tool for establishing PoA results -- the smoothness framework -- is unsuitable for IDV settings, and so we must introduce new techniques to address the unique challenges imposed by such settings. In the domain of $n \\ll m$, we establish impossibility results even for surprisingly simple scenarios.
---
PDF下载：
--> English_Paper.pdf (759.44 KB)

2022-4-16 11:04:35 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：establishing SIMULTANEOUS Coordination Contribution Environments

具有相互依赖价值的简单拍卖的无政府状态的价格*阿隆·伊登（Alon Eden）米歇尔·费尔德曼（Michal Feldman)、因巴尔·塔尔加姆-科恩（Inbal Talgam-Cohen§Ori Zviran)2021年3月2日摘要我们通过考虑具有相关价值的设置来扩展关于同时物品拍卖的无政府状态（PoA）价格的文献；我们通过相互依赖价值的基本经济模型(IDV)来做到这一点。众所周知，在具有私有值的多项设置中，相关值会导致糟糕的PoA，它可能是代理数n的多项式。在更一般的IDV模型中，我们证明了在单项目设置下PoA可以是多项式的。从积极的方面来看，我们发现了市场中信息分散的一个自然条件，称为γ-异质性，它使PoA得到了良好的保证。在此条件下，我们证明了对于单项目设置，标准机构的PoA与γ是退化的。对于m>1个项目，我们给出了两个领域之间的分离：如果n≥m，我们设计了一个新的同时项目拍卖，它具有良好的PoA（关于γ)，欠有限信息不对称。据我们所知，这是多项设置中相关值的正向PoAresult。建立这一结果的主要技术障碍是，建立PoA结果的标准工具--平滑度框架--不适用于IDV设置，因此我们必须引入新的技术来解决此类设置带来的独特性。在n m域中，我们对非常简单的场景建立了不可能结果。1引言我们研究了以社会福利最大化为目标的向单位需求代理销售异质商品的简单而实用的机制。虽然许多文献关注于真实机制（对此，报告物品的真实价值符合代理人的最佳利益），但这些机制往往复杂、计算和认知要求高，必须以集中的方式运行[Dobzinski,2011,Li,2017a,Ausubel et al.，2006]。在许多现实生活中，如电子商务，实际使用的机制是简单的，以分布式的方式运行，但不真实。一个主要的例子是e-Bay进行的拍卖，其中每件物品都是单独出售的。A.Eden、M.Feldman和O.Zviran的工作得到了欧洲研究委员会(ERC)根据欧盟地平线2020研究和创新计划（赠款协议号866132）和以色列科学基金会（赠款号317/17）的部分支持。I.Talgam-Cohen的工作得到了以色列科学基金会（批准号336/18）和Taub家庭基金会的支持。“哈弗大学(aloneden@seas.harvard.edu)→特拉维夫大学(michal.feldman@cs.tau.ac.il)§Technion，以色列理工学院(italgam@cs.technion.ac.il)→特拉维夫大学(orizviran@mail.tau.ac.il)，其中代理人对每件物品都有一个价值，她对一个包的价值是一个包的物品的最大价值。在第二价格拍卖中，这样一个对最多赢得一次拍卖感兴趣的代理人可能会报告低于她的真实价值，以避免多次[2016a]开创了同时物品拍卖的研究，即对每个物品单独进行单一物品拍卖。由于这类拍卖是真实的，它们的表现是由它们的贝叶斯无政府价格（B-PoA）来衡量的，即最优福利和最坏均衡的福利保证之间的贝叶斯无政府价格。赫里斯托杜卢埃。许多后续研究表明，当使用的拍卖是firerst或second-price拍卖时，这种简单的格式在组合设置中实现了近乎最优的福利（见Roughgarden et al.[2017]关于结果的概述）。

重要的是，以前的所有著作都假设独立于买方的估价，因为否则PoA可能是代理人数量的多项式[Bhawalkarand Roughgarden，2011,Feldman et al.，2013,Roughgarden，2014]。在许多情况下，独立性假设是不现实的。例如，如果被拍卖的物品有可能在未来被转售，这种可能性会影响代理对该物品的价值，从而依赖于其他人对它的估价。这种依赖性被相互依赖的价值(IDV)模型所正式描述[Milgrom和Weber，1982]，在最近toMilgrom和Wilson因其在拍卖理论方面的工作而被授予诺贝尔经济学奖后，该模型受到了极大的兴趣。在这个模型中，价值的相关性直接来自于市场的一个最基本的方面--信息在代理人之间的分散方式。更详细地说，每个代理都有一个私人已知的信号，它捕获了关于待售物品的部分知识。她对每个项目的价值是市场上与该项目相关的所有信息的函数；也就是说，她自己的信号以及所有其他代理人的信号（对她来说是未知的）。自从Milgrom和Weber[1982]以来，经济学文献和计算机科学文献对IDV设置进行了广泛的研究[Ito和Parkes，2006,Constantin等人，2007,Robuet等人，2013，Chawla等人，2014，Roughgarden和Talgam-Cohen，2016,Eden等人，2019]；有关概述见Krishna[2009]，有关其他相关工作见第1.3节。该模型所描述的现实情景包括公共价值拍卖[Klemperer，1998]、矿权拍卖[Wilson，1969]和转售[Myerson,1981,Roughgarden和Talgam-Cohen,2016]。本文以后者为例：例1.1（转售模型）。设sibe是agent i∈[n]的私有信号，均匀分布于0和1之间。这个信号捕捉到代理i对待售项目的赞赏。对于某些参数β∈(0,1）,Agent I的估值函数为vi(s)=Si+βPJ6=IsJ.也就是说，代理也会考虑其他人对该项目的评估（可能是因为她计划最终转售该项目）。我们的主要问题是：main question。什么是带有IDV的同时物品拍卖的B-PoA？我们建立的边界部分地回答了Roughgarden等人的一个公开问题。[2017]关于同时物品拍卖的B-PoA所适用的自然、经济上有意义的相关形式。1.1在处理IDV中的B-PoA的限定任务时，会出现一些挑战。直觉表明，可以用相互依赖的价值来建模的问题领域非常大，其中包括最常被研究的私人价值设置，无论是相关的还是不相关的。由于宽屏，这是不足为奇的，在完全普遍的情况下，没有希望达到一个良好的界限的b-poa。我们的下界形式化了为了得到一个独立于代理数量的界而需要的假设。在相互依赖的模型中，一个标准的假设是单交叉(SC)。从直觉上看，这意味着一个代理人所拥有的信息对她自己的价值比对他人的价值更有说服力。在相互依存的环境中，供应链能够产生许多积极的结果[Ausubel等人，2000年，Maskin等人，1996年，Chawla等人，2014年]。例如，在单一物品设置下，真实（广义）Vickrey拍卖只在SC下实现最优福利。然而，只有SC才能保证简单拍卖的B-PoA结果，即使是单个项目。下面的命题表明，任何将项目分配给具有最高价值的代理的机制都容易产生很大程度的社会影响，即使在SC.命题1.2中也是如此。

存在一个满足SC的单项目n投标人设置，使得每一个将项目分配给最高价值投标人的拍卖的PoA为Ω(n)。虽然充分的证明推迟到附录a.2，但这个否定结果背后的直觉对确定肯定结果的必要假设有指导意义：考虑n个投标人，当i≥3时，其seSignals分别属于子集S={1}，S={1}和Si=[0,1]。考虑V=pi∈[n]Si+,V=2(S+),VI=sifor i≥3,其中>0为任意小值。在这种情况下，投标人i≥3的信号对投标人1的价值有一个信号，但对投标人2的价值没有信号。在这些投标人有高信号的情况下，投标人1的价值明显高于投标人2的价值。然而，投标人i≥3从来没有赢得该项目，因为投标人1超过了他们的价值为每一个信号亲。因此，他们也可以在平衡状态下报告低信号，导致投标人2赢得项目的结果。对于每一个确定性的真实（事后激励相容）机制，都有一个与命题1.2类似的结果。在相互依存的背景下，激励相容性(IC)和个人理性(IR)是事后定义的，即，鉴于所有其他投标也是真实的，参与并报告她的真实信号符合每个投标人的最佳利益（如实投标是该机制的事后定义--见第2.3节）。如果对于每个信号profile s,bidder i和bi,xi(s)vi(s)-pi(s)≥max{xi(bi，s-i)vi(s)-pi(bi，s-i)，0}，则单项机制是后IC-IR机制。后IC-IR机制可以被描述为具有单调分配规则的机制[例如，Roughgarden和Talgam-Cohen,2016）：对于每个bidder i和部分bid profile b-i，分配规则xi(bi，b-i)在bi中（弱）增加。单调分配规则与由分配规则唯一确定的支付规则耦合。对于确定性机制，胜利者i是由他的临界出价来收费的。对于这类机制，我们展示如下（见附录A.2)。命题1.4。存在一个满足单交叉的单项目N投标人设置，使得每一个确定性的事后IC-IR机制的PoA都是Ω(√n)（即使在无过度出价的情况下）。即使在标准的无过度出价假设下（见第2节）和信号的子模块性等附加条件下，这也是成立的[Eden et al.，2019]。1.2我们的结果我们研究了代理向拍卖报告其信号的简单机制。关于贝叶斯均衡，我们所有的肯定结果都成立，贝叶斯均衡是最有力的保证，因此传播到其他均衡概念（见观察2.8）。此外，我们还表明，即使在单个项目的环境中，纯均衡也不需要存在（见命题a.1)，这进一步激励了我们选择基准。由于我们正在处理新的未知领域，我们的起点是新项目，在那里我们已经面临私人价值解决中不存在的新挑战。我们考虑自然拍卖形式，如firerst-price和second-price。如上所述，这类拍卖的PoA本质上取决于代理的数量。在命题1.2和1.4的证明中，单个投标人被其他人的信号高度支持，而所有其他投标人都具有私人价值。因此，出价者对出价者信号的Ect变化可能很大。我们将这种变化的程度参数化为γ（定义3.2)，并建立依赖于γ的正结果。我们对单个项目的主要正结果适用于广义Vickrey拍卖(GVA)--这是Vickrey拍卖对相互依赖值的自然推广[Maskin,1996,Ausubelet al.,2000]。我们证明了SC下GVA的B-PoA是γ（见定理3.3)，并且这是紧的（见定理3.4）。

当考虑一个松弛的SC概念c-SC时，我们对GVA和第二价格拍卖都得到了max{γ，c}+1的一个界（定理3.3和c.3)，它是非常紧的（见定理3.4和c.4)。这个结果的一个非平凡的蕴涵是，在γ=c=1的每一个IDV环境中，它认为每一个平衡都是完全的。例如，这是我们的转售模型运行示例（示例1.1）中的ceCase。我们考虑一个具有异构项目和单位需求价值的组合环境。我们允许信号是多维的，这在IDVWithology中是出了名的难以设定的[Dasgupta and Maskin，2000,Jehiel and Moldovanu，2001]。我们对这个案子的结果更加微妙。首先，我们表明，一般说来，对于一个非常自然的机制类，包括我们在本文中所推理的机制类，人们不能近似最优福利。在这个例子中，所有投标人的价值来源于单个投标人的信号；也就是说，这使人们避免了极端的信息不对称。因此，我们为有限信息不对称的设置提供了结果，就像我们的运行示例（关于条件的正式认识，请参见4.2节）。然后，我们展示了两个域之间的分离：投标人多于项目的情况(n≥m)和项目多于投标人的情况。对于n≥m的情况，weconsider是一种机制，它对每一个项目进行二次价格拍卖，考虑每个竞标者的价值是她在出价时的估价，将其他竞标者的出价归零。我们把这种机制称为同时私有化的二价拍卖。在我们的环境中出现的一个微妙之处是，使代理人能够明确表达参与单个项目拍卖的意愿。我们对多个项目的主要积极结果是，对于γ-异构单位需求竞标者，在有限的信息不对称下，同时私有化第二价格拍卖的B-PoA为O(γ)（在c-SC下，我们得到O(max{γ，c}）的界-详见定理4.7）。相比之下，对于具有私人价值的同时拍卖，已知即使对于一般类型的估价（例如。克里斯托杜卢等人。[2016a])。我们的证明不同于光滑性框架，因为典型的证明要求对知道自己对一个项目的价值的投标人的偏差进行推理，而相互依赖的情况则不是这样。我们的证明将福利分解为两个项，并分别限制我们的拍卖性能（更多细节见第4节）。对于M_n的情况，我们提供了一个很强的否定结果。我们考虑onecan设想的最简单的设置：存在nitems，每个项目的投标人都有一个共同的值，该值基于该项目所有投标人的信号之和(Vi`(s)=1+PJSJ`for every item`)。所有信号（任何投标人/项目对）都是I.I.D.采样的。这个例子展示了在我们的环境中协调的原则：对于每个项目，投标人的价值都是相等的，因此，尽管信息是在投标人之间分配的，但原则是识别有价值的项目。从先验来看，所有项目看起来都是一样的，但信号的分布是以一种产生球和宾类现象的方式设置的--每个项目的期望值是常数，但n个项目的最大值是θ（ln n/ln ln n）。因此，Opt=θ（n ln n/ln ln n）。另一方面，根据标准的不出价假设（这对于我们在n≤m制度中的积极结果至关重要），投标人投标的项目数量必须是有界的，这反过来又限制了投标人的预期福利。

因此，我们证明，对于所讨论的设置，对于每一个同时物品拍卖和每一个均衡σ，opt/eq(σ)=～Ω(logn)（完整细节见第5节）。注意，这意味着稳定性的代价是～Ω(logn)，这是一个比先前所知的1.3相关的workswoothness框架更强的负结果。许多分析拍卖PoA的论文都使用了著名的平滑框架[Roughgarden，2015a]，以及它对拍卖和完全信息博弈的适应[Roughgarden，2015b，Syrgkanis和Tardos，2013]。在Roughgarden等人的调查中可以找到更多关于这一点的信息。（2017）.同时拍卖。紧随Chawla等人。[2014],许多后续研究了同时拍卖，其中同时进行的拍卖要么是第二价格（Vickrey）[Bhawalkar和Roughgarden,2011,Fu et al.,2012,Roughgarden,2015b],要么是firegrst-PriceAuction[Hassidim et al.,2011,Syrgkanis and Tardos,2013,Christodoulou et al.,2016b,Feige et al.,2015]。这些结果最终表明，对于最一般的无补价估价类别--次加性估价，同时进行的二价拍卖（在无出价条件下）和二价拍卖分别获得了4和2的PoA[Feldman et al.，2013]。这些结果要求价值是不相关的。具有相关价值的简单拍卖。Syrgkanis和Tardos[2013]表明，对于单个物品的拍卖，即使对于相关的价值分布，无ZF状态的价格也是1-1/E，这是紧的[Syrgkanis,2014]。当数值不相关时，Hoy等人。[2018]表明这个界限是可以改进的。Lucier和Leme[2011]的工作适用于通过第二价格拍卖出售的具有相关价值的单个物品（更普遍地，适用于通过普惠制拍卖出售的多个单位）。在无出价假设下，拍卖的每一个BNE都达到了~Ω隐藏o（log n）个时间。一种实际用于分配赞助搜索广告时隙的拍卖格式。GSP代表广义第二价格，不要与本文研究的广义Vickrey拍卖混淆！至少是最大期望福利的1/4。对于所有已知的与二次价格拍卖有关的积极的PoA结果，都需要这种不出价过高的假设或其变体[参见Roughgardenet al.，2017年，第8.1节]。Lucier和Leme[2011]的结果是光滑性的一个强化变体，称为半光滑性或带有私人偏差的光滑性。半光滑框架由Caragiannis等人进一步发展。[2015]其中，1/4的界限提高到1/2.927。其他目标和拍卖格式。哈特林等人。[2014]和Azar等人。[2017]分别在最大化收入和流动福利（适用于预算设置的福利）的背景下考虑了同时进行的物品拍卖。现在考虑多单位（同质项目）设置和向下倾斜的估值。统一价格拍卖给具有m个最高边际的竞买人m个可用单元，收取(m+1)个最高边际。即使有相关性，这种拍卖中每一个满足不出价条件的BNE都保证了最优预期福利的1/4[de Keijzer et al.,2013,Babaio The et al.,2014]。德瓦努尔等人。[2015]考虑一个简单的投标格式，其中投标人只提交一个实数作为他们的投标。他们分析了一种他们称之为“单一出价”的机制，并表明这种机制给出了次加估值的O（log m）近似，这对于他们认为的一类机制来说本质上是紧的[Braverman et al.，2016]。费尔德曼等人。[2016]在限制互补条件下分析了这一机制。AMD中的相互依赖值相互依赖值模型近年来受到算法机制设计界的关注。这种兴趣是由Roughgarden and Talgam-Cohen[2016]和Li[2017b]发起的，它们成功地应用了简单vs.

相互依赖环境的最佳范例。Roughgarden和Talgam-Cohen[2016]表明，一个独立的先验单样本机制可以逼近最优收益，而Li[2017b]也使用了非常相似的条件来证明，运行具有垄断储备的VCG也可以逼近最优福利。肖拉等人。[2014]侧重于消除假设。他们展示了一种机制，该机制近似于拟阵环境中的最佳收入，不做任何分配假设。他们对valuationfunctions所做的假设是单交叉的，我们在多项设置中使用子模条件来获得阳性结果。伊登等人。[2018]考察了在福利最大化的背景下，如果我们去除单一交叉假设，会发生什么。在没有任何估值假设的情况下，他们注意到事情可能会变得任意糟糕。因此，他们在本文中考察了c-SC条件，并给出了改进的近似界，该界依赖于参数C，有时也依赖于n。伊登等人。[2019]不要做任何单交叉类型假设，而是专注于信号的子模块性假设（他们称之为SoS）。他们注意到，在单参数域中，当一方的价值信号与其他投标人的价值信号的价值无关时，这一条件单独为福利和收入提供常数因子近似，在一般组合设置中也是如此。即使信号是多维的，后一结果也成立。2初步记号法。设x，y是向量，i是索引，A是索引的子集。然后xAis取x的指数A得到的向量。设x-a=xA（特别是x-iis向量x，其入口已移除）。我们所说的x≤y指的是xi≤yi。向量1和0是全1和全零向量。2.1基本问题解决以下是销售单个商品的标准相互依赖设置[Milgrom和Weber，1982]:有n个投标人（代理），每个投标人i具有一个私人已知的信号sifrom signalspace Si（在r≥0)。设s=(s,...,sn)∈s s×···×sn表示所有投标人的信号量。每个投标人i也有一个众所周知的估价vi:S→r≥0，它是信号参数S的函数。这种价值对其他投标人信号的依赖是相互依赖的特性。函数VII在各坐标系中弱增，在Si中严格增。设v=(v,...,vn)表示所有投标人的估价。我们还考虑了有m个待售项目的组合设置：对于多个项目，siis是多维的，并且每个项目都有一个信号SI`。第`项的值VI`等于S`=(S1`,...,SN`)。我们着重于单位需求的估价，对于项目T[m]的asubset的价值为vi(T；s)=max`∈T{vi`(s\')}。作为经典相互依赖模型的一部分，估价过程被假定为单交叉(SC)[例如Milgrom和Weber,1982,Maskin,1996,Ausubel等人,2000]。如果每一个投标人对i，i，每一个信号参数加上每一个δ≥0,vi(Si+δ，s-i)-vi(s)≥vi(Si+δ，s-i)-vi(s),则估价参数v为SC。直观地说，SC意味着投标人自身的价值从信号的变化中得到最大的影响。伊登等人。[2018]针对c≥1引入了一种称为c-SC的自然弛豫，即c(vi(Si+δ，s-i)-vi(s))≥vi(Si+δ，s-i)-vi(s)。我们的结果推广到这种放松。谁知道是什么。我们处理全信息和贝叶斯设置。在任何一个模型中，都有符号空间S，...,Snand估值函数v,.在完全信息环境中，所有投标人都知道所有信号（但机制不知道）。在Bayesiansettings（我们的主要焦点）中，投标人i拥有si的私人知识，这是从一个众所周知的分布Fiwith密度FI中提取的。

我们用F来表示已知的信号相关的联合分布。即使信号是独立采样的，这些值也是相关的，因为它们依赖于相同的信号。这概括了其他论文[Bateni等人，2015年，Chawla等人，2015年，Immorlica等人，2020年]中发现的各种类型的相关性。当处理一个单项目时，我们进一步允许信号本身是相关的，即F不一定是一个ProductDistribution。我们用FSIE表示s-igiven信号的分布SI.submodularity。第4节假定估值函数的子模块性；这意味着，随着竞标者自身信号的增加，其他人信号的增加对她价值的边际影响越来越小：伊登等人。[2019]定义一个更强的估值子模块化版本，称为信号上的子模块化(SoS)。定义2.2（Chawla et al.[2014])。如果对于每一个信号si，其他投标人的每两个报价s-i≤s-i，并且每δ≥0，vi(si+δ，S-i)-vi(si，S-i)≥vi(si+δ，S-i)-vi(si，S-i)，则估价VII是子模的。对于多个项目，同样的规定适用于vi`（而不是vi)，用si`，(S`)-i替换si，S-i.2.2机制。我们的目标是最大化福利，即对于单个项目，将其分配给vi值最高的投标人，对于多个项目和单位需求投标人，将匹配的项目分配给总价值最大的投标人。我们用Opt(s)表示给定定值的最优福利，用Opt(s)表示期望的最优福利，并用Opt=Es￣F[Opt(s)]表示期望的最优福利。一个机制由（确定性）分配规则x和支付规则p的对(x，p)组成。该机制向每个投标人i征求信号报告（投标）BII。Letb=(b，..，bn)表示出价。该机制为每个投标人i输出一个关于她是否赢得该项目以及她的付款pi(b)的指示Xi(b)∈0,1}。分配规则x保证可行性，即对于每一个b，Pixi(b)≤1。投标人i的期望效用是ui(b，s)=xi(b)vi(s)-pi(b)。无出价(NOB)。在关于PoA的文献[例如Bhawalkar和Roughgarden，2011年]中，我们通常假设NOB，具体如下：Definition2.3（用于相互依赖的单项NOB）。如果bi≤i投标人，则bi投标。如果对于所有b'Aσ(s),b satis firegions NOB.NOB假设反映了竞标者不愿因出价过高而使自己暴露于负面效用，并有助于解释某些拍卖形式如第二价拍卖在实践中的普遍存在。众所周知，在没有NOB的情况下，二级价格拍卖具有无界的POA标准机制。在IDV机制中，价值最高的投标人是根据征求的投标b和公共知识估价方案V.规定2.4（关键投标）计算的。给定一个部分出价表b-i，投标人i的关键出价b*ii是她赢得该项目的lowestreport，即b*i=min{bi xi(b)=1}。广义Vickrey拍卖(GVA)征集信号出价，将物品分配给价值最高的出价者i，并收取她的临界出价值vi(B*i,B-i)。此外，还可以自然地将第二价和第二价拍卖推广到相互依赖（我们一直参考这些，而不是独立私人价值版本）。考虑两个具有（独立私人）价值的出价者，其中1。出价1，0是这种价格拍卖的均衡，其福利是，但最优福利是1。在这个均衡中，出价者的出价远远高于她的价值。第二价格拍卖征集信号出价，将物品分配给价值最高的出价人，并收取价值第二高的出价。第2.7条（相互依赖的第一价格）。

figurrst-price拍卖征集信号出价，将物品分配给价值最高的竞拍者，并收取她的价值作为付款。2.3无政府背景下的价格σi(·)是竞拍者i的出价策略作为其真实信号的函数。投标策略可以是纯的（映射到单个报告信号）或混合的（映射到报告信号上的分布）。给定策略参数σ=(σ，..，σn)，设σ(s)是出价信号的映射，σ-i(s-i)是不包括代理i出价的映射。我们重点讨论了以下均衡概念：1。事后均衡(EPE)：如果σ是确定性的，并且对于每个具有信号si的投标人i和每个信号Profecture s-i，ui(σ(s)；s)≥ui((bi，σ(s-i))；s）对于每个bi。纯纳什均衡(PNE)：如果σ是确定性的，并且对于每个投标人i，ui(σ(s)；s)≥ui((bi，σ(s-i))；s)，投标策略profectioneσ构成了具有信号profectione s的完全信息设置的PNE。3。贝叶斯-纳什均衡(BNE)：一个（可能是随机的）投标策略参数σ构成了一个具有信号分布F的贝叶斯设置的BNE，如果对于每个投标人i和信号si,并且每个bi,es-iéfsi[ui(σ(s)；s)]≥es-iéfsi[ui((bi，σ(s-i))；s)]。请注意，PNE和EPE之间的区别在于，在PNE中，投标人考虑了其他投标人的信号，而在EPE中，投标人不知道其他投标人的信号，只知道他们根据自己的投标策略投标。此外，尽管BNE和EPE都不要求投标人知道其他投标人的信号，但EPE是一个强概念，因为它要求投标人对其他投标人信号的每一次实现都做出最好的响应，而BNE只要求投标人对其他投标人信号的期望做出最好的响应。下面的观察总结了这两个概念之间的关系。观察2.8（平衡层次结构）。修理一个机械装置和一个信号装置。每个EPE也是一个PNE W.R.T.对于适当的贝叶斯解，每个PNE都是BNE。上述观察的证明推迟到附录B.1。事后均衡不一定是确定性的，但当我们在下界的上下文中使用这些均衡时，对确定性的限制只会加强我们的结果。无政府状态的代价(PoA)。单项目机制(x，p)对signal Profile s和bid Profile b isPixi(b)vi(s)实现的预期福利。如果机制（特别是分配规则）从上下文中是明显的，我们用SW(b，s)来表示。对于均衡策略σ，设Eq(σ，s)=E[SW(σ(s),s)]为σ在s处的期望福利，且Eq(σ)=Esèf[Eq(σ，s)]，拍卖的事后PoA、Nash PoA和Bayesian PoA分别为:EP-POA=sups,v,σ:σ为EPEOpt(s)Eq(σ，s)；NE-PoA=sups,v,σ:σ是PNEOpt(s)Eq(σ，s)；B-PoA=supF,v,σ:σ是BNEOptEq(σ)。也可以限制设置的类别，例如，那些具有满足SC属性的估值属性的设置，或者满足NOB属性的策略。这样的限制通常会改善PoA，我们利用这种方法来实现我们的结果。观察2.8意味着EP-PoA的下界和B-PoA的上界会传播到其他概念。3单项：一个积极的结果在本节中，我们重点讨论单项设置。我们的主要结果是一个（参数化的）属性，它与SC一起导致了良好的PoA边界。回想一下上面描述的设置，在这里，比如说，agent3a的信号只包含她自己和agent1的值，而不包含其他agent。在相反的极端中，一个代理信号的变化会平等地影响所有其他代理的值。即:πi,j,j:vj(Si+δ,s-i)-vj(s)=vj(Si+δ,s-i)-vj(s)，我们称此条件为齐次条件。

我们可以在运行的例子--转售模型--以及在其他突出的设置中验证同质性，如Klemperer\'swallet-game[Klemperer，1998]、公共值[Wilson，1969]、私有值和私有/公共值插值[Bergemann和Morris，2013]。我们发现，同质性与SC一起保证了完全的e_ciency（这是推论C.1的直接推论）。命题3.1。在具有SC和同质的单项目环境下，GVA的每一个均衡都是完全E_cient的，这一结果的鲁棒性有多大？换句话说，当我们从同质性中移开时，原始人将如何改进？为此，我们引入了下面的参数化性质，它度量了一个估值项目离同质性有多远。第3.2(γ-信号价值影响的异质性）。如果对于每个代理i,另外两个代理j,j,signalprofile s和δ>0,γ(vj(Si+δ，s-i)-vj(s))≥vj(Si+δ，s-i)-vj(s),则估值公式为γ-信号值影响中的异质性，或简言之γ-异质性。γ=1的特例是均匀的。我们在本节中的主要结果是对γ-异质SC估值的B-PoA的一个紧界。Ourresult扩展到c-SC Profigurles[Eden et al.，2019]，其中PoA随参数c而优雅地退化（对于c=1，SC是c-SC）。定理3.3（单项的主要肯定结果）。考虑一个具有γ-异构，c-SC连续估值的单项目设置。NOB下GVA的B-PoA以1+max{γ,c}为界。ForSC估值的B-PoA是严格的γ。这些结果甚至对相关信号也成立。定理3.3本质上是紧的，如下定理所示。定理3.4。存在满足γ-异质性和c-SC的单项目设置，使得广义Vickrey拍卖的theNE-PoA任意接近于max{c,γ}，即使在没有出价的情况下，这个下界的证明推迟到本节结束。我们指出1+max{γ,c}的上界和下界也适用于具有相互依赖性的2Pa,更多细节见附录c.2。在证明3.3之前，我们引入了以下技术引理和推论，这些引理在整个论文中都是有用的。引理3.5。设v是满足γ-异质性和C-SC的估值条件。然后，对于每两个代理i,j,信号序列s和坐标方向非负向量δ=(δ,..,δi-1,0,δi+1,..,δn),vj(s+δ)-vj(s)≥vi(s+δ)-vi(s)/max{γ,c}。通过重命名假设i=1和j=n；因此，δ=0。设S`=(S+δ,S+δ,...,S`+δ`,S`+1,...,sn)；也就是，将坐标系增加δ\'s后的向量s。注意S=S。我们的假设是：vj(s+δ)–vj(s)=vn(s+δ)–vn(s)=vn(sn)–vn(SN-1)+N-1XK=2 vn(sk)–vn(SK-1)≥v(sn)–v(SN-1):/c+N-1XK=2 v(sk)–v(SN-1)/γ≥v(sn)–v(SN-1)/γ≥v(sn)–v(SK-1)/v(sn)–v(SN-1)=2 v(sk)–v(SK-1)/max{γ,c}+N-1XK=2 v(sk)–v(SN-1)/max{γ,c}+N-1XK=2-vi(s))/max{γ，c}，其中firerst不等式遵循c-SC和γ-异种假设。以下是引理3.5和推论3.6的直接推论。设v是满足γ-异质性和C-SC的估值条件。对于每两个坐标系i，j，信号序列s和坐标非负向量δ=(δ,...,δi-1,0,δi+1,...,δn),如果对于d≥max{γ,c},vj(s+δ)≥vi(s+δ)/d,则vj(s+δ)≥vi(s+δ)/d,该定理即使在附加的信号子模性假设下也成立，更多信息请参考Eden等人。（2019）证明。通过引理3.5，vj(s+δ)-vj(s)≥(vi(s+δ)-vi(s))/max{γ,c}≥(vi(s+δ)-vi(s))/D.结合vj(s)≥vi(s)/D成立了引理。我们现在进行定理3.3的证明。定理3.3的证明。设s为信号源，b为出价源，使得b≤s。Leti∈argmaxjvj(s)，w(b)是b下的胜者。我们证明了tui((si,b-i)；s)≥vi(s)-max{γ,c}vw(b)(s)。