Codeforces 98E DP 博弈论 纳什均衡

A 有 $n$ 张牌,B 有 $m$ 张牌,桌上还有一张反扣着的牌,牌的编号在 $ [1, n + m + 1] $ 之间且互不相同。用这些牌进行博弈,每轮每人可以进行如下操作中的一个:

  • 猜桌面上的反扣着的牌上的数字,猜对则获得胜利,猜错则对方胜利。
  • 询问对方是否有某张牌,若拥有则对方需要出示这张牌,否则继续游戏。

若A 和B 都绝顶聪明,求A 的胜率。

$ n, m \le 1000 $ .

Sol.

十分复杂的博弈。我们考虑分类讨论先手后手各自的策略。记 $ f_{n,m} $ 为先手剩 $ n $ 后手剩 $ m $ 的先手胜率。

边界值 $ f_{0,m}={1\over m+1}, f_{n,0}=1 $ .

首先先手在两方都有剩牌的时候去猜桌面的牌,显然 suboptimal.

那么先手可以

  1. 询问一张自己没有手牌,称为“询问”。

    1. 若后手持有该牌即选择信任,则先手收益为 $ {m\over m+1}(1-f_{m-1,n}) $ ;
    2. 若后手没有该牌但选择信任,则后手胜,先手收益为 $ 0 $ ;
    3. 若没有该牌且不信任,则相当于先手在下一轮获得胜利,那么收益将加上 $ 1\over m+1 $ .
  2. 询问一张有的手牌,则称为“欺骗”。

    1. 若后手信任,则必错,先手收益 $ 1 $ ;
    2. 否则先手相当于丢弃一张牌。

收益矩阵如下

$$ \begin{matrix} &\text{信任} & \text{不信任} \\ \text{询问} &{m\over m+1}(1-f_{m-1,n}) &{1\over m+1}+{m\over m+1}(1-f_{m-1,n}) \\ \text{欺骗} &1 & 1-f_{m,n-1} \end{matrix} $$

设 $ p $ 为先手询问而非欺骗的概率,注意到这是一个 zero-sum game ,则必存在一个混合策略 Nash Equilibrium ,由此知当两方胜率相等时进入均衡点,此时胜率必为这个取值。

从另一个角度我们也可以得到这一点,因为我们知道先手要最大化后手要最小化胜率,则有

$$ \max_p\min \{{m\over m+1}(1-f_{m-1,n})\times p+(1-p),({1\over m+1}+{m\over m+1}(1-f_{m-1,n}))\times p+(1-f_{m,n-1}\times(1-p)\} $$

和 Nash Equilibrium 得到的结果一样,不必多说。这在博弈论里的一般化结果称为 minimax theorem.

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1000 + 10;
const double eps = 1e-7;
double f[maxn][maxn];
void dfs(int n, int m)
{
    if(f[n][m] > eps) return;
    if(m == 0) {f[n][m] = 1; return;}
    if(n == 0) {f[n][m] = 1. / ((double)m + 1); return;}
    dfs(m, n - 1); dfs(m - 1, n);
    double p = (m + 1) * f[m][n - 1] / ((double)(m + 1) * f[m][n - 1] + 1);
    f[n][m] = p * (double)m * (1.0 - f[m - 1][n]) / ((double)m + 1) + (1.0 - p);
}
int main()
{
    int n, m; read(n, m);
    dfs(n, m);
    printf("%.15lf %.15lf\n", f[n][m], 1. - f[n][m]);
    return 0;
}

标签: none

添加新评论