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

2022-5-7 15:24:10

通过批准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）。然而，这些规范机制非常复杂，不太可能在实际环境中使用。

扫码加我拉你入群

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

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

mingdashike22

2022-5-7 15:24:19

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

扫码加我拉你入群

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

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

kedemingshi

2022-5-7 15:24:23

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

扫码加我拉你入群

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

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

mingdashike22

2022-5-7 15:24:26

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

扫码加我拉你入群

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

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

2022-5-7 15:24:30

最后，在部分诚实和真诚的情况下，[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的规范机制都因其复杂性而受到批评，这使得它们的使用有些不切实际。

扫码加我拉你入群

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

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

点击查看更多内容…

mingdashike22

2022-5-7 15:24:34

文献[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）。

扫码加我拉你入群

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

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

2022-5-7 15:24:37

实用性文件的集合用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）而失败。然而，由于对手不同意这个选择，两个玩家也不会从批准中获益。为了解决这个有问题的问题，我们为每个玩家提供一个激励，让他们批准这个有效的替代方案，而不管对手是否批准。

扫码加我拉你入群

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

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

2022-5-7 15:24:41

我们考虑机制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δ开发的所有结果也将适用于实施机制为批准投票但存在通信噪声的场景。

扫码加我拉你入群

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

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

kedemingshi

2022-5-7 15:24:44

有趣的是，我们将看到，在系统中插入这样的噪声只会导致选择帕累托有效平衡。在我们陈述我们的主要积极结果之前，这是机制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。

扫码加我拉你入群

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

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

能者818

2022-5-7 15:24:47

我们用af P（A）表示所有平均固定点的集合。图1展示了平均固定点的定义。下面的引理表明，甚至包括平均不动点在内的更严格的边界概念也总是存在的，这显然保证了平均不动点的存在（即AF P（A）≠).引理1。每个集合A至少允许一个边界包括平均固定点。证据我们设置x=avg（A），对于t≥2我们设置xt=avg（A\A<，<（xt）-1)).如果A<，<（x）= 然后，xis a边界包括平均固定点。否则，我们知道x>>xbecause只有严格低于平均水平的实用程序被从setA中删除。同样，如果A<，<（x）\A<，<（x）= 然后，xis a边界包括平均固定点。否则，x>>x因为只有严格低于平均水平的实用程序被从A组中删除\A<，<（x）。最多有n种不同的结果，因此对于一些≤n+1我们将有一个<，<（xt）\A<，<（xt）-1)= X是一个包含平均固定点的边界。一个自然的问题出现了：包含平均固定点的边界是否一定是唯一的？下面的例子说明答案是否定的。设A=（（1,1），（0.8,0），（0,0.8）），则（1,1）和（0.6,0.6）均为边界，包括平均固定点。平均固定点的集合不一定是单一的。然而，下面的引理表明，平均固定点集具有以下结构：它必须是（弱）帕累托主导结果的序列。引理2。每两个平均固定点x，y∈afp（A），或x≤≤y还是y≤≤x、证据。通过矛盾的方式假设x，y满足x>yand，x<yA.≤,≤（十）\A<，<（x）应使x=平均值（（A\A.≤,≤（x） )∪Bx）。我们表示Ax=（A）\A.≤,≤（x） )∪Bx，表示BCx=（A≤,≤（十）\A<，<（x））\Bx互补下边界点（不包括在平均值中）。

扫码加我拉你入群

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

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

2022-5-7 15:24:51

同样地，我们表示Ay、By和BCy。注意thaay=（Ax∪F）\图2：集合Ax，Ay，Bx，By，F和G。其中（见图2）F={a∈A.∶Y≤A.≤x、 a≤x}\BCyandG={a∈A.∶A.≤y、 x≤A.≤y}\通过关于平均值x（特别是玩家2的平均值xof），当我们从Ax切换到Ay时，我们添加弱低于x（集合F）的点，移除弱高于x（集合G）的点。因此，y≤x、这是一个矛盾。平均固定点（引理1）的存在和平均执行点的结构（引理2）允许我们定义最小平均固定点的概念。定义3。A点mafp（A）∈[0,1]是mafp的最小平均固定点∈AF P（A），对于每个y∈AF P（A）它认为y≥≥马夫。注意，引理1和引理2证明了mafp（A）的存在性和唯一性。2.2纯纳什均衡的刻画在陈述我们的主要正结果之前，我们介绍了几个概念。对于集合a，我们用PE（a）={a来表示∈ A.∶ 没有b∈ A使得b>>A}是A的帕累托有效点集。我们的主要积极结果是机制AVδ的纯纳什均衡结果的精确表征。定理1。对于每个集合A和每个0<δ≤1，机制AVδ的纯纳什均衡结果集正是以下两种结果的结合：1。协议结果集sag（A）={（1）-δ） a+δx∶A.∈pe（A），x∈afp（A）和A≥≥x} .2。分歧结果集为（A）={x∈AF P（A）∶没有一个∈A使得A>>x}。平衡结果如图3所示。给出了一个具有单不一致均衡和两个一致均衡的集合A。图3:AVδ的平衡结果。证据见第2.5节。一个简单的推论表明，AVδ是一种匿名机制，所有的均衡结果（近似）都是有效的。推论1。

