對(duì)策論亦稱競賽論或博弈論。是研究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。一般認(rèn)為，它既是現(xiàn)代數(shù)學(xué)的一個(gè)新分支，也是運(yùn)籌學(xué)中的一個(gè)重要學(xué)科。對(duì)策論發(fā)展的歷史并不長，但由于它所研究的現(xiàn)象與人們的政治、經(jīng)濟(jì)、軍事活動(dòng)乃至一般的日常生活等有著密切的聯(lián)系，并且處理問題的方法又有明顯特色。所以日益引起廣泛的注意。

在日常生活中，經(jīng)?？吹揭恍┚哂邢嗷ブg斗爭或競爭性質(zhì)的行為。具有競爭或?qū)剐再|(zhì)的行為稱為對(duì)策行為。在這類行為中。參加斗爭或競爭的各方各自具有不同的目標(biāo)和利益。為了達(dá)到各自的目標(biāo)和利益，各方必須考慮對(duì)手的各種可能的行動(dòng)方案，并力圖選取對(duì)自己最為有利或最為合理的方案。對(duì)策論就是研究對(duì)策行為中斗爭各方是否存在著最合理的行動(dòng)方案，以及如何找到這個(gè)合理的行動(dòng)方案的數(shù)學(xué)理論和方法。

1.對(duì)策問題

對(duì)策問題的特征是參與者為利益相互沖突的各方，其結(jié)局不取決于其中任意一方的努力而是各方所采取的策略的綜合結(jié)果。
先看一個(gè)大家都熟悉的例子。

例1 （囚徒困境）警察同時(shí)逮捕了兩人并分開關(guān)押，逮捕的原因是他們持有大量偽幣，警方懷疑他們偽造錢幣，但沒有找到充分證據(jù)，希望他們能自己供認(rèn)，這兩個(gè)人都知道：如果他們雙方都不供認(rèn)，將被以持有大量偽幣罪被各判刑 18 個(gè)月；如果雙方都供認(rèn)偽造了錢幣，將各被判刑 3 年；如果一方供認(rèn)另一方不供認(rèn)，則供認(rèn)方將被從寬處理而免刑，但另一方面將被判刑 7 年。將嫌疑犯 A 、 B 被判刑的幾種可能情況列于表 1。

表1 各種情況對(duì)應(yīng)的判刑年數(shù)

	供認(rèn)	不供認(rèn)
供認(rèn)	（3,3）	（0,7）
不供認(rèn)	（7,0）	（1.5,1.5）

我們從這個(gè)問題中看一看對(duì)策問題的基本要素

1.1.對(duì)策的基本要素

1.1.1.局中人

在一個(gè)對(duì)策行為（或一局對(duì)策）中，有權(quán)決定自己行動(dòng)方案的對(duì)策參加者，稱為局中人。通常用 $I$ 表示局中人的集合．如果有 $n$ 個(gè)局中人，則 $I=\{1,2, \cdots, n\}$ 。一般要求一個(gè)對(duì)策中至少要有兩個(gè)局中人。在例 1 中，局中人是 $A,B$ 兩名疑犯。

1.1.2.策略集

一局對(duì)策中，可供局中人選擇的一個(gè)實(shí)際可行的完整的行動(dòng)方案稱為一個(gè)策略。參加對(duì)策的每一局中人 $i, \quad i \in I$ ，都有自己的策略集 $S_{i}$ 。一般，每一局中人的策略集中至少應(yīng)包括兩個(gè)策略。

1.1.3.贏得函數(shù)（支付函數(shù)）

再一局對(duì)策中，各局中人所選定的策略形成的策略組稱為一個(gè)局勢，即若 $s_{i}$ 是第 $i$ 個(gè)局中人的一個(gè)策略，則 $n$ 個(gè)局中人的策略組
$S=\left(S_{1}, S_{2}, \cdots, S_{n}\right)$
就是一個(gè)局勢。全體局勢的集合 $S$ 可用各局中人策略集的笛卡爾積表示，即：
$S=S_{1} \times S_{2} \times \cdots \times S_{n}$
當(dāng)局勢出現(xiàn)后，對(duì)策的結(jié)果也就確定了。也就是說，對(duì)任一局勢， $s \in S$ ，局中人 $i$ 可以得到一個(gè)贏得 $H_{i}(s)$ 。顯然， $H_{i}(s)$ 是局勢 $s$ 的函數(shù)，稱之為第 $i$ 個(gè)局中人的贏得函數(shù)。這樣，就得到一個(gè)向量贏得函數(shù) $H(s)=\left(H_{1}(s), \cdots, H_{n}(s)\right)$ 。
本節(jié)我們只討論有兩名局中人的對(duì)策問題，其結(jié)果可以推廣到一般的對(duì)策模型中去。

