学习心得 - 数学 - 博弈论

· · 算法·理论

定义

博弈有以下几种：

  1. 合作博弈
  2. 对称博弈
    • 收益是否对称。
  3. 零和博弈
    • 收益是否互补。
  4. 顺序博弈
    • 顺序区别。
  5. 完美博弈
    • 是否知道全部信息。
  6. 信息博弈
    • 是否知道规则信息。

一般解决的是非完美信息博弈，也就是 Alice 和 Bob 玩游戏。

博弈图

感性理解：一个决定胜负的图。具体的，对于每一个博弈状态，与其后继状态连边，形成的图就是博弈状态图。要是一个状态连向必败点，那么这个状态就必胜（令对手必败），反之必败。

Nim 游戏

博弈：n 堆石头每堆 a_i 个，必须取。取最后一个的人赢。

结论：异或值为 0 先手败否则必胜。

把 Nim 游戏对应到博弈图上就是异或值不为 0 可以变成 0。而异或值变 0 一定会变为非 0，读者自证不难。所以结论成立。

SG 函数 / 有向图博弈

博弈：在一个有向图上推石子，推不动的玩家失败。

你会发现这个东西本质就是在一个博弈图上走。这个就是最基本的博弈类型。

结论：定义 \operatorname{SG}(x)=\operatorname{mex}_{y\in nxt_x} \operatorname{SG}(y)。当博弈图起点（开始状态）的 \text{sg} 值全部异或等于 0，那么先手必胜，否则必败。

威佐夫博弈

经典博弈，需要使用黄金分割数。

(b-a)\frac{1+\sqrt{5}}{2}=a

时先手必败。