2021年3月ACM经济计算交易中基于信号传递成本的机制设计揭示原理

ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月具有信号传递成本Andrew Kephart和Vincent Conitzer，杜克大学，美国揭示原理是机构设计中的一个重要工具。它允许设计者将注意力限制在真实的机制上，极大地促进了分析。这也证明了算法，允许某些计算问题，在机制设计，以解决在多项式时间。不幸的是，当不是每一种类型都可以误报其他类型（部分验证模型），或者更普遍地误报可能代价高昂时，揭示原则可能无法成立。这也导致NP-硬度结果。这篇文章的主要贡献包括的条件下，披露原则仍然成立时，报告可能是昂贵的特征。（这些是前面部分验证情况下给出的条件的推广[11，21]。此外，我们的结果扩展到的情况下，而不是直接报告类型，代理发送信号，不直接对应于类型。在这种情况下，我们获得的条件时，机制设计者可以限制注意到一个给定的（但任意）从类型到信号的映射，而不失一般性。CCS概念：·计算理论→动力学机构设计附加关键词和短语：自动机制设计、信号成本、部分验证、相关原则、证据、代价高昂的虚假陈述ACM参考格式：安德鲁·凯普哈特和文森特·科尼泽2021年具有信号传递成本的机制设计的揭示原理 ACM Trans. 经济Comput. 9，1，第6条（2021年3月），35页。https://doi.org/10.1145/34344081介绍机制设计涉及根据一个或多个代理人的私人信息做出决策，如果他们认为这不符合他们的利益，他们就不会如实报告这些信息。目标是定义一种机制-一个由代理人玩的游戏-定义代理人采取的行动并将这些行动映射到结果，以便在平衡中，代理人这可能会让我们陷入一种难以控制的境地，即必须搜索我们可以定义的所有可能的博弈。幸运的是，我们被启示原则（RP）拯救了。它指出，任何可以由机制实现的东西也可以由我们感谢ARO的资助W 911 NF-12-1-0550和W 911 NF-11-1-0332; NSF的资助IIS- 1527434、IIS-0953756、IIS-1814056、CCF-1101659和CCF-1337215;以及古根海姆奖学金。作者Kephart和V.Conitzer，杜克大学，计算机科学系，LSRC Building D101，308 Research Drive，Durham，NorthCarolina 27708-0129;电子邮件：andrewkephart@gmail.com，conitzer@cs.duke.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2021计算机协会。2167-8375/2021/03-ART6 $15.00https://doi.org/10.1145/34344086ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月第六章：A. Kephart和V.科尼策∈∈∈ {∞}真实机制，在平衡中的代理人如实报告他们的类型。这极大地减少了搜索空间并且在某些情况下允许在多项式时间内找到最优机制（例如，如果药物数量恒定且允许随机结果[6，7]）。当然，揭示原理在机构设计中获得分析结果的过程中也非常有用。不幸的是，在某些情况下，启示原则并不成立。值得注意的是，这是部分验证设置的情况。2这里，某些类型可能无法报告它们是其他类型（未检测到）。例如，在线市场中的代理可能能够假装在她真的到达后的0分钟到30分钟之间到达，而不是更早或更晚。我们可以用这个例子来说明非真实机制有时可以让我们比真实机制更好地区分类型。类型的代理（即，到达时间）12：10可以报告它是“12：20”类型因此，类型为12：20的座席可以通过报告其类型为“12：45”来证明相反，“12：20”类型的真实报告不能证明这一点，因为12：10类型的座席也可以生成这样的报告。由于在这种情况下缺乏显示原理，确定特定选择函数是否可以实现的问题通常成为NP困难的[1]。因此，很自然地，我们会试图在错误报告图上描述这些条件的特征--它代表了哪些类型会错误报告哪些其他类型--在这些条件下，揭示原则成立。这样的特征化可以帮助我们获得机构设计的分析结果和有效寻找机构的算法。事实上，这些条件以前已经被刻画过[11，21];我们后来重新审视它们，因为它们是我们刻画的特殊情况。在实践中，一种类型是否会误报另一种类型并不总是黑白分明的。很多时候，一种类型可能会以某种代价误报另一种类型。我们称这种机制设计为报告成本。报告成本可能与财务费用或所付出的努力相对应例如，未成年人可能会花点钱买个假驾照消费者可能会使用一些技巧来提高自己的信用评分。在大学录取中，学生可以通过额外的准备来提高他/她的3一般来说，对于代理可能报告的每个类型θΘ和每个报告θθ，都有一个非负成本c（θ，θ）（c（θ，θ）= 0）。传统机制设计是c（θ，θ）处处=0的特殊情况;部分验证是特殊情况其中，c（θ，θθ）=0，且c（θ，θ）=0。由于部分核实是一种特殊情况，因此，直接得出的结论是，披露原则一般不适用于代价高昂的报告。然而，在这篇文章中，我们确定了启示原则仍然成立的充分必要条件，推广了部分启示情况的早期条件[11，21]。此外，我们提出了一个更一般的设置，我们的结果，4即一个代理可以被限制为发送不一定直接对应于类型的（昂贵的）信号。我们称这种机制设计与信号成本。这里我们说一个智能体发出一个信号s，而不是报告一个类型θ。这让我们进入了信号博弈的领域。例如，思考斯宾塞在这个模型中，代理人通过达到一定的教育水平来表示他们的类型（能力）;这个想法是，能力较高的代理人可以更容易地达到更高的教育水平，因此在均衡中，不同类型的代理人分开，雇主采取不同的水平。[1]从分析和算法的角度来看，这只是不幸的。事实上，在这些情况下，一个不诚实的机制往往比任何诚实的机制表现得更好。我们展示了几个这样的例子。2也被称为铁证。3我们在这里没有想到准备有价值的测试之外，例如，学习代数是为了能够解决更多的问题，而是为了获得技巧，例如，如何在不确定的情况下最好地猜测--这可以提高考试成绩但在其他方面没有社会价值。[4]这一条的EC具有信号传递成本的机制设计的揭示原理第六章：ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月→ →→在招聘决策中考虑教育因素在这种情况下，类型和信号之间没有预先的对应关系现在考虑一个雇主，他可以承诺从信号（教育水平）到招聘决策的映射这样，雇主就可以设计一种机制，但不能将注意力限制在直接意义上的这将是非常有帮助的雇主知道从类型到信号（代理人将被激励遵循）的映射，具有以下属性：如果有任何这样的映射足以满足雇主的目标，那么这个映射也是如此在标准机构设计中，这种特殊映射是真实的映射。在我们的例子中，不清楚哪种映射- ping（如果有的话）起作用.但是，对于任何给定的映射，我们提供了它具有所需性质的充分必要当然，这概括了前面讨论过的情况，即信号对应于类型，如实报告是无成本的;在这种情况下，兴趣映射是真实的。我们相信，机制设计与信号成本框架将越来越重要。这是因为这些运行机制越来越多地拥有关于代理的数据，而不是事先对他们一无所知，只能询问他们的偏好。现在，一个代理可以经常改变机制中的数据，但是这需要代理付出一些努力（或其他）代价。因此，标准的机制设计框架，代理人可以报告任何类型在没有成本的但是，机制设计与昂贵的信令框架。在第6节和第7节中，我们考虑了信号传递成本之外的方面，如估值函数和选择函数，是已知的情况。1.1介绍性示例-检查游戏“检查博弈”的例子说明了我们的模型以及失败，一般来说，在机制设计与报告成本设置的启示原则。6，7我们将在第3节介绍另一个更复杂的例子。假设贝丝正在考虑从帕姆那里买一箱农产品。产品可以是新鲜的，体面的，或腐烂的（帕姆会知道它是什么）。贝丝可以接受或拒绝板条箱。如果农产品是新鲜的或体面的，那么Beth会愿意接受它;否则，她会拒绝它。这给出：Θ={fresh，decent，rotten}-类型的集合O={accept，reject}-结果集F={fresh accept，decent accept，rotten reject}--贝丝试图实现的选择函数。在做出决定之前，贝丝可以检查一下农产品。然而，在一些成本帕姆可以添加染料或气味的产品，这将改变它如何出现贝丝。因此，我们也有S={fresh-dec-dec[5]当然，标准的机制设计框架（在这种框架中，误报是没有成本的）可以很好地解决运行机制的一方拥有比代理人更早的信息的情况关键是，标准框架没有解决代理能够以某种代价改变这种先验信息的6我们在参考文献[15]中提出了一个类似的例子这是一个最小的例子，其中一个选择函数是由一些不真实的机制，但不是由任何真实的机制。[7]当然，我们不是第一个注意到，当报告有限时，启示原则可能不成立。参考文献[11]显示了部分验证的特殊情况。第六章：A. Kephart和V.科尼策ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月{→}{→}{→}由于我们在报告成本设置中，因此此集合与类型集合相同我们在每个信号上加上““符号，以将其与相应的类型区分开来下面的矩阵给出了使θ型板条箱发出信号s的成本。例如，花费30英镑，帕姆就能让一箱腐烂的农产品看起来很新鲜。由于我们在报告成本设置中，c（θ，θ）=0，新鲜c（θ，s）=decent烂弗赖什下降腐烂如果接受板条箱，Pam收到的值为208：vθ（接受）=20vθ（拒绝）= 0。贝丝需要致力于一种机制，根据产品的外观来选择结果。只要产品没有腐烂，就接受产品的天真机制，H=freshaccept，dectientaccept，rottenreject就会失败。对帕姆来说，花10英镑的成本让腐烂的农产品看起来不错，净赚10英镑，这是值得的。因此，贝丝最终会无意中接受腐烂的农产品。Beth应该使用N = freshsh接受，减少拒绝，拒绝拒绝。在N下，如果产品真的腐烂了，帕姆就不值得去改变它，它会被拒绝。然而，如果产品是体面的，那么帕姆将使它看起来是新鲜的，它将被接受，从而实现贝丝在这里，启示原则并不成立。存在一组结果、选择函数和评价函数（即这里给出的那些），使得存在实现选择函数的机制（即N）。但是，不存在既激励代理如实报告又实现选择功能的机制（H将是我们最好的候选者）这个例子具有信号是类型报告的属性，并且报告一个类型是无成本的。在类型发出不直接对应的信号的更一般的设置中，对于这些类型，我们并不立即清楚真实的报告意味着什么;在这种情况下，我们感兴趣的是，我们是否可以在不失一般性的情况下，将我们的注意力限制在一 些 将 G 从 类 型 映 射 到 信 号 。在 上 面 的 例 子 中 ， 感 兴 趣 的 映 射 是 G=freshfresh ，decentdecectient，rotten rotdectient，我们证明了我们不能在不失去一般性的情况下限制对它的注意。1.2主要结果我们可以捕捉到我们主要结果背后的高级直觉（在报告成本设置中）：启示原理成立，当且仅当相对于ab和bc，ac较小对于所有类型a，b，c.（回想一下，c是对应于类型c的信号。在这里，我们还介绍了发射成本的简写形式。）为什么会这样呢？让我们试着创造一个违背显示原理的选择函数F。因此，F应该是非真实可实现的，但不是真实可实现的。8一般来说，每个结果对代理的价值取决于类型。000100030100具有信号传递成本的机制设计的揭示原理第六章：ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月→构造F，使得a嫉妒b因此，在一个真实的机制中，当ab很小时，a会想要发射b来接收ob。因此，F不是真正可实现的。当bc也很小时，我们可以尝试通过让b发出c来接收ob来非真实地实现F。但是，如果ac很小，那么a也会发射c，因此我们无法实现F. 因此，启示原则成立。但是，如果ac很大，那么我们可以成功地保持ob远离aatc，实现F.所以启示原则失败了。1.2.1与检查游戏有关。我们说明了我们的直觉如何适用于检查游戏的例子。考虑类型三元组：a=腐烂，b=体面，c=新鲜。这个三元组的启发式算法如下：启示原理成立，当且仅当c（rotten，fresh）相对于c（rotten，decent）和c（decent，fresh）是小的。在检验博弈中，c（rotten，fresh-rash）=30，c（rotten，dec-rash）=10，c（decent，fresh-rash）=10。这些成本违反了启发式的不等式。9因此，启示原则并不成立。但是，如果我们要修改成本函数以尊重启发式- 令c（rotten，freshsh）=0。在N下，所以贝丝会接受N下的烂鱼。因此，N不再实现F，所以启示原理成立。- 令c（rotten，declent）=30。在H下，所以贝丝会拒绝在H下腐烂的鱼。因此H现在实现了F，所以启示原理成立。- 设c（decent，fresh-drop）=30。在N下，帕姆不值得让像样的鱼看起来新鲜。所以贝丝会拒绝N下的好鱼。因此N不再实现F，所以启示原理成立。2模型正如在这种类型的设置中常见的那样，我们专注于单个信号发射代理的情况;这对应于保持其他代理在一个例子中，我们有一组类型Θ;我们通常使用θ，θ1，θ2，.。来表示变量类型和a，b，c，. 以表示特定类型。我们有一组信号，其中s，s1，s2. 表示可变信号，x、y、z表示特定信号。(When代理直接报告类型，我们有S= Θ。）然后我们有启示原理映射G：ΘS，它为每种类型指定一个信号。问题是设计者是否可以在不失一般性的情况下，将注意力限制在每种类型θ发出信号G（θ）的机制上。（当代理直接报告类型时，感兴趣的映射G总是恒等函数，对应于真实的报告。10）、我们始终假设G是从类型到信号的一对一（内射）映射，并且仅将类型映射到具有有限成本的信号。这会自动保持在[9]在这里，我们故意模糊了不等式的精确数学表述，因为它可以根据我们所考虑的设置而变化。我们稍后会给出准确的陈述。[10]下一节将更详细地讨论启示原理映射第六章：A. Kephart和V.科尼策ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月→→→−→×→≥× →≥类型报告案例。在一般的信号模型中，这并不是完全没有损失一般性，但如果G将两种类型映射到同一个信号，那么它们永远不会收到不同的结果。这个假设允许我们通过使用θ，θ1，...来重载我们的符号。、a、b、... 还指示具有相同名称的类型的指定信号也就是说，我们使用一种简写，其中θ既指类型θ，也指信号G（θ）。这在类型报告设置中是自然的，并且在一般信令设置中保持方便正因为如此，我们很少明确提到G（它通常是固定的），但G隐含在信号的命名中。我们也有一组结果（备选方案）O。有一个赋值函数v：ΘOR，其中vθ（o）是类型θ对结果o的赋值。最后，有一个成本函数c：ΘSR0，其中c（θ，s）表示发射s时产生的成本类型θ。我们经常用ax来表示c（a，x）。把这个简写和G的简写结合起来，我们经常用ab来表示c（a，G（b））。一种机制首先由分配函数A：SO定义，其中A（s）=O表示当发出信号s时该机制选择结果O。当我们允许传输时，该机制的另一部分是传输函数T：SR，其中T（s）表示代理在发出s时接收的传输。（因此，T（s）0意味着代理人正在付款。<具有类型θ、发出信号s、接收结果o和转移t的智能体令R：ΘS表示智能体对机制的响应，其中R（θ）=s表示智能体在其真实类型为θ时发出s。我们说R对机构M=（A，T）是最优的，如果对所有θ和s，u（θ，R（θ），A（R（θ）），T（R（θ））u（θ，s，A（s），T（s））.我们通常对实现选择函数F：ΘO感兴趣。我们有时用简写oa表示F（a）。一个机制M=（A，T）与响应R一起实现F，如果R对M和对所有θ都是最优的，A（R（θ））=F（θ）。（此外，它实现了转移T（R（θ））和效用u（θ，R（θ），A（R（θ）），T（R（θ）类型θ。我们说一个机制是真实的，如果所有类型都按照G发射，否则就是不真实的。类似地，如果类型θ发出的信号不是G（θ），我们就说类型θ发出错误信号。我们有时会用N来表示一个不一定真实的机制，用H来表示一个真实的机制。[12]此外，RN和RH指的是相应机制的最佳响应。2.1真实性和启示原则映射，G启示原则的关键是对真实性的清晰理解。在类型报告设置中，真实性是直截了当的：如果类型报告自己，则类型是真实的在信号设置中因为在信号和类型之间没有假定的关系，所以我们对真实性没有固有的概念。[13]我们不是强加一个任意的真实性定义，而是用G映射使它由用户定义（因此，我们确实对G施加了一个限制：从类型到信号必须是一对一这有两个原因：- 一对一的G映射是（隐含地）假设在早期的启示原则工作中的类型报告设置：在真实的报告，显然，不同的类型是假设11例如，假设一个设置有两种类型，只有一种可能的信号。这里，只有一个可能的映射G因此，从技术上讲，揭示原理适用于这种映射，即使它将两种类型映射到同一个信号。[12]这里，H代表[13]将一种类型的真实排放定义为排放成本最低的信号是很诱人的，但这是有局限性的。我们可以想象这样一种情况：每个人都可以以零成本发出一个共同的“什么都不做”的信号具有信号传递成本的机制设计的揭示原理第六章：ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月来制作不同类型的报告。通过继续这个假设，我们的工作更直接可比。- 我们认为，G函数的启示原则，不是一对一的，将看起来明显不同，并使表征显着更加繁琐，没有太大的好处。这是因为当G（θ1）=G（θ2）时，任何满足F（θ1）<$F（θ2）的选择函数F将自动地不能根据定义真实地实现[14]因此，揭示原理成立，当且仅当这些选择功能都不是非真实地可实现的（此外，其他条件也成立）。证明这一点与我们在这里提出的一对一情形的证明有很大的不同我们的证明研究非真实的实现是否可以2.2揭示原理我们说RP保持在一个映射G上，只要我们可以，不失一般性，限制我们的注意力，当试图实现选择功能的真实机制。定义2.1（启示原则）。 给定Θ、S和c，揭示原理在G上成立，如果：对于每个O，v，N =（AN，TN），且RN对 N 是最优的。存在另一种机制H=（AH，TH），其中AH（G（θ））=AN（RN（θ））对所有的θ，其中真实发射响应RH（其中RH（θ）=G（θ））对H是最优的.因此，可以真实地实现任何可以实现的选择函数F在这里，当我们确定揭示原理是否成立时，估价和选择函数都是未知的。这是解释启示原则的标准方式稍后，我们将考虑一个在估值已知的情况下的启示原理的变体。最后，我们将考虑一个更进一步的变体，其中赋值和选择函数都是已知的，我们称之为完全指定的实例。有时，我们还希望用特定的转移和/或转移来实现选择函数。公用事业。定义2.2（固定转移）。如 果 当我们在机制H上增加额外的约束时，揭示原理成立，那么揭示原理对固定转移（对代理人）成立：TH（G（θ））= TN（RN（θ））对所有θ。定义2.3（固定公用设施）。 如果当我们在机制H上增加额外的约束时，揭示原理成立， 那 么 揭 示 原 理 在 固 定 效 用 下 成 立 ：u（θ，G（θ），AH（G（θ）），TH（G（θ））= u（θ，RN（θ），AN（RN（θ）），TN（RN（θ）））.如果转移或效用不是固定的，那么我们说它们是可变的。我们还考虑了没有传输的场景，其中有两种类型：定义2.4（均衡中没有转移当我们只考虑（真实的和非真实的）机制M的空间时，如果启示原理成立，则它在平衡中不存在转移，其中：对于所有θ，TM（RM（θ））= 0。[14]如果G是随机的，也会出现同样的问题--智能体被期望使用混合策略--并且多个类型在同一信号上放置这就是为什么我们只考虑代理人的纯策略的原因之一。第六章：A. Kephart和V.科尼策ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月请注意，这允许负（或正，但这些都没有用）转移到代理不发出的信号。定义2.5（完全没有转移）。如果当我们只考虑机制M的空间时，揭示原理成立，则它完全不存在转移，其中：TM（·）=0。请注意，如果揭示原理适用于固定转移，那么当我们希望在均衡中没有转移时，它也适用。这并不自动意味着，当我们根本没有转移时，启示原理就成立了。当我们有一个我们希望代理永远不使用的信号时，两个禁止转移条件之间的差异就变得相关了。在没有转移的平衡状态下，我们可以在其上放置足够的负转移以防止使用。但是，在根本没有转移的情况下，我们唯一的办法就是给它带来一个没有吸引力的结果，这可能是不够的。但是，正如我们将要展示的，在类型报告的背景下，对于未知的估值，披露原则是相同的，对于已知的估值，披露原则本质上是相同的。当我们在信号设置中时，找到确保启示原理保持不变的有用条件是目前一个悬而未决的问题。我们将使用首字母缩略词来指代我们的各种启示原则。用来描述启示原则的可能的单词和用来代表这些单词的字母如下：固定的，可变的，Ttransfers，效用，N o T transfers（in）Eequilibrium，NoT transfersA tA ll和Known（valuations）。例如，FTFU意味着固定的转移和固定的效用，KNTEVU意味着已知的估值，均衡中没有转移，可变效用。2.2.1找到G映射。在这项工作中，我们假设G映射是外生的。如果G有一个自然的候选者，这当然是有帮助的。明显的情况是当类型空间和信号空间相等时，G对应于如实报告。有时，类型和信号空间会有所不同，但仍然有一个自然的G。例如，假设代理的私人信息是她的为了发出信号，她可以参加一些书面语言测试中的任何一个自然的G映射将是期望她参加与她的母语相对应的测试。但这可能并不总是最好的方式。例如，母语可能有一个很难掌握的脚本，因此通过代理自己的语言测试需要付出很大的期望代理使用更简单的脚本来代替相关语言的测试可能有助于实现。我们甚至可以使用不在类型空间中的语言。例如，拉丁语测试可以挑选出罗曼语的使用者，即使今天没有母语为拉丁语的人。然而，尽管有这些理论上的可能性，我们可能会怀疑启示原则是否成立：如果某件事可以实现，那么它也可以通过一种机制来实现，这种机制使代理人有动机用她的母语参加考试。我们的研究结果允许一个确定当这是情况。然而，一般来说，我们的条件并没有给出任何明确的指导，当一个G满足启示原则存在，如果是这样，如何找到它。我们把这个留给未来的研究。3运行示例：储备粮食银行我们将使用一个正在运行的食品银行的例子来说明我们框架的各种实例这个例子是类型报告，因为信号空间和类型空间重合。想象一下，一个城市有四个区：北、东、南、西，每个区都有一个食物银行，里面住着很多人一个人具有信号传递成本的机制设计的揭示原理第六章：ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月根据人口统计和健康状况，市政府已经确定了它对每个地区接受某些类型食物的人口的重视程度。例如，它可能希望在一个有许多年幼儿童的地区分发牛奶，在一个有许多单身中年人的地区分发蔬菜。请注意，城市的目标是不同的，从最大化的总和效用的人谁将利用食品银行。在这个例子中，我们假设有三种食物类型，（那些高）纤维，蛋白质和维生素。决定在每个银行储存哪些食物是简单的，除了民众-如果他们喜欢另一个地区的食物，他们可能会从一个地区旅行到另一个地区这将对应于他们这样的误报代价高昂，因为它需要前往另一个地区。这些费用汇总如下：西北东南北c（θ，θθ θ）=西东南将此报告成本结构可视化为图表也很有用。两个区域之间的有向边表示从一个区域到另一个区域的旅行成本我们放弃了零成本自我报告的优势。15未示出的所有其他边被假设为具有无限的成本。假设每个地区的人们对食物的评价如下：纤维蛋白维生素vθ（o）=西北东南此外，假设城市纤维蛋白维生素北J（θ，o）=西东南城市的问题是指定一个机制，也就是说，每个地区的食品银行分发哪些食品，这样它就对均衡结果感到满意。可能的话，市政府也可以向每个来到食品银行的人分发（福利）转移。在信令设置中，这些边缘可能不是零成本的。0288∞042∞402∞2201912331361111000010501050510第六章：A. Kephart和V.科尼策ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月我们假设任何食物银行都没有能力限制，也就是说，如果来的人太多，它也不会耗尽食物因此，这是一个机制设计问题的一个单一的代理人出现在食品银行的人，因为其他代理人这个问题有多种变体，取决于城市是否可以进行转移，是否希望这些转移达到一定的数量，是否关心人们前往不同地区所产生的交通成本，等等。如果启示原则适用于所讨论的变体，那么城市的问题就容易得多;它可以专注于真实的实现，即，这样就没有人会去另一个地区。如果它不成立，那么城市需要考虑的机制，确实激励一些地区的人口前往另一个地区的食品银行，因为这可能会导致更好的结果比任何真实的机制可以实现。我们将看到这两种情况的例子。4启示原则结果总结我们现在总结我们的主要结果，那些具有未知赋值和未知选择函数的启示原理，即，标准启示原则4.1Intuition高级概述我们首先提供一个高层次的概述我们的主要结果背后的直觉揭示原理成立，当且仅当对于由非真实机制N实现的任何选择函数F，也存在实现F的真实机制H。也就是说，对于每个θ，我们有H（θ）=F（θ）和RH（θ）=θ。为了提供直观的目的，我们在这里将自己限制在只有一种类型的信号在N中不真实的情况下。在N下，让b通过发出某个信号x<$b获得F（b）。在H下，A（b）=F（b），所以b现在可以通过真实地发射来获得F（b）这可能会导致某些类型的A现在更喜欢发射B而不是真实地发射A。我们可以将这些类型以及它们之间的相关信令成本可视化如下。[16]我们在这里使用我们的成本函数的简写，因此（例如）ax是类型a的主体发出信号x所产生的成本。这种显示成本的方式大量利用了我们将类型和这些类型发出的信号合并在一起的事实，这在类型报告的情况下是自然的，但在一般的信号情况下更微妙该图中的边对应于边开始处的类型在边结束处发射信号，并且边上的权重是这样做的成本一般来说，图中的某些信号可能没有与它们相关联的类型;这样的信号在图中不能有传出边在类型报告设置中，每个顶点都有一个成本为0的自边，但在一般信令设置中并非如此有两种方法可以使用转移来保持H中的真实性。可变转移，可变效用第一：支付代理额外的发射。这保持了一个诚实的，但可能会导致其他类型的错误发射到一个低于H。所以我们也要支付所有能发出a的类型，以此类推。16可能存在图中未显示的其他类型具有信号传递成本的机制设计的揭示原理第六章：ACM Transactions on Economics and Computation，卷。号91.第六条。出版日期：2021年3月−≤−∞∞⇒≥∧⇒–−−≥过程在没有到达b的情况下终止。如果我们必须支付b，那么额外的转移将被抵消，一切都将化为乌有。因此，对于可变的转移和可变的效用，如果在从b到a的范围（G）中不存在沿着信号的有限排放成本边的路径，则揭示原理成立。（注意，不在范围（G）内的信号没有对应的类型，因此根据定义不能有输出边。可变转移、固定和可变公用事业第二：支付较少的代理人排放b。我们可以安全地从b在N下发送x所收到的转移中减去bxbb（使b在H和N下同样快乐）。[17] 请注意，a在N下不发射x。考虑a在H下排放b的动机比在N下排放x的动机大多少它是（ax ab）（bx bb），它是非正的当且仅当ax ab+bx bb。在这种情况下，蒸馏器不会误发射。因此，对于可变的转移，如果ax ab+bx bb成立，那么启示原理对于固定的效用也成立（因此对于可变的效用也成立）。注意，在bb=0的情况下，该条件等同于信令成本结构上的三角不等式成立固定转移，可变效用如果我们有固定的转移（但可变的效用），那么前两种技术都不允许。因此，a应该不愿意直接发射b，因为它不想在N下发射x。要做到这一点，就必须要有Abax。此外，这个条件只有在b实际上可以发射x时才是必要的。18所以我们有bx ab+bx，则VTFU条件不能成立，因为ax将总是非负的。第5.2节.当VTFU条件成立时，RP在可变转移和固定效用的情况下成立。P屋顶。VTFU条件RP保持我们将证明，对于任何F，对于任何非真实现，我们都可以构造一个真实现。设N与RN一起实现F.令H=N，除了：AH（θ）=F（θ），其中θ∈ΘTH（θ）