战略博弈的支付区域及其极值点

所以可以把x写成凸组合x=Pkt=1λtytof一些点y，yk公司∈ 对于所有t，λ+····+λk=1，λt>0，然后我们得到pkt=1λtc·yt=α。自每年年初至今∈ 沙子S H+，关系式c·yt≥ α对每个t都成立。接下来，对于每个t，c·yt=α，然后是yt∈ S∩因此，H也是支持S的超平面。引理3.7的直接结果是，有限战略游戏的非合作和合作支付区域具有相同的支持超平面。定理3.8。Let（N，（Ai）i∈N、 （ui）i∈N） 成为一个明确的战略游戏。然后，RN中的超平面H是Sncif的支持超平面，并且仅当它是Sco的支持超平面时。凸集的一个重要性质是，到RN的非空紧凸集K的每个支撑超平面至少包含K的一个极值点（参见Moore（1999，p.303））。因此，凸多面体Sco的每个支撑超平面都必须有Sco的一个极值点。同样，尽管一个不合作的支付区域Snc可能不是凸的，但每个支持的超平面Sncalso至少包含一个Snc的极值点，这实际上可以通过使用纯策略文件来实现。推论3.9。Let（N，（Ai）i∈N、 （ui）i∈N） 成为一个明确的战略游戏。然后，每个支持Snc的超平面都至少包含Snc的一个极值点。证据设H是Snc的支撑超平面。那么H也是Scoby定理3.8的支撑超平面，因此它包含了Scoby的一个极值点。自关系ext（Sco）起 ext（Snc）通过定理3.5成立，我们可以得出结论，超平面H必须包含Snc的一个极值点。战略博弈的收益区域及其极值点74。支付区域的极值点示例我们现在给出一些支付区域的极值点示例。

如图所示，这些例子揭示了非凸集的所有“凸角”都是极值点，因此本文对非凸集极值点的定义在直觉上是合理的。值得注意的是，支付区域的一个极端点是作为支付利润实现的，玩家可以选择混合策略，而不是选择纯策略。在本节中，我们进一步阐明了极值点、纯收益和非混合收益之间的关系。这里的纯薪酬是指通过选择纯战略产生的薪酬；不可混合的支付文件是指只能由纯战略文件生成的支付文件。示例4.1。考虑以下两人游戏。我们可以看到ext（Sco）=ext（Snc）=Spu。此游戏的非合作支付区域如图1所示。图1：。ext（Sco）=ext（Snc）=Spu。示例4.2。考虑以下两人游戏。aaaa0，2 0，1 0，0a3，0 3，2 2，2很容易看出ext（Sco）={（0，0），（3，0），（3，2），（0，2）}，ext（Snc）=ext（Sco）∪{（2，2）}，Spu=ext（Snc）∪ {（0，1）}。因此，ext（Sco）ext（Snc）Spu。此游戏的非合作支付区域如图2.8 YU-SUNG TU和WEI-TORNG Juang所示。图2。外部（Sco）外部（Snc）Spu。对于有限战略博弈（N，（Ai）i∈N、 （ui）i∈N） ，支付文件v∈ 如果RNI可以由非退化混合策略文件生成，即v∈（u（σ）σ∈易∈N（Ai）\\Yi∈NAi）。如果支付文件只能由纯战略文件生成，则称其为不可混合支付文件，而且它当然是纯支付文件。然而，纯收益不一定是不可混合的。例如，图2中的纯payoff对（0，1）是可混合的。另一方面，图1和图2中的所有极值点都是不可混合的。

