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

在不丧失普遍性的情况下，我们假设在备选方案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

然后，玩家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δ的参数。

这是因为所有的论据都依赖于这样一个事实，即在平均数的计算中包含（排除）低于平均数的数字会降低平均数。这一基本事实也适用于加权平均数。更正式地说，平均值的类似物是加权平均值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。

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。

我们称平均固定点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。在下面的例子中，在所有均衡中，至少有一个参与者在均衡中没有采取真诚的策略。

这个例子还表明，标准批准投票机制（见[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）。

请注意，在这个动作文件中，玩家的报酬是（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）。

因此，本文的结果可以推广到偏好是有序单调的情况。参考文献[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年）。

《纳什讨价还价问题的其他解决方案》，《计量经济学》，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年）。

“重新审视非扩张博弈均衡点的完备性概念”，《国际博弈论杂志》，4（1），25-55。[30]Sj–ost–om，T.（1994）。“按需求机制实施”，经济设计，1（1），343-354。[31]田，G.（1989）。“通过单一价值、可行且持续的机制实施林达尔通信”，《经济研究评论》，56（4），613-621。[32]田，G.（1993）。“通过预扣机制实施林达尔分配”，《数理经济学杂志》，第22169-179页。[33]杨，H.P.（1993）。《公约的演变》，《计量经济学》，第57-84页。[34]邹，J.，梅尔，R.和帕克斯，D.（2015）。“涂鸦民调中的战略性投票行为，”Proc。第18届ACM计算机支持的合作工作和社会计算会议（CSCW）。无域限制的虚拟实现Sabreu和Sen[2]证明了它们在轻度域限制下的虚拟实现特性。特别是，他们认为玩家对备选方案的偏好是严格的；i、 例如，对于i=1，2代表ai≠ a\'Iforevery a\'≠ a′。在没有严格限制的情况下，正如本文中的设置，我们得到了以下负面结果。提议3。没有一个帕累托有效的社会选择函数实际上是可以实现的，即使是两种选择。证据我们设定ε<，证明了满足ε-帕累托有效均衡存在性的每一种机制都必须违背均衡结果的唯一性。非正式地说，我们的想法是考虑效用函数（（0,1），（1,1）），其中玩家2在两个备选方案之间是不同的。玩家2可能会表现得好像实用程序文件是（（0,0），（1,1）），这在一个近似有效的机制中应该会导致第二个动作的高权重。或者，玩家2可能会表现得好像实用程序是（（0,1），（1,0）），这将导致第二个动作的权重降低。