# Deposit game

[TOC]

Rio Li 發明了一個遊戲：

> 剛剛開車回家的路上想到了一個類似今際之國方塊或者賭博默示錄的策略遊戲，分享給大家，看有興趣的臉友會不會想到最好的策略
>
>「空頭支票」
遊戲前置： 兩個玩家，分別有兩張紙跟一支筆
遊戲規則 ：
（1）兩個玩家一起分別執行，在其中一張紙寫上存單以及一個1-1000之間的整數，並在另外一張紙寫上支票以及一個1-1000之間的整數（兩場紙寫的順序不限），請勿窺視另外一人寫的數字，也努力不要讓另外一人窺視。
（2）雙方確認彼此寫完後，同時揭露兩張紙，並進入提領的程序，如其中一人A寫的支票數字a等於或者小於對方B寫的存單數字b，則A 提領並獲得分數a，B獲得差額分數b-a，而如果A寫的支票數字a大於B寫的存單數字b，則提領失敗，A獲得0分數，B獲得分數b ，雙方誰先提領不限
（3） 雙方結算提領的分數與保留的分數加總為一回合的總分
（4）重複進行共三回合、三回合累積總分最多的玩家獲勝

首先觀察到：存款行為的報酬不會和對方的存款行為有關，提款行為的報酬也不會和對方的提款行為有關。所以只要分析一個玩家只存款，另外一個玩家只提款的狀況就好。完整的遊戲只是雙方同時玩兩盤簡化版的遊戲，並對調角色。

所以簡化版的遊戲是一個兩玩家同時賽局：

存款者有行動 $d \in [1, 1000]$ ，提款者有行動 $w \in [1, 1000]$

存款者報酬為

$$
U_D(d, w) = \begin{cases}
d-w & \text{if } d >= w \\
d & \text{otherwise.}
\end{cases}
$$

提款者報酬為

$$
U_W(d, w) = \begin{cases}
w & \text{if } d >= w \\
0 & \text{otherwise.}
\end{cases}
$$

我們可以先看單純策略

## 單純策略

首先看存款者的最佳反應。

給定提款者行動 $w$ 之下，存款者最佳的策略是

$$
d^* = \begin{cases}
1000 & \text{if } w < 500 \\
w -1 & \text{otherwise.}
\end{cases}
$$

如果提款小於五百，則存一千元以取得大於五百塊的差額。但如果提款多於五百，則會想要存比提款額恰好少一塊錢，以獲取多於五百塊的報酬。

再來看提款者的最佳反應：

給定存款行動 $d$ 之下，提款者最佳的策略是

$$
w^* = d
$$

反正存款者存多少錢，提精確的數字把存款提光即可。

我們可以把雙方的最佳反應畫在圖上，橫軸是提款金額，縱軸是存款金額。紅色實線是存款者對提款者行動的最佳反應。紫色虛線是提款者對存款者行動的最佳反應。兩條線貌似在提款五百元以上重疊，但實際上那兩條線有一塊錢的差距，是完全平行的。

紅紫兩線沒有交點，表示存提雙方沒有一組存款和提款數字是雙方都願意停留在那邊而不單方面偏離的。這代表這個遊戲沒有單純策略的均衡，需要考量混合策略。


https://www.desmos.com/calculator/eiewosvg3n

## 混合策略（Mixed strategy）

混合策略是雙方會各自在 1~1000 的數字配機率，共一千個變數。在給定對手選擇的機率之下，自己要極大化自己的期望報酬（假設風險中立）。存提雙方自己都有各自一千種可能的行動，混合策略的均衡就是要讓對方不管選什麼行動，期望報酬都一樣。

令提款者提款 $w$ 的機率為 $p_w$ ，存款者存款 $d$ 的機率為 $q_d$

我們用一些向量符號來包裝這些變數

$$
\begin{align}
\mathbf{p} &= \begin{bmatrix}
p_1 \\
\vdots \\
p_{1000}
\end{bmatrix}
\end{align}
$$

$$
\begin{align}
\mathbf{q} &= \begin{bmatrix}
q_1 \\
\vdots \\
q_{1000}
\end{bmatrix}
\end{align}
$$