然而，如以下示例所示，非合作支付区域的极端点和有限战略游戏的非混合支付不是一回事。示例4.3。考虑以下两人游戏G.aaa0，0 0，0a-1.-1 1，-1值得注意的是，Gis的支付对（0，0）是可混合的，它是G的非合作支付区域的一个极值点。此外，非可混合支付可能不是非合作支付区域的一个极值点，如下面的两人游戏G.aaa所示-1、0、0、，-1a0，0 1，0很容易检查Gis的Payoff对（0，0）是否不可混合，它不是G的非合作Payoff区域的极值点，如图3所示。Gis的非合作Payoff区域是一个顶点为（0，0）的三角形(-1.-1） ，和（1，-1） 。战略博弈的收益区域及其极值点9图3。非混合支付对（0，0）不是Snc的极值点。在凸分析中，一个称为支持超平面定理的基本结果表明，如果x是Rn的闭凸子集C的边界点，那么在x处至少存在一个到C的支持超平面（参见Boyd和Vandenberghe（2004，第51页））。通过应用备注3.3.1，我们得出，对于一个合作支付区Sco，存在一个通过Sco的任何给定下一个极端点的支撑超平面。与推论3.9不同的是，如下面的例子所示，这不一定是一个不合作的Payoff区域的情况。示例4.4。考虑以下两人游戏。aaaa4，4 0，0 0，0a0，0 8，2 0，0a0，0 0，0 2，8我们可以看到，payoff对（4，4）是Snc的一个极值点，也是Sco的一个内部点。因此，应用定理3.8，不存在通过点（4，4）的支持超平面，如图4.5所示。

应用研究非凸集的极值点不仅有助于我们描述非合作支付区域的形状，而且使我们能够有效地证明博弈论中关于帕累托有效性和社会有效性的一些结果。定义5.1。A点w∈ RnPareto支配着v点∈ Rnif w 6=v和WI≥ Vi对于i=1，n、 设S是Rn的非空子集。S的帕累托前沿定义为asP（S）={v∈ S |{w∈ S | w Pareto支配v}= }.换句话说，S的帕累托边界上的点v意味着∈ 没有其他点w∈ 因此，wi≥ vifor all i.对于一个确定的战略游戏，我们将在下面的内容中详细介绍非合作支付区帕累托边界上的支付对。在具有水平/垂直切线的付款对上。根据Maynard Smith（1982）和Vickers and Cannings（1987），进化稳定策略被定义为所有个体采用的策略，如果突变体的种群份额小于入侵屏障，则无突变策略可以在自然选择的影响下入侵。间接进化10杜宇松和魏东娟图4。Sncis的极值点（4，4）是Sco的内部点。该方法是进化博弈论的一个分支，在进化博弈论中，个体的特征是偏好，而不是预先编程的策略。它受到了极大的关注，因为在这种具有可观察偏好的进化方法的基础上，效率是结果稳定的必要条件（参见g¨uth和Yaari（1992）、Samuelson（2001）和Dekel et al。

（2007年））。当我们检查一个帕累托有效策略对在间接进化的两种群模型中是否稳定时，突变策略对可能具有以下特性：一个突变对中的一个突变类型比一个种群中的现任者接收的多，而另一个突变类型比另一个种群中的现任者接收的少。即使任何这样的突变对如果其种群份额低于相应的屏障，总是会被淘汰，但是否存在一个统一的入侵屏障仍然是不明确的，尤其是当突变对和现任突变对的策略越来越接近时。这一论点促使我们注意突变的顺序，即两个群体中与现任者的两个能力差距将分别在相反的方向上缩小。事实上，相应的入侵屏障可能变得任意小的情况将意味着，一个种群中落后于现有种群的突变体所造成的追踪缺口，实际上比另一个种群中领先突变体所造成的领先缺口闭合得更快。但这与非合作支付区的形状相矛盾。因此，这种突变策略对不可能存在。为了更准确地说明这个结果，让Snc Rbe是两人有限战略博弈的非合作支付区域，而let（v*, v*) 成为Snc的付款人。假设{（vt，vt）}是snc中的一个payoff对序列，收敛于（v*, v*) 带vt-v*> 0，定义领先差距，v*-vt>0，定义每个t的牵引间隙。如果连接序列的曲线具有水平切线t（v*, v*), 然后是支付对（v*, v*) 不会位于Snc的帕累托边界，如图5所示。

