通过批准投票实现帕累托有效纳什

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Pareto Efficient Nash Implementation Via Approval Voting》
---
作者：
Yakov Babichenko, Leonard J. Schulman
---
最新提交年份：
2017
---
英文摘要：
  We study implementation of a social choice correspondence in the case of two players who have von Neumann - Morgenstern utilities over a finite set of social alternatives, and the mechanism is allowed to output lotteries. Our main positive result shows that a close variant of the popular approval voting mechanism succeeds in selecting only Pareto efficient alternatives as pure Nash equilibria outcomes. Moreover, we provide an exact characterization of pure Nash equilibria profiles and outcomes of the mechanism. The characterization demonstrates a close connection between the approval voting mechanism and the notion of average fixed point, which is a point that is equal to the average of all points that it does not Pareto dominate.
---
中文摘要：
我们研究了在有限的社会选择集上具有冯·诺依曼-摩根斯坦效用的两个玩家的社会选择对应的实现，该机制允许输出彩票。我们的主要积极结果表明，一种接近大众认可投票机制的变体成功地仅选择帕累托有效的替代方案作为纯纳什均衡结果。此外，我们还提供了纯纳什均衡曲线和机制结果的精确表征。该特征说明了批准投票机制与平均不动点概念之间的密切联系，平均不动点等于所有不受帕累托支配的点的平均值。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> Pareto_Efficient_Nash_Implementation_Via_Approval_Voting.pdf (610.41 KB)

2022-5-7 15:24:06 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：帕累托 alternatives Quantitative Alternative Internation

通过批准Yakov Babichenko实现帕累托效率的纳什*, Leonard J.Schulman+2018年7月2日摘要我们研究了两名玩家的社会选择对应的实现，他们在一组有限的社会选择上拥有冯·诺依曼-摩根斯坦效用，并且该机制被允许输出彩票。我们的主要积极结果表明，一种接近大众认可投票机制的变体成功地仅选择帕累托有效的替代方案作为纯纳什均衡结果。此外，我们还提供了纯纳什均衡的精确描述和机制的结果。这一特征表明，批准投票机制与平均固定点的概念之间存在密切联系，平均固定点等于所有不受帕累托支配的点的平均值。1简介帕累托效率是机制设计和实现理论的关键要求。是否存在实现帕累托有效结果的机制的问题一直没有得到解决*工业工程与管理系，以色列海法Technion 320003。这项研究得到了美国空军科学研究基金会#FA9550-09-1-0538、美国海军研究基金会#N00014-09-1-0751以及沃尔特·S·贝尔和杰里·韦斯奖学金的支持。+加州理工大学计算与数学科学系。加利福尼亚州帕萨迪纳91125。这项研究部分得到了NSF奖#13197451618795的支持。在文献中广泛研究。马斯金[16]和其他[7,19,2]的经典著作描述了纳什可实现的社会选择对应（SCC），并构建了鲁棒机制，即所谓的规范机制，以实现每一个纳什可实现的SCC（尤其是帕累托有效的SCC）。然而，这些规范机制非常复杂，不太可能在实际环境中使用。

本文关注的问题是，帕累托效率是否可以通过（非独裁的）简单而现实的机制来实现。我们在一个相当普遍的背景下解决这个问题：两个玩家拥有冯·诺依曼-摩根斯特恩的公用事业，而不是一套有限的社会选择。基于简单且在实践中广泛使用的批准投票机制（见[5,34]），我们引入了一种仅实现帕累托有效结果的机制。我们考虑一个标准设置，即备选方案的数量是有限的，机制的结果是彩票多于备选方案。我们正在寻找一种满足以下性质的机制：（a）纯纳什均衡总是存在的。（b） 所有纯纳什均衡结果（近似）都是帕累托有效的。（c） 该机制是匿名的：也就是说，它在参与者中是对称的（这一要求反映了该机制的“公平性”）。在批准投票机制中，每个玩家要么批准，要么不批准每个替代者。选择达到最大批准数量的替代方案。如果平局，最大化者之间的选择是随机一致的。几十年来，许多专业协会[5]一直在使用审批投票机制，最近，商业协调项目Doodle也在使用这种机制，见[34]。众所周知，批准投票机制承认帕累托有效的纯纳什均衡，但也可能承认无效。结果可以推广到顺序偏好的情况，见第4.3节。虚拟实现中解决了这个确切的设置，请参见[2]。或者，我们可以关注严格纳什均衡的子集。

