数学博弈论

事实上，如果第一个玩家选择了一个选项*m={*0, *1.*（m）- 1） }，那么第二个p层可以选择j* 从G（必须存在，因为m被定义为最小排除数），并继续获胜*j+*j作为第二名选手。如果第一个玩家从G中选择一个选项，比如*a、 我们正在鉴别两个病例。如果a>m，则第二个玩家减少*a到*我赢了。如果a<m，那么第二个玩家可以减少*我要*a和胜利。（请注意，根据mex的定义，a=m是不可忽略的。）34 2. 组合游戏Theorem 2.4（SPRAGUE-GRUNDY）。每个公平的组合对策G={A，B，C，…|A，B，C，…，T}等价于一个唯一的nim型对策*m、 数m被称为格伦迪数G（G），可以递归计算：（12）m=G（G）=mex{G（A），G（B），G（C），…，G（T）}。证据我们通过对| G |和注G的归纳来证明这个定理≡ O如果| G |=0。通过归纳，我们现在证明了这个定理对于G的所有选项，即A是正确的≡ *a、 B≡ *b等。a=G（a），b=G（b）等。因此我们可以讨论G≡ *m=*G（G）与引理2.1的证明完全相同。G不能等同于另一个nim gam e*k自（如下文第2.11条所示）：*K≡ *m==> k=m。例2.11。显示所有自然数k和n：*K≡ *M<==> k=m.EX.2.12（青蛙的格兰迪数）。设F（n，k）为x的青蛙游戏。2.4和G（n，k）是它的格兰迪数。对于k=3，F（n，k）具有选项sF（n- 1,3），F（n）-2,3），F（n）- 3, 3).所以相关的格伦迪数G（n，3）具有递归G（n，3）=mex{G（n- 1,3），G（n）- 2,3），G（n）- 3)}.显然，G（0，3）=0，G（1，3）=1和G（2，3）=2。然后，递归产生后续的格兰迪数：N012345678910··G（n，3）01230123012··第二名玩家赢得nim游戏*m当且仅当m=0。因此，第一个玩家可以在GRUNDY numberG（G）6=0的情况下赢得公平的游戏G。

