双并行重复博弈中“模仿朋友”的不可战胜性：存在条件、零行列式策略关联及探索改进

《Journal of Theoretical Biology》：Unbeatable imitation of a friend

　　

即使模仿非常简单，在多智能体（multi-agent）情境中有时也能取得成功。在重复博弈（repeated games）中，模仿的成功已由对其他智能体的不可战胜性（unbeatability）来刻画。既有研究规定了在重复对称博弈（repeated symmetric games）中模仿对共同玩家（co-players）不可战胜的条件，并阐明了不可战胜模仿（unbeatable imitation）的存在与称为零行列式策略（zero-determinant strategies, ZD strategies）的收益控制策略的存在密切相关。然而，这些结果针对的是由一个玩家群体进行一个重复博弈的情境。已有研究指出，对同一群体中其他玩家的模仿与对其他群体中处于相同角色的其他玩家的模仿通常导致不同结果。在此，研究人员考察后一种情境下不可战胜模仿的存在条件，该情境由两个不同玩家群体进行的两个并行重复博弈（two concurrent repeated games）描述。研究人员发现，不可战胜模仿的存在条件比不可战胜零行列式策略（unbeatable zero-determinant strategies）的存在条件更强，而二者均非常受限。此外，研究人员发现，加入探索（exploration）可使模仿策略即使在本无探索模仿会被击败的博弈中也不可战胜。研究人员的发现表明，即使在两个并行重复博弈情境中，不可战胜模仿与收益控制（payoff control）之间仍存在强关联。

Masahiko Ueda 研究“模仿朋友”情境下模仿与ZD策略的表现。研究背景是：模仿虽简单却在多智能体系统中常获成功；TFT（Tit-for-Tat）等模仿策略不依赖具体收益值而易于实施；既有不可战胜模仿结果主要针对同一群体内“模仿对手”，而同一群体内模仿与他人同角色模仿（“模仿朋友”）通常结果不同，后者表现及ZD策略存在性尚不清楚。为此，研究人员建立两个相同阶段博弈由两个群体并行的重复博弈模型，定义记忆一策略（memory-one strategy：仅依赖上一轮行动剖面选择行动）、不可战胜（unbeatable：无论其他玩家策略及焦点玩家初始行动如何，收益不低于朋友）、TFT、IIB（Imitate-If-Better：上轮被朋友击败才模仿其行动）、公平ZD策略（fair ZD strategy：单方面强制双方收益相等），并引入弱收益单调博弈（weakly payoff-monotonic game）、强收益单调博弈（strongly payoff-monotonic game）及带专制动作博弈（game with an autocratic action）。结论是：公平ZD策略存在当且仅当阶段博弈为非平凡弱收益单调博弈；IIB与TFT不可战胜当且仅当阶段博弈为强收益单调博弈；TFT在非平凡强收益单调博弈中为公平ZD策略，IIB为不可战胜ZD策略；加入探索的ε-IIB在带专制动作博弈中几乎必然不可战胜。其意义在于揭示“模仿朋友”情境下不可战胜模仿与收益控制之间的强关联，并说明探索可扩展模仿的有效性。主要关键技术方法：构建两个相同阶段博弈并行重复、无贴现时间平均收益的模型；以记忆一行为策略刻画TFT、IIB、公平ZD及ε-IIB；定义朋友情形下的不可战胜、弱/强收益单调博弈与带专制动作博弈；通过定理证明（利用ZD存在条件、Akin引理、极限平均及Fatou引理等）给出充要条件，并以时间平均收益单样本数值模拟验证代表性博弈。
3.1 公平ZD策略的存在条件：通过理论证明，公平ZD策略存在当且仅当阶段博弈为针对该玩家的非平凡弱收益单调博弈；数值模拟中，焦点玩家采用公平ZD策略时其时间平均收益似收敛到1，而朋友收益为1。
3.2 不可战胜模仿策略的存在条件：通过必要性与充分性证明，IIB不可战胜当且仅当阶段博弈为强收益单调博弈，TFT亦同；弱收益单调博弈中IIB可被击败，强收益单调博弈中TFT与IIB不可战胜；数值模拟在随机行动条件下验证了TFT与IIB的不可战胜性。
3.3 不可战胜模仿作为ZD策略：通过理论证明，非平凡强收益单调博弈中TFT为公平ZD策略；IIB为ZD策略，单方面强制〈[s_j(a₂′)?s_j(a₁′)]I(s_j(a₁′)j(a₂′))〉^*=0（I(·)为示性函数），由此说明IIB的不可战胜性可由ZD收益控制解释。
3.4 Imitate-If-Better（IIB）策略的改进：通过定义ε-IIB（被击败时以概率ε随机抽样动作）并证明，在带专制动作博弈中ε-IIB几乎必然不可战胜；数值模拟显示，IIB可被朋友击败时，ε-IIB表现可与朋友相当。
讨论部分总结：公平ZD策略存在条件弱于不可战胜模仿条件，但“模仿朋友”情境下二者均强烈限制阶段博弈结构；弱/强收益单调博弈描述玩家可单方面获得最大收益的情境，似近乎无意义，但焦点玩家不完全知道收益函数而可观察朋友行动与收益时，结果仍有价值；探索可改善IIB；与强化学习中的ε-greedy不同，ε-IIB不包含学习；不可战胜模仿可解释为不可战胜ZD策略，扩展了“模仿对手”结果；公平ZD仅为一类，勒索型ZD策略（extortionate ZD strategies）等及更一般的不可战胜策略存在条件仍是开放问题；研究隐含完美监控、无观察误差等假设，未来需澄清观察误差、结构化种群、个体敏感性、环境波动、对称性及多于两个并行博弈等情形。研究结论（译）：研究人员的发现表明，即使在两个并行重复博弈情境中，不可战胜模仿与收益控制之间仍存在强关联。