存款者的最佳化問題是給定 $\mathbf{p}$ 之下，找到能夠讓期望效用最大的 $\mathbf{q}$：

$$
\max_{\mathbf{q}}{E[U_D(d, w)]}
$$
我們可以把期望值與報酬展開：
$$
\max_{\mathbf{q}}{
\sum_{d=1}^{1000}{[
\sum_{w=1}^{1000}U_D(d, w)p_w
]q_d}
}\\
= \max_{\mathbf{q}}{
\sum_{d=1}^{1000}{[
\sum_{w=d+1}^{1000}{p_wd}+\sum_{w=1}^{d}{p_w(d-w)}
]q_d}
}
$$

裡面的部分還能進一步整理：

$$
\sum_{w=d+1}^{1000}{p_wd}+\sum_{w=1}^{d}{p_w(d-w)} = d - \sum_{w=1}^{d}{p_ww}
$$

這邊的報酬可以看成是存款方選 $d$ 這個行動時，報酬是可以穩拿 d ，但要扣掉有機率被提款方提走的部分。

接著來看提款方的最佳化問題：

$$
\max_{\mathbf{p}}{E[U_W(d, w)]}
$$

展開之後為

$$
\max_{\mathbf{p}}{
\sum_{w=1}^{1000}{[
\sum_{d=1}^{1000}U_W(d, w)q_d
]p_w}
}\\
= \max_{\mathbf{p}}{
\sum_{w=1}^{1000}{[
\sum_{d=w}^{1000}{q_d w}
]p_w}
}
$$

我們也關注裡面的部分就好

$$
\sum_{d=w}^{1000}{q_d w} = w \sum_{d=w}^{1000}{q_d}
$$

這意思是如果提款方提 $w$ 時，如果運氣夠好存款方存得多時，就都提得到。但運氣不好就什麼都沒有。

## 尋找混合策略均衡

正式的找法是一個複雜的演算法，後面再來嘗試。我們先用一些簡單的直覺來找。

先看存款方。存款方會想要盡力把機率配在報酬高的 $d$ 上面，而提款方會想要讓存款方不管選什麼行動，報酬都一樣。所以我們要對所有 $d$ ，存款方的報酬都一樣

$$
d - \sum_{w=1}^{d}{p_ww}
$$
換句話說：

$$
1 -p_1= 2 -(p_1+p_2) = \cdots = 1000 - (p_1+\cdots + p_{1000})
$$

我們可以用個通式表達

$$
(d-1) - \sum_{w=1}^{d-1}{p_ww} = d - \sum_{w=1}^{d}{p_ww}
$$

整理之後，

$$
p_dd = 1
$$

$$
p_d = \frac{1}{d}
$$

這邊的直覺是，存款方每多存一塊錢，邊際收益是多一塊錢，邊際成本是 $d$ 元被整個領走的風險。因此把提款方把機率調整為 $1/d$ ，使得多存一塊錢的邊際期望報酬是零。

但這裡有個明顯的問題，$p_1 \cdots p_{1000}$ 是機率，必須各自大於零，加總等於 1 。

但照上面的算式， $p_1 = \frac{1}{1}$ ，光第一個變數就等於一了，一千個變數加下來一定大於一。

所以實際上要「對所有 $d$ ，存款方的報酬都一樣」是做不到的。可以做到的是讓存款方報酬最大的那些選項報酬一樣。

我們可以用附錄的 Python 腳本去找到機率權重。



### 提款方

我們再來看提款方的報酬。

$$
w \sum_{d=w}^{1000}{q_d}
$$

我們也可以觀察提款方的邊際報酬，來看存款方要怎麼配機率給他。

$$
w \sum_{d=w}^{1000}{q_d} = (w + 1) \sum_{d=w+1}^{1000}{q_d}
$$

$$
w q_w = \sum_{d=w+1}^{1000}{q_d}
$$

$$
q_w = \frac{1}{w}\sum_{d=w+1}^{1000}{q_d}
$$