总的来说，我们注意到：o不偏不倚比赛的获胜策略：采取行动G7→ G′到选项G′的格伦迪数G（G′）=0.6。我喜欢玩356.1部分游戏。格兰迪数之和。如果G和H是公平的对策，且它们的m=G（G）和n=G（H），则它们的GRUNDY数为G（G+H）=G(*n+*m） 的确，如果G≡ *m和H≡ *n、 然后G+H≡ *m+*n必须保持。为了研究求和，我们可以把自己局限于nim博弈。此外，基本性质G（G+G）=G(*n+*n） =G（O）=0建议在二元代数的背景下研究和。二元代数。回想一下，每个自然数n都有一个唯一的二进制表示，即2，n的幂=∞Xj=0αjj，二元系数αj∈ {0, 1}. 我们根据规则0定义0和1的二元加法⊕ 0 = 0 = 1 ⊕ 1和0⊕ 1 = 1 = 1 ⊕ 0并将其扩展到自然数：∞Xj=0αjj⊕∞Xj=0βjj=∞Xj=0（αj）⊕ βj）2j。备注2.5。注意，αj=0必须适用于所有j>logn ifn=∞Xj=0αjj和αj∈ {0, 1}.例2.13。自然数m，n，k:n的二进制加法⊕ m=m⊕ nn⊕ （m）⊕ k） =（n）⊕ m）⊕ 千牛⊕ M⊕ k=0<==> N⊕ m=k.回想定理2.2！36 2. 组合博弈和定理。我们认为NIM游戏有三堆N，M和K对象，即3个单一NIM游戏的总和。*N*m、 及*k、 引理2.2。对于所有自然数n，m，k，一有：（1）如果n⊕M⊕k6=0，则第一个玩家获胜*n+*m+*k、 （2）如果n⊕M⊕k=0，则第二名玩家获胜*n+*m+*k、 证据。我们在n+m+k上用归纳法证明了引理，并注意到（1）和（2）在n+m+k=0的情况下显然是正确的。

通过归纳，我们现在假设引理对所有自然的麻木词n′，m′，k′是真的，这样n′+m′+k′<n+m+k。我们现在必须证明引理对n，m，k具有二进制表示sn=∞Xj=0αjj，m=∞Xj=0βjj，k=∞Xj=0γjj。在（1）与n的情况下⊕ M⊕ k6=0，必须至少有一个j使得αj⊕βj⊕ γj=1。设J为此类指数J的最大值。其中两个系数αJ、βJ、γJ必须相等，第三个系数的值必须为1。假设αJ=βJandγJ=1，这意味着⊕ m<k和n+m+（n⊕ m） <n+m+k.设k′=n⊕m、 我们声称，第一个玩家可以通过减少*克托*k′。事实上，归纳假说认为引理对n，m，k′是正确的。辛森⊕ M⊕ k′=n⊕ M⊕N⊕ m=0，属性（2）gu Arantes是减少nim游戏中第二个玩家的获胜策略*n+*m+*k′。但后者最初是第一个玩家！因此，我们发现陈述（1）是正确的。在案例（2）中，当n⊕M⊕k=0时，第一名玩家必须在三堆中的一堆上移动。让我们这么说吧*n减少到*n′。因为n=m⊕k、 我们没有6=m⊕k，因此n′⊕M⊕k6=0。因为引理被假定为n′，m，k的真引理，所以陈述（1）保证了简化博弈中第一个玩家的获胜策略*n′+*M*k、 六,。我是第37个玩家，最初是第二个玩家。定理2.5（公平博弈之和）。对于任意部分组合对策G和H，一个hasG（G+H）=G（G）⊕ G（H）。证据设n=G（G），m=G（H），k=n⊕m、 然后n⊕m+k=0。所以引理2.2说第二个玩家赢了n*+ *M*（n）⊕m） ，哪个yieldsG+H≡ *n+*M≡ *（n）⊕ m） 。因此，n⊕ m必须是G+H的格兰迪数。我们将使用ni m gameG=*1 + *3.* + * 5 + *7个桩，分别带有1个、3个、5个和7个物体。

桩尺寸的二进制表示为1=1·23=1·2+1·25=1·2+0·2+1·27=1·2+1·2+1·2。所以G的格兰迪数是G(*1 + *3.* + * 5 + *7) = 1 ⊕ 3.⊕ 5.⊕ 7 = 0.因此，在正常比赛中，第二名球员可以赢得G。例2。1 4. 支持第一个玩家从7英寸G=*1 + *3.*+ *5 + *7.第二个玩家应该如何回应？例2.15。有一堆10块红色的鹅卵石，还有一堆10块黑色的鹅卵石。两层交替移动，选项如下：o任意一层：取至少1块但不超过3块红色卵石或：取至少1块但不超过2块黑色卵石。哪些球员在正常比赛中有获胜策略？（提示：分别计算红堆和黑堆的格伦迪数（如例2.4所示），并应用定理2.5。）第三章零和博弈零和博弈是对组合博弈模型的抽象。它们是从数学优化问题中自然产生的拉格朗日对策，为博弈论和数学优化理论之间提供了重要的联系。特别是，博弈中的战略均衡对应于优化问题的最优解。相反，数学优化技术是分析博弈论情况的重要工具。与前一章一样，我们考虑了2个代理（或玩家）的游戏行为。然而，玩家不必从s cratch计算出明确的策略，而是假设他们已经拥有了可能的策略集X和Y（或决定，或行动等）。一个玩家现在选择了一个策略x∈ X和另一个玩家a策略y∈ Y因此，可以将Γ视为在sy杆=X×y={（X，y）|X上演奏∈ 十、 y∈ Y}∪{σ} 在所有可能的球员联合战略选择中，让她有一个初始状态σ。

Γ是一个零和博弈，如果有函数u:X×Y→ R将战略选择的效用（x，y）编码为单个参与者的效用值加起来等于零：（1）u（x，y）=u（x，y）是x参与者的收益；（2） u（x，y）=-U（x，y）是y玩家的增益。所以这两名球员有相反的目标：（X）X球员想要选择X∈ X为最大化U（X，y）。（Y） Y玩家想要选择Y∈ 使U（x，Y）最小化。我们用Γ=Γ（X，Y，U）来表示相应的零和博弈。零和GA-MESEX。3.1. 一个组合博弈，其策略集分别为X和Y，原则上是一个具有效用函数U（X，Y）的零和博弈=+1如果x是x玩家的制胜策略-1如果y是x-player0的制胜策略，则为0。1.矩阵对策在有限策略集的情况下，比如X={1，…，m}和Y={1，…，n}，函数U:X×Y→ R可以用矩阵形式给出：U=嗯。u1nuu。u2n。。。。。。。。。嗯。巫统∈ Rm×n.Γ=（X，Y，U）是一种游戏，其中X-玩家选择一行i，他们选择一列j。这种联合选择（i，j）h作为行玩家的可用性值uijh和(-uij）为专栏播放机。作为例子，考虑效用矩阵（13）U=+1.-2.-1 +2.没有明显的总体“最佳”策略选择。无论玩家选择的是哪一个i栏或j栏，其中一个玩家都会发现另一个选择会更有利。从这个意义上说，这个游戏没有“解决方案”。在进一步探讨这一点之前，我们将介绍一个关于两层之间平衡项的零和解的一般概念。2.均衡让我们假设零和博弈Γ=（X，Y，U）中的两个参与者都在规避风险，并希望在最坏的情况下以最佳方式确保自己。

因此，考虑最坏情况函数离子（14）u（x）＝min。∈余（x，y）∈ R∪ {-∞}U（y）=maxx∈徐（x，y）∈ R∪ {+∞}.因此，x-player在事后看来面临着首要问题！2.平衡41（15）maxx∈XU（x）=maxx∈Xminy∈YU（x，y），而y-player必须解决miny（16）的双重问题∈YU（y）=miny∈Ymaxx∈XU（x，y）。根据定义，可以立即推断出任何x∈ X安迪∈ 原始对偶不等式：（17）U（x）≤ U（x，y）≤ 我们在（x）处说th*, Y*) ∈ 如果满足等式U（X），则X×Y是博弈Γ的平衡点*) = U（y）*), i、 例如，如果一元对偶不等式实际上是一个等式：（18）maxx∈Xminy∈YU（x，y）=U（x*, Y*) = 米尼∈Ymaxx∈《平衡》中的徐（x，y）*, Y*), 没有一个规避风险的参与者有动机偏离所选择的策略。从这个意义上说，均衡代表了参与者的最优策略。例3.2。在矩阵U为（13）的矩阵博弈中，确定两个参与者的最佳最坏情况策略，并确保博弈不平衡。给fu rthermore举一个至少有一个平衡点的ma trix博弈的例子。如果策略集X和Y是有限的，因此Γ=（X，Y，U）是一个矩阵博弈，那么均衡是否存在的问题原则上可以通过一个简单的过程在有限时间内解决：o检查每个策略对（X*, Y*) ∈ X×Y表示属性（18）。如果X和Y是有限的，通常只有当函数U:X×Y时才能确定平衡的存在→ R具有特殊的性质。从理论角度来看，凸性的概念是非常有用和重要的。42 3. 零和GA MES3。凸零和对策称为点x，…，的凸组合，xk∈ Rn是系数为λi的线性组合x=kXi=1λixi≥ 0这样的t hatkXi=1λi=1。x的一个重要解释是基于系数向量λ=（λ。

