賽局淺說

．原載於數學傳播第一卷第三期
．作者當時任教於台大數學系

賽局淺說

姚景星;劉睦雄

在現今激烈競爭的社會中，賽局理論 (Game Theory) 因應而生。其理論為 Von Neumann 於1928年所奠基。當時，他的研究並不受到重視，直到1944年《Theory of games and economic behavior》一書問世才受到廣泛注目。那麼，賽局到底是什麼？首先，我們來看如下二人「零和賽局」的例子，這可以說是孩提時代的遊戲。

例 1：設二人猜拳，各按己意同時出剪刀、石頭、布之一種，來作打賭。（當然猜拳以前彼此不知對方出什麼），則第一人可採用之策略的集合為 $X=\{\mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 249}\hskip 0.0pt pl... ...t plus0.2pt minus0.1pt{\fontfamily{cwM3}\fontseries{m}\selectfont \char 132}}\}$ ，第二人可採用之策略的集合為 $Y=\{\mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 249}\hskip 0.0pt pl... ...t plus0.2pt minus0.1pt{\fontfamily{cwM3}\fontseries{m}\selectfont \char 132}}\}$ ，其打賭輸贏之償付辦法由二人協議如下：若第一人出石頭，第二人亦出石頭時，第一人由第二人得 2 元，若第一人出石頭，第二人出布時，第二人由第一人得 1 元，亦可說第一人得 -1 元（輸 1 元）。其他類推，亦即二人出同樣時，第一人由第二人得 2 元，出不同樣時，第二人由第一人得 1 元。其償付辦法列於表 1：

$x \backslash y$	石頭	布	剪刀
石頭	2	-1	-1
布	-1	2	-1
剪刀	-1	-1	2

表一

我們以

$\begin{displaymath} M= \pmatrix{ 2 & -1 & -1 \cr -1 & 2 & -1 \cr -1 & -1 & 2 \cr } \end{displaymath}$

表示償付矩陣。而以 (X,Y,M) 表示此二人零和賽局。我們要研究的問題是「以何種方式打賭時，對這兩人均合算」的問題。

賽局為多數（上例為二人）之競爭者間之競爭 (play) 以形式的構造表示之一組規則，一般需要滿足如下三條件：

: (1) 各競爭者 (player) 在競爭之各階段中可選擇之策略的集合為已知。（如上例 1 之 X,Y）。
: (2) 選擇策略時各競爭者可利用之情報均已確定。（如上例 1 之 X,Y,M 及由此可導出之種種結果，參閱後述）。
: (3) 一次競爭終止時，各競爭者之償付 (payoff) 規則預先已決定，（如上例 1 之 M）。

競爭者之策略 (strategy) 為於賽局中競爭者可使用之手段（如例 1 之石頭，布、剪刀），且

: (a) 於競爭之各階段，對所有可能發生之狀況，競爭者應採用之手段業已決定。
: (b) 各競爭者相互間無法預知對方使用之策略。

: 定義 1：若各競爭者之策略之集合均為有限時稱此賽局為有限賽局，否則稱為無限賽局。譬如例 1 之 X,Y，均為有限集合，故例 1 之賽局為有限賽局。
: 定義 2：若競爭者有 n 人時稱為 n 人賽局 (n person game)，各競爭者之償付總和為零時，稱此賽局為零和賽局 (zero sum game)。

譬如例 1 競爭者有 2 人，第一人贏 2 元時第二人輸 2 元，第一人輸 1 元時第二人贏 1 元，故二人之償付和均為 0，即上例1為二人零和賽局。

限於篇幅，本文只研討二人零和賽局。如上例 1 二人零和賽局須要知道二人之各策略之集合 X,Y 及二人之償付矩陣，即要知道定義於 X x Y 上之實數函數 M(x,y), $x\in X$ , $y\in Y$ ，才可得二人零和賽局 (X,Y,M)，下面我們考慮如何解如此之二人零和賽局之問題。

