首頁 | 搜尋

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

賽局淺說

姚景星;劉睦雄

 
 

在現今激烈競爭的社會中,賽局理論 (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={x1,x2,x3,x4},第二人可採用之策略之集合為 Y={y1,y2,y3},償付辦法約定如下(表 2),

$X\backslash Y$ y1 y2 y3 $\min_yM(x,y)$
x1 -70 -6 -30 -70
x2 4 -5 -90 -90
x3 3 2 4 2
x4 -10 -80 5 -80
$\max_xM(x,y)$ 4 2 5  
表二

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

我們現在考慮此二人零和賽局之解,用償付矩陣中之數目表示第一人之所得,故第一人希望數目越大者越好,反之,第二人希望數目越小越好。因賽局 G=(X,Y,M) 中之 X,Y,M 是公開給競爭者,所以賽前可利用此情報研討採用如何策略較佳的問題。第一人採用 x1 時其最差之所得為 $\min_y(x_1,y)=M(x_1,y_1)=-70$,採用 x2, x3, x4 時其最差之所得各為 $\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$;反之,第二人採用 y1, y2, y3 時最大損失各為 $\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}

此賽局有解,即第一人之最佳策略為 x3,第二人之最佳策略為 y2,此賽局之值 VG=2,即第一人贏定 2 元,誰不照此最佳策略誰就不利。例如第一人懂得這原理,第二人不明瞭時第一人一定採用最佳策略 x3,第二人不知道第一人會採用那一個策略,若第二人採用 y1y3 時損失 M(x3,y1)=3M(x3,y3)=4 均比採用最佳策略 y2 之損失 M(x3,y2)=2 為大,反之若第一人不明白此原理,第二人知道時,第二人一定採用最佳策略 y2,第一人因不知第二人會採用那一個策略,若第一人不採用最佳策略 x3 時其所得各為 M(x1,y2)=-6M(x2,y2) = -5M(x4,y2)=-80 均比採用最佳策略和之所得 M(x3,y2)=2 為小。亦即誰不採用最佳策略誰就不利,此賽局第一人贏定 2 元,所以第二人不要與第一人打此賭。

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

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

如例 2 中 VG=2

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

如例 2 中 x3y2,各為第一、二人之最佳策略。

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

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

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

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

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

己方之戰略(或策略):a1= 轟炸機 I 裝載炮彈,a2= 轟炸機 II 裝載炮彈
敵方之戰略(或策略):b1= 攻擊轟炸機 I,b2= 攻擊轟炸機 II

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

1. a1b1(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. a2b1(II 裝彈,攻擊 I)

M(a2,b1)=1

3. a1b2(I裝彈,攻擊II)

M(a1,b2)=1

4. a2b2(II 裝彈,攻擊 II)
轟炸機將戰鬥機擊落(其機率為 0.3)或戰鬥機未被擊落且轟炸機亦未受損傷(其機率為 0.7 x 0.4),亦即

M(a2,b2) = 0.3 x 1 + 0.7 x 0.4 = 0.58

故償付矩陣為如下(表 3)

$A\backslash B$ b1 b2
a1 0.82 1
a2 1 0.58

己方之策略為 A={a1,a2},敵方之策略為 B={b1,b2},償付矩陣 $
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}

故此例無法在單純策略,即 AB 中之戰略找到答案,必須將策略(或戰略)之範圍擴大才可獲得解,設在 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$ 表示己方以機率 p1 採用策略 a1 並且以機率 p2 採用策略 a2,而稱 p=(p1,p2) 為己方(第一人)之混合策略,同樣 $q=(q_1,q_2)\in H$ 表示敵方以機率 q1 採用策略 b1 並且以機率 q2 採用策略 b2 而稱 q=(q1,q2) 為敵方(第二人)之混合策略。若己方採用混合策略 p=(p1,p2),敵方採用混合策略 q=(q1,q2) 時償付(期待償付)由表 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)$ 表示第一人以機率 pi 取策略 xi, $i=1,2,\cdots,n$$q=(q_1,q_2,\cdots,q_m)(\in H)$ 表示第二人以機率 qj 取策略 yj, $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.82p1q1 + p2q2 + p2q1 + 0.58p2q2,

\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 採用戰略 a1 並且以機率 0.3 採用戰略 a2,敵方之最佳戰略為 q*=(0.7,0.3),以機率 0.7 採用戰略 b1 並且以機率 0.3 採用戰略 b2

己方如何實際實施最佳混合戰略 p*=(0.7,0.3),這可如下實施;先作 10 張大小厚度一樣之卡片,其中 7 張記 a1 其餘 3 張記 a2,將這些放入袋中混合後抽出一張,若 a1 則採用戰略 a1,即轟炸機 I 裝載炮彈,若抽出一張結果為 a2 時採用戰略 a2,即轟炸機 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(xi,q*)<vi,pi*=0
(b) $\sum_{\{y_j\vert M(q^*,y_j)>v\}} q_j^*=0$ (即對應 M(p*,yj)>vj,qj*=0

證明: (a)對各 yi$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={xi|M(xi,q*)<v}, $U_n=\{x_i\vert M(x_i,q^*)<v-\frac{1}{n}\}$,且令 C(Un)=X-Un,則對所有 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=(q1,q2,q3) 使得 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*=p1*, p2*, p3*) 及各 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

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


編輯:李渭天 最後修改日期:4/26/2002