，λk）是一个概率分布：o如果从集合{x，…，xk}中以概率λi选择一个点xi，那么凸组合x的成分实际上是s到所选点的期望成分值。另一种观察X的方法是：如果在Li席席席上放置大小为L的权重，则X是重心。一组X 如果X包含所有可能的有限子集{X，…，xk}的所有凸组合，则Rn是凸的 X.EX.3.3。设S={S，…，sm}一个带m的ar比特集≥ 1.要素。证明了S上的所有概率分布λ的集合构成了Rm的一个比较凸子集。函数f:X→ R是凸的（或凸的u p），如果X是某个坐标空间R的凸子，并且对于每个X，xk∈ 概率分布λ=（λ，…，λk），一个hasf（λX+…+λkxk）≤ λf（x）+…+λkf（xk）。如果g=-f是凸的（向上）。用这个术语，我们说如果（1）X和Y是非空凸策略集，零和对策Γ=（X，Y，U）是凸的；（2） 利用率U:X×Y→ R是这样的（a）对于每个y∈ Y，地图X7→ U（x，y）是凹的。（b） 每x∈ 十、 地图y 7→ U（x，y）是凸的。更多详情参见附录第2节3。凸零和对策43一般凸零和对策的主要定理保证在紧策略集的情况下至少存在一个平衡点：定理3.1。一个凸零和对策Γ=（X，Y，U）具有紧策略集X和Y，且连续效用U允许策略均衡（X*, Y*) ∈ X×Y。证据由于x和y是凸的和紧的，所以z＝x×y，因此也是z×z。考虑g:z×z上的连续函数。→ 其中g（（x′，y′，（x，y））=U（x，y′）- U（x′，y）。因为U在第一个变量x和(-U） 凹在s经济变量y中，我们发现G在第二个变量（x，y）中是凹的。

因此，我们从附录中的推论A.1中得出一个元素（x）的存在性*, Y*) ∈ Z满足所有人（x，y）∈ Z不等式0=G（（x）*, Y*), （十）*, Y*)) ≥ G（（x）*, Y*), （x，y））=U（x，y*) - U（x）*, y） 和henceU（x，y*) ≤ U（x）*, y） 为了所有的x∈ X和所有y∈ Y这个是x*如果y玩家选择y，x玩家的最佳策略是什么*∈ Y同样地，y*对x是最优的*. 换句话说，（x*, Y*)是（X，Y，U）的平衡。定理3.1不仅在博弈论中，而且在一般的数学优化理论中都有重要的影响，我们将在下面的第4节中更详细地描述。为了说明这种情况，让我们首先看看rando在有限零和博弈中使战略决策最优化的特例。3.1. 简化了矩阵游戏。具有有限集X={1，…，m}的零和博弈eΓ=（X，Y，U）的效用U可以描述为amatrix U=[uij]∈ Rm×N，系数uij。这样的矩阵游戏并不一定承认公平。假设玩家随机选择各自的策略。也就是说，x-玩家决定x上的概率分布x，并选择一个i∈ X和概率XI。类似地，y-player在y上选择概率分布，并选择j∈ Y和p概率yj。然后x-player的预期增益isU（x，y）=mXi=1nXj=1ijxiyj。44 3. 零和GA MESSo我们得到一个零和博弈Γ=（X，Y，U），其中X是X上的概率分布集，X是概率分布集onY。X和Y是紧凸集（参见E X.3.3）。函数U在这两个分量中都是线性的，既凹又凸。因此，Γ是满足定理3假设的凸博弈。1因此允许一种平衡。这证明了冯·诺依曼的定理：定理3.2（冯·诺依曼）。让你∈ Rm×nbe系数为uij的任意矩阵。