例 2：設二人作下列之打賭，第一人可採用之策略之集合為 X={x₁,x₂,x₃,x₄}，第二人可採用之策略之集合為 Y={y₁,y₂,y₃}，償付辦法約定如下（表 2），

$X\backslash Y$	y₁	y₂	y₃	$\min_yM(x,y)$
x₁	-70	-6	-30	-70
x₂	4	-5	-90	-90
x₃	3	2	4	2
x₄	-10	-80	5	-80
$\max_xM(x,y)$	4	2	5

表二

得二人零和賽局 G=(X,Y,M),X,Y 中之策略通常稱為單純策略。償付矩陣中之數目表示第一人之所得，正數表示第一人由第二人可得之金額，負數表示第一人輸之金額，例如 M(x₁,y₁)=-70 表示第一人採用策略 x₁，第二人採用策略 y₁ 時，第一人輸給第二人 70 元，亦即第一人所得 -70 元，又 M(x₃,y₁)=3 表示第一人採用策略 x₃，第二人採用策略 y₁ 時，第一人可由第二人得 3 元。二人各按己意同時提出策略（當然二人現出前均不知道對方採用什麼策略），其結果按償付辦法付款。由表 2 之償付矩陣好像此打賭對第一人不利，你希望當第二人嗎？

我們現在考慮此二人零和賽局之解，用償付矩陣中之數目表示第一人之所得，故第一人希望數目越大者越好，反之，第二人希望數目越小越好。因賽局 G=(X,Y,M) 中之 X,Y,M 是公開給競爭者，所以賽前可利用此情報研討採用如何策略較佳的問題。第一人採用 x₁ 時其最差之所得為 $\min_y(x_1,y)=M(x_1,y_1)=-70$ ，採用 x₂, x₃, x₄ 時其最差之所得各為 $\min_yM(x_2,y_3)=-90$ ， $\min_yM(x_3,y)=M(x_3,y_2)=2$ ， $\min_yM(x_4,y)=M(x_4,y_2)=-80$ ；反之，第二人採用 y₁, y₂, y₃ 時最大損失各為 $\max_xM(x,y_1)=M(x_2,y_1)=4$ ， $\max_xM(x,y_2)=M(x_3,y_2)=2$ ， $\max_xM(x,y_3)=M(x_4,y_3)=5$ ，這些結果已列於表 2 中。明顯的，第一人希望採用他的最差所得（最保守之所得）中為最大之策略，即

$\begin{eqnarray*} \max_x\min_yM(x,y) &=& \max[M(x_1,y_1),M(x_2,y_3),M(x_3,y_2),M(x_4,y_2)] \\ &=& M(x_3,y_2)=2 \end{eqnarray*}$

第二人希望採用他的最大損失（最保守之損失）中為最小之策略即

$\begin{eqnarray*} \min_y\max_xM(x,y) &=& \min[M(x_2,y_1),M(x_3,y_2),M(x_4,y_3)] \\ &=& M(x_3,y_2) = 2 \end{eqnarray*}$

因此，

$\begin{displaymath} \max_x\min_yM(x,y)=\min_y\max_xM(x,y)=M(x_3,y_2)=2 \end{displaymath}$

此賽局有解，即第一人之最佳策略為 x₃，第二人之最佳策略為 y₂，此賽局之值 V_G=2，即第一人贏定 2 元，誰不照此最佳策略誰就不利。例如第一人懂得這原理，第二人不明瞭時第一人一定採用最佳策略 x₃，第二人不知道第一人會採用那一個策略，若第二人採用 y₁ 或 y₃ 時損失 M(x₃,y₁)=3、M(x₃,y₃)=4 均比採用最佳策略 y₂ 之損失 M(x₃,y₂)=2 為大，反之若第一人不明白此原理，第二人知道時，第二人一定採用最佳策略 y₂，第一人因不知第二人會採用那一個策略，若第一人不採用最佳策略 x₃ 時其所得各為 M(x₁,y₂)=-6， M(x₂,y₂) = -5、 M(x₄,y₂)=-80 均比採用最佳策略和之所得 M(x₃,y₂)=2 為小。亦即誰不採用最佳策略誰就不利，此賽局第一人贏定 2 元，所以第二人不要與第一人打此賭。

