1 (分钱)两人之间分\(10\)。使用下述方法:每个人说出一个至多为10的数字(非负整数)。如果两人说出的数字之和不超过10，那么每个人得到她所说出的钱数(多出的钱被销毁)，如果两人提出的数字之和超过10并且数目不同，那么说出较小数的人得到自己所说的钱数，而另一个人则得到剩余的钱。如果两数之和超过10并且两数相等，那么每个人各自得到\(5\)。确定每个局中人关于另一个局中人每个行动的最优反应，从而求得博弈的纳什均衡。
| 最优反应函数 | 纳什均衡 |
|---|---|
 |
 |
2 Cournot's duopoly game with linear inverse demand and different unit costs Following the analysis in the text, the best response function of firm 1 is
while that of firm 2 is
To find the Nash equilibrium, first plot these two functions. Each function has the same general form as the best response function of either firm in the case studied in the text. However, the fact that \(c_1 \neq c_2\) leads to two qualitatively different cases when we combine the two functions to find a Nash equilibrium. If \(c_1\) and \(c_2\) do not differ very much then the functions in the analogue of Figure 59.1 intersect at a pair of outputs that are both positive. If \(c_1\) and \(c_2\) differ a lot, however, the functions intersect at a pair of outputs in which \(q_1=0\).
Precisely, if \(c_1 \leq \frac{1}{2}\left(\alpha+c_2\right)\) then the downward-sloping parts of the best response functions intersect (as in Figure 59.1), and the game has a unique Nash equilibrium, given by the solution of the two equations
This solution is
If \(c_1>\frac{1}{2}\left(\alpha+c_2\right)\) then the downward-sloping part of firm 1's best response function lies below the downward-sloping part of firm 2's best response function (as in Figure 12.1), and the game has a unique Nash equilibrium, \(\left(q_1^*, q_2^*\right)=\) \(\left(0, \frac{1}{2}\left(\alpha-c_2\right)\right)\).
In summary, the game always has a unique Nash equilibrium, defined as follows:
The output of firm 2 exceeds that of firm 1 in every equilibrium.
3 巴什博弈
巴什博弈属于基本的博弈问题，其典型特征为：给定\(n\)堆物品，两个人轮流从这堆物品中取物品，规定每次最少取1个，最多取\(m\)个，最后取光者为胜。
当\(n=m+1\)时，由于一次最多只能取\(m\)个，所以无论先取者拿走多少个，后取者都能一次拿走剩余的物品，后取者取胜；当\(n=(m+1)×r+s\)（其中\(r\)为任意自然数，\(s \leq m\))，如果先取者要取走\(s\)个物品，如果后取者取走\(x(x \leq m)\)个，那么后取者只要取走\(m+1−k\)个，结果剩下\((m−1)(r−1)\)个，以后保持这样的取法，那么先取者肯定获胜，总之，要保持给对手留下 \((m+1)\)的倍数，就能最后获胜。
结论1：若\((m+1)∣n\)，则先手必败，否则先手必赢。
结论2：当\((n−1)\%(m+1)=0\)时先手必输。
4 威佐夫博弈
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
如何解决威佐夫博弈问题？
首先，我们定义\((a_i, b_i) \\ (a_i \leq b_i, i = 1, 2, ..., n)\)表示两堆物品的数量并称其为局势，如果甲面对\((0,0)\)，那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势，前几个奇异局势为\((0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)\)。任意给定一个局势\((a,b)\)，如下公式可以判断其是否为奇异局势：
\(a_k = \lfloor \frac {k \times (1 + \sqrt{5})}{2} \rfloor, \\ b_k = a_k + k \\ (k = 0, 1, 2, ..., n)\)
面对非奇异局势，先手必胜；面对奇异局势，先手必败。
5 斐波那契(Fibonacci)博弈
斐波那契博弈的典型特征是：给定一堆个数为n nn的石子，两个玩家轮流取石子，满足：先手不能在第一次把所有的石子取光；第一次取完后的每次可以取得石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)；取走最后一个石子的人为玩家。
如何解决这一类博弈问题？
首先先给出结论：当\(n\)为斐波那契数的时候，先手必败，即存在先手的必败态当且仅当石头个数为Fibonacci数。
下面给出证明：
根据“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。如n = 83 = 55 + 21 + 5 + 2 n=83 = 55+21+5+2n=83=55+21+5+2，我们看看这个分解有什么指导意义：假如先手取2颗，那么后手无法取5颗或更多，而5是一个Fibonacci数，那么一定是先手取走这5颗石子中的最后一颗，同理，接下去先手取走接下来的后21颗中的最后一颗，再取走后55颗中的最后一颗，那么先手赢。
反证：如果\(n\)是Fibonacci数，如n = 89 n=89n=89：记先手一开始所取的石子数为\(y\)
（1）若\(y \geq 34\)颗（也就是89的向前两项），那么一定后手赢，因为89−34=55=34+21<2∗34。
（2）若\(y<34\)时剩下的石子数\(x\)介于55到89之间，它一定不是一个Fibonacci数，把\(x\)分解成Fibonacci数：\(x=55+f[i]+…+f[j]\)，若，如果\(f[j]<=2y\)，那么对B就是面临\(x\)局面的先手，所以根据之前的分析，后手只要先取\(f[j]\)个即可，以后再按之前的分析就可保证必胜。
判断斐波那契数的方法可以采用通项公式法或遍历法。如果数据范围大会卡时间则考虑矩阵快速幂优化等。
6 Nim博弈
Nim游戏是一个典型的博弈问题，建立在Nim游戏基础上的博弈一般都具有相同的框架特征。
\(n\)堆物品，每堆有\(a_i\)个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。取走最后一个物品的人获胜。
例如，如果现在有\(n=3\)堆物品，而每堆分别有2,5,4 个，那么可以取走第1堆中的2个物品，局面就变成了0,5,4；或者也可以取走第2堆的4个物品，局面就变成了2,1,4。如果现在的局面为0,0,5，甲取走了第3堆的5个物品，也就是取走了最后一个物品，此时甲获胜。
首先回顾“博弈图”。我们通过绘画博弈图，可以在 \(O\left(\prod_{i=1}^n a_i\right)\) 的时间里求出该局面是否先手必赢。
显然，这样的推导方式时间复杂度是非常高的，我们需要换一种思路进行推导。
定义 \(\operatorname{Nim}\) 和 \(=a_1 \oplus a_2 \oplus \ldots \oplus a_n\)。那么当且仅当 Nim 和为 0 时，该状态为必败状态；否则该状态为必胜状态。
如何证明Nim和的正确性? 为什么异或值会和和状态的胜负有关?
为了证明该定理，只需要证明下面三个定理:
定理 1: 没有后继状态的状态是必败状态。
定理 2: 对于 \(\mathrm{a}_1 \oplus \mathrm{a}_2 \oplus \ldots \oplus \mathrm{a}_{\mathrm{n}} \neq 0\) 的局面，一定存在某种移动使得 \(\mathrm{a}_1 \oplus \mathrm{a}_2 \oplus \ldots \oplus \mathrm{a}_{\mathrm{n}}=0\) 。
定理 3 : 对于 \(\mathrm{a}_1 \oplus \mathrm{a}_2 \oplus \ldots \oplus \mathrm{a}_{\mathrm{n}}=0\) 的局面，一定不存在某种移动使得 \(\mathrm{a}_1 \oplus \mathrm{a}_2 \oplus \ldots \oplus \mathrm{a}_{\mathrm{n}}=0\)
对于 定理 1 ，没有后继状态的状态只有一个，即全 0 局面。此时 \(\mathrm{a}_1 \oplus \mathrm{a}_2 \oplus \ldots \oplus \mathrm{a}_{\mathrm{n}}=0\) 。
对于 定理 2 ，不妨假设 \(a_1 \oplus a_2 \oplus \ldots a_n=k \neq 0\) 。如果我们要将 \(a_i\) 改为 \(a_i^{\prime}\) ，则 \(a_i^{\prime}=a_i \oplus k\) 。 \(\mathrm{k}\) ，因而这也是个合法的移动。
对于 定理 3 ，如果我们要将 \(a_i\) 改为 \(a_i^{\prime}\) ，则根据异或运算律可以得出 \(a_i=a_i^{\prime}\) ，因而这不是个合法的移动。