problem

洛谷鏈接

solution

納什均衡 是博弈論中一種解的概念，它是指滿足下面性質的策略組合：任何一位玩家在此策略組合下單方面改變自己的策略，其他玩家策略不變，都不會提高自身的收益。

一個策略組合被稱為納什均衡當且僅當每個博弈者的均衡策略都是為了達到自己期望收益的最大值。

納什博弈是一種非合作博弈均衡。

通俗地講，是個人主義，只考慮增加自身的收益而忽略甚至往往會損害團隊性收益。

以上只是本題的題目背景。

首先要明確，當不知道桌上牌真的是什么的時候，是不會直接猜測的。

因為這樣會直接結束游戲。或者說，如果現在就猜，假設對方手中還有 $k$ 張牌未知，獲勝的概率只有 $\frac{1}{k+1}$，不如讓給對方猜。到游戲最后勝敗概率都是 $\frac{1}{2}$。

定義 $f(x,y):$ 先手有 $x$ 張牌對方未知，后手有 $y$ 張牌對方未知，此時先手的收益 / 獲勝概率。

注意：全文的“先手”僅指當前局面誰是操作者，是相對而言的。并非游戲一開始的指定先后手。

這道題很切合實際，因為先手的策略是存在欺詐的，而后手也有是否相信的考慮。所以涉及到更多情況的討論。

• 先手老實：詢問的是不屬于自己手上的牌，即后手的 $y$ 張牌以及桌上的 $1$ 張牌。

  • 后手相信。

    • 先手詢問的牌有 $\frac{y}{y+1}$ 概率后手有，那么后手將會明牌，未知牌數 $?1$。

      交換后的先手/下一個局面先手 獲勝概率就為 $f(y?1,x)$。

      則當前局面先手獲勝概率即為 $\frac{y}{y+1}(1?f(y?1,x))$。

    • 先手詢問的牌有 $\frac{1}{y+1}$ 概率后手沒有。

      那么因為相信先手，后手就會以為這張牌先手也沒有，就只能是桌上的牌了。

      下一局直接猜，猜對了。

      當局的先手就輸了。收益為 $0?\frac{1}{y+1}$。

    總收益 $:\frac{y}{y+1}(1?f(y?1,x))$。

  • 后手不信。

    • 先手詢問的牌有 $\frac{y}{y+1}$ 概率后手有。

      收益還是 $\frac{y}{y+1}(1?f(y?1,x))$。

    • 先手詢問的牌有 $\frac{1}{y+1}$ 概率后手沒有。

      因為不信，后手就不會猜這張牌，并且認為先手爆了一張明牌。

      但是后手也不會丟牌，所以在先手這里就真的知道桌上牌了。

      下一輪后手隨便操作后又交換回來順序，先手就會直接叫牌。

      收益為 $1?\frac{1}{y+1}$。

    總收益 $:\frac{y}{y+1}(1?f(y?1,x))+\frac{1}{y+1}$。

  說明：因為先手叫的是后手手中明確有的牌，不管后手信不信，都是一樣的局面(后手明牌了一張)，一樣的收益。

  這里只是硬性分類討論而言。畢竟在現實中如果先手叫的牌是后手有的，這還能說不信嗎。

• 先手狡猾：欺詐后手，即詢問的是一張自己手里有的牌。

  • 后手相信。

    后手會直接認為這張牌就是桌上的牌，因為自己沒有，而先手是老實人。

    后手下一局做先手就會直接猜測，結果猜錯。

    那么下一局的后手，即本局的先手，就會獲得勝利。

    收益為 $1$。

  • 后手不信。

    相當于先手自爆了一張明牌，后手接下來面臨的局面勝率就是 $f(y,x?1)$。

    所以本局先手的勝率為 $1?f(y,x?1)$。

我們可以形象地做個表格出來看。

后手選擇/先手收益/先手操作先手老實先手狡猾

后手相信	$\frac{y}{y+1}(1?f(y?1,x))$	$1$
后手不信	$\frac{y}{y+1}(1?f(y?1,x))+\frac{1}{y+1}$	$1?f(y,x?1)$

假設先手老實操作的概率為 $p$，狡猾操作的概率為 $1?p$。

令 $a=\frac{y}{y+1}(1?f(y?1,x)),b=1,c=a+\frac{1}{y+1},d=1?f(y,x?1)$。

根據納什博弈的定義，后手怎么操作的對應收益是不變的，先手也不會改變。

即：$p?a+(1?p)?b=p?c+(1?p)?d?p=\frac{d?b}{a?c+d?b}$。

先手收益為 $p?a+(1?p)?b$。

code

#include <bits/stdc++.h> using namespace std; #define double long double #define eps 1e-10 #define maxn 1005 int n, m; double f[maxn][maxn];double dfs( int x, int y ) {if( ! x ) return 1.0 / (y + 1);if( ! y ) return 1.0;if( f[x][y] ) return f[x][y];double a = y * 1.0 / (y + 1) * (1 - dfs( y - 1, x ));double b = 1.0;double c = 1.0 / (y + 1) + a;double d = 1.0 - dfs( y, x - 1 );double p = (d - b) / (a - c + d - b);return f[x][y] = p * a + (1 - p) * b; }int main() {scanf( "%d %d", &n, &m );printf( "%.10Lf %.10Lf\n", dfs( n, m ), 1 - dfs( n, m ) );return 0; }

總結

以上是生活随笔為你收集整理的CF98E Help Shrek and Donkey（纳什博弈 + 大讨论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。