扫码加我拉你入群

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

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

2022-5-7 15:24:55

对于每个集合a，机制AVδ允许一个纯纳什均衡，而AVδ是一个匿名机制，在所有均衡中δ-帕累托有效。推论1的证明。很容易检查AVδ是否是匿名的。也很容易检查AG（A）中的所有元素∪DIS（A）是δ-帕累托有效的。剩下的部分是展示AG（A）∪DIS（A）≠. 引理1afp（A）≠. 对于一些平均固定点X∈AF P（A），如果x不是由任何效用函数支配的帕累托函数，那么x∈DIS（A）。否则，就存在a∈Pe（A）帕累托支配x，然后（1）-δ） a+δx∈AG（A）。定理1可以用社会选择对应关系和虚拟实现来表述。对于一系列实用程序a，我们将最小AFP帕累托效率响应（见定义3）定义为σ（a）={a∈P E（A）∪AF P（A））∶A.≥≥mafp（A）}。定理1的直接推论如下。推论2。这种机制实际上实现了社会选择的对应。事实上，在定理1的证明中，我们展示了一个更强大的结果，该结果刻画了纳什均衡行为集（不仅仅是结果）。对于集合a而言，博弈ΓAVδ（a）的纳什均衡集是以下两种均衡的结合：一致均衡，如果存在帕累托主导的平均执行点x，则存在一致均衡≤≤a换a∈P E（A）。平衡作用曲线如图4所示。图4：协议平衡文件。不一致均衡，如果存在帕累托效率平均点x，则存在该均衡。图5显示了均衡作用曲线。图5：不一致平衡曲线。2.3谈判正如我们所见，建议的批准投票机制是对称的，它只实现了部分有效的结果，此外，结果集是规模不变的（因为均衡结果是规模不变的）。

扫码加我拉你入群

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

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

2022-5-7 15:24:58

效率、对称性和尺度不变性是谈判理论中普遍接受的公理，见[14]。因此，在与有限的替代者谈判问题的背景下考虑建议的机制是有效的（该模型之前已经讨论过，见[1]）。谈判背景下的实施主要针对子博弈完美均衡实施进行了研究，参见[3,16,10,1,18]，这对经典谈判解决方案的实施产生了强烈的积极影响。另一方面，Nash实现在文献中受到的关注较少。一个明显的原因是，上述强有力的积极结果对于Nash的实施是不可能的，见[18]。建议的批准投票机制具有多重均衡结果，因此无法确定一个独特的点作为谈判问题的解决方案。事实上，正如我们在附录中的命题3中所示，存在一种具有独特均衡结果的命名机制，其满足近似帕累托效率的要求。尽管如此，该机制确实对讨价还价互动的可能结果做出了一些预测：没有一个参与者在最小平均固定点获得低于其效用的补偿。在这里，我们在经典的“派的划分”问题中证明了这一观察结果（参见Rubinstein[24]）。对于一般谈判集，也可以进行类似的操作。在馅饼分割问题中，有一个商品单元应该在讨价还价者之间分割。有几种方法可以用有限的备选方案来模拟这个问题：1。集合是A=（（0,1），（1,0））.2。集合是conv线（（0,1）、（1,0））的ak网格。即A=（（ck，1-ck）kc=0。还有一种建模方法，它不假设对问题的定义是有效的。3.集合是三角形conv（（1,0）、（0,1）、（0,0））的ak网格。

扫码加我拉你入群

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

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

kedemingshi

2022-5-7 15:25:01

