Codeforces 98E DP 博弈论 纳什均衡

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. 询问一张自己没有手牌,称为“询问”。
  2. 若后手持有该牌即选择信任,则先手收益为 $ {m\over m+1}(1-f_{m-1,n}) $ ;
  3. 若后手没有该牌但选择信任,则后手胜,先手收益为 $ 0 $ ;
  4. 若没有该牌且不信任,则相当于先手在下一轮获得胜利,那么收益将加上 $ 1\over m+1 $ .
  5. 询问一张有的手牌,则称为“欺骗”。
  6. 若后手信任,则必错,先手收益 $ 1 $ ;
  7. 否则先手相当于丢弃一张牌。

收益矩阵如下
$$
\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

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu