9博弈的矩阵形式

博弈的矩阵形式概要矩阵博弈：另一种博弈理论定义信息完全的博弈的最大最小（Minimax）信息隐藏的博弈的最大最小（Minimax）已有假设：俩人对弈：玩家A与B。信息完全：俩玩家亲历所有的状态及决定。每个决定是顺序做出。零和：A得到的等于B损失的。将取消这些限制。首先取消信息完全的假设，由此导出更实际的模型。博弈的扩展形式：用树代表博弈ABA玩家的一个纯策略：该玩家为其所遇到的每种可能状态而做的移动（走步）。ABAA的纯策略：策略1：(1L,4L)策略2：(1L,4R)策略3：(1R,4L)策略4：(1R,4R)B的纯策略：策略1：(2L,3L)策略2：(2L,3R)策略3：(2R,3L)策略4：(2R,3R) 一般情况：如果有N个状态和M个移动，则有多少个纯策略存在？（MN）A的纯策略：策略I：(1L,4L)策略II：(1L,4R)策略III：(1R,4L)策略IV：(1R,4R)IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1B的纯策略：策略I：(2L,3L)策略II：(2L,3R)策略III：(2R,3L)策略IV：(2R,3R)博弈的矩阵形式IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1博弈的矩阵形式博弈的矩阵范式：上表包含A与B的纯策略的所有可能组合的回报值。该表完全表征博弈，无需关于规则等的任何额外信息。虽然在许多场合，纯策略数目太大，不能用表来显示，但矩阵是能用来导出博弈本质的基本表征。A的纯策略B的纯策略Minimax：矩阵形式IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的极大值每行的极小值Minimax：矩阵形式IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的极大值每行的极小值极大值=博弈值=+2对于博弈矩阵每行所示的每种策略，A应假设B会采用A策略下的最佳策略，即行中极小值的策略。因此，A能获得的最佳值是各行极小值的最大值：相应的纯策略是该博弈的最佳解，即假设B表现最佳，A应采用的最佳策略。Minimax：矩阵形式IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的极大值所有列的极小值能用相反的论点。对于博弈矩阵每列所示的每种策略，B应假设A会采用B策略下的最佳策略，即列中极大值的策略。因此，B玩家能获得的最佳值是各列极大值的最小值：问题：得到的是一样的结果吗？总存在一个解吗？Minimax还是Maximin？极小值=博弈值=+2IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的极大值所有列的极小值注意到，两种场合下得到一样的值和一样的策略。其它也总是这样吗？IIIIIIIV-1I-1-1+2+2+2II+4+4+2+2+1III+5+1+5+1+1IV+5+1+5+1所有行的极大值每行的极小值极大值=博弈值=+2极小值=博弈值=+2IIIIIIIVI-1-1+2+2II+4+4+2+2III+5+1+5+1IV+5+1+5+1+5+4+5+2每列的极大值所有列的极小值Minimax与Maximin（vonNeumann）第1基本定理：对一个信息完全的俩人零和对弈：对每位玩家，总存在一个最佳纯策略Minimax=Maximin

注：这只是minimax搜索算法的博弈理论形式。信息隐藏的博弈另一个例子俩位玩家A与B，各有一枚硬币他们选择性地给对方看自己硬币的正面或反面。如果他们都选择正面，则B付给A两块钱。如果他们都选择反面，则B付给A一块钱。如果他们选择不同的面，则A付给B一块钱。示例的作用这个示例能模拟大量的实际情况。实例：A是一位店主，而B是一名检察官。检察官选一天来执行检查。店主挑某天来藏匿坏东西。如果各自的行动日不同，B赢；否则，A赢。这类实际问题能简化为类似上面的硬币游戏。扩展形式AB问题：因为移动是同时进行的，所以B不知道A的移动。博弈信息不再是完全的，而是有隐藏的了。HTH+2-1T-1+1BA矩阵形式容易验证：maximin=-1，minimax=+1。不再有maximin=minimax。因此，也应该不存在纯策略解。事实上，一个信息隐藏的零和博弈是不存在纯策略解的。为什么无纯策略解？直觉：如果A考虑移动H，则他必须假设B会选择对他最为不利的移动T。因此，A应转而尝试移动T，但这一次他必须假设B会选择对他最为不利的移动H。因此，A应转而尝试移动H，但这一次他必须假设B会选择对他最为不利的移动T。因此，A应转而尝试移动T，但这一次他必须假设B会选择对他最为不利的移动H。因此，A应转而尝试移动H，但这一次他必须假设B会选择对他最为不利的移动T。……HTH+2-1T-1+1BA不是选择一个固定的纯策略，假设A以p为概率随机选择策略H，并以1-p为概率选择策略T。如果B选移动H，A所期望的回报是：