即A={（ck，dk）∶c、 d∈N和ck+dk≤1}. （2）对于模型1和模型2，两种机制AV和AVδ的唯一结果是点（，）。这不是很有趣。实际上，（，）是建模1和建模2的每个匿名机制M的唯一结果。这源于这样一个事实：由匿名机制诱导的博弈是一个常数和为1的对称博弈，因此具有唯一的纳什均衡结果（，）。对于δ和kin模型的小值，分析AVδ机制的结果是有趣的（3）。以下命题表明，结果接近于连接点（0.39,0.61）和（0.61,0.39）的效率段。提议1。设A=A（k）为等式（2）中的集合。对于每个k和每个δ>0，机制AVδ的所有纯纳什均衡结果都是（δ+k）-接近于分段conv（（x，1）-x），（1）-x、 x），其中x≈0.39是方程x的解-x段中的x+=0∈[0,].在证明命题之前，我们给出了一个关于平均固定点的简单观察结果（给出引理2），这将有助于找到a（k）的平均固定点。引理3。设A为效用函数的对称集合，设x=（x，x）为A的平均固定点，则x=x。根据集合的对称性，（x，x）也是一个平均固定点。根据引理2，它必须是（x，x）≤≤（x，x）或相反（x，x）≤≤（x，x）。在这两种情况下，x=x。图6：分割饼图的平衡示例。命题1的证明。首先，我们将集合A=A（k）的平均固定点近似为误差k。根据引理3，A的所有平均固定点的形式为（x，x）forx∈[0,].我们考虑的是连续版本，其中我们替换了集合A\A<，<（x，x）和A\A.≤,≤（x，x）通过setB=conv（（0,0）、（0,1）、（1,0））\具有均匀密度的conv（（0,0）、（0,x）、（x,0）、（x,x））。

扫码加我拉你入群

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

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

2022-5-7 15:25:06

B的质心近似于A的平均值\A<，<（x，x）和A的平均值\A.≤,≤（x，x）误差高达kb，因为这些表达式之间的差异仅取决于靠近A的边界点≤,≤（x，x）\A<，<（x，x）是A中所有点的最大分数\A.≤,≤（x，x）。B的质心由下式给出-十、(,)-x（x，x）（3）其中（，）是conv的质心（（0，0），（0，1），（1，0）），（x，x）是conv的质心（（0，0），（0，x），（x，x）），x是这些集合的相应面积。通过平均定点假设，我们从公式（3）中推断：-十、-十、=十、=>十、-x+=0这个方程对x有唯一的解∈[0,]. 因此，（k）的所有平均固定点（y，y）都位于（x，x）附近。最后，通过对OREM 1中平衡结果的描述，我们得到所有平衡都是一致平衡，其中一致点是（a，1）-a）为了你≤A.≤1.-结果δ接近（a，1）-a）。参见图6。值得解释的是，为什么允许低效率的替代方案可以创造更广泛的高效谈判解决方案。无效的替代方案会增加惩罚的程度；i、例如，玩家i可以减少玩家3的报酬-我在下面（图6）。因此，新的均衡出现了，玩家i采取了一种“聪明”的惩罚策略，在这种策略中，对手的最佳选择是同意一个他得到的分数低于1的分区。图6中玩家1的这种“聪明”惩罚策略的一个例子是，该策略包括右下梯形中的22个实用程序和一个额外的实用程序（0.6,0.4）。

扫码加我拉你入群

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

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

2022-5-7 15:25:09

这种策略在上述意义上是“聪明的”，因为它平衡了玩家1的两个相反目标：一方面，惩罚玩家2，迫使玩家2同意不公平的划分；另一方面，排除对自己不利的替代方案，因为正概率δ考虑了这些不利的替代方案（即使在达成一致的情况下）。2.4帕累托前沿允许该机制返回彩票结果，而我们测量了机制相对于纯效用的效率。例如，考虑以下备选方案集合：A=（（1,0）、（0.6,0）、（0,1）、（0,0.6））。A的唯一平均固定点为（0.4,0.4），这是帕累托效率（关于toA）。因此，根据定理1（0.4，0.4）是唯一的（不一致）平衡结果。有理由认为均衡结果（0.4,0.4）不是帕累托最优的，因为该机制可以选择具有预期效用（0.5,0.5）的彩票。帕累托最优性的一个更强大的概念（在我们的环境中可能更合适）是帕累托前沿。给定集合a，如果没有替代y，则结果x=（x，x）ε-接近帕累托前沿∈conv（A）使得y>>x+（ε，ε）。我们认为，机制AVδ可以修改为一个类似的机制，其结果在所有均衡中任意接近帕累托前沿。备选方案[n]上的k-均匀分布是[n]中备选方案的多个大小k上的均匀分布。我们用k-UN（[n]）表示[n]上所有k-一致分布的集合。在修改后的机制AVkδ中，每个参与者提交一组经批准的备选方案的k-均匀分布。也就是说，每个玩家i=1，2提交一个列表Li k-UN（[n]）。机制AVkδ选择结果彩票的方式与AVδ完全相同。