我們可以隨便設定一個 $q_{1000}$ 初始值，然後逐步決定出其他的 $q$ ，最後把所有的值縮放成加總為一，就能變成合理的機率分佈了。

$q_{999} = \frac{1}{999}q_{1000}$
$q_{998} = \frac{1}{998}(q_{999}+q_{1000}) =\frac{1000}{998*999}q_{1000}$

我們發現 $q_{999}$ 會從 $q_{1000}$ 掉快一千倍下來，但 $q_{998}$ 以後的值會都和 $q_{999}$ 差不多大。也就是存款者需要以近千倍機率偶爾存個 1000 元，吸引提款者提款高金額。但其他存款數字幾乎不用怎麼出現。

另外因為存款者已經沒誘因玩 367 塊以下的存款了，所以我們也可以把那邊的機率截斷變成零。
最後的機率分配就如下圖。最後算出來該存一千元的機率是 36% 。


提款者的收益分佈也和存款者很像


## 用演算法找均衡

前面用了很人工的方式找均衡。如果要用比較演算法的方式去做的話就是要解線性規劃的問題。我們前面沒有辦法配機率的行動，報酬會比其他行動低。因此可以引入一些鬆弛變數（Slack variable）去墊高他們的報酬。最後解出來的結果應該會是下面兩種情況：

- 配給行動的機率為零，鬆弛變數不為零。這是期望報酬不足的劣勢策略。
- 配給行動的機率不為零，但鬆弛變數必須是零。這是最後在混合均衡的策略。

但要製作出上述限制式會讓整個最佳化問題變成不是線性規劃。

照這個思路的演算法的方式是 Lemke-Howson 演算法 ，這個 [參考資料](https://www.cs.ubc.ca/~kevinlb/teaching/cs532l%20-%202012-13/lectures/week2.pdf) 有介紹。

最後 Lemke-Howson 演算法有 Python 實作。但行動的數量沒辦法太多。目前演算法執行時遇到 multiplicity 的錯誤，沒辦法算出答案。假設我們把存提款的數字限縮到 1~9 ，那演算法就還能執行成功。以下是雙方的報酬矩陣

Depositor:
[[0 1 1 1 1 1 1 1 1]
 [1 0 2 2 2 2 2 2 2]
 [2 1 0 3 3 3 3 3 3]
 [3 2 1 0 4 4 4 4 4]
 [4 3 2 1 0 5 5 5 5]
 [5 4 3 2 1 0 6 6 6]
 [6 5 4 3 2 1 0 7 7]
 [7 6 5 4 3 2 1 0 8]
 [8 7 6 5 4 3 2 1 0]]

Withdrawer:
[[1 0 0 0 0 0 0 0 0]
 [1 2 0 0 0 0 0 0 0]
 [1 2 3 0 0 0 0 0 0]
 [1 2 3 4 0 0 0 0 0]
 [1 2 3 4 5 0 0 0 0]
 [1 2 3 4 5 6 0 0 0]
 [1 2 3 4 5 6 7 0 0]
 [1 2 3 4 5 6 7 8 0]
 [1 2 3 4 5 6 7 8 9]]

計算出來的混合策略，直覺和手算得差不多。存款者分配大概三分之一的機率存最大值，然後小機率玩其他值。提款者也把機率配到存款者獲利最大的行動。


## 結論

我們目前手工找到一個存款方和提款方大概是期望值 368 元的混合策略均衡。存或提 367 元以下是劣勢策略，雙方都不玩。368 到一千元間雙方會照某個配好的機率分佈隨機玩，雙方都不會想偏離那個均衡。

真人實際玩的話，大概存款方要想辦法說服對方：自己有近三分之一的機率會存一千元，以鼓勵提款方提高提款金額。

## 後記

我一直在思考，哪些現實世界的現象是對應這樣的賽局。
於是請教了原作者 Rio Li 當初想到這個遊戲的靈感。他說這是來自職場的靈感。職場主管需要對團隊成員開政治支票，如果支票開得小，團隊成員會覺得主管沒有太多資源；但若支票開得大，又有無法兌現而失去信任的風險。

## 附錄

程式碼 https://github.com/slothservice/deposit_game