简述Fictitious Play原理及实现

阅读：评论：0

背景

对博弈求均衡是算法博弈论的一个重要内容，这里介绍一个经典的求均衡算法：Fictitious Play（虚拟对弈）。

在博弈论中，虚拟对弈（Fictitious Play）是由乔治·W·布朗（George W. Brown）首次提出的一种学习规则[1]。在这种规则中，每个玩家假设对手采用静态（可能是混合）策略。在每一轮中，每个玩家根据对手的实际行动频率做出最佳响应。如果对手确实使用静态策略，这种方法当然是适当的；但如果对手的策略是非静态的，这种方法就存在缺陷。例如，对手的策略可能依赖于虚拟玩家的上一次动作。—上述内容参考了维基百科的内容。

模型

具体来说，Fictitious Play算法的步骤如下：

初始化：给定玩家的初始策略。
迭代：重复以下步骤直到收敛或达到预定的迭代次数：
a. 玩家观察对手的策略，并根据对手策略的估计选择自己的最佳响应策略。
b. 更新玩家的策略，可以使用加权平均等方式进行更新。
c. 对手也进行相同的步骤，根据玩家的策略估计选择最佳响应策略，并更新对手的策略。
输出：输出最终收敛的策略作为纳什均衡策略的估计。

步骤a, 可以数学上表示为：
a i t , ∗ ∈ B R i ( p − i t = 1 t ∑ τ = 0 t − 1 I { a − i τ = a , a ∈ A } ) a_i^{t, *} in mathbf{B R}_ileft(p_{-i}^t=frac{1}{t} sum_{tau=0}^{t-1} mathscr{I}left{a_{-i}^tau=a, a in mathbb{A}right}right) \ ait,∗∈BRi(p−it=t1τ=0∑t−1I{a−iτ=a,a∈A})
a i t , ∗ a_i^{t, *} ait,∗ 表示在第 t t t 轮中，玩家 i i i 选择的最佳响应动作。它是从集合 BR i textbf{BR}_i BRi 中选择的，该集合包含了对手在前 t t t 轮中采取的动作的经验频率。
B R i ( p − i t = 1 t ∑ τ = 0 t − 1 I { a − i τ = a , a ∈ A } ) mathbf{B R}_ileft(p_{-i}^t=frac{1}{t} sum_{tau=0}^{t-1} mathscr{I}left{a_{-i}^tau=a, a in mathbb{A}right}right) BRi(p−it=t1τ=0∑t−1I{a−iτ=a,a∈A})表示在给定对手的动作频率 p − i t p_{-i}^t p−it（对手在前 t t t 轮中采取特定动作的平均频率）的条件下，玩家 i i i 的最佳响应动作的集合。这个集合包含了对手可能采取的动作，并且玩家 i i i 会根据对手的动作频率选择最佳响应动作。换句话说，公式表达了在Fictitious Play算法中，玩家 i i i 通过观察对手在前 t t t 轮中的动作频率 p − i t p_{-i}^t p−it，从对手可能的动作集合中选择一个最佳响应动作 a i t , ∗ a_i^{t, *} ait,∗。这个选择是基于对手的动作频率的估计，玩家 i i i 希望通过选择最佳响应动作来最大化自己的收益。

步骤b, 可以数学上表示为：
p i t + 1 = ( 1 − 1 t ) p i t + 1 t a i t , ∗ , for all i p_i^{t+1}=left(1-frac{1}{t}right) p_i^t+frac{1}{t} a_i^{t, *}, text { for all } i pit+1=(1−t1)pit+t1ait,∗, for all i
p i t + 1 p_i^{t+1} pit+1：表示在第 t + 1 t+1 t+1 轮中，玩家 i i i 的策略更新后的值。它是通过对上一轮策略 p i t p_i^t pit 进行加权平均得到的。

( 1 − 1 t ) p i t left(1-frac{1}{t}right) p_i^t (1−t1)pit：表示上一轮策略 p i t p_i^t pit 的加权部分。权重为 ( 1 − 1 t ) left(1-frac{1}{t}right) (1−t1)，其中 t t t 表示当前的轮数。

1 t a i t , ∗ frac{1}{t} a_i^{t, *} t1ait,∗：表示最佳响应动作 a i t , ∗ a_i^{t, *} ait,∗ 的加权部分。权重为 1 t frac{1}{t} t1，其中 t t t 表示当前的轮数。

综合起来，公式表示了在每一轮中，玩家 i i i 的策略更新为上一轮策略 p i t p_i^t pit 的加权平均值，其中上一轮策略占据的权重逐渐减小，最佳响应动作占据的权重逐渐增加。这种加权平均的方式使得玩家的策略在每一轮中逐渐逼近最佳响应策略，从而达到更优的策略选择。

代码实现

这里采用的二人博弈模型为：

下面为Fictitious Play算法的Python实现：

p1 = np.array([0.25, 0.75])  # 玩家1选择动作a和动作b的概率
p2 = np.array([0.75, 0.25])  # 玩家2选择动作a和动作b的概率num_iterations = 100  # 迭代次数# 迭代步骤
for iteration in range(num_iterations):#print("iterations: ", iteration)# 计算玩家1对玩家2的平均策略    #print("p1: ", p1)#print("p2: ", p2)avg_p1 = p1[0]*0+p1[1]*1avg_p2 = p2[0]*0+p2[1]*1#print("avg_p1", avg_p1)#print("avg_p2", avg_p2)# 玩家1根据玩家2的平均策略选择最佳响应动作p1_best_response = 0 if avg_p2 <= 0.5 else 1#print("p1_best_response:", p1_best_response)#print("p1_best_response:", np.eye(2)[p1_best_response])# 玩家2根据玩家1的平均策略选择最佳响应动作p2_best_response = 0 if avg_p1 <= 0.5 else 1#print("p2_best_response:", p2_best_response)#print("p2_best_response:", np.eye(2)[p2_best_response])# 更新策略p1 = (1 - 1 / (iteration + 2)) * p1 + (1 / (iteration + 2)) * np.eye(2)[p1_best_response]p2 = (1 - 1 / (iteration + 2)) * p2 + (1 / (iteration + 2)) * np.eye(2)[p2_best_response]# 输出最终策略
print("玩家1的策略：", p1)
print("玩家2的策略：", p2)

最后收敛到了[0.5, 0.5]周围，符合预期。如果p1 = np.array([0.25, 0.75])，p2 = np.array([0.25, 0.75])，则为收敛到[0, 1]周围，也符合预期。