扫码加我拉你入群

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

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

2022-5-7 15:25:12

唯一不同的是，这里我们有一个均匀分布在k-均匀分布上，这导致了一个分布在替代品上。提议2。AVkδ机制允许每个集合都有一个纯纳什均衡，AVkδ机制是一个匿名机制，它是δ+k-在等位平衡中接近帕累托前沿。证据集合A上的机制AVkδ与集合k-UN（A）上的机制AVδ相同，其中k-UN（A）={Ei~u（ai）∶u是[n]上的k-均匀分布。}是a上k-均匀分布下的预期结果集。通过推论1，这证明了纯纳什均衡的存在。对于帕累托边界上的每条线conv（a，b），其中a，b∈pe（A），结果{mka+k-mkb}km=1是帕累托前沿的k-均匀分布结果。图7展示了isk远离帕累托前沿的每一点都是由帕累托主导的，这是由一个这样的矩阵Mka+k构成的-mkb。因此δ-Pareto对k-UN（A）的效率意味着δ+k接近A的帕累托前沿。根据推论1，集合k-U N（A）上机制AVδ的所有平衡都是δ-帕累托有效的（相对于k-UN（A）），这意味着注意到k-均匀差异分布的数量是有限的，并且等于（N+k）-1k-1).图7：由k-均匀结果支配的帕累托点。集合A上的机制AVkδ的所有平衡都是δ+k-靠近帕雷托前线。2.5定理1的证明我们首先介绍几个额外的符号。对于一套实用程序 Awe表示为IS={i∈ [n]∶ 人工智能∈ S} 相应的备选方案集。

扫码加我拉你入群

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

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

2022-5-7 15:25:17

在相反的方向上，对于一组备选方案L，我们用AL表示A={al∈A.∶L∈五十} 对应的公用事业文件集。对于包含边界点B的固定点xA.≤,≤（十）\A<，<（x）（即平均值\A.≤,≤（x） )∪B）我们把B中的边界点分成两个集合Bi={a∈B∶ai=xi}，其中BB=B.我们首先展示每个结果x=（x，x）∈ DIS（A）是一种不一致的平衡结果。我们将公用事业分成两部分\A.≤,≤（x）分为两组：Di={a∈A.∶对于i=1，2，ai>xi}。比安和迪亚尔的场景如图8所示。固定点x属于DIS（A），因此不存在A∈ 这样A>>x。那么设置B∪ 丹B∪ 敢于脱节。因此，公司的薪酬（IB∪D、 IB∪D）是x（因为x是一个固定点）。我们认为，行动图8：分歧均衡。（IB）∪D、 IB∪D）这是一个纳什均衡。玩家1批准所有高于平均水平的备选方案（D），不批准所有低于平均水平的备选方案。因此，玩家1不能通过保持分歧来增加他的报酬。请注意，B中的所有备选方案∪对玩家1来说，这是低于平均水平的选择。因此，每一项协议都会减少第一层的支付。对称参数证明玩家2没有可证明的偏差。在我们证明AG（A）中的每一个结果都是不一致均衡结果之前，我们先介绍一个引理，这将有助于它的证明。引理4。设x为平均固定点，设A是一个（玩家2）的列表，它批准了A<，>（x）中的所有备选方案∪乐队不赞成一场比赛中所有的选择≤,≤（十）\B.ThenmaxSAavg（S）∪S） =x.证明。对于S={a∈ A.∶ A.≥ x} 我们有平均值∪ S） =x，这是因为x是一个平均固定点，每一个选择的边界点{a∈A.∶a=x}不影响AVG。

扫码加我拉你入群

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

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

2022-5-7 15:25:22