本文中的所有结果都适用于严格平衡，在温和的泛型假设下，见第4.1.1节。第3节讨论了最大化者之间的非均匀选择情况。例如，电气与电子工程师协会（IEEE）、美国数学协会（MAA）和美国统计协会（ASA），仅举几例。平衡，见[5]和示例1。我们考虑对批准机制的以下修改：如果任何替代方案都得到了双方的批准，则概率为（1-δ） 该机制在获得两个批准的备选方案中统一随机选择（与原始机制相同）；而对于概率δ，该机制在至少一个参与者批准的备选方案中均匀随机地选择。注释1显示了这种机制修改的动机。请注意，该机制只需要关于每个备选方案的二进制消息，这比直接披露原则更简单，后者需要每个备选方案的确切效用。我们的主要积极结果（见第2.2节）准确描述了经过修改的批准投票机制的纯纳什均衡结果和结果。这一特征意味着修改后的批准投票机制满足上述属性（1）-（3）。有趣的是，该机制的结果与平均固定点（见第2.1节）的概念密切相关，该固定点等于所有非帕累托主导点的平均值。粗略地说，结果集是一组帕累托有效的替代方案，帕累托控制一个平均固定点，或者如果帕累托有效，则控制一个平均固定点本身。论文的结构如下。1.1节进一步讨论了有关批准投票和实施理论的相关文献。

主要结果见第2节，其中我们还讨论了结果在谈判中的应用（第2.3节）。第3节概括了更广泛类别的机制的结果，第4节以讨论结束。1.1相关文献1。1.1赞成投票赞成投票是在投票环境[5,4,21]中研究的，通常是在投票人数较多而备选方案较少的情况下。已经观察到，批准投票承认帕累托有效纳什均衡[5]，但也可能承认帕累托无效均衡[5]。据我们所知，我们的工作是合理修改批准投票，成功地只选择帕累托有效结果作为纯纳什均衡结果。我们这样做是为了两人互动；在第4.2节中，我们展示了三个或更多玩家是不可能的。与我们的研究最为密切相关的是N\'unez和Laslier[22]最近的一篇论文，通过以下结果证明了批准投票机制在两人互动中的有效性：在部分诚实的行为假设下，批准投票机制诱导的两人博弈允许一个纯纳什均衡，并且其所有纯纳什均衡都是帕累托有效的。我们的结果与[22]不同，因为我们没有对玩家施加任何行为假设，即玩家的偏好完全由他们的效用决定。此外，我们在修改后的批准投票机制中对玩家效用的下界改进了标准批准投票机制的下界。在[22]中，证明了每个玩家至少得到了平均结果。我们证明了每个玩家在最差的平均执行点上至少得到了他的效用。每个平均固定点帕累托支配着平均结果，因此这是一个强边界。

最后，在部分诚实和真诚的情况下，[22]中的主要定理表明，对于标准的批准投票机制，存在一个纯纳什均衡，双方都使用真诚的行为。有趣的是，在我们修改的批准机制中，这种说法不再成立，见第4.1.2.1.1.2节实施理论中的示例3帕累托效率社会选择对应关系（SCC）的实施是实施理论中的一个核心主题。Hurwicz和Schmeidler[12]的不可能结果表明，如果我们要求纯纳什均衡总是存在的，并且所有纯纳什均衡结果都是帕累托有效的，那么只有独裁的SCC才能实现纳什均衡。这种不可能的结果可以通过对玩家的偏好提出（温和的）领域限制（见[7]）或通过虚拟实现来避免，虚拟实现只需要大致实现社会选择对应（见[2]）。在本文中，我们坚持虚拟实现方法：我们对偏好没有限制，但该机制实现的结果是ε-接近帕累托效率，而不是完全诚实。部分诚实的假设是，如果一个玩家在两个动作a和b之间没有区别，其中a是真诚的动作（即它包含所有高于某个阈值的选项），b是不真诚的，那么玩家严格地倾向于a而不是b。帕累托效率。更一般地说，在完全信息环境下的纳什实现已经在各个方面得到了广泛的研究。Maskin[16]提出的一个方面是可以Nash实现的SCC类的特征，参见[16,7,19,2]。实现任何可实现的SCC的规范机制都因其复杂性而受到批评，这使得它们的使用有些不切实际。

文献[25,17,28]对经典机制的简化进行了研究，但经典机制仍然相当复杂。这导致了实现理论的另一个分支，该分支旨在使用简单且实际可实现的机制实现具体的SCC。在所有均衡中实现帕累托效率的这种机制（除了判决机制外）只有在具体情况下才为人所知，例如交换经济环境[11,8,30,26]，更具体地说，是在瓦尔拉斯分配[23,6]和林达尔分配[31,32]中。本文属于实施理论的这一分支，讨论了彩票结果的有限个备选方案的设置。这个确切的设置已经在著作[2,7]中的一般SCC的背景下进行了研究，但是使用了规范机制；他们表明，这种机制只能实现帕累托效率的结果。本文的贡献在于简化了实施机制。我们表明，经过修改的批准机制实际上实现了帕累托有效的SCC。此外，在第3节中，我们引入了一类加权批准投票机制，该机制实现了一类更丰富、更高效的SCC（见推论2）。我们的SCC类类似于Dutta和Sen在[7]中引入的SCC类。[7]中的SCC类被证明可以通过（相对复杂的）规范机制实现。我们的SCC类可以通过（相对简单的）加权批准投票机制实现。2批准投票机制有限的备选方案集为[n]={1,2，…，n}。玩家的i=1，2冯·诺依曼-摩根斯坦备选方案k=1，2。。。，n用aki表示。我们将实用程序标准化，以便0≤阿基≤ 1.备选方案k的效用函数用ak表示∶= （ak，ak）。

