CF98E

CF98E Help Sherk and Donkey

Description

有一副互不相同的牌共 张。有两个人，第一个人 张，第二个人 张。另外有一张牌放在桌子上。

两个人玩游戏轮流操作（其中第一个人为先手）。有如下 种操作类型：

1. 猜测：猜桌上的那张牌是什么。如果猜对了则获胜，猜错了则失败。操作完之后游戏结束。

2. 指定：报一张牌的名字，如果对方手上有这张牌，则将该牌丢弃，游戏继续；如果对方手上没有这张牌，对方则会表示他不拥有此牌。

现在假设两个人都知道这 张牌分别是什么，但是不知道桌上和对方手里的牌具体是什么。

若双方都采取最优策略进行游戏，问先手和后手获胜概率。

。

Sol

纳什均衡入门题。

定义 为先手有 张牌，后手有 张牌，先手的胜率。

那么先手可以干两件事：报一张自己有的牌或者自己没有的牌。

下文称报自己有的牌是lie，报自己没有的牌是ask。

后手也可以干两件事：认为先手在lie或者ask。

大力分讨一下：

• 先手报ask，后手有这张牌：概率 ，后手弃掉这张牌，转移到 。
• 先手报ask，后手没有这张牌：概率 。
  • 认为他在ask：后手直接获胜，收益为 。
  • 认为他在lie：先手直接获胜，收益为 。
• 先手报lie，后手认为他在ask：后手直接落败，收益为 。
• 先手lie，后手认为他在lie：相当于先手弃掉这张牌，转移到 。

整理一下选择每种状态的收益：

	先手ask	先手lie
后手认为ask
后手认为lie

设先手选取ask的概率是 ，那么选取lie的概率就是 ，那么后手为了最小化先手的胜率就会选这两种选择中先手期望较小的操作，先手为了最大化自己的胜率就会让这两个的最小值尽量大。

也就是要最大化 这两个式子都是关于 一次函数，问题变为一次函数求交点，直接计算即可。

时间复杂度 。