1.2.零和對(duì)策（矩陣對(duì)策）

零和對(duì)策是一類特殊的對(duì)策問題。在這類對(duì)策中，只有兩名局中人，每個(gè)局中人都只有有限個(gè)策略可供選擇。在任一純局勢下，兩個(gè)局中人的贏得之和總是等于零，即雙方的利益是激烈對(duì)抗的。
設(shè)局中人Ⅰ，Ⅱ的策略集分別為：
$S_{1}=\left\{\alpha_{1}, \cdots, \alpha_{m}\right\}, S_{2}=\left\{\beta_{1}, \cdots, \beta_{n}\right\}$
當(dāng)局中人Ⅰ選定策略 $\alpha_{i}$ 和局中人Ⅱ選定策略 $\beta_{j}$ 后，就形成了一個(gè)局勢 $\left(\alpha_{i}, \beta_{j}\right)$ ，可見這樣的局勢共有 $mn$ 個(gè)。對(duì)任一局勢 $\left(\alpha_{i}, \beta_{j}\right)$ ，記局中人Ⅰ的贏得值為 $a_{i j}$ ，并稱：
$A=\left[\begin{array}{llll}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2 n}} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} \\ {a_{m 1}} & {a_{m 2}} & {\cdots} & {a_{m n}}\end{array}\right]$
為局中人Ⅰ的贏得矩陣（或?yàn)榫种腥刷虻闹Ц毒仃嚕?。由于假定假定?duì)策為零和的，故局中人Ⅱ的贏得矩陣就是 $-A$ ，一個(gè)零和對(duì)策就給定了，零和對(duì)策又可稱為矩陣對(duì)策并可簡記成：
$G=\left\{S_{1}, S_{2} ; A\right\}$

例2 設(shè)有一矩陣對(duì)策 $G=\left\{S_{1}, S_{2} ; A\right\}$ ，其中 $S_{1}=\left\{\alpha_{1}, \alpha_{2}, \alpha_{3}\right\}$ ， $S_{2}=\left\{\beta_{1}, \beta_{2}, \beta_{3}, \beta_{4}\right\}$
$A=\left[\begin{array}{cccc}{12} & {-6} & {30} & {-22} \\ {14} & {2} & {18} & {10} \\ {-6} & {0} & {-10} & {16}\end{array}\right]$

從 $A$ 中可以看出，若局中人Ⅰ希望獲得最大盈利30，需采用策略 $\alpha_{1}$ ，但此時(shí)若局中人Ⅱ采用策略 $\beta_{4}$ ，局中人Ⅰ采取策略 $\alpha_{1}, \alpha_{2}, \alpha_{3}$
時(shí)，最壞的贏得結(jié)果分別是：
$\min \{12,-6,30,-22\}=-22$
$\min \{14,2,18,10\}=2$
$\min \{-6,0,-10,16\}=-10$
其中最好的可能為 $\max \{-22,2,-10\}=2$ 。如果局中人Ⅰ采取策略 $\alpha_{2}$ ，無論局中人Ⅱ采取什么策略，局中人Ⅰ的贏得君不悔少于2.
局中人Ⅱ采取各方案的最大損失為 $\max \{12,14,-6\}=14, \quad \max \{-6,2,0\}=2$ ， $\max \{30,18,-10\}=30$ ，和 $\max \{-22,10,16\}=16$ 。當(dāng)局中人Ⅱ采取策略 $\beta_{2}$ ，其損失不會(huì)超過2。注意到在贏得矩陣矩陣，2即是所在航中的最小元素又是所在列中的最大元素。此時(shí)，只要對(duì)方不改變策略，任一局中人都不可能通過變換策略來增大贏得或減少損失，成這樣的局勢為對(duì)策的一個(gè)穩(wěn)定點(diǎn)或穩(wěn)定解。

