策略切换下的稳定性研究

### 策略切换下的稳定性研究 在博弈论的研究中，传统的策略制定方式往往假设参与者能考虑所有可能的未来，并据此制定最优策略。然而，在实际的博弈场景中，这种理想化的策略制定方式并不现实。本文将探讨一种更符合实际情况的策略概念——类似过程的策略，以及在策略切换下的稳定性问题。 #### 1. 概述 以板球比赛为例，投球手在助跑时会思考诸多问题，如球该投向击球手的外侧还是内侧、是否投短球、是否投慢球等；击球手在站位时也会考虑，如果投球手将球投向自己的内侧，是全力击球得分还是稳妥地得一分，以及如果自己得分过多，投球手是否会被换下场。 在理想情况下，投球手和击球手都能拥有关于对方能力和场地状况的完美信息，并在投出第一球前就制定出最优的混合策略。但实际比赛远非如此理想，反而更具趣味性。如果我们不仅想预测比赛结果，还想了解比赛的进程，就需要关注参与者如何从众多策略中选择一个，这自然引出了部分策略和策略切换的概念。 参与者进入游戏时，会带着关于游戏结构、其他参与者技能的信息以及一组初始可能的策略。随着游戏的进行，他们会根据观察结果修改策略，从一个策略切换到另一个策略，甚至可能设计出新的策略。这种互动的动态过程最终会导致一些策略被淘汰，一些策略变得稳定。 在这样的模型中，我们可以研究一些问题，例如： - 游戏最终是否会稳定在整个游戏区域的某个子集内？ - 参与者能否使用不涉及策略切换的策略来确保某些目标？ - 给定游戏的一个子区域，参与者的策略在该子集中是否有效？ 本文将探讨这些问题的算法解决方案，并给出一种简单而富有表现力的语法来指定和组合策略。 #### 2. 相关工作 动态学习在博弈论中已得到广泛研究。例如，Young 考虑了一种模型，其中每个参与者根据过去其他参与者的行为信息样本选择最优策略。在合作博弈论中，参与者会动态决定加入哪个联盟，研究关注联盟结构如何随时间变化以及参与者最终会形成哪个联盟。进化博弈论研究参与者如何观察邻居的收益并相应地改变策略以最大化适应性。 本文的工作基于博弈论的逻辑基础，采用逻辑描述策略和算法来回答问题。模态逻辑已被用于以各种方式推理游戏，如交替时态逻辑（ATL），以及其各种扩展，用于明确将参与者的知识和策略纳入逻辑。此外，还有使用动态逻辑描述游戏和策略的工作。 #### 3. 预备知识 ##### 3.1 扩展形式游戏 设 $N = \{1, \ldots, n\}$ 为参与者集合。对于每个 $i \in N$，$A_i$ 是一个有限的动作集合，表示参与者的行动。假设参与者的动作集合相互不相交，即 $A_i \cap A_j = \varnothing$（$i \neq j$）。$A = A_1 \times \cdots \times A_n$ 表示动作元组的集合，$\hat{A} = A_1 \cup \cdots \cup A_n$ 表示所有参与者的动作集合。 扩展形式游戏是一棵树 $T = (T, \Rightarrow, t_0)$，其中 $T \subseteq A^*$ 是一个前缀封闭的集合，称为节点或游戏位置的集合。初始游戏位置或树的根是 $t_0 = \epsilon$（空字），边关系为 $\Rightarrow \subseteq T \times T$。游戏中的一次玩法就是从 $t_0$ 开始的一条路径。为了技术上的方便，假设所有玩法都是无限的。 严格来说，一个游戏由游戏树和参与者的获胜条件组成。在本文中，获胜条件将是游戏模型的一些相当通用的属性。假设游戏的结果和收益来自一个固定的有限集合，可以使用逻辑框架中的命题对其进行编码。本文的主要重点是参与者的策略，而不是获胜条件本身。 ##### 3.2 策略 参与者 $i$ 的策略是一个函数 $\mu : T \to A_i$，它告诉参与者在每个游戏位置应该选择哪个动作。对于游戏的历史 $\bar{a}_1 \cdots \bar{a}_k$，参与者 $i$ 在该历史之后的策略是一个函数 $\mu[\bar{a}_1 \cdots \bar{a}_k] : \{\bar{a}_1 \cdots \bar{a}_k u \in T\} \to A_i$，其中 $u \in A^*$。$\mu[\epsilon]$ 是整个游戏的策略，我们直接用 $\mu$ 表示。 $\mu[\bar{a}_1 \cdots \bar{a}_k]$ 可以看作是 $T$ 的一个子树 $T^{\mu[\bar{a}_1 \cdots \bar{a}_k]} = (T', \Rightarrow', t_0')$，其中根 $t_0' = \bar{a}_1 \cdots \bar{a}_k \in T'$。对于任何节点 $t = \bar{a}_1 \cdots \bar{a}_l \in T'$（$l \geq k$），如果 $\mu[\bar{a}_1 \cdots \bar{a}_k](t) = a$，则 $t$ 在 $T^{\mu[\bar{a}_1 \cdots \bar{a}_k]}$ 中的子节点恰好是那些 $t\bar{a} \in T$ 且 $\bar{a}(i) = a$ 的节点。 我们将这样的子树 $T^{\mu[\bar{a}_1 \cdots \bar{a}_k]}$ 称为策略 $\mu[\bar{a}_1 \cdots \bar{a}_k]$ 的策略树。注意，$\mu[\bar{a}_1 \cdots \bar{a}_k]$ 在 $t \notin T'$ 位置的值不影响符合 $\mu[\bar{a}_1 \cdots \bar{a}_k]$ 的玩法的结果。因此，我们可以在不损失一般性的情况下，用策略树来解释策略的语义。我们也可以互换使用“策略”和“策略树”这两个术语。 设 $\Omega_i(t)$ 表示参与者 $i$ 在历史 $t$ 之后在 $T$ 中的所有策略的集合，$\Omega_i = \cup_{t \in T} \Omega_i(t)$。注意，对于任何游戏 $T$，策略集合是无限的。 **策略的组合**：设 $\mu_1, \mu_2 \in \Omega_i$。假设参与者 $i$ 以策略 $\mu_1$ 开始玩游戏 $T$，在 $k$ 轮（$k \geq 0$）后，她决定在游戏的剩余部分使用策略 $\mu_2$。得到的策略 $\mu$ 也是参与者 $i$ 的策略集合中的一个元素，即 $\mu \in \Omega_i$。我们可以将 $\mu$ 看作是策略 $\mu_1$ 和 $\mu_2$ 的组合，用 $\mu_1^k\mu_2$ 表示。 策略 $\mu_1^k\mu_2$ 的策略树 $T^{\mu_1^k\mu_2}$ 是通过取 $T^{\mu_1}$ 并移除所有高度大于或等于 $k + 1$ 的节点，得到一个高度为 $k$ 的树，然后在这个树的每个叶节点 $\bar{a}_1 \cdots \bar{a}_k$ 上粘贴 $T^{\mu_2[\bar{a}_1 \cdots \bar{a}_k]}$ 得到的。 ##### 3.3 部分策略 给定 $T = (T, \Rightarrow, t_0)$ 和历史 $\bar{a}_1 \cdots \bar{a}_k \in T$，参与者 $i$ 在该历史之后的部分策略 $\sigma[\bar{a}_1 \cdots \bar{a}_k]$ 是一个部分函数 $\sigma[\bar{a}_1 \cdots \bar{a}_k] : \{\bar{a}_1 \cdots \bar{a}_k u \in T\} \rightharpoonup A_i$，其中 $u \in A^*$。如果 $\sigma$ 在某个历史 $\bar{a}_1 \cdots \bar{a}_k u \in T$ 上未定义，参与者可以在那里选择任何可用的动作。$\sigma[\epsilon]$ 被视为整个游戏的策略 $\sigma$。 部分策略 $\sigma[\bar{a}_1 \cdots \bar{a}_k]$ 的策略树 $T^{\sigma[\bar{a}_1 \cdots \bar{a}_k]} = (T', \Rightarrow', t_0')$ 是 $T$ 的一个子树，根为 $t_0' = \bar{a}_1 \cdots \bar{a}_k \in T'$。对于任何节点 $t = \bar{a}_1 \cdots \bar{a}_l \in T'$（$l \geq k$），如果 $\sigma[\bar{a}_1 \cdots \bar{a}_k](t) = a$，则 $t$ 的子节点恰好是那些 $t\bar{a} \in T$ 且 $\bar{a}(i) = a$ 的节点；如果 $\sigma[\bar{a}_1 \cdots \bar{a}_k]$ 在 $t$ 上未定义，则 $t$ 的子节点是 $\{t\bar{a} | t\bar{a} \in T\}$，即游戏树 $T$ 中节点 $t$ 的所有子节点。 我们用 $\Sigma_i(t)$ 表示参与者 $i$ 在历史 $t$ 之后在 $T$ 中的所有部分策略的集合，$\Sigma_i = \cup_{t \in T} \Sigma_i(t)$ 表示参与者 $i$ 的所有部分策略的