直观的原因很清楚：如果（v*, v*) 如果帕累托系数与SNC相关，且满足上述条件的序列存在，则SNC将有一个严格凸的子区域包含该序列，并且它将是战略博弈的支付区域，其极值点11与备注3.5.1相矛盾。下面我们将使用第3节中讨论的非合作支付区的性质给出严格的证明。图5：。支付对（1，2）不会位于Snc的帕累托边界。尽管一场游戏中只有两名玩家，但实际的非合作支付区域往往过于复杂。这里是确定支付对是否不位于非合作支付区域的帕累托边界的另一种方法。定理5.2。让（{1，2}，A，A，u，u）是一个两人的有限战略游戏。假设{（vt，vt）}是SNC中收敛到（v）的序列*, v*) ∈ SNCandstaties vt>v*和v*> VT适用于所有t。如果条件限制→∞vt公司- v*vt公司- v*= 0保持，然后（v*, v*) /∈ P（Snc）。证据假设（v*, v*) ∈ P（Snc）。这意味着对于每个（x，x）∈ Snc，wehave v*> xif x>v*, 和v*≥ xif x=v*. 由于ext（Snc）是定理3.5的一个有限集，我们可以选择vksuch，即（5.1）{（x，x）∈ 外部（Snc）| v*< x<vk}=.根据Snc的紧性（见引理3.2），我们可以选择'vk=max{β∈ R |（vk，β）∈ Snc}，然后是vk≤ \'vk<\'v*. 考虑紧集={（x，x）∈ Snc | v*≤ x个≤ vk}，并定义线性函数f:a→ R byf（x，x）=（v*- (R)vk）x+（vk- v*)x、 在我们的假设下，f在A上达到最大值，比如m。此外，（x，x）是真的∈ f-1（m）表示v*< x<vk，从假设limt→∞vt公司-v*vt公司-v*= 0，并且从f的水平曲线是具有斜率“vk”的平行直线段这一事实来看-v*vk公司-v*.我方索赔ext（f-1（m）） 外部（Snc）。要看到这一点，请假设（\'x，\'x）∈ f-1（m）和（\'x，\'x）/∈ 外部（Snc）。

然后v*< \'x<vk，我们可以选择不同的点（y，y），（z，z）∈ A使得（\'x，\'x）∈ {θ（y，y）+（1）- θ） （z，z）|θ∈ （0，1）} A、 （\'x，\'x）的事实∈ f-1（m）表示（y，y），（z，z）∈ f-1（m），因此θ（y，y）+（1-θ） （z，z）∈ f-每θ1（m）∈ （0，1）。这意味着（\'x，\'x）/∈外部（f-1（m））。此外，由于f-1（m）为紧凑型，集合ext（f-1（m））是引理3.4的非空引理。因此我们得到了 6=外部（f-1（m）） 外部（Snc）∩ {（x，x）∈ Snc | v*< x<vk}，12 YU-SUNG TU和WEI-TORNG Juangjuang矛盾（5.1）。备注5.2.1。根据镜像对称性，应该有一个与OREM 5.2相对应的结果。也就是说，如果snc中的序列{（vt，vt）}收敛到（v*, v*) ∈ SNC满足vt<v*和v*< VT对于所有t，然后是极限点（v*, v*) 不位于Snc的帕累托边界，前提是连接序列的曲线在（v*, v*).关于理性支付区域。在某些环境中，例如在完全重复的情况下，纯支付函数的凸组合中使用的系数有时仅限于有理数。对于一个n人有限战略博弈，我们用sqcot表示所有凸组合的集合，其中包含纯支付函数的有理系数。同样，我们用SQnC表示理性混合策略可实现的所有支付的集合。然后SQCOI在Sco中密集，SQNCIS在Snc中密集。如果σ是一个合理的混合策略文件和u（σ）∈ P（Snc），那么很明显u（σ）∈ P（SQnc）。相反，如果支付函数u（σ）位于Snc中密集的QNC的帕累托前沿，我们会得到u（σ）的结果吗∈ P（Snc）？在一个两人有限的战略博弈中，答案是肯定的，并且对于合作支付区域也是成立的，如下定理所示。定理5.3。让（{1，2}，A，A，u，u）是一个两人的有限战略游戏。然后P（SQnc） P（Snc）和P（SQco） P（Sco）。证据

这两种情况的证明是相似的；我们只显示P（SQnc）P（Snc）。让v∈ SQN和v/∈ P（Snc）。然后存在w∈ Snc这样，w Paretodominates v。如果w>vand w>v，那么由于Snc中SQncis稠密，我们可以选择'x∈ SqnC使得'x>vand'x>v，这意味着v/∈ P（SQnc）。否则，在不丧失一般性的情况下，我们假设w>vand w=v。由于Sncis是一个紧集（见引理3.2），我们可以取'w=max{α∈ R |（α，v）∈ Snc}，然后我们有'w≥ w> v.如果（(R)w，v）∈ ext（Snc），那么，根据定理3.5，点（\'w，v）是纯支付对，因此（\'w，v）∈ SQnc。因此v/∈ P（SQnc）。如果（(R)w，v）/∈ ext（Snc），我们可以选择两个不同的点u，u∈ SNC如（(R)w，v）∈ {θu+（1- θ） u |θ∈ （0，1）} Snc。选择“w”的方式导致u6=vand u6=v。在不损失一般性的情况下，假设u>v。由于“w>v”，我们始终可以选择λ∈ （0，1）使得点（x，x）=λ（(R)w，v）+（1-λ） u属于Snc，条件x>vand x>vare满足。同样，由于Snc中SQncis密集，因此存在'x∈ SQnC使得'x严格帕累托支配v，即v/∈ P（SQnc）。上述定理中的关系似乎直观明了，因为对于每个支付函数，要么使用有理系数实现，要么任意接近一个有理系数。但上述结果不能推广到一般玩家游戏。这里我们提供了一个n=3的反例。反例的主要思想是由上述证明引起的。请注意，在最后一种情况下，我们总是可以在包含非极值点的线段上选择一个点，并将其包含在Payoff区域中，以便理性Payoff对严格受Pareto支配。然而，如果支付区域是由多人游戏而不是由两人游戏生成的，则可能无法执行此操作。如果σi的所有值都是有理数，则参与者i的混合策略σi是有理的。