由此例我們一般的可定義如下之專有名詞。

定義 3：二人零和賽局 G=(X,Y,M)，若 $\max_x \min_y M(x,y) = \min_y \max_x M(x,y)$ ，設此值為 V_G，稱 V_G 為賽局之單純值 (pure value) 或簡單稱為賽局之值。

如例 2 中 V_G=2。

定義 4：設 V_G 為 G 之單純值，當 $\min_y M(x_0,y)=V_G$ , $x_0\in X$ 時稱 x₀ 為在 G 中第一人之最佳策略 (good strategy)。當 $\max_x M(x,y_0)=V_G$ , $y_0\in Y$ 時，稱 y₀ 為在 G 中第二人之最佳策略。

如例 2 中 x₃、y₂，各為第一、二人之最佳策略。

我們再舉一個有關戰爭策略的例子如下：

例 3： A 軍對敵方 B 軍之軍事基地派出轟炸機 I 及 II。轟炸機 I 先飛行，然後 II 接著飛行。設 2 架轟炸機中有 1 架裝載炸彈，另一架護航，在出航前那架擔任之職務不明（為了機密），當然，敵方之軍事基地以一架戰鬥機迎擊該二轟炸機。在轟炸機上分別裝有速射砲。當戰鬥機攻擊後續之轟炸機 II 時，僅會遭遇轟炸機 II 之砲火。若戰鬥機攻擊先頭之轟炸機 I 時將遭遇二架轟炸機之砲火，因此，在前者戰鬥機被擊落之機率設為 0.3，後者之場合（受二架轟炸機之砲火攻擊），戰鬥機被擊落之機率 0.7。

當戰鬥機可躲避轟炸機之砲火峙，則戰鬥機可能擊落轟炸機之機率為 0.6。在轟炸機之立場者要到達目標將炮彈擲下，而戰鬥機方面，則欲阻止轟炸機達成目的，今欲問雙方之最適戰略（或策略）為何？亦即

: (a) 對 A 軍而言，炮彈裝在何機較適宜。
: (b) 對 B 軍而言，以攻擊何者較為適宜。

下面我們來解此問題，先求此二人零和賽局。

: 己方之戰略（或策略）：a₁= 轟炸機 I 裝載炮彈，a₂= 轟炸機 II 裝載炮彈
: 敵方之戰略（或策略）：b₁= 攻擊轟炸機 I，b₂= 攻擊轟炸機 II

下列考慮賽局之償付矩陣，即求其平均利得。

1. a₁b₁（I 裝彈，攻擊 I）
轟炸機將戰鬥機擊落（其機率為 0.7）或戰鬥機未被擊落且轟炸機亦未受傷（其機率為0.3 x 0.4），亦即

$\begin{displaymath} M(a_1,b_1) = 0.7 \times 1 + 0.3 \times 0.4 = 0.82 \qquad \m... ...us0.1pt{\fontfamily{cwM7}\fontseries{m}\selectfont \char 48})} \end{displaymath}$

2. a₂b₁（II 裝彈，攻擊 I）

M(a₂,b₁)=1

3. a₁b₂(I裝彈，攻擊II)

M(a₁,b₂)=1

4. a₂b₂（II 裝彈，攻擊 II）
轟炸機將戰鬥機擊落（其機率為 0.3）或戰鬥機未被擊落且轟炸機亦未受損傷（其機率為 0.7 x 0.4），亦即

M(a₂,b₂) = 0.3 x 1 + 0.7 x 0.4 = 0.58

故償付矩陣為如下（表 3）

$A\backslash B$	b₁	b₂
a₁	0.82	1
a₂	1	0.58

己方之策略為 A={a₁,a₂}，敵方之策略為 B={b₁,b₂}，償付矩陣 $M= \pmatrix{ 0.82 & 1 \cr 1 & 0.58 \cr }$ 此二人零和賽局為 (A,B,M)。因

