9博弈的矩阵形式课件.ppt

博弈的矩阵形式,概要,矩阵博弈：另一种博弈理论定义 信息完全的博弈的最大最小（Minimax） 信息隐藏的博弈的最大最小（Minimax）,已有假设： 俩人对弈：玩家A与B。 信息完全：俩玩家亲历所有的状态及决定。每个决定是顺序做出。 零和：A得到的等于B损失的。 将取消这些限制。首先取消信息完全的假设，由此导出更实际的模型。,博弈的扩展形式：用树代表博弈,A,B,A,玩家的一个纯策略：该玩家为其所遇到的每种可能状态而做的移动（走步）。,A,B,A,A的纯策略： 策略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),B的纯策略： 策略I：(2L,3L) 策略II：(2L,3R) 策略III：(2R,3L) 策略IV：(2R,3R),博弈的矩阵形式,博弈的矩阵形式,博弈的矩阵范式：上表包含A与B的纯策略的所有可能组合的回报值。 该表完全表征博弈，无需关于规则等的任何额外信息。 虽然在许多场合，纯策略数目太大，不能用表来显示，但矩阵是能用来导出博弈本质的基本表征。,A的纯策略,B的纯策略,Minimax：矩阵形式,所有行的极大值,每行的极小值,Minimax：矩阵形式,所有行的极大值,每行的极小值,极大值=博弈值=+2,对于博弈矩阵每行所示的每种策略，A应假设B会采用A策略下的最佳策略，即行中极小值的策略。因此，A能获得的最佳值是各行极小值的最大值： 相应的纯策略是该博弈的最佳解，即假设B表现最佳，A应采用的最佳策略。,Minimax：矩阵形式,每列的极大值,所有列的极小值,能用相反的论点。 对于博弈矩阵每列所示的每种策略，B应假设A会采用B策略下的最佳策略，即列中极大值的策略。因此，B玩家能获得的最佳值是各列极大值的最小值： 问题：得到的是一样的结果吗？ 总存在一个解吗？,Minimax还是Maximin？,极小值=博弈值=+2,每列的极大值,所有列的极小值,注意到，两种场合下得到一样的值和一样的策略。 其它也总是这样吗？,所有行的极大值,每行的极小值,极大值=博弈值=+2,极小值=博弈值=+2,每列的极大值,所有列的极小值,Minimax与Maximin,（von Neumann）第1基本定理 ： 对一个信息完全的俩人零和对弈： 对每位玩家，总存在一个最佳纯策略 Minimax=Maximin 注：这只是minimax搜索算法的博弈理论形式。,信息隐藏的博弈,另一个例子,俩位玩家A与B，各有一枚硬币 他们选择性地给对方看自己硬币的正面或反面。 如果他们都选择正面，则B付给A两块钱。 如果他们都选择反面，则B付给A一块钱。 如果他们选择不同的面，则A付给B一块钱。,2019/11/15,17,可编辑,示例的作用,这个示例能模拟大量的实际情况。 实例：A是一位店主，而B是一名检察官。检察官选一天来执行检查。店主挑某天来藏匿坏东西。如果各自的行动日不同，B赢；否则，A赢。 这类实际问题能简化为类似上面的硬币游戏。,扩展形式,A,B,问题：因为移动是同时进行的，所以B不知道A的移动。 博弈信息不再是完全的，而是有隐藏的了。,B,A,矩阵形式,容易验证： 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。 ,B,A,不是选择一个固定的纯策略，假设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程序相似) ： maxp min(3p-1,-2p+1),采用随机策略,B,A,解的图形化,如B选H，则期望回报为3p-1,如B选T，则期望回报为-2p+1,不管B遵循什么可能的策略(概率为q)，所导致的回报都将位于与B的纯策略相对应的两条直线之间,解的图形化,min(3p-1,-2p+1),最佳p值： p*=argmaxp min(3p-1,-2p+1)=2/5 期望回报： maxp min(3p-1,-2p+1)=1/5,混合策略,A不再可能找到一种纯策略。 需将问题稍加改变：假设对弈开始时，A随机选择一种纯策略。 在此场合，A选择一种纯策略的概率为p，选择另一种纯策略的概率为1-p。 混合策略：随机选择纯策略，且由概率p完全定义。 问题：虽然A不能找到一种最佳纯策略，但是能找到一种最佳混合策略p，对吗？ 答案：对。从上面简单例子得出的结果对一般博弈仍成立。由此可产生一个为零和博弈寻找最佳混合策略的方法。,混合策略的最大最小,（von Neumann）第2定理： 对一个信息隐藏的俩人零和对弈： 总存在一个最佳混合策略，并具有下面值： maxp min(pm11+(1-p)m21，pm12+(1-p)m22) 其中，对弈的矩阵形式为： 注：这是minimax结果在混合策略上的一个直接推广。,混合策略的最大最小,（von Neumann）第2定理： 对一个信息隐藏的俩人零和对弈： 总存在一个最佳混合策略 此外，与信息完全的对弈一样，以怎样的次序来看待玩家并不重要。因此，minimax等于maximin ： maxp min(pm11+(1-p)m21，pm12+(1-p)m22)= minq max(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随机地改变处理每种牌型的方法。一个好的玩家应用一种好的策略。 博弈理论的结果是将在信息隐藏的博弈中对类似欺骗这样行为的需求形式化。 博弈理论采用理性玩家假设。简单说，