CF98E Help Shrek and Donkey

博主： tony102
发布时间：2021 年 11 月 08 日
2062 次浏览
暂无评论
2744字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF98E)

## Sol

入门纳什均衡。联考题里面别人介绍的一种方法，就是说假如两个人以上的一个非合作博弈中，每个人都知道对方的每一个策略的收益，并且每一个人都做出最符合自己利益的情况的决策，无一参与者可以“独自行动”（即单方面改变决定）而增加收获时的策略就是纳什均衡点。求出纳什均衡点是 NP-完全的，在参与者匿名的情况下，则仅需多项式时间即可逼近纳什均衡。

回到本题。现在 A 有 $n$ 张牌，$B$ 有 $m$ 张牌，牌山里只有一张牌。假如先手根本就不问 B，上来直接猜，那么猜中的概率是 $\frac{1}{m+1}$ 。 很显然，然而只有青铜这么做，因为只要对方的牌还没有空，那么通过“指定”操作，仍然可以保持 $\frac{1}{m+1}$ 的胜率并且知道对方一张牌使得概率提升。

设 $f(n,m)$ 表示先手有 $n$ 张牌，后手有 $m$ 张牌时，先手胜的概率。每次的收益就是获得的概率提升。注意，这里的先后手并非常规博弈意义下的先后手必胜的那种，仅仅用于描述当前操作的人是谁（相对关系），~~可能大家都懂，但是这里我卡了一下子才绕过来，只有青铜实锤了~~。假如 A 现在是先手， A 此时会问 B 一张自己手中没有的牌。假如 B 手中有这张牌，那么 B 会鸣出这张牌，先后手交换。那么 A 获得的收益即为：$\frac{m}{m+1} (1 - f(m - 1, n))$ （有 $\frac{m}{m+1}$ 的概率猜的牌在 B 手中，将牌鸣出且交换了以后的先手不胜的概率为 $1 - f(m-1,n)$）；若 B 手中没有这张牌，则 B 认为 A 问的牌就是牌山里唯一的牌，A 的收益为 $\frac{1}{m+1} \cdot 0$ 。

~~如果以为这就完了，那可能连白银都打不过。~~

A 现在不仅可以问 B 自己手中没有的牌，还可以诈 B 一手：问自己手中有的牌，让 B 迷雾。感觉这是这题比较有趣的一个地方。现在情况发生了改变，我们来梳理一下加上这种情况后会发生什么。

原先的情况依然可能发生。我们称 A 不诈 B （即问自己手中有的牌）的情况叫做以和为贵，诈 B 的情况叫做不讲武德。同时 B 也可以选择相信 A 不诈和诈两种情况，分别称做相信和不信。下面通过一个表格 $w$ 来说明 A 的收益情况并解释：

| 后手\先手 |       以和为贵（不诈）       |    不讲武德（诈他）     |
| :-------: | :--------------------------: | :---------------------: |
|   相信    |   $0 \cdot \frac{1}{m+1}$    | $1 \cdot \frac{1}{m+1}$ |
|   不信    | $\frac{m}{m+1} (1-f(m-1,n))$ |     $1 - f(m,n-1)$      |

原先分析的不诈的情况就是第二列。现在分析第三列。

假如 A 诈 B，可是 B 仍然相信 A 没有在诈，则 B 相信 A 没有这张牌即该牌在牌山里，错误，那么 A 再次操作的时候必胜。则猜中这张牌的概率为 $\frac{1}{m+1}$ 必胜概率为 $1$ ，乘在一起就是 $1 \cdot \frac{1}{m+1}$。

如果 B 没有相信 A（认为 A 在诈），那么 B 会回答没有且不会鸣出任何牌。相当于此时 A、B 先后手转换，且 A 损失一张牌。即 $1 - f(m,n-1)$。

同时注意边界情况，当 $m = 0$ 时先手必知牌山里的牌，胜率 $1$ ；当 $n=0$ 时，先手不猜则先后手转换后先手变成后手且必败，胜率为 $0$

此时引入纳什均衡，设 A 有 $p$ 的概率以和为贵，$1-p$ 的概率不讲武德。纳什均衡就是要在该决策的情况下，无论怎么样获得的收益都均衡（不动点）。即：

$$
p \cdot w_{1,1} + (1-p) \cdot w_{2,1} = p \cdot w_{1,2} + (1-p) \cdot w_{2,2}
$$

移项即可解得：$p = \frac{w_{2,2} - w_{2,1}}{w_{1,1}-w_{2,1}-w_{1,2}+w_{2,2}}$

每次转移就是：$f_{n,m} = w_{1,1} \cdot p + (1 - p) \cdot w_{2,1}$

## Idea

这种决策带概率的属于混合策略的纳什均衡。如果决策不依靠概率，则为纯策略型的纳什均衡。

一般就是有一些决策的概率是需要确定的，且决策后的收益可以算。这个时候要求确定的一个值（纳什均衡点）使得每一个决策方获得收益都不会在变（即达到均衡）。

很有意思的一个算法。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e3 + 5;

int m, n;
double f[SIZE][SIZE];

double dp(int x, int y) {
    if (f[x][y]) return f[x][y];
    if (!y) return f[x][y] = 1.000;
    if (!x) return f[x][y] = 1.000 / (y + 1);
    double w11 = 1.000 * y / (y + 1) * (1.000 - dp(y - 1, x)), w21 = 1.000,
    w12 = w11 + 1.000 / (y + 1), w22 = 1.000 - dp(y, x - 1);
    double p = (w21 - w22) / (w12 + w21 - w11 - w22);
    return f[x][y] = p * w11 + (1.000 - p) * w21;
}

int main() {
    scanf("%d %d", &m, &n);
    double p = dp(m, n);
    printf("%.10lf %.10lf\n", p, 1.000 - p);
    return 0;
}
```

最后修改：2021 年 11 月 08 日