定義1 設(shè) $f(x, y)$ 為一個(gè)定義在 $x \in A$ 及 $y \in B$ 上的實(shí)值函數(shù)，如果存在 $x^{*} \in A$ ， $y^{*} \in B$ ，使得對(duì)一切
$x \in A$ 和 $y \in B$ 有：
$f\left(x, y^{*}\right) \leq f\left(x^{*}, y^{*}\right) \leq f\left(x^{*}, y\right)$
則稱 $\left(x^{*}, y^{*}\right)$ 為函數(shù) $f$ 的一個(gè)鞍點(diǎn)。

定義2 設(shè) $G=\left\{S_{1}, S_{2} ; A\right\}$ 為矩陣對(duì)策，其中 $S_{1}=\left\{\alpha_{1}, \alpha_{2}, \cdots, \alpha_{m}\right\}$ ， $S_{2}=\left\{\beta_{1}, \beta_{2}, \cdots, \beta_{n}\right\}, \quad A=\left(a_{i j}\right)_{m \times n}$ 。若等式
$\max _{i} \min _{j} a_{i j}=\min _{j} \max _{i} a_{i j}=a_{i^{*} j^{*}}（1）$
成立，記 $V_{G}=a_{i^{*} j^{*}}$ ，則稱 $V_{G}$ 為對(duì)策 $G$ 的值，稱使（1）式成立的純局勢 $\left(\alpha_{i^{*}}, \beta_{j^{*}}\right)$ 為對(duì)策 $G$ 的鞍點(diǎn)或穩(wěn)定解，贏得矩陣中與 $\left(\alpha_{i}, \beta_{j^{*}}\right)$ 相對(duì)應(yīng)的元素 $a_{i^{*} j^{*}}$ 稱為贏得矩陣的鞍點(diǎn)， $\alpha_{i^{*}}$ 與 $\beta_{j}$ 分別稱為局中人Ⅰ和Ⅱ的最優(yōu)純策略。

給定一個(gè)對(duì)策 $G$ ，如何判斷它是否有鞍點(diǎn)呢？為了回答這一問題，先引入下面的極大極小原理。

定理1 設(shè) $G=\left\{S_{1}, S_{2} ; A\right\}$ ，記 $\mu=\max _{i} \min a_{i j}, \quad v=-\min _{j} \max a_{i j}$ ，則必有 $\mu+v \leq 0$

定理2 零和策略 $G$ 具有穩(wěn)定解的充要條件是 $\mu+v=0$

2.零和定理的混合策略

具有穩(wěn)定解的零和問題是一類特別簡單的對(duì)策問題，它所對(duì)應(yīng)的贏得矩陣存在鞍點(diǎn)，任一局中人都不可能通過自己單方面的努力來改進(jìn)結(jié)果。然而，在實(shí)際遇到的零和對(duì)策中更典型的是
$\mu+v \neq 0$ 的情況。由于矩陣中不存在鞍點(diǎn)，此時(shí)在只使用純策略的范圍內(nèi)，對(duì)策問題無解，下面我們引進(jìn)零和對(duì)策的混合策略。

設(shè)局中人Ⅰ用概率 $x_{i}$ 選用策略 $\alpha_{i}$ ，局中人Ⅱ用概率 $\mathcal{Y}$ 選用策略 $\beta_{j}$ ， $\sum_{i=1}^{m} x_{i}=\sum_{j=1}^{n} y_{j}=1$ ，記 $x=\left(x_{1}, \cdots, x_{m}\right)^{T}, \quad y=\left(y_{1}, \cdots, y_{n}\right)^{T}$ ，則局中人Ⅰ的期望贏得為 $E(x, y)=x^{T} A y$ ，簡單記：
$S_{1}^{*}=\left\{\left(x_{1}, \cdots, x_{m}\right)^{T} | x_{i} \geq 0, i=1, \cdots, m ; \sum_{i=1}^{m} x_{i}=1\right\}$
$S_{2}^{*}=\left\{\left(y_{1}, \cdots, y_{n}\right)^{T} | y_{j} \geq 0, j=1, \cdots, n ; \sum_{i=1}^{n} y_{j}=1\right\}$