$\begin{displaymath} \min_{j=1,2}M(a_1,b_j)=M(a_1,b_1)=0.82,\min_{j=1,2}M(a_2,b_j)=M(a_2,b_2)=0.58\end{displaymath}$

故

$\begin{displaymath} \max_{i=1,2}\min_{j=1,2}M(a_i,b_j)=M(a_1,b_1)=0.82 \end{displaymath}$

又

$\begin{displaymath} \max_{i=1,2}M(a_i,b_1)=M(a_2,b_1)=1,\max_{i=1,2}M(a_i,b_2)=M(a_1,b_2)=1, \end{displaymath}$

故

$\begin{displaymath} \min_{j=1,2}\max_{i=1,2}M(a_i,b_j)=M(a_2,b_1)=M(a_1,b_2)=1 \end{displaymath}$

即

$\begin{displaymath} \max_{i=1,2}\min_{j=1,2}M(a_i,b_j)<\min_{j=1,2}\max_{i=1,2}M(a_i,b_j) \end{displaymath}$

故此例無法在單純策略，即 A，B 中之戰略找到答案，必須將策略（或戰略）之範圍擴大才可獲得解，設在 A 上之機率之集合設為 $E=\{p=(p_1,p_2)\vert\leq p_i,i=1,2,p_1+p_2=1\}$ ，在 B 上之機率之集合設為 $H=\{q=(q_1,q_2)\vert\leq q_j,j=1,2,q_1+q_2=1\}$ 。 $p=(p_1,p_2)\in E$ 表示己方以機率 p₁ 採用策略 a₁ 並且以機率 p₂ 採用策略 a₂，而稱 p=(p₁,p₂) 為己方（第一人）之混合策略，同樣 $q=(q_1,q_2)\in H$ 表示敵方以機率 q₁ 採用策略 b₁ 並且以機率 q₂ 採用策略 b₂ 而稱 q=(q₁,q₂) 為敵方（第二人）之混合策略。若己方採用混合策略 p=(p₁,p₂)，敵方採用混合策略 q=(q₁,q₂) 時償付（期待償付）由表 3 可得如下

$\begin{eqnarray*} M(p,q) &=& p_1q_1M(a_1,b_1)+p_1q_2M(a_1,b_2)+p_2q_1M(a_2,b_1) ... ...q_2M(a_2,b_2) \\ &=& 0.82p_1q_1 + p_1q_2 + p_2q_1 + 0.58p_2q_2 \end{eqnarray*}$

我們可得新的二人零和賽局 (E,H,M)，而此賽局稱為原賽局 (A,B,M) 局之混合延伸 (mixed extension)。此例在賽局 (A,B,M) 中無法得解，故我們考慮其混合延伸 (E,H,M) 之解。欲解此賽局我們先作一些準備，由此例我們可一般定義如下之專有名詞。

: 定義 5：設 G=(X,Y,M) 為一賽局，第一、二人之各策略集合為 $X=\{x_1,x_2.\cdots,x_n\}$ , $Y=\{y_1,y_2.\cdots,y_m\}$ ，X 上之機率之集合設為 $E=\{p=(p_1,p_2,\cdots,p_n)\vert p_i\geq0, \sum_{i=1}^np_i=1\}$ ，Y 上之機率之集合設為 $H = \{q=(q_1,q_2,\cdots,q_m)\vert q_j\geq0, \sum_{j=1}^mq_j=1\}$ ， $p=(p_1,p_2,\cdots,p_n)(\in E)$ 表示第一人以機率 p_i 取策略 x_i, $i=1,2,\cdots,n$ ； $q=(q_1,q_2,\cdots,q_m)(\in H)$ 表示第二人以機率 q_j 取策略 y_j, $j=1,2,\cdots,n$ 。對 $p\in E$ , $q\in H$ ，定義 $M(p,q)=\sum_{i=1}^n\sum_{j=1}^mM(x_i,y_j)p_iq_j$ ，則可得一賽局 $\Gamma=(E,H,M)$ 而稱此為 G 之混合延伸。 $x\in X$ , $y\in Y$ 稱為 G 中之單純策略 (pure strategy)， $p\in E$ , $q\in H$ 稱為 G 中之混合策略 (mixed strategy)。