p(+2)+(1-p)(-1)=3p-1如果B选移动T，A所期望的回报是：

p(-1)+(1-p)(+1)=-2p+1因此，最坏的情形是，B选择在上述两种场合中回报最小的那种策略：

min(3p-1,-2p+1)那么，A应调整p，以使其回报最大(这与标准maximin程序相似)：

maxpmin(3p-1,-2p+1)采用随机策略HTH+2-1T-1+1BA解的图形化如B选H，则期望回报为3p-1如B选T，则期望回报为-2p+1不管B遵循什么可能的策略(概率为q)，所导致的回报都将位于与B的纯策略相对应的两条直线之间解的图形化min(3p-1,-2p+1)最佳p值：p*=argmaxpmin(3p-1,-2p+1)=2/5期望回报：maxpmin(3p-1,-2p+1)=1/5混合策略A不再可能找到一种纯策略。需将问题稍加改变：假设对弈开始时，A随机选择一种纯策略。在此场合，A选择一种纯策略的概率为p，选择另一种纯策略的概率为1-p。混合策略：随机选择纯策略，且由概率p完全定义。问题：虽然A不能找到一种最佳纯策略，但是能找到一种最佳混合策略p，对吗？答案：对。从上面简单例子得出的结果对一般博弈仍成立。由此可产生一个为零和博弈寻找最佳混合策略的方法。混合策略的最大最小（vonNeumann）第2定理：对一个信息隐藏的俩人零和对弈：总存在一个最佳混合策略，并具有下面值：

maxpmin(pm11+(1-p)m21，pm12+(1-p)m22) 其中，对弈的矩阵形式为： 注：这是minimax结果在混合策略上的一个直接推广。m11m12m21m22混合策略的最大最小（vonNeumann）第2定理：对一个信息隐藏的俩人零和对弈：总存在一个最佳混合策略此外，与信息完全的对弈一样，以怎样的次序来看待玩家并不重要。因此，minimax等于maximin

：

maxpmin(pm11+(1-p)m21，pm12+(1-p)m22)=

minqmax(qm11+(1-q)m12，qm21+(1-q)m22)= 注：这是minimax结果在混合策略上的一个直接推广。22对弈的方法因为两个关于p的函数是线性的，所以可以在下面三种情况下到达极大值：p=0，p=1，两直线的交点，如果在0与1之间的某值p处出现极大值。min(pm11+(1-p)m21，pm12+(1-p)m22)最大值最大值最大值一般场合：NM博弈22对弈的问题：A和B每位玩家各有2种策略。以上结果可推广到NM博弈，但较难计算。一个混合策略是一个概率矢量p=(p1,…,pN)，其中pi是A选择策略i的概率，且pi=1。用线性规划求解下面问题来寻找最佳策略：A的期望回报，如B选择纯策略j，A以概率pi选择纯策略i。图示：2M博弈minj(pm1j+(1p)m2j)maxpminj(pm1j+(1p)m2j)pm1j+(1p)m2j讨论用来选择最佳混合策略的判据是在数次博弈后A获得的平均回报。用随机挑选的纯策略作为混合策略，并寻找最佳混合策略，这对吗？实际上，这只是把通常情形下所发生的事实形式化而已。例如，扑克对弈中，如果A遵循某种单一纯策略，即在每次处理一手特殊牌型时，采取相同的行动，则B能猜到并回应这种策略，以降低A的回报。正确的做法是，根据某种策略，A随机地改变处理每种牌型的方法。一个好的玩家应用一种好的策