博弈论——零和博弈

版权声明：本文为原创文章，未经博主允许不得用于商业用途。

基础知识

• 零和博弈：在两名玩家的博弈中，满足$\forall a_1\in A_1,\forall a_2\in A_2,u_1(a_1,a_2)+u_2(a_1,a_2)=0 $即为零和博弈，即两名玩家的总收益为0。
• 对于零和博弈可以只使用一个玩家的收益函数简化表示，即$G=\{\{1,2\},\{A_1,A_2\},\{u\}\}$

纯策略博弈

• 在零和博弈中，两名玩家都不希望结果太坏，因此玩家i决策依据如下原则：$\underset{a_i\in A_i}{\max }\underset{a_j\in A_j}{\min }{u}_i(a_i,a_j)$，即都在最坏策略下做出最好选择。
  • 由于总体收益为0，即$\underset{a_2}{\max }{u}_2=\underset{a_2}{\max }-u_1=-\underset{a_2}{\min }{u}_1$因此上述公式可以化为：
    • Player1:$a_1=arg\underset{a_1\in A_1}{\max }\underset{a_2\in A_2}{\min }u(a_1,a_2)$
    • Player2:$a_2=arg\underset{a_2\in A_2}{\min }\underset{a_1\in A_1}{\max }u(a_1,a_2)$
• 最小化最大化定理：$MinMax\ge MaxMin$
  • 可以用反证法，如果存在$p=MinMax<q=MaxMin$，设$p$为第$i_1$行第$j_1$列，$q$为第$i_2$行第$j_2$列，则p为第$i_1$行最大值，q为第$j_2$列最小值，因此$u(i_1,j_2)\ge q,u(i_1,j_2)\le p\Rightarrow p\ge q$，矛盾。
  • 因此纳什均衡存在的充要条件即$MinMax=MaxMin$

例题：

• 对于Player1，$argMin=\{(U,L),(U,M),(M,M),(D,M).(D,R)\}$,其中收益最大值点为(M,M)，因此选择策略M。
• 对于Player2，$argMax=\{(L,D),(M,M),(R,U)\}$，当Player1收益最低点为(M,M)，因此选择策略M。

综上纳什均衡点为(M,M)

混合策略零和博弈

在混合策略中，收益函数可以表示为$U(p,q)=pM{q}^T.p=(p_1,...,p_m)\in {\Delta }_1,q=(q_1,...,q_n)\in {\Delta }_2$,M为纯策略收益矩阵。

因此同样可以表示两玩家的策略：

• Player1:$p=arg\underset{p\in {\Delta }_1}{\max }\underset{q\in {\Delta }_2}{\min }u(p,q)$
• Player2:$q=arg\underset{q\in {\Delta }_2}{\min }\underset{p\in {\Delta }_1}{\max }u(p,q)$

极大极小定理同样适用。