定理 1 設 G=(X,Y,M) 為一賽局， $\Gamma=(E,H,M)$ 為 G 之混合延伸，即對各 $p\in E$ , $q\in H$ ，下式成立。

: (a) $\min_{q\in H} M(p,q) = \min_{y\in Y} M(p,y)$
: (b) $\max_{p\in E} M(p,q) = \max_{x\in X} M(x,q)$

證明： (a)對各 $q\in H$ ，因

$\begin{displaymath} \begin{eqalign} M(p,q)&= \sum_{j=1}^m\sum_{i=1}^nM(x_i,y_j)p... ...m_{j=1}^mq_j\\ &= \min_{j=1,2,\cdots,m}M(p,y_j) \end{eqalign}\end{displaymath}$

故

$\begin{displaymath}%% eq (1) \min_{q \in H} M(p,q) \geq \min_{y \in Y} M(p,y) \end{displaymath}$

(1)

今可將 $y\in Y$ 視為以機率 1 取 y，即 $Y \subset H$ ，因此

$\begin{displaymath}%% eq (2) \min_{y \in Y} M(p,y) \geq \min_{q \in H} M(p,q) \end{displaymath}$

(2)

由(1)(2)可得 $\min_{q\in H} M(p,q) = \min_{y\in Y} M(p,y)$ 。

同樣可證得(b)亦成立。

我們現在利用定理 1 解例 3 之賽局，因

M(p,q) = 0.82p₁q₁ + p₂q₂ + p₂q₁ + 0.58p₂q₂,

故

$\begin{eqaligntwo*} M(a_1,q) &=0.82q_1+(1-q_1)=1-0.18q_1 & (p_1=1, & p_2=0) \\ ... ...\\ M(p,b_2) &=p_1+0.58(1-p_1)=0.58+0.42p_1 & (q_1=0, & q_2=1) \end{eqaligntwo*}$

故由定理 1，

$\begin{eqnarray*} \min_{q\in H}M(p,q)&=&\min_{j=1,2}M(p,b_j) = \min[M(p,b_1),M(p,b_2)] \\ &=&\min(1-0.18p_1,0.58+0.42p_1) \end{eqnarray*}$

圖一

由圖 1 得知，

$\begin{displaymath} \max_{p\in E}\min_{q\in H}M(p,q)=\min_{q\in H}M(0.7,q)=0.874 \end{displaymath}$

同樣，

$\begin{eqnarray*} \max_{p\in E}M(p,q) &=& \max_{i=1,2}M(a_i,q)=\max[M(a_1,q),M(a_2,q)] \\ &=& \max[1-0.18q_1,0.58+0.42q_1] \end{eqnarray*}$

可得

$\begin{displaymath} \min_{q\in H} \max_{p\in E}M(p,q)= \min_{p\in E} M(p,0.7) = 0.874 \end{displaymath}$

故

$\begin{displaymath} \min_{q\in H} \max_{p\in E} M(p,q) = \max_{p\in E} \min_{q\in H} M(p,q) = 0.874 \end{displaymath}$

即賽局有解，己方之最佳混合戰略為 p^*=(0.7,0.3)，以機率 0.7 採用戰略 a₁ 並且以機率 0.3 採用戰略 a₂，敵方之最佳戰略為 q^*=(0.7,0.3)，以機率 0.7 採用戰略 b₁ 並且以機率 0.3 採用戰略 b₂。

己方如何實際實施最佳混合戰略 p^*=(0.7,0.3)，這可如下實施；先作 10 張大小厚度一樣之卡片，其中 7 張記 a₁ 其餘 3 張記 a₂，將這些放入袋中混合後抽出一張，若 a₁ 則採用戰略 a₁，即轟炸機 I 裝載炮彈，若抽出一張結果為 a₂ 時採用戰略 a₂，即轟炸機 II 裝載炮彈。敵方亦可同樣實施，這一種遊戲同學間可以模擬試試，將可發見其中的樂趣。