这也是平均值的最大值∪S） =x，因为每一次对上述平均值的反对或对低于平均值的备选方案的批准都会降低平均值。现在我们证明了每个结果（1-δ） a+δx∈ AG（A）是一个协议平衡体。我们用R=A表示≤,≤（a）∩ A.≥,≥（x）实用程序显示在由两点a和x构成的矩形中。我们还表示C=a>，≤（x，a）\ R、 C=A≤,>（a，x）\R.设R=RRbe R中公用事业项目的任意划分。图9显示了Bi、R和C集。图9：协议均衡。我们认为行动文件（L，L）=（IB∪C∪R∪{a} ，IB∪C∪R∪{a} ）是一种协议平衡。首先很容易检查我∩L={a}和L∪L=I（A）\A.≤,≤（x） )∪B、因此，结果确实是o=（1）-δ） a+δx.参与者1无法改善“不一致”支付，因为所有高于平均水平的替代方案都得到其中一个参与者的批准（即，属于L∪五十），不一定是玩家1。此外，所有低于平均水平的备选方案都被玩家1（即不是L）否决。现在我们证明了“协议”支付不能通过参与者1的单边偏离而得到改善。玩家1可以破坏协议（即，不同意a），通过引理4，这将使他的支付减少到xor更少。最后，玩家1不能通过切换到另一个（或添加额外的）协议选项来提高协议支付，因为对于所有b∈五十、 b≤a、对称参数证明player2没有可证明的偏差。现在我们转到证明的第二部分，在这里我们证明了所构造的上述均衡都是博弈的纯纳什均衡。我们首先证明，在每个协议均衡中，协议结果是唯一的：引理5。设（L，L）为纯纳什均衡，使得∩L≠ , 然后是everyi，j∈L∩五十、 ai=aj。证据假设我∩L≠ 交叉口包含具有不同特性的备选方案。

扫码加我拉你入群

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

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

2022-5-7 15:25:25

在不丧失普遍性的情况下，我们假设在备选方案L中，并非所有参与者1的结果都是相同的∩五十、而我∈ L∩Lob获得玩家1的最小效用。玩家1将通过反对备选方案i（即L′=L）获得收益\{i} ）因为A vg（AL′）∪五十） =平均值（AL）∪五十）（因为工会保持不变）和avg（AL′）∩五十） >平均值（AL）∩五十）。现在我们声称，对于每一个平衡点，认可集的并集形成一个平均固定点。引理6。设（L，L）为纯纳什均衡，设x=avg（AL）∪五十），那么x是一个平均固定点；i、 e.，A\A.≤,≤（十）艾尔∪LA.\A<，<（x）。证据如果存在一个替代l，那么 L∪Land ali>Sithen玩家i与Li之间存在可预测的偏差∪{l} 。因此\A.≤,≤（十）艾尔∪L.如果存在替代方案L∈L∪那么我们考虑两种情况。案例1:l∈利布特lL3-i、然后，球员i与李娜有一个可预测的偏差\{l} 。案例2:l∈ L∩然后通过引理5得到唯一的一致结果。玩家1通过从其批准集中排除备选方案l（以及所有备选方案k，使得ak=al）而对分歧产生了有利的偏差。因此艾尔∪LA.\A<，<（x）。下面的引理表明，一致性结果（如果存在）比分歧性结果更好，并且是有效的：引理7。设（L，L）为纯纳什均衡，使得∩L≠ 让我们∈艾尔∩五十、然后1。A.≥≥平均值（AL）∪五十） .2。A.∈P E（A）。证据1.相反，假设a<avg（AL∪五十）。引理5a是唯一一致的结果。玩家1通过将替代Ia（以及玩家2所扮演的所有相同替代IB）排除在其集合之外，从而对分歧产生了有利的偏差。类似的论证排除了A<avg（AL）的可能性∪五十） .2。假设a′>>a的存在。通过（1）我们知道a′>>a≥≥平均值（AL）∪五十）。通过引理6，我们得到a′∈ 艾尔∪L.在不丧失一般性的情况下，我们假设∈L

扫码加我拉你入群

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

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

2022-5-7 15:25:28

然后，玩家1可以通过在协议集中加入“a”来增加他的支付。下面的引理表明分歧平衡必须是有效的：引理8。设（L，L）为纯纳什均衡，使得∩L=, 还有诺亚∈A的平均值为∪五十）。证据相反，假设存在一个>>平均值（AL∪五十）。通过引理6，我们得到A∈ 艾尔∪L.在不丧失一般性的情况下，我们假设∈ L.然后，玩家1可以通过在自己的集合中加入a，并将分歧转化为a上的一致意见来增加他的支付效果。总结而言，每个分歧均衡结果都是一个平均固定点（引理6），并且不受任何效用函数（引理8）的支配，该效用函数将结果集合限制为DIS（a）。在每个协议均衡中，协议都基于一个唯一的结果（引理5），即帕累托效率（引理7）。此外，设置L∪L形成平均固定点（引理6）和平均值（L∪五十）帕累托由协议结果主导（引理7）。这限制了AG（A）中的结果集。3加权批准投票机制批准投票机制从交叉点或联盟中统一随机选择一个替代方案。为了证明结果，有必要假设机构选择备选方案（从交叉点或从并集）的分布为每个备选方案分配正概率。例如，我们可以考虑一种机制，其中每个备选方案i的权重wi>0。如果集合不相交（L∩L=), 该机制选择了备选方案j∈L∪LWITHWJ∑我∈L∪Lwi。如果集合相交（L∩L≠ ), 该机制选择了备选方案j∈ L∪具有概率δwj的lw∑我∈L∪Lwi，它选择了另一个∈L∩l概率（1）-δ） wj∑我∈L∩Lwi。我们用AVwδ表示这种机制，其中w=（w，…，wn）。我们认为，所有支持AVδ的参数都可以转化为avwδ的参数。