实用性文件的集合用A表示∶={ak∶1.≤K≤n} 这是[0,1]中n个点的集合。在批准投票机制（AV）中，每个参与者i=1，2提交一组批准的备选方案Li [n] 。如果集合不相交（即L∩L=) 然后我们说玩家不同意，彩票的结果是L上的均匀分布∪ L（或超过[n]ifL∪L=). 否则，当我∩L≠, 我们说玩家达成了协议，而最终的彩票是对L的统一分配∩L.形式上，我们用UN（B）表示有限集B上的均匀分布，并用F（L，L）定义结果=如果L=L，则为UN（[n]）=,联合国（L）∪五十） 如果我∩L= 我呢∪L≠,联合国（L）∩五十） 如果我∩L≠,其中，第一个条件仅用于为所有对集合充分定义f。对于两个向量x，y∈ [0，1]如果x>yandx>y，我们说x（严格地）帕累托支配y，我们表示x>>y。我们说结果x∈如果没有A，则[0,1]是ε-帕累托效率（关于A）∈ A使得A>>x+（ε，ε）。对于ε=0，我们说x是帕累托系数。批准投票机制可能包含无效平衡，如以下示例所示。例1。在4个备选方案的情况下，让效用函数集合beA=（（1,0），（0,1），（0.9,0.9），（，）。很容易检查，纯行动文件（L，L）=（{1，4}，{2，4}）是一个纯纳什均衡，其结果（，）是无效的。通过更详细地考虑上述示例，我们可以看到，两个参与者都不会因为批准了有效的替代方案（0.9,0.9）而失败。然而，由于对手不同意这个选择，两个玩家也不会从批准中获益。为了解决这个有问题的问题，我们为每个玩家提供一个激励，让他们批准这个有效的替代方案，而不管对手是否批准。

我们考虑机制AVδ，它与AV机制相同，只是在一个方面不同。就协议而言（L）∩L≠) 彩票的结果是统一分配的∩l概率为1-δ（概率不是1），均匀分布∪l概率δ。形式上，f（L，L）=如果L=L，则为UN（[n]）=,联合国（L）∪五十） 如果我∩L= 我呢∪L≠,(1 -δ） 联合国（L）∩五十） +δUN（L）∪五十） 如果我∩L≠,备注1。这种概率δ的“错误”可能有几种解释（一个显而易见的解释。）机械设计人员为了诱导更好的行为而故意犯下的“错误”（另一种解释。）该机制执行标准的批准投票机制，但在参与者和该机制之间的通信中存在噪音。当玩家i发送一个01关于他是否不同意/批准第j个备选方案的信息，概率很小ε该信息在通信过程中出现。如果我们假设噪声在备选方案和参与者之间是独立的，那么得到的彩票与AVδ的彩票相似（当δ=Θ（ε））。唯一的区别是，在后一种情况下，概率很小（O（ε）阶），彩票结果将是[n]上的均匀分布。这种差异显然不会影响战略推理。因此，将为机制AVδ开发的所有结果也将适用于实施机制为批准投票但存在通信噪声的场景。

有趣的是，我们将看到，在系统中插入这样的噪声只会导致选择帕累托有效平衡。在我们陈述我们的主要积极结果之前，这是机制AVδ的pureNash平衡结果的精确表征，我们引入了一个固定点概念，它（我们将在结果中看到）与机制AVδ密切相关。众所周知，向系统中插入噪声可能会对选择理想平衡产生影响。经典结果在不同的环境中建立了这样的平衡选择[29,9,33,27]。2.1平均固定点我们从几个符号开始。对于向量B的有限集合 [0,1]我们表示平均值（B）=∣B∣∑B∈Bb，其中平均值（B）∈[0, 1].用于收集实用程序文件A和A点x∈[0，1]我们用A<，<（x）={A表示∈A.∶ a<x，a<x}从x开始的轴的第三象限中的一组实用程序。其他象限也使用了类似的符号（例如，A<，>（x）是第二象限）。类似地，我们表示A≤,≤（x） ={a∈A.∶A.≤x、 a≤x} 包括轴的第三象限。定义1。向量x=（x，x）是一个包含集合A的平均固定点的边界，如果平均值（A\A<，<（x））=x。我们称之为包含的平均定点边界，因为公用设施位于较低的边界A上≤,≤（十）\A<，<（x）包含在平均值的计算中。平均固定点的限制性较小，允许下边界上的部分点属于平均集，而部分不属于平均集。图1：平均固定点。定义2。如果存在子集B，则向量x=（x，x）是集合A的平均固定点 A.≤,≤（十）\A<，<（x）使得平均\A.≤,≤（x） )∪B） =x。