為解例題 1，再證明下列定理 2。

定理2：若 G=(X,Y,M) 具有值 v， $X=\{x_1,x_2,\cdots,x_n\}$ ， $Y=\{y_1,y_2,\cdots,y_m\}$ 且若 $p^*=(p_1^*,p_2^*,\cdots,p_n^*)$ 為第一人之最佳混合策略， $q^*=(q_1^*,q_2^*,\cdots,q_m^*)$ 為第二人之最佳混合策略，則

: (a) $\sum_{\{x_i\vert M(x_i,q^*)<v\}} p_i^* = 0$ （即對應 M(x_i,q^*)<v 之 i,p_i^*=0）
: (b) $\sum_{\{y_j\vert M(q^*,y_j)>v\}} q_j^*=0$ （即對應 M(p^*,y_j)>v 之 j,q_j^*=0）

證明： (a)對各 y_i， $M(p^*,y_j)\geq \inf_j M(p^*,y_j)=v$ ，因此 $M(p^*,q^*)=\sum_{j=1}^mM(p^*,y_j)q_j^*\geq v$ ，同理對各 $x_i\in X$ ， $M(x_i,q^*)\leq v$ ，故 $M(p^*,q^*)\leq v$ ，所以 M(p^*,q^*)=v。

設 U={x_i|M(x_i,q^*)<v}, $U_n=\{x_i\vert M(x_i,q^*)<v-\frac{1}{n}\}$ ，且令 C(U_n)=X-U_n，則對所有 n，

$\begin{eqnarray*} v&=&\sum_{i=1}^np_i^*M(x_i,q^*) =\sum_{x_i\in U_n}p_i^*M(x_i,... ...-\frac{1}{n})\sum_{x_i\in U_n}p_i^* + v\sum_{x_i\in C(U_n)}p_i^* \end{eqnarray*}$

又因 $\sum_{x_i\in U_n}p_i^*+\sum_{x_i\in C(U_n)}p_i^*=1$ ，故 $v<v-\frac{1}{n}\sum_{x_i\in U_n}p_i^*$ 。因此對各n， $\sum_{x_i\in U_n}p_i^*=0$ 亦即 $\sum_{x_i\in U}p_i^*=0$ 。

(b)證明同樣可得。

利用此定理可如下解例 1，今第 2 人欲取策略 q=(q₁,q₂,q₃) 使得 M(x,y)=k（定數），即解下列方程組（由表 1）。

$\begin{displaymath} \begin{eqalign} & 2q_1-q_2-q_3=k \\ & -q_1+2q_2-q_3=k \\ &... ... \\ & q_1+q_2+q_3=1 \\ & q_i\geq0, \;\; i=1,2,3 \end{eqalign}\end{displaymath}$

解之可得 k=0， $q_1,q_2,q_3=\frac{1}{3}$ ，即可能當作第二人最佳混合策略為 $q^* = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ 。對第一人之最佳混合策略 (p^*=p₁^*, p₂^*, p₃^*) 及各 y（第二人之單純策略），必有 M(p^*,y)=0 即由表 1 可得下列方程組。

$\begin{displaymath} \begin{eqalign} & 2p_1^*-p_2^*-p_3^* = 0 \\ & -p_1^*+2p_2^*... ..._2^*+p_3^* = 1 \\ & p_i^* \geq 0, \;\; i = 1,2,3 \end{eqalign}\end{displaymath}$

其解為 $p_1^* = p_2^* = p_3^* = \frac{1}{3}$ ，即例 1 之第一二人之各最佳策略各為 $p^*=(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ ， $q^* = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ ，此賽局之值為 0。即最佳策略是以機率 $\frac{1}{3}$ 各採用石頭、布、剪刀，可利用一個公正骰子投出，若 1,2 時採用石頭，3,4 時採用布，5,6 時採用剪刀。

上述解法並非萬靈丹，有些需利用線性計劃法才可解出。

對外搜尋關鍵字：
．賽局理論
．Von Neumann


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：李渭天

最後修改日期：4/26/2002