扫码加我拉你入群

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

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

2022-5-7 15:25:32

这是因为所有的论据都依赖于这样一个事实，即在平均数的计算中包含（排除）低于平均数的数字会降低平均数。这一基本事实也适用于加权平均数。更正式地说，平均值的类似物是加权平均值AVGW（B）=∑人工智能∈Bwi人工智能∈B与平均固定点类似的是加权平均固定点的概念。定义4。给定集合A和权重w，如果存在子集B，向量x=（x，x）是集合A的加权平均固定点 A.≤,≤（十）\ A<，<（x）使AVGW（（A\ A.≤,≤（x） )∪ B） =x。我们用AF Pw（A）表示加权平均分数集。同样，我们可以定义最小加权平均固定点的概念。定义5。A点（A）∈[0,1]是最小加权平均固定点，如果∈AF Pw（A），并且对于每个y∈AF Pw（A）保持y≥≥中全景。使用与第2.1节中类似的参数，我们可以证明最小平均执行点存在且唯一。我们对加权批准投票机制的均衡结果进行了类似的描述。定理2。对于每个集合A，每0<δ≤ 1和每个权重向量w，机制的纯纳什均衡结果集AVwδ正是以下两种均衡结果的并集：1。协议均衡结果集sag（A）={（1）-δ） a+δx∶A.∈pe（A），x∈AF Pw（A）和A≥≥x} .2。不一致均衡结果集为（A）={x∈AF Pw（A）∶没有一个∈ A使得A>>x}。该证明使用的参数与定理1的证明完全相同，其中平均值的概念被加权平均值的概念取代。同样，我们可以将加权最小AFP帕累托有效对应关系定义为σw（A）={A∈P E（A）∪AF Pw（A））∶A.≥≥中波法新社（A）}。与推论2类似的加权批准投票机制说明如下。推论3。

扫码加我拉你入群

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

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

能者818

2022-5-7 15:25:36

AVwδ机制实际上实现了社会选择对应关系σw。这一推论在实现文献中有相似之处。我们将wto标准化为一个概率向量。我们定义了社会选择对应关系τw（A）={x∈体育（会议（A））∶十、≥≥avgw（A）}。注意，σwandτ与之类似。在这两种情况下，对应选择了帕累托支配某个阈值的所有帕累托有效点。对于σw，阈值点是最小加权平均固定点，对于τw，阈值点只是加权平均值。Dutta和Sen[7]已经证明（在温和的域限制下）τwc可以使用他们的规范机制实现。我们证明，类似SCC的离散模拟可以使用加权批准投票机制实现，该模拟选择最小平均固定点而不是加权平均值作为阈值点。我们还强调，加权平均固定点总是帕累托主导加权平均，因此我们的机制实现了Dutta和Sen[7]机制实现的结果的一个子集。1其他解决方案概念4。1.1严格纳什均衡分析当前批准投票机制的混合纳什均衡集仍然是一个有趣的开放问题。鉴于这个问题仍然悬而未决，很自然地会问，该机制的纯纳什均衡是否比混合的解决方案“更自然”。在温和的泛型假设下，我们认为纯纳什均衡更自然，因为它们是严格的；i、例如，每个玩家都会因偏离平衡而输掉比赛。更具体地说，泛型假设是：1。玩家的效用偏好是严格的；i、 e，哎≠如果≠a′.2。

扫码加我拉你入群

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

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

2022-5-7 15:25:39

