用零和博弈来思考田忌赛马

yinda_peng

  首先，什么是零和博弈？


  零和博弈是一类特殊的博弈问题，在此类博弈中，只有两名局中人，每个局中人的策略为有限个，在任意纯局势下，两个局中人的赢得之和总是为零，即两者的利益争夺是十分激烈的。
  
  设局中人I、II的策略集分别为S_I={x₁,...,x_m}   S_II={y₁,..,y_n}
当局中人I选定策略x_i,局中人II选定策略y_j后，就形成了一个局势(x_i,y_j)，可见这样的局势共有m*n个。对任意一个局势，记局中人I的获益值为a_ij，得到获益矩阵如下：

由于博弈是零和的，是以局中人II的获益矩阵即为-A。

“田忌赛马”就是“零和博弈”，齐王所失即为田忌所得，只有两个局中人，策略集是有限的，可以采用零和博弈。

  首先齐王和田忌可能的策略有A³₃ = 3！= 6 种，分别为“上中下”、“上下中”、“中上下”、“中下上”、“下上中”、“下中上”。

那么记齐王的策略集为S₁={x₁,...x₆},田忌的策略集为S₂={y₁,...y₆}，则齐王的获益矩阵为：

并设齐王和田忌的最优混合策略分别为x^* = [x^*₁...x^*₆]和y^* = [y^*₁...y^*₆]。求x^*和y^*归结为求解如下两个的方程组：

其中x=[x₁,...x₆]^T;U=[u,u,u,u,u,u]^T;y=[y₁,...y₆]^T;V=[v,v,v,v,v,v]^T。实际上，这两者都有无穷多组解，前一个式子的解为：

对策值u=1。类似地，可以给出y的解。

  因为方程组有无穷多解，其中的最小范数解为：x_i = 1/6,i = 1,2,...6; y_j = 1/6,j = 1,2,...6,  u=v=1,即双方都以1/6的概率选取每个纯策略。或者说在6个纯策略中随机地选取一个即为最优策略。总的结局也是齐王赢得的期望值为一千两黄金。(每场输家给赢家一千两黄金)在原故事中，田忌之所以能赢，不外乎是事先知道了齐王选用的策略，也就是马出场的顺序，从而采取针对。

import numpy as np
import sympy as sp

A = np.array([[3,1,1,1,-1],[1,3,1,1,-1,1],[1,-1,3,1,1,1],[-1,1,1,3,1,1],[1,1,-1,1,3,1],[1,1,1,-1,1,3]],dtype = int)
Az1 = np.hstack([A.T,-np.ones((6,1))])
Az2 = np.vstack([Az1,[1,1,1,1,1,1,0]])
B = np.array([[0,0,0,0,0,0,1]]).T
Az3 = np.hstack([Az2,B])
Az4 = sp.Matrix(Az3.astype(int))
s1 = Az4.rref()
s2 = np.linalg.pinv(Az2) @ B
print("行最简形：",s1[0])
print("最小范数解：",s2)

不二如是

感谢分享