策略规范与生物模型简化研究

### 策略规范与生物模型简化研究 #### 策略规范相关理论 在策略规范的研究中，我们关注有界内存策略。对于玩家 $i$ 的策略 $\sigma$，若存在有限状态转换器（FST） $A = (Q, →, I, f)$，其中状态集 $Q$ 是 $\sigma$ 的记忆，$I$ 是初始记忆，$→$ 是记忆更新函数，$f$ 是动作输出函数，满足特定条件，则称 $\sigma$ 为有界内存策略。当 $\overline{a}_1 \cdots \overline{a}_{k - 1}$ 是一个玩法，且序列 $q_0, q_1, \cdots, q_k$ 由 $q_0 \in I$ 和 $q_i \xrightarrow{\overline{a}_i} q_{i + 1}$ 确定时，$\sigma(\overline{a}_1 \cdots \overline{a}_{k - 1}) = f(q_k)$。 给定玩家 $i$ 的策略 $\mu$，FST $A$ 在 $T_{\mu}^G$ 上的运行是一个 $Q$ 标记树 $(T, ⇒, t_0, \chi)$。标记函数 $\chi : T \to Q$ 定义为：$\chi(t_0) = q_0 \in I$，若 $\overline{a}_1 \cdots \overline{a}_k ⇒ \overline{a}_1 \cdots \overline{a}_{k + 1}$，则 $\chi(\overline{a}_1 \cdots \overline{a}_k) \in →(\chi(\overline{a}_1 \cdots \overline{a}_k), \overline{a}_{k + 1})$。若存在 $A$ 在 $T_{\mu}^G$ 上的运行 $\chi$ 满足条件 $\forall t = \overline{a}_1 \cdots \overline{a}_k \in T_{\mu}^G$，$\overline{a}(i) = f(\chi(t))$，则称 $\mu$ 被 $A$ 接受，$A$ 的语言 $L(A) = \{ \mu | \mu$ 被 $A$ 接受 $\}$。 有如下引理：给定游戏竞技场 $G$、玩家 $i \in N$ 和策略规范 $\pi \in \Pi_i$，其中 $\pi$ 中提及的所有原子策略都是有界内存的，我们可以构造一个 FST $A_{\pi}$，使得对于所有 $\mu \in \Omega_i$，有 $\mu \in [[\pi]]_G$ 当且仅当 $\mu \in L(A_{\pi})$。 另外，定义无切换策略：若策略 $\pi$ 不包含 $\frown$ 或 $+$ 构造，则称其为无切换策略。对于玩家 $i$ 的策略 $\pi \in \Pi_i$，$\pi$ 的子策略集 $S_{\pi}$ 就是 $\pi$ 的子公式。设 $SF(S_{\pi})$ 是 $S_{\pi}$ 中的无切换策略集，对于给定的 $\pi$，$SF(S_{\pi})$ 是一个有限集。 在游戏竞技场 $G$ 和玩家的策略规范给定的情况下，我们会思考是否存在 $G$ 的某个子竞技场，使得玩家按照策略规范玩游戏时，游戏会稳定到该子竞技场。这个子竞技场在某种意义上是游戏的平衡状态。同时，也有必要探究如果游戏稳定到这样一个平衡子竞技场，特定玩家的策略是否会在切换方面达到稳定。 对于游戏竞技场 $G = (W, →, w_0)$、策略规范 $\pi \in \Pi_i$ 和其对应的 FST $A_{\pi} = (Q, →, I, f, \lambda)$，我们定义 $G$ 相对于 $A_{\pi}$ 的限制 $G \upharpoonright A_{\pi} = (W', →', w_0')$，其中 $W' = W \times Q$，$w_0' = \{ w_0 \} \times I$，且 $(w_1, q_1) \xrightarrow{\overline{a}}' (w_2, q_2)$ 当且仅当 $w_1 \xrightarrow{\overline{a}} w_2$，$q \xrightarrow{\overline{a}} q_2$ 且 $f(q_1) = \overline{a}(i)$。 有以下两个重要定理： - **定理 5.1**：给定游戏竞技场 $G = (W, →, w_0)$（$W$ 上有可观察量的赋值）、$G$ 的子竞技场 $R$ 以及玩家 1 到 $n$ 的策略规范 $\pi_1, \cdots, \pi_n$，问题“所有符合这些规范的玩法最终是否会稳定到 $R$？”是可判定的。判定步骤如下： 1. 构造图 $G_{\pi} = (\cdots ((G \upharpoonright A_{\pi_1}) \upharpoonright A_{\pi_2} \cdots ) \upharpoonright A_{\pi_n}) = (W_{\pi}, →_{\pi}, w_{\pi})$。 2. 设 $F \subseteq G_{\pi} = (W', →')$，其中 $W' = \{ (w, q_1, \cdots, q_n) | w \in R, q_1 \in Q_{\pi_1}, \cdots, q_n \in Q_{\pi_n} \}$，$→' = →_{\pi} \cap (W' \times W')$。 3. 检查 $F$ 是否是 $G_{\pi}$ 中的最大连通分量。若是，进入步骤 4；否则，输出“NO”。 4. 检查从所有初始节点 $w' \in w_{\pi}$ 出发的所有路径是否都到达 $F$。若是，输出“YES”；否则，输出“NO”。 - **定理 5.2**：给定游戏竞技场 $G = (W, →, w_0)$（$W$ 上有可观察量的赋值）、$G$ 的子竞技场 $R$ 以及玩家 1 到 $n$ 的策略规范 $\pi