我们称平均固定点x为平凡的，如果A.\ A<，<（x） = 1，即单个备选方案的平均isdone（该备选方案必须以帕累托统领所有其他备选方案）。第二种泛型假设要求玩家在一个非平凡的平均固定点和他的一个备选点之间永远不存在差异。很容易看出，在这些假设下，机制的纯纳什均衡avδ（见第2.2节）是严格的。4.1.2主导策略的顺序消除产生的自然方向是分析批准投票机制w.r.t.主导策略的顺序消除（而非纳什均衡）。不幸的是，我们对均衡策略的描述（见第2.2节）表明，在某些情况下，许多策略在顺序消除过程中仍然存在（因此顺序消除的预测能力较低）。这仅仅源于这样一个事实，即（单个玩家的）每一种严格的平衡策略都能在任何连续的淘汰中幸存下来。对于（单个参与者的）严格均衡策略集比较大的例子，可以构建一个“多”备选方案的案例，其中帕累托主导一个平均固定点X，帕累托主导一个有效备选方案a（即集合B）∶={b∈A.∶x<b<a}较大），见图4。在这种情况下，通过添加B（即集合{B）中相应的策略列表，B的每个备选方案子集都可以“完成”到参与者1的严格均衡策略∈ A.∶ b> X和b<a}\B）。因此，每一个这样的“完成的”策略都能在被主导的策略被淘汰后幸存下来。请注意，这些完整的策略不一定是真诚的策略，而是形式{b]的策略∈A.∶b> c}对于某些常数c。在下面的例子中，在所有均衡中，至少有一个参与者在均衡中没有采取真诚的策略。

扫码加我拉你入群

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

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

2022-5-7 15:25:43

这个例子还表明，标准批准投票机制（见[22]）所保证的纯纳什均衡的存在，在我们修改的批准投票中并不保证。例3。有六个选项的效用A=（（9,0）、（0,9）、（8,8）、（7,7）、（6,0）、（0,6））。A的唯一平均固定点为（5,5）。根据我们对纯纳什均衡的描述，该博弈恰好允许两个纯纳什均衡：（{1,3,4,5}，{2,3,6}）和（{1,3,5}，{2,3,4,6}）。请注意，{2,3,6}不是参与者2的真诚策略（因为它包含备选方案（0,6）而不是（7,7）），{1,3,5}不是参与者1.4.2的真诚策略两个以上的参与者很自然地会问，在两个以上参与者的情况下，批准投票机制的类似修改是否成功地仅选择帕累托有效的结果。如果有两个以上的参与者，则不清楚如何确定获得少于最大批准的替代方案的权重。在这里，我们建议对两人机制进行自然扩展，但为这种扩展提供一个三人反例。samecounter示例也适用于其他扩展。给定一个行动计划，k为最大批准数（在所有备选方案中）。概率δm∑ki=1δk该机构在至少获得k批准的备选方案中随机均匀选择- m玩家（请注意，实际上，k玩家批准的替代者被选择的概率最高∑ki=1δk）。反例包括八个可选变量a=（（24,0,0），（0,24,0），（0,0,24），（7,7,0），（7,0,7），（0,7,7），（5,5），（6,6,6））。考虑一下动作文件（{1,4,5,7}，{2,4,6,7}，{3,5,6,7}），其中每个玩家都以非零支付批准所有备选方案，但备选方案除外（6,6,6）。

扫码加我拉你入群

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

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

能者818

2022-5-7 15:25:48

请注意，在这个动作文件中，玩家的报酬是（5±O（δ），5±O（δ），5±O（δ）），这是由备选方案（6，6，6）决定的。我们在这里介绍了一种直觉，即所提出的行动计划是一个纯粹的纳什均衡。参与者1对至少获得1/2/3批准的备选方案的平均回报为6.14/4.75/5。通过批准备选方案（6、6、6），玩家1将减少至少获得1次批准的备选方案的平均收益，而其他平均值（至少2次和3次批准）将保持不变。通过不批准备选方案（5，5，5），玩家1将其支付减少到4.75±O（δ），因为在这种偏差之后，批准的最大数量是2。可以检查所有其他偏差（包括同时批准和不批准多个备选方案的更复杂偏差）是否会减少玩家的1支付。对称性同样适用于玩家2和3.4.3的顺序偏好。在本文中，我们假设玩家对备选方案有红衣主教冯·诺依曼-摩根斯坦偏好。事实上，定理1的证明只使用了玩家i偏好的以下属性爱彩票：1。联合国（B）∪{a} )iUN（B）用于a宫内节育器（B）；也就是说，玩家更喜欢在列表中添加一个高于平均水平的选项。2.联合国（B）\{a} )iUN（B）代表联合国（B）ia；也就是说，玩家更喜欢从列表中删除一个belowaverage选项。这两个属性适用于比冯·诺依曼-摩根斯坦偏好更一般的设置。我们可以假设，对彩票的偏好是有序的、单调的。单调性假设概率质量从较低偏好的彩票转移到严格偏好的彩票会产生严格偏好的彩票。请注意，单调性意味着属性（1）和（2）。