然后就有了x*∈ X和y*∈ 如此之大∈Xminy∈yxijijxiyi=Xijuijx*艾伊*i=米尼∈Ymaxx∈第二十一条戒酒西医。其中X是{1，…，m}上所有概率分布的集合，{1，…，n}上所有概率d分布的集合。3.2. 协同计算方面。虽然在零和博弈中计算平衡通常不容易，但对于随机矩阵博弈来说，这项任务变得容易处理。例如，考虑两组x= { 1，…，M}安迪＝{ 1，…，n}和效用矩阵Re=嗯。u1nuu。u2n。。。。。。。。。嗯。巫统∈ Rm×n概率分布x∈X和y∈ Y，X-player i sU（X，Y）=mXi=1nXj=1ijxiyj=nXj=1yj的预期效用mXi=1uijxi.因此，对于x-player来说，最坏的情况发生在y-player选择一个概率分布时，该概率分布将全权重1置于k上∈ Y使得mXi=1uikxi=min（mXi=1uikxi | j=1，…，n）=U（x）。因此（19）maxx∈XU（x）=maxz∈R、 x∈X{z|z≤mXi=1对于所有i=1，m} 。J.冯·诺依曼（1928）：祖尔·德格塞尔沙夫斯皮尔，马萨诸塞州。安娜兰1004。拉格朗日对策45类似地，当x-玩家将全概率权重设为1时，y-玩家的最坏情况也会出现l ∈ X使得nxj=1uljyj=max（nXj=1uijj | i=1，…，m）=U（y）。这会产生肉末∈YU（y）=minw∈R、 y∈Y{w|w≥nXj=1uijjj对于所有j=1，n} 。该分析显示：位置3.1。如果（z）*, 十、*) 是（19）和（w）的最优解*, Y*) （20）的最优解，然后（1）（x）*, Y*) 是Γ=（X，Y，U）的平衡。（2） z*= 马克斯∈徐（x）=米尼∈YU（y）=w*.备注3.1。如下面第4.4节所述，优化问题（19）和（19）是所谓的线性规划，它们彼此是对偶的。在实践中可以非常有效地解决这些问题。对于显式求解算法，我们请感兴趣的读者参考有关数学优化的标准文献。4.

拉格朗日对策零和对策的分析与数学优化中的一项基本技术密切相关。非优化问题的一种非常普遍的形式是ismaxx∈Ff（x），其中F可以是任何集合，F:F→ R是任意的目标函数。然而，在我们的上下文中，我们将研究更具体的问题，并通过数学优化问题来理解形式（21）maxx的问题∈Xf（x）使得g（x）≥ 0，其中X是某些坐标s的子集，具有目标函数f:X→ R.向量值函数g:X→ 这是一种限制。g、 ，U.FAIGLE，W.KERN和g.STILL，数学程序设计的算法原理，Springer（2002）46 3。零和GA-MESfunction并结合m实值限制函数gi:X→ 辅助组件。（21）isF={x的可行解集∈ X | gi（X）≥ 0表示所有i=1，m} 。备注3.2。模型（21）将问题作为最大化问题进行优化。当然，由于minx的存在，极小化问题也可以在这个模型中表述出来∈Ff（x）=-马克斯∈目标函数F（x）=-f（x）。优化问题（21）产生了一个零和博弈∧=（X，Rm+，L），其效用是所谓的拉格朗日函数（22）L（X，y）=f（X）+yTg（X）=f（X）+mXi=1yigi（X）。我们把to∧称为拉格朗日对策。例3.4（凸拉格朗日博弈）。如果X是凸的且目标函数f:X→ （21）中的R以及限制函数gi:X→ 罕见的凹，那么拉格朗日对策∧=（X，Rm+，L）是凸零和对策。实际上，对于每个y，L（x，y）在x中是凹的≥ 0，且每x以y为单位呈线性∈ 由于线性函数是凸的，所以对策∧是凸的。互补性松弛。