如果混合策略的所有混合策略都是理性的，则混合策略的σ是理性的。战略博弈的收益区域及其极值点13示例5.4。考虑以下三人游戏，其中支付函数由u表示。图6显示了此游戏的非合作支付区域Sncof。aaa级√2.-1、10、0、，-1a0，0，-1.-2.√2，1aaaa√2.-1、10、0、，-1a0，0，-1.-2.√2、1该策略对玩家1具有严格的支配作用；该策略对玩家2具有严格的主导作用；玩家3的行为对其支付没有影响。让σ*是一个纳什均衡，在这个均衡中，参与者独立选择他们的策略。然后σ*= a、 σ*= a、 和σ*是第三层的可能策略之一。因此，u（σ*) = （0，0，-1） 。我们声称u（σ*) ∈ P（SQnc）。然而，u（σ*) /∈ P（Snc）和u（σ*) /∈ P（Sco），如图6所示。为了验证这一说法，我们证明了u（σ*) ∈ P（SQco）；因此，由于u（σ*) ∈ SQncandSQnc SQco，我们有u（σ*) ∈ P（SQnc）。设Д为一个相关策略，其性质为u（Д）帕累托支配u（σ*). 这意味着Д（a，a，a）+Д（a，a，a）=√2[Д（a，a，a）+Д（a，a，a）]，和Д（a1j，a2j，a）+Д（a1j，a2j，a）6=0，j=1，2。因此，u（Д）/∈ SQco，因此我们可以得出结论，u（σ*) ∈ P（SQco）。图6：。P（SQco）*P（Sco）；P（SQnc）*P（Snc）。关于社会效率。帕累托效率只能保证，没有人能够在不让其他人变得更糟的情况下变得更好。尽管个体之间存在巨大差异，但这种情况仍将是帕累托有效的。为了减少公用事业分配的不平等，决策者的目标是在帕累托边界上选择社会福利最高的点。

然而，由于不平等的概念多种多样，因此没有简单的标准来选择这些不同的社会福利职能。在这里，对于一个有限的战略游戏（N，（Ai）i∈N、 （ui）i∈N） ，我们考虑一个加权效用社会福利函数W:Snc→ 定义byW（v）=Xi∈Nαivi、14 YU-SUNG TU和WEI-TORNG Juang，这是聚合单个公用设施最广泛使用的方法之一。可以证明，尽管不合作支付区域的形状尚不清楚，但在纯战略利益下，可以实现加权效用社会福利函数的最大值。在解释这一点之前，让我们先回顾一下凸分析中极值点的重要性。极值点在解决如下所述的凸优化问题中起着至关重要的作用。RN的紧凸子集上的连续凸函数总是在子集的极值点处达到其最大值（参见Aliprantis和Border（2006，第298页））。这被称为鲍尔最大原理。应该强调的是，这个结果并不意味着所有的最大化者都是极值点。现在将社会福利函数W推广到域Sco，即Rn的一个紧凸子集。然后存在v∈ ext（Sco），使得W（v）=max{W（v）| v∈ Sco}。根据定理3.5，我们知道ext（Sco） 外部（Snc） Spu。因此，关系Spu Snc公司 S表示W（v）=最大{W（v）| v∈ Snc}=最大值{W（v）| v∈ Spu}。因此，对于非合作支付区域上定义的加权功利主义社会福利函数，无论该支付区域的形状如何，都可以通过纯战略文件获得其最大值。结论对于每个n人有限战略博弈，合作支付区域是Rn中的一个凸多面体，而非合作支付区域是该多面体的一个紧连通子体。