博弈论学习笔记

· · 算法·理论

我们夏令营要每人讲一个知识点，然后就有了这篇文章。

0. 前置知识

纳什均衡（Nash equilibrium）：任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自身的收益。

帕累托最优（Pareto Optimality）：是指资源分配的一种理想状态，假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。

本次题目网址，密码 114514。

1. 博弈论

在生活中，我们常见几种游戏：

这几种游戏属于博弈游戏，属于博弈论（Game Theory），是经济学的一个分支。它主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。通俗地，它所研究的是在一个游戏中，进行游戏的多位玩家的策略。

上面列举的几个例子属于公平组合游戏（Impartial Game），一般具有以下特点：

当然还存在非公平组合游戏（Partizan Game），即游戏者在某一确定状态可以做出的决策集合与游戏者有关，信息不对等。大部分的棋类都属于非公平组合游戏，如五子棋、象棋、围棋等，以及一些卡牌游戏。

和公平组合游戏相反的，还有反常游戏（Misère Game），其获胜规则与公平组合游戏相反。如 Nim 游戏中取走最后一颗石子的为胜者，而反常 Nim 游戏中取走最后一刻石子的为败者。

本节讲述生活中最常见的博弈类型。当你没写作业的时候，你需要与老师对赌，猜老师会不会仔细检查你的作业；我们常用的最古老的游戏石头剪刀布也是一种博弈。但现在我们考虑一种比较困难的情况：囚徒困境博弈（Prisoner's Dilemma）。

现在有两个小偷 A 和 B 联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果两个犯罪嫌疑人都坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪，各被判刑 8 年；如果只有一个犯罪嫌疑人坦白，另一个人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑 2 年，而坦白者有功被减刑 8 年，即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱 1​​​ 年。

画表：

决策 A 坦白 A 抵赖
B 坦白 (8,8) (10,0)
B 抵赖 (0,10) (1,1)

从数学角度分析：

  1. 对 A 来说，尽管他不知道 B 作何选择，但他知道无论 B 选择什么，他选择“坦白”总是最优的。显然，根据对称性，B 也会选择“坦白”，这是纳什均衡。结果是两人都被判刑 8 年。
  2. 但是，倘若他们都选择“抵赖”，每人只被判刑 1​ 年。在四种行动选择组合中，【抵赖，抵赖】是较优的，属于帕累托最优，因为偏离这个行动选择组合的任何其他行动选择组合都至少会使一个人的境况变差。
  3. 但是，“坦白”是任一犯罪嫌疑人的占优战略，而 【坦白，坦白】是一个占优战略均衡。不难看出，此处与纳什均衡存在冲突。

然而人的行为活动错综复杂，所以囚徒困境只能作为简化模型参考，具体决策还得具体分析。

2. 巴什博弈

巴什博弈（Bash Game）是一个经典的博弈模型，其基本问题为：有一堆总数为 n 的物品，2 名玩家轮流从中拿取物品。每次至少拿 1 件，至多拿 m 件，不能不拿，最终将物品拿完者获胜。

引入策梅洛定理（Zermelo’s Theorem）：二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。由此可得巴什博弈属于一种公平组合游戏。

巴什博弈的必胜策略：在先取完者胜的巴什博弈中，若 n 可被 m+1 整除，则后手方必胜，否则先手方必胜。

证：可以采用 DP 思想，以数学归纳法证明。

首先考虑两种简单情形，我们称某一 n 的值是先手方或后手方的制胜位置，是指此 n 值下先手方或后手方有必胜策略：

下面我们考虑所有的 n，设 n=k\times(m + 1)+r，其中 0\le r<m+1。由带余数除法可知，满足上面条件的整数 k 与 r 是唯一的。仍分为两种情形讨论：

整理得证。

另外，当先手有必胜策略时，第一轮拿取的石子数一定，为 n\bmod (m+1)。接下来两名玩家每轮拿取的石子数量之和为 m+1。请自行证明。

3. Nim 博弈

Nim 博弈（Nim Game）是一种经典的博弈游戏，其基本形式如下：地上有 n 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。

根据策梅洛定理，这是一个公平组合游戏，因此存在必胜方和必败方。先引出其获胜条件：当 n 堆石子的数量异或结果为 0 时，后手必胜；否则先手必胜。

证：我们把每一轮博弈视作树上的一个节点，形成一棵博弈树（Game Tree）。每个节点的后继表示该节点的递归方式。例如：

易见 0 可以向 1 和 2 转移。现在考虑什么时候 0 这个状态是必胜的？

注意，必胜是对于当前这个状态是必胜的，与是谁无关，赢的人只是处于一个胜的状态而已。

现在看实际问题：我们要得到 0 这个数，那么当你取完时还剩 0​ 个，你就显然是胜的。然后再通过最后的这个显然的必胜状态，往前递推找出其余的必胜状态。显然博弈论是必然会出现循环节的，因为它是一种不断递归求解的过程，每次都可以取到当前这个循环节上的必胜状态，并且让你的对手能达到的下个状态全部都是必败状态，那样就稳了。

考虑子问题，当 n=1 的时候显然是先手必胜，因为直接全部取掉就好，可以理解成 {a_1} \oplus 0；当 n=2 的情况就考虑一堆的石头和另一堆相不相等，可以理解为 a_1\oplus a_2。显然，最后结果若是 0，则后手必胜，否则前手必胜。

