人工智能与博弈论

博弈策略求解¶

概念：对于一个有$N$个玩家参加的博弈，玩家在博弈中采取的策略为$\sigma_i$.对于所有玩家，所有策略构成一个策略集合$\sigma=\set{\sigma_1,\sigma_2,\cdots,\sigma_N}$，记除玩家i外其它玩家的策略组合记作$\sigma_{-i}=\set{\sigma_1,\cdots,\sigma_{i-1},\sigma_{i+1},\cdots,\sigma_N}$

最优反应策略：给定策略组合$\sigma$，玩家$i$在终结局势下的收益为$u_i(\sigma)$，给定其它玩家的策略组合$\sigma_{-i}$的情况下，对玩家$i$的最优反应策略$\sigma_i^*$满足如下条件

\[u_i(\sigma_i^*,\sigma_{-i})\geqslant\max_{\sigma_i'\in\Sigma_i}u_i(\sigma_i',\sigma_{-i})\]

其中$\Sigma_i$是玩家i可选择的所有策略。

在策略组合$\sigma^*$中，如果每个玩家的策略相对于其他玩家的策略而言都是最佳反应策略，那么$\sigma^*$是纳什均衡策略，即

\[ u_i(\sigma^*)\geqslant\max_{\sigma_i'\in\Sigma_i}u_i(\sigma_i^*,\cdots,\sigma_N^*) \]

近似求解纳什均衡：遗憾最小化算法

概念：遗憾最小化算法是一种根据以往博弈过程中所得遗憾程度来选择未来行为的方法
累加遗憾值：玩家i在过去$T$轮中采取策略$\sigma_i$的累加遗憾值定义如下 $$ Regret_i^T(\sigma_i)=\sum_{t=1}^Tu_i(\sigma_i,\sigma_{-i}^t)-u_i(\sigma') $$
有效遗憾值： $$ Regret_i^{T,+}(\sigma_i)=\max(Regret_i^T(\sigma_i),0) $$
遗憾匹配：

\[ P(\sigma_i^{T+1})=\left\{\begin{array}{ll} \dfrac{Regret_i^{T,+}(\sigma_i)}{\sum\limits_{\sigma'\in\Sigma_i}Regret_i^{T,+}}&,if \sum_{\sigma_i'\in\Sigma_i}Regret_i^{T,+}(\sigma_i')>0\\ \dfrac{1}{|\Sigma_i|}&,Otherwise \end{array} \right. \]

遗憾最小化算法在实际使用中需要反复模拟博弈多次，才能拟合近似的最优反应策略。

问题：对于围棋和扑克等需要多轮决策(即序贯决策)才能判断胜负的博弈问题无法一次决策分胜负

虚拟遗憾最小化算法：

思想：对于任何序贯决策的博弈对抗，可将博弈过程表示成一棵博弈树，博弈树种的每一个中间节点都是一个信息集$I$，信息集中包含中间节点状态及到达该节点的所有历史行动

在信息集$I$下，玩家可以采取的行动集合记作$A(I)$，玩家i所采取的行动$a_i\in A(I)$可认为是其采取的策略$\sigma_i$的一部分，在信息集$I$下采取的行动$a$所代表的策略集记为$\sigma_{I\to a}$.计算虚拟遗憾值的对象就是博弈树中每个中间结点在信息集下所采取的行动，并根据遗憾值匹配得到该结点在信息集下应该采取的策略$\sigma_{I\to a}$

在一次博弈中，所有玩家交替采取的行动序列记为$h$，对于所有玩家的策略组合$\sigma$，行动序列$h$出现的概率记为$\pi^\sigma(h)$，在策略组合$\sigma$下，所有能够到达该信息集的行动序列的概率累加就是该信息集的出现概率，即$\pi^\sigma(I)=\sum_{h\in I}\pi^\sigma(h)$

博弈的终结局势集合记为$Z$，对于任意一个终结局势$z\in Z$，玩家$i$在终结局势下的收益记作$u_i(z)$，给定行动序列$h$，依照策略组合$\sigma$最终到达终结局势$z$的概率记作$\pi^\sigma(h,z)$

在策略组合$\sigma$下，对玩家i而言，从根结点到当前结点的行动序列路径h的虚拟价值计算如下： $$ v_i(\sigma,h)=\sum_{z\in Z}\pi_{-i}^\sigma(h)\times\pi^\sigma(h,z)\times u_i(z) $$ （不考虑玩家i的策略到达当前节点的概率*当前节点到达叶子节点的概率*叶子节点的收益）

在定义行动序列路径h的虚拟价值之后，就可如下计算玩家i在基于路径h到达当前结点采取行动a的遗憾值： $$ r_i(h,a)=v_i(\sigma_{I\to a},h)-v_i(\sigma,h) $$ 对能够到达同一个信息集I(即博弈树中同一个中间结点)的所有行动序列的遗憾值进行累加，即可得到信息集I的遗憾值： $$ r_i(I,a)=\sum_{h\in I}r_i(h,a) $$ 类似于遗憾最小化算法，虚拟遗憾最小化的遗憾值是$T$轮重复博弈后的累加值，即 $$ Regret_i^{T,+}(I,a)=\sum_{t\in I}r_i^t(I,a) $$ 有效遗憾值： $$ Regret_i^{T,+}(\sigma_i)=\max(Regret_i^T(\sigma_i),0) $$ 根据有效虚拟遗憾值进行遗憾匹配，以计算经过T轮博弈后，玩家i在信息集I情况下于后续T+1轮选择行动a的概率，即

\[ \sigma_i^{T+1}(I,a)=\left\{\begin{array}{ll} \dfrac{Regret_i^{T,+}(I,a)}{\sum\limits_{a\in A(I)}Regret_i^{T,+}(I,a)}&,if \sum_{a\in A(I)}Regret_i^{T,+}(I,a)>0\\ \dfrac{1}{|A(I)|}&,Otherwise \end{array} \right. \]

算法步骤：

初始化遗憾值和累加策略表为0
采用随机选择的方法决定策略
利用当前策略与对手进行博弈
计算每个玩家采取每次行动后的遗憾值
根据博弈结果计算每个行动的累加遗憾值以更新策略
重复3~5若干次，不断优化策略
据重复博弈最终的策略，完成最终的动作选择

安全子博弈：

思想：完全信息博弈下的子博弈与博弈其他部分无关，可以单独考虑
概念：在子博弈的求解过程中，得到的结果一定不差于全局的近似解法

博弈规则设计¶

双边匹配算法¶

稳定婚姻问题：假设有n个单身男性构成的集合M=$\set{m_1,\cdots,m_n}$,以及n个单身女性构成的集合$F=\set{f_1,\cdots,f_n}$。对于任意一名单身男性m,他都有自己爱慕的单身女性的顺序$s_{mi}:=f_{mi,1}\succ\cdots\succ f_{mi,n}$,这里$f_{mi,j}$表示第i名男性所喜欢单身女性中排在第j位的单身女性。算法的最终目标是为这n个男性和女性匹配得到n对伴侣，每一对伴侣可以表示为$(m_i,f_j)$

算法步骤：

单身男性向最喜欢的女性表白
所有收到表白的女性从向其表白的男性中选择最喜欢的男性，暂时匹配
未匹配的男性继续向没有拒绝过他的女性表白。收到表白的女性如果没有完成匹配，则从这一批表白者中选择最喜欢的男性。即使收到表白的女性已经完成匹配，但是如果她认为有更喜欢的男性，则可以拒绝之前的匹配者，重新匹配
如此循环迭代，直到所有人都成功匹配为止

单边匹配算法¶

最大交易圈算法：

首先记录每个标的物的初始占有者，或者对物品进行随机分配
每个交易者连接一条指向他最喜欢的标的物的边，并从每一个标的物连接到其占有者或者具有高优先权的交易者
此时形成一张有向图，且必存在环，这种环称为“交易圈”。对于交易圈中的交易者，将每人指向结点所代表的标的物赋予交易者，同时交易者放弃原先占有的标的物，占有者和匹配成功的标的物离开匹配市场
从剩余的交易者和标的物之间重复进行交易圈匹配，直到无法形成交易圈，算法停止