这是一个面试题,题目是

甲有一枚硬币,可以控制正面还是反面朝上,乙去猜。如果甲的硬币正面朝上,且乙猜正面,则甲给乙1块钱;如果甲的硬币反面朝上,且乙猜反面,则甲给乙3块钱;其它情况,乙给甲2块钱。游戏重复很多很多次,乙应该采取何种策略使自己收益最大或损失最小?

该题目是一个标准的无限重复零和博弈问题,乙的最优策略是一个混合策略,即以一定的概率猜正面,以一定的概率猜反面。

最优策略可以由极大极小算法计算,不过我完全没看懂算法的运行过程。一个简单的算法似乎是这样的:
列出博弈中乙的支付矩阵(payoff matrix):

1 -2
-2 3

假设乙以概率a猜“正”,以概率b猜“反”,则乙在甲出“正”时的期望收益为a-2b,在甲出“反”时的期望收益为-2a+3b,当两者相等时为最优策略,再加上a+b=1,可以解出a= ,b=

同时最优策略也是该博弈的纳什均衡,而2个玩家、零和博弈的纳什均衡点可以由线性规划方法给出。线性规划方法中,支付矩阵的每一项需要加上一个常数,以使所有的收益相为正。设支付矩阵为

线性规划需要解出向量
Minimize:

Subject to the constraints:


解出

将u正则化得到 ,分别即乙猜“正”的概率和猜“反”的概率。