现在扩展到 n，最终获胜式子为 0\oplus0\oplus0\oplus0=0，其最初状态为 a_1 \oplus a_2 \oplus a_3 \oplus a_4=s（s 为任意正整数）。由于一个数异或上它自己，答案肯定是 0。尝试转移为：s\oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4=0。设 s 的最高位为 s_k，如果 s_k 的位数要高于 s 那么它前面高出的那几位是不会变的，在第 k 位上，s_k\oplus s 得到的答案应该是 0；又因为 s_k 的前几位不变，第 k 位从 1 变成了 0 ，所以它是变小了的，这满足了每次从一堆数中取出部分(将原数减小)的要求。也满足了将任意 a_1 \oplus a_2 \oplus a_3 \oplus a_4=s 转移成 a_1 \oplus a_2 \oplus a_3 \oplus a_4=0 。

如何，你不断的将异或和变成 0 ，别人只能被动的把异或和变成 s ，又因为最后获胜的时异或和要为 0 ，所以不断取 0​ 的时必胜的。

整理得证。

4. 推荐题目

CodeForces 533C：Board Game

题目大意：A 和 B 各执一枚棋子，位置分别是 (x_a,y_a) 和 (x_b,y_b)。A 可以向左向上走，B 可以向左向上向左上走，位置不能重叠，每次可以选择走或不走，先到 (0,0) 的获胜。

题解：热身题，没有涉及任何博弈论知识，纯手推。A 可以往左或下走，而 B 能往左，下或左下走。可以分类讨论：

  1. A 的 x 和 y 加起来没有 B 的 x 大，A 赢。

  2. A 的 x 和 y 加起来没有 B 的 y 大，A 赢。

  3. A 的 x 和 y 没有对手的 x 和 y 大，A 赢。

  4. 其余 B 赢。

HDU 1846：Brave Game

题目大意：两个人轮流取 1\sim m 颗石子，先取完 n 颗石子的人获胜。

题解：巴什博弈板子题，不多说。上代码：

if(n % (m + 1) == 0) cout << "second";
else cout << "first";

HDU 4764：Stone

题目大意：两人在白板上写数字，若一个人写了数字 x，则第二个人写的数字 y 要满足 1 \le y\ –\ x \le k，且第一次写的数字要满足在 [1,k] 内，先写到数字 N​ 的人输。

题解：转换一下，有 N 个石子，每次只能取 1\sim k 个，先取完的输。这和巴什博弈不同，是一种变形，称为反常游戏（Misère Game），这么考虑：假设我们有 n-1 个石子，如果后手能取完 n-1 个石子，那么下一个人必须取走最后一个石子，所以后手必胜，所以取走 n 个石子，取完胜的后手必胜条件等价于取走 n-1 个石子，取完输的后手必胜条件 (n-1)\bmod(m+1)=0 则后手必胜。

POJ 2368：Buttons

题目大意：给定一堆石头共 k 个，每人轮流拿 1\sim L 个石头，求出最小的 L 使后者存在必胜策略。

题解：典型的巴什博弈。首先想让后手胜，就必须把 L+1 的局面留给先手。这题没问我们谁会赢，问的是后手要赢的最小 L 值为多少。那我们就找到能被 k 整除的最小大于 2 的因数，之后减 1​ 就是答案了。

洛谷 P2197：Nim 游戏

题目大意：地上有 n 堆石子（每堆石子数量小于 10^4），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，他想知道是否存在先手必胜的策略。

题解：Nim 博弈板子题，不多说。上代码：

int ans = 0;
for(int i = 1;i <= n;i++){
    int t; cin >> t;
    ans ^= t;
}
if(ans) cout << "Yes\n";
else cout << "No\n";

POJ 2975：Nim

题目大意：给定 n 堆石子，分别有 a_1,a_2,a_{\ldots},a_n 个，问有多少种方法使得第一次操作是必胜决策。

题解：求出异或值 x=a_1\oplus a_2\oplus \ldots \oplus a_n，因而有 x\oplus a_1\oplus a_2\oplus \ldots \oplus a_n=0，依次组合 x 和每个 a_i。然而对于 a_i，取之后必然越来越小，所以要 a_i\oplus x<a_i 即可将 a_i 变成 a_i\oplus x，拿去 a_i−(a_i\oplus x) 个棋子。 统计满足 a_i\oplus x<a_i​ 的个数即可。

CodeForces 731E：Funny Game

题目大意：一个长度为 N 的序列 a_i ，双方轮流操作。每次的操作是选择一个长度大于 1 的前缀，计算它的和 s ，然后用 s 替换它的前缀，同时当前玩家获得 s​​ 的分数。当只剩下一个元素时，游戏结束。双方均想最大化自己的分数-对手的分数，计算这个值。

题解：我们不关心谁是先手谁是后手，只关注分差。令 dp_i 表示从后往前第 i 位的最大得分差，则有：

dp_i=\max_{j\in[i+1,n]}\{pre_j-dp_j\}

计算前缀和，dp 序列转移即可。

5. 应试技巧

对于博弈问题，常见几个字眼：

博弈论常与以下知识点联考：