济源建网站,如何做网络推广员,网站空间商是什么意思,网课营销方案problem
洛谷链接
solution
纳什均衡 是博弈论中一种解的概念#xff0c;它是指满足下面性质的策略组合#xff1a;任何一位玩家在此策略组合下单方面改变自己的策略#xff0c;其他玩家策略不变#xff0c;都不会提高自身的收益。
一个策略组合被称为纳什均衡当且仅当…problem
洛谷链接
solution
纳什均衡 是博弈论中一种解的概念它是指满足下面性质的策略组合任何一位玩家在此策略组合下单方面改变自己的策略其他玩家策略不变都不会提高自身的收益。
一个策略组合被称为纳什均衡当且仅当每个博弈者的均衡策略都是为了达到自己期望收益的最大值。
纳什博弈是一种非合作博弈均衡。
通俗地讲是个人主义只考虑增加自身的收益而忽略甚至往往会损害团队性收益。
以上只是本题的题目背景。
首先要明确当不知道桌上牌真的是什么的时候是不会直接猜测的。
因为这样会直接结束游戏。或者说如果现在就猜假设对方手中还有 kkk 张牌未知获胜的概率只有 1k1\frac 1 {k1}k11不如让给对方猜。到游戏最后胜败概率都是 12\frac 1 221。
定义 f(x,y):f(x,y):f(x,y): 先手有 xxx 张牌对方未知后手有 yyy 张牌对方未知此时先手的收益 / 获胜概率。
注意全文的“先手”仅指当前局面谁是操作者是相对而言的。并非游戏一开始的指定先后手。
这道题很切合实际因为先手的策略是存在欺诈的而后手也有是否相信的考虑。所以涉及到更多情况的讨论。 先手老实询问的是不属于自己手上的牌即后手的 yyy 张牌以及桌上的 111 张牌。 后手相信。 先手询问的牌有 yy1\frac {y}{y1}y1y 概率后手有那么后手将会明牌未知牌数 −1-1−1。 交换后的先手/下一个局面先手 获胜概率就为 f(y−1,x)f(y-1,x)f(y−1,x)。 则当前局面先手获胜概率即为 yy1(1−f(y−1,x))\frac{y}{y1}\Big(1-f(y-1,x)\Big)y1y(1−f(y−1,x))。 先手询问的牌有 1y1\frac 1{y1}y11 概率后手没有。 那么因为相信先手后手就会以为这张牌先手也没有就只能是桌上的牌了。 下一局直接猜猜对了。 当局的先手就输了。收益为 0⋅1y10·\frac{1}{y1}0⋅y11。 总收益 :yy1(1−f(y−1,x)):\frac{y}{y1}\Big(1-f(y-1,x)\Big):y1y(1−f(y−1,x))。 后手不信。 先手询问的牌有 yy1\frac {y}{y1}y1y 概率后手有。 收益还是 yy1(1−f(y−1,x))\frac{y}{y1}\Big(1-f(y-1,x)\Big)y1y(1−f(y−1,x))。 先手询问的牌有 1y1\frac 1{y1}y11 概率后手没有。 因为不信后手就不会猜这张牌并且认为先手爆了一张明牌。 但是后手也不会丢牌所以在先手这里就真的知道桌上牌了。 下一轮后手随便操作后又交换回来顺序先手就会直接叫牌。 收益为 1⋅1y11·\frac{1}{y1}1⋅y11。 总收益 :yy1(1−f(y−1,x))1y1:\frac{y}{y1}\Big(1-f(y-1,x)\Big)\frac{1}{y1}:y1y(1−f(y−1,x))y11。 说明因为先手叫的是后手手中明确有的牌不管后手信不信都是一样的局面(后手明牌了一张)一样的收益。 这里只是硬性分类讨论而言。毕竟在现实中如果先手叫的牌是后手有的这还能说不信吗。 先手狡猾欺诈后手即询问的是一张自己手里有的牌。 后手相信。 后手会直接认为这张牌就是桌上的牌因为自己没有而先手是老实人。 后手下一局做先手就会直接猜测结果猜错。 那么下一局的后手即本局的先手就会获得胜利。 收益为 111。 后手不信。 相当于先手自爆了一张明牌后手接下来面临的局面胜率就是 f(y,x−1)f(y,x-1)f(y,x−1)。 所以本局先手的胜率为 1−f(y,x−1)1-f(y,x-1)1−f(y,x−1)。
我们可以形象地做个表格出来看。
后手选择/先手收益/先手操作先手老实先手狡猾后手相信yy1(1−f(y−1,x))\frac{y}{y1}\Big(1-f(y-1,x)\Big)y1y(1−f(y−1,x))111后手不信yy1(1−f(y−1,x))1y1\frac{y}{y1}\Big(1-f(y-1,x)\Big)\frac{1}{y1}y1y(1−f(y−1,x))y111−f(y,x−1)1-f(y,x-1)1−f(y,x−1)
假设先手老实操作的概率为 ppp狡猾操作的概率为 1−p1-p1−p。
令 ayy1(1−f(y−1,x)),b1,ca1y1,d1−f(y,x−1)a\frac{y}{y1}\Big(1-f(y-1,x)\Big),b1,ca\frac{1}{y1},d1-f(y,x-1)ay1y(1−f(y−1,x)),b1,cay11,d1−f(y,x−1)。
根据纳什博弈的定义后手怎么操作的对应收益是不变的先手也不会改变。
即p∗a(1−p)∗bp∗c(1−p)∗d⇒pd−ba−cd−bp*a(1-p)*bp*c(1-p)*d\Rightarrow p\frac{d-b}{a-cd-b}p∗a(1−p)∗bp∗c(1−p)∗d⇒pa−cd−bd−b。
先手收益为 p∗a(1−p)∗bp*a(1-p)*bp∗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;
}