扫码加我拉你入群

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

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

2022-5-7 15:25:51

因此，本文的结果可以推广到偏好是有序单调的情况。参考文献[1]安巴尔奇，N.（1993）。“区域单调解的非合作基础”，《经济学季刊》，245-258。[2] Abreu，D.和Sen，A.（1991年）。“纳什均衡中的虚拟实施”，计量经济学，997-1021。[3] 宾莫尔，K.，鲁宾斯坦，A.和沃林斯基，A.（1986）。“经济建模中的纳什谈判解决方案”，《兰德经济学杂志》，176-188页。[4] 布拉姆斯，S.（2008）。《数学与民主》，普林斯顿大学出版社。[5] 布拉姆斯，S.和菲什伯恩，P.C.（2007）。支持投票，斯普林格科学和商业媒体。[6] Chakravorti，B.（1991年）。“为可行地实施沃尔拉斯绩效而减少战略空间”，社会选择与福利，8.3235-245。[7] 杜塔，B.和森，A.（1991年）。《经济学研究评论》第58.11212-128页，“两人NASH实施的必要和充分条件”。[8] Dutta，B.，Sen，A.和Vohra，R.（1994年）。“通过经济环境中的基本机制实现纳什”，经济设计1.1173-203。[9] Harsanyi，J.C.和Selten，R.（1988年）。《平衡选择的一般理论》，麻省理工学院出版社。[10] 霍华德·J·V.（1992）。“完美均衡中的社会选择规则及其实施”，《经济理论杂志》，56（1），142-159。[11] Hurwicz，L.（1979年）。“在纳什均衡点产生沃尔拉斯和林达尔分配的结果函数，”经济研究评论，217-225。[12] 赫维茨，L.和施梅德勒，D.（1978年）。“保证纳什均衡存在和帕累托最优的结果函数的构造”，《计量经济学》，1447-1474。[13] 杰恩斯，E.T.（2003）。《概率论：科学的逻辑》，剑桥大学出版社。[14] Kalai，E.和Smorodinsky，M.（1975年）。

扫码加我拉你入群

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

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

2022-5-7 15:25:55

《纳什讨价还价问题的其他解决方案》，《计量经济学》，513-518。[15] 凯恩斯，J.M.（1921）。概率论，第四章，差异原则。麦克米伦公司，4164。[16] 马斯金（1999）。《纳什均衡与福利最优》，《经济学研究评论》，66（1），23-38。[17] 麦克尔维，R.D.（1989）。“一般社会选择应对的纳什实施博弈形式”，社会选择与福利，6（2），139-156。[18] 宫川，E.（2002）。《谈判解决方案的子博弈完美实施》，《博弈与经济行为》，41（2），292-308。[19] Moore，J.和Repullo，R.（1990年）。《纳什实施：一个完整的特征》，《计量经济学》，1083-1099年。[20] 莫林，H.（1984）。“实施Kalai Smorodinsky讨价还价解决方案”，经济理论杂志，33（1），32-45。[21]迈尔森，R.B.和韦伯R.J.（1993）。“投票均衡理论”，《美国政治学评论》87（1），102-114。[22]努涅兹，M.和拉斯利尔，J.F.（2014）。“通过批准进行谈判”，Thema工作文件第2014-06号，塞尔基-庞图瓦兹大学。[23]Reichelstein，S.和Reiter，S.（1988年）。“具有最小信息空间的游戏形式”，《计量经济学》，661-692。[24]鲁宾斯坦，A.（1982）。《谈判模型中的完美均衡》，《计量经济学》，97109。[25]Saijo，T.（1988）。“马斯金定理中的战略空间缩减：纳什实施的有效条件”，计量经济学，693-700。[26]Saijo，T.，Tatamitani，Y.和Yamato，T.（1996）。《走向自然实施》，《国际经济评论》，949-980年。[27]萨缪尔森，L.（1998）。进化博弈与均衡选择，第一卷。麻省理工学院出版社。[28]塞加尔，I.R.（2010）。“很少沟通的纳什实施”，理论经济学，5（1），51-71。[29]塞尔滕，R.（1975年）。

扫码加我拉你入群

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

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