警察小偷博弈

簡介

小鎮上有兩處有價值的地點，A地和B地，價值分別為

和

。警察和小偷必須同時決定去A地還是B地巡邏或者偷竊，如果小偷偷竊的地方恰好為警察巡邏的地點，那么小偷失去該地點的價值，警察獲得該地方的價值；如果小偷偷竊的地方恰為警察沒有巡邏的地點，那么小偷獲得該地點的價值，警察失去該地點的價值。從上面的文字描述中我們可以抽象出下面的這樣收益矩陣：

警察╲小偷	A	B
A	,	,
B	,	,

警察小偷博弈常常用於說明使用混合策略的必要性：如果警察預先暴露了自己要去的地點，那么小偷就會選擇與警察不同的地點，從而在博弈中獲勝。如果小偷預先暴露了自己要去的地點，那么警察就會選擇與小偷相同的地點來贏得博弈的勝利。

如果兩處地點的價值相同，不妨設其價值均為1，那么我們就得到了硬幣匹配博弈（Matching pennies）。它對應於下面的情景：兩名玩家各有一枚硬幣，各自選擇將自己的硬幣翻為正面或者背面，若兩枚硬幣均為正面或均為反面，則玩家1獲得兩枚硬幣，否則玩家2獲得兩枚硬幣。

策略與均衡

混合策略

我們首先說明，上述博弈沒有純策略納什均衡。此處用二元組（X，Y）代表警察在X地巡邏，小偷在Y地偷竊的純策略組合。

在純策略組合（A，A）下，小偷的收益為，此時小偷只需要改為選擇地點B偷竊，就可以獲得更高的收益，故（A，A）不是純策略納什均衡。類似的，（B，B）不是純策略納什均衡。
在純策略組合（A，B）下，警察的收益為，此時警察只需要將巡邏地點改為B，就可以獲得更高的收益，故（A，B）不是純策略納什均衡。類似的，（B，A）不是純策略納什均衡。

上面的分析說明了警察小偷博弈沒有純策略納什均衡，我們需要考慮雙方使用混合策略的情形。

均衡計算

為了計算出該博弈的混合策略納什均衡，不妨設警察在A地巡邏的機率為p，在B地巡邏的機率為1-p；小偷在A地偷竊的機率為q，在B地偷竊的機率為1-q。並使用二元組（p，q）代表混合策略組合。

假設（p，q）為納什均衡，由納什均衡的定義可知，此時任一方單方面改變策略（即改變p，q的值）都不會獲得更高的收益。從警察的角度考慮，假設在此策略組合下，面對小偷以q的機率選擇A地這一策略，警察選擇A地或者B地這兩個純策略的收益如果不同，那么警察選擇收益更高的那一純策略會獲得比使用混合策略更高的收益。這與納什均衡定義矛盾，故面對小偷的策略，無論警察選擇A地還是B地都有相同的收益，也即：