定義3 若存在 $m$ 維向量 $\overline{x}$ 和 $n$ 維向量 $\overline{y}$ ，使得對(duì)一切 $m$ 維向量 $x$ 和 $n$ 維向量 $y$ 有：
$\overline{x}^{T} A \overline{y}=\max _{x} x^{T} A \overline{y}=\min _{y} \overline{x}^{T} A y$
則稱 $(\overline{x}, \overline{y})$ 為混合策略對(duì)策問題的鞍點(diǎn)。

定理3 設(shè) $\overline{x} \in S_{1}^{*}, \quad \overline{y} \in S_{2}^{*}$ ，則 $(\overline{x}, \overline{y})$ 為 $G=\left\{S_{1}, S_{2} ; A\right\}$ 的解的充要條件是：
$\left\{\begin{array}{ll}{\sum_{j=1}^{n} a_{i j} \overline{y}_{j} \leq \overline{x}^{T} A \overline{y},} & {i=1,2, \cdots, m} \\ {\sum_{i=1}^{m} a_{i j} \overline{x}_{i} \geq \overline{x}^{T} A \overline{y},} & {j=1,2, \cdots, n}\end{array}\right.$

定理4 任意混合策略對(duì)策問題必存在鞍點(diǎn)，即必存在概率向量 $\overline{x}$ 和 $\overline{y}$ ，使得：
$\overline{x}^{T} A \overline{y}=\max _{x} \min _{y} x^{T} A y=\min _{y} \max _{x} x^{T} A y$

使用純策略的對(duì)策問題（具有穩(wěn)定解的對(duì)策問題）可以看成使用混合策略的對(duì)策問題的特殊情況，相當(dāng)于以概率 1 選取其中某一策略，以概率 0 選取其余策略。

例3 $A,B$ 為作戰(zhàn)雙方， $A$ 方擬派兩架轟炸機(jī)Ⅰ和Ⅱ去轟炸 $B$ 方的指揮部，轟炸機(jī)Ⅰ在前面飛行，Ⅱ隨后。兩架轟炸機(jī)中只有一架帶有炸彈，而另一架僅為護(hù)航。轟炸機(jī)飛至 $B$ 方上空，受到 $B$ 方戰(zhàn)斗機(jī)的阻擊。若戰(zhàn)斗機(jī)阻擊后面的轟炸機(jī)Ⅱ，它僅受Ⅱ的射擊，被擊中的概率為0.3（Ⅰ來不及返回攻擊它）。一旦戰(zhàn)斗機(jī)未被擊中，他將以0.6的概率擊毀其選中的轟炸機(jī)。請(qǐng)為 $A,B$ 雙方各選擇一個(gè)最優(yōu)策略，即，對(duì)于A方應(yīng)該選擇哪一架轟炸機(jī)裝載炸彈？對(duì)于 $B$ 方戰(zhàn)斗機(jī)應(yīng)阻擊哪一架轟炸機(jī)？

解：雙方可選擇的策略集分別是：
$S_{A}=\left\{\alpha_{1}, \alpha_{2}\right\}, \quad \alpha_{1} :$ 轟炸機(jī)Ⅰ裝炸彈，Ⅱ護(hù)航。
$\quad \quad \quad \quad \quad\quad \quad \quad \alpha_{2}：$ 轟炸機(jī)Ⅱ裝炸彈，Ⅰ護(hù)航。

贏得矩陣 $R=\left(a_{i j}\right)_{2 \times 2}$ ， $a_{i j}$ 為 $A$ 方采取策略 $\alpha_{i}$ 而 $B$ 方采取策略 $\beta_{j}$ 時(shí)，轟炸機(jī)轟炸 $B$ 方指揮部的概率，由題意可計(jì)算出：
$a_{11}=0.7+0.3(1-0.6)=0.82$
$a_{12}=1, \quad a_{21}=1$
$a_{22}=0.3+0.7(1-0.6)=0.58$
即贏得矩陣：
$R=\left[\begin{array}{cc}{0.82} & {1} \\ {1} & {0.58}\end{array}\right]$
易求得 $\mu=\max _{i} \min a_{i j}=0.82, \quad v=-\min _{i} \max _{i} a_{i j}=-1$ 。由于 $\mu+v \neq 0$ ，矩陣 $R$ 不存在鞍點(diǎn)，應(yīng)當(dāng)求最佳混合策略。

現(xiàn)設(shè) $A$ 以概率 $x_{1}$ 取策略 $\alpha_{1}$ ，以概率 $x_{2}$ 取策略 $\alpha_{2}$ ； $B$ 以概率 $y_{1}$ 取策略 $\beta_{1}$ ，以概率 $y_{2}$ 取策略 $\beta_{2}$ 。

先從 $B$ 方來考慮問題。 $B$ 采用 $\beta_{1}$ 時(shí)， $A$ 方轟炸機(jī)攻擊指揮部的概率期望值為 $E\left(\beta_{1}\right)=0.82 x_{1}+x_{2}$ ，而 $B$ 采用 $\beta_{2}$ 時(shí)， $A$ 方轟炸機(jī)攻擊指揮部的概率的期望值為 $E\left(\beta_{2}\right)=x_{1}+0.58 x_{2}$ 。若 $E\left(\beta_{1}\right) \neq E\left(\beta_{2}\right)$ ，不妨設(shè) $E\left(\beta_{1}\right)<E\left(\beta_{2}\right)$ ，則 $B$ 方必采用 $E\left(\beta_{1}\right)<E\left(\beta_{2}\right)$ ，則 $B$ 方必采用 $\beta_{1}$ 以減少指揮部被轟炸的概率。故對(duì) $A$ 方選取的最佳概率 $x_{1}$ 和 $x_{2}$ ，必滿足：
$\left\{\begin{array}{l}{0.82 x_{1}+x_{2}=x_{1}+0.58 x_{2}} \\ {x_{1}+x_{2}=1}\end{array}\right.$
即：
$\left\{\begin{array}{l}{a_{11} x_{1}+a_{21} x_{2}=a_{12} x_{1}+a_{22} x_{2}} \\ {x_{1}+x_{2}=1}\end{array}\right.$
由此解得 $x_{1}=0.7, \quad x_{2}=0.3$

同樣，可以從 $A$ 方考慮問題，得：
$\left\{\begin{array}{l}{0.82 y_{1}+y_{2}=y_{1}+0.58 y_{2}} \\ {y_{1}+y_{2}=1}\end{array}\right.$
即：
$\left\{\begin{array}{l}{a_{11} y_{1}+a_{12} y_{2}=a_{21} y_{1}+a_{22} y_{2}} \\ {y_{1}+y_{2}=1}\end{array}\right.$
并解得 $y_{1}=0.7, \quad y_{2}=0.3$ 。 $B$ 方指揮部被轟炸的概率的期望值 $V_{G}=0.874$ 。

記零和對(duì)策 $G$ 的解集為 $T(G)$ ，下面三個(gè)定理是關(guān)于對(duì)策解集性質(zhì)的主要結(jié)果：

定理4 設(shè)有兩個(gè)零和對(duì)策
$G_{1}=\left\{S_{1}, S_{2} ; A_{1}\right\}, \quad G_{2}=\left\{S_{1}, S_{2} ; A_{2}\right\}$
其中 $A_{1}=\left\{a_{i j}\right\}, \quad A_{2}=\left\{a_{i j}+L\right\}, \quad L$ 為任一常數(shù)。則
（1） $V_{G_{2}}=V_{G_{1}}+L$
（2） $T\left(G_{1}\right)=T\left(G_{2}\right)$

定理5 設(shè)有兩個(gè)零和對(duì)策
$G_{1}=\left\{S_{1}, S_{2} ; A\right\}, \quad G_{2}=\left\{S_{1}, S_{2} ; \alpha A\right\}$
其中 $\alpha>0$ 為任一常數(shù)。則：
（1） $V_{G_{2}}=\alpha V_{G_{1}}$
（2） $T\left(G_{1}\right)=T\left(G_{2}\right)$

定理6 設(shè) $G=\left\{S_{1}, S_{2} ; A\right\}$ 為一零和對(duì)策，且 $A=-A^{T}$ 為反對(duì)稱矩陣（亦稱這種對(duì)策為對(duì)稱對(duì)策）。則
（1） $V_{G}=0$
（2） $T_{1}(G)=T_{2}(G)$