引言
社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来解决这样的问题开始于 17 世纪的科学家，如 C.，Huygens 和 W.，Leibnitz 等。现代博弈论起源于 1944 年 J.，Von Neumann 和 O.，Morgenstern 的著作《Theory of Games andEconomic Behavior》。而发扬光大其应用并且拿到诺贝尔经济学奖的学者则冠属普林斯顿大学的John Nash。
博弈论亦称对策论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。博弈论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为博弈行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。博弈论就是研究博弈行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。
博弈论的初步分类和定义
公元前的春秋战国，田忌赛马的故事已经构成了博弈问题的基础。博弈问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。那么一般根据博弈双方同时（同步）出手或异步出手可以分为静态博弈和动态博弈。也可以根据场上对局信息是否完全分为完全信息博弈和不完全信息博弈。若对局是重复进行的，则可以分为无限次重复博弈和有限次重复博弈。
描述博弈论的三要素为玩家（Player）、战略（Strategy）、利得（Utility）。
通常用$I$表示玩家的集合．如果有$n$个局中人，则$I=\{1,2,3,...,n \}$。一般要求一个博弈中至少要有两个玩家。比如田忌赛马的故事中，博弈玩家就有2个。
一局博弈中，可供玩家选择的一个实际可行的完整的行动方案称为一个战略。对于每一个参与博弈的玩家$i$，必然存在一个战略集合$S_i$，且该战略集合不为空集并至少包含两个战略。例如在田忌赛马问题中，所有玩家的战略均为$\{ 上马，中马，下马\}$
所有的战略组合则形成了一个战略组$\mathrm S$。在田忌赛马问题中，可能出现的战略组可以是$(上马，中马)\in \mathrm S$。其中上马为玩家$A$的战略，中马为玩家$B$的战略。
因此，由实分析的知识可以知道战略组$\mathrm S$为所有可能战略$S_i$的笛卡尔积，即如下式所示：
$$
\mathrm S= S_1 \times S_2 \times S_3 \times …\times S_n
$$
对于每一个战略组合，都有且只有一个结果。这也很现实，如果田忌出上马而对家出中马，明显有且只有田忌获得胜利（同时对家该局判定为输）这一个结果；在其他的博弈中，也可能出现平局等结果。容易知道这是一个一一映射，因此我们用利得函数$U_i(\mathrm S)$来衡量最后的结果。这代表着第$i$个玩家在这场游戏中得到的分数（或者利益）。这种分数常常不是具体化的，而仅仅作为一种差异化的体现。一般利得函数$U$为向量函数，因为其包含了各个玩家的利得，如下式所示：
$$
U(\mathrm S)=(U_1(\mathrm S),U_2(\mathrm S),…,U_i(\mathrm S))
$$
以玩家的角度来看，因为每一个战略组所得到的利得不同，因此这个情况下利得可以表示为矩阵$\mathbf M_i$。例如，玩家$A$一共有$m$个战略，玩家$B$一共有$n$个战略，当玩家$A$和玩家$B$选定战略$\alpha_i$和$\beta_j$后，就形成了一个局势可见的战略组合，这样的局势共有$m\times n$个。对任一战略组合，记利得为$U_{ij}$，即可以得到利得矩阵
博弈论事实上就是在研究如何在已知信息下找到最优的战略，因此具体事例还需具体分析。按照理性人假设，每一个参与博弈的玩家都会试图寻找最优策略，因此博弈容易进入一个均衡状态，这种均衡状态将会在后文提到。
因此博弈也可以表示为集族（或者空间）$G={I,S_i,\mathbf M_I} $
完全信息静态博弈
零和博弈
零和博弈是一种最经典也是最特殊的博弈，博弈玩家一般只有两名，且均只有有限个战略。而博弈双方的利得矩阵之和必为零矩阵。
> > 例1 考虑一零和博弈，其中玩家A和B各有战略$S_A=\{\alpha_1,\alpha_2,\alpha_3\}$，$S_B=\{\beta_1,\beta_2,\beta_3,\beta_4\}$ > > 利得矩阵为 > $$ > \mathbf M_A=\begin{bmatrix} > 12 & -6 & 30 & -22\\ > 14 & 2 & 18& 10\\ > -6 & 0 & -10& 16 > \end{bmatrix} > $$ >
为满足所有矩阵的加和$\sum \mathbf M$为零矩阵，该例中B矩阵很明显为$\mathbf M_B=-\mathbf M_A$。另外，利得矩阵也可以用有序数对组的表格表示，该类表格被称为利得表
| $\beta_1$ | $\beta_2$ | $\beta_3$ | $\beta_4$ | |
|---|---|---|---|---|
| $\alpha_1$ | （12，-12） | （-6，6） | （30，-30） | （-22，22） |
| $\alpha_2$ | （14，-14） | （2，-2） | （18，-18） | （10，-10） |
| $\alpha_3$ | （-6，6） | （0，0） | （-10，10） | （16，-16） |
该博弈中，对于玩家A，由于30的利得远超所有其他情况能获得的利得，因此单纯地，玩家A始终会选择战略$\alpha_1$，而对于玩家B，很明显22的利得是全场最大的，因此玩家B也会始终选择战略$\beta_4$，由于利得是由双方共同决定的，若玩家B寻得其最优战略，则会导致玩家A的利得由30变为-22。考虑到此时双方的选择都会使得对方的损失最大化，因此合适的策略应该是在最坏的结果中寻找最好的结果。
因此对于玩家A，$\alpha_1$的最劣利得为$\min\{12,-6,30,-22\}=-22$，$\alpha_2$的最劣利得为$\min\{14,2,18,10\}=2$，$\alpha_3$的最劣利得为$\min\{-6,0,-10,16\}=-10$。而所有的最劣利得中，相对损失小的则为$\max\{-22,2,-10\}=2$，在这种情况下，无论玩家B选择何种战略，玩家A的损失都不会超过2。而对于玩家B，同理可以知道最劣的利得中最优利得为$\max{-14,-2,-30,-16}=-2$。因此玩家A和玩家B都倾向于选择$\alpha_2$和$\beta_2$作为他们各自的战略。注意到在利得矩阵中，2 既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变战略，任一局中人都不可能通过变换战略来增大利得或减少损失，称这样的局势为博弈的一个稳定解或均衡解。亦或称为零和博弈的纳什均衡（Nash Equilibrium）。
注意到这样的性质，在零和博弈中，寻找最优的战略路径实际上在寻找局部的极值。我们引入如下的定义来使得其严格化。
定义1：设$f(x,y)$为一个定义在$\mathbb R$上的实值函数，且$x\in A,y\in B$，如果存在$x^*\in A,y^*\in B$使得对一切$x\in A$和$y\in B$有 $$ f(x,y^*)\leq f(x^*,y^*)\leq f(x^*,y) $$ 则$f(x^*,y^*)$称为函数 $f$ 的一个鞍点。 定义2：存在一个零和博弈的空间$G=\{I,S_A,S_B,\mathbf M_I\}$，其中$S_A=\{\alpha_1,\alpha_2,\alpha_3\,...,\alpha_m \}$，$S_B=\{\beta_1,\beta_2,\beta_3,...,\beta_n \}$，$\mathbf M_I=[U_{ij}]_{m \times n}$，若等式 $$ \max_i\min_jU_{ij}=\min_j\max_iU_{ij}=U_{i^*j^*} $$ 成立，则$U_G=U_{i^*j^*}$为该零和博弈的均衡利得，而满足上式的战略组合$(\alpha_{i^*},\beta_{i^*})$ 则被称为**鞍点**或者**稳定解**由于博弈的利得矩阵是离散的，当博弈问题有解时，其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质：
性质1：无差别性 若战略组合集$S=\{(\alpha_{i_1},\beta_{j_1}),(\alpha_{i_2},\beta_{j_2}),...,(\alpha_{i_n},\beta_{j_n})\}$为博弈$G$的$n$个解，则必然有$U_{i_1j_1}=U_{i_2j_2}=...=U_{i_nj_n}$。 性质2：可交换性 若若战略组合集$S=\{(\alpha_{i_1},\beta_{j_1}),(\alpha_{i_2},\beta_{j_2}),...,(\alpha_{i_n},\beta_{j_n})\}$为博弈$G$的$n$个解，则任意两两战略角标的线性交换$(\alpha_{i_1},\beta_{j_2}),(\alpha_{i_1},\beta_{j_2})$等也是其中的解。囚徒困境
“囚徒困境”是一种带有博弈性质的心理活动，体现了个人理性和集体理性、个人主义和道德主义的关系。行为主体面临选择的两难境地时，往往会趋向于考虑相对利己但是不利于集体最大利益的方式。
囚徒困境也是最经典的非零和博弈，其问题描述如下例所示：
例2：两个人因盗窃被捕，警方怀疑其有抢劫行为但未获得确凿证据可以判他们犯了抢劫罪，除非有一个人供认或两个人都供认。即使两个人都不供认，也可判他们犯盗窃物品的轻罪。
囚徒被分离审查，不允许他们之间互通消息，并交代政策如下：
1.如果两个人都供认，每个人都将因抢劫罪加盗窃罪被判三年监禁；
2.如果两个人都拒供，则两个人都将因盗窃罪被判处半年监禁；
3.如果一个人供认而另一个拒供，则供认者被认为有立功表现而免受处罚，拒供者将因抢劫罪、盗窃罪以及抗拒从严而被重判5年。
那么这样的问题可以用一个模拟的利得表表示
| A\B | 供认 | 拒供 |
|---|---|---|
| 供认 | （-3，-3） | （0，-5） |
| 拒供 | （-5，0） | （-0.5，-0.5） |
由于二人的利得为非对称，非零和的，因此不能简单使用零和矩阵的方式进行寻找最优战略。
为了寻找最优战略，我们引入如下定理：
定理1：强占优战略
若$s_i^*$是玩家$i$的强占优策略，$S_j$是玩家$j$的战略集合，则其应满足如下的性质
$$
\forall s_i\in S_i \
\forall s_j \in S_j \
U_i(s_i^*,s_j)>U(s_i,s_j)
$$
遵循定理1，我们观察例1举出的囚徒困境，若玩家A选择供认，因为$-3>-5,0>-0.5$无论对方选择拒供或者供认，所获得的利得都应该要比拒供更大。对于玩家B也是同理，因此最后的最优战略组合应该是$(供认,供认)$。这能说明为什么甚至在合作对双方都有利时，保持合作也是困难的。
在强占优策略无法行得通时，我们还有其他的方法寻找最优战略。
例3 考虑一博弈$G=\{I,S_A,S_B,\mathbf M_I\} $，其中玩家A和B各有战略$S_A=\{a,b,c\}$，$S_B=\{\alpha, \beta,\gamma,\epsilon\}$ 利得矩阵为 $$ \mathbf M_A=\begin{bmatrix} 1 & 3 & 0 & 3\\ 2 & 3 & 1 & 2\\ 2 & 4 & 1 & 3 \end{bmatrix} \ \mathbf M_B= \begin{bmatrix} 1 & 2 & 3 & 1\\ 3 & 4 & 3 & 3\\ 1 & 2 & 1 & 3 \end{bmatrix} $$定理2：弱占优战略
若$s_i^*$是玩家$i$的弱占优策略，$S_j$是玩家$j$的战略集合，则其应满足如下的性质
$$
\forall s_i\in S_i \
\forall s_j \in S_j \
U_i(s_i^*,s_j)\geq U(s_i,s_j)，\mathrm {and \ for \ some \ that} \
U_i(s_i^*,s_j)> U(s_i,s_j)
$$
对于玩家A，我们寻找其弱占优策略，可以得到A的弱占优战略是$c$，而对于B，我们可以得到弱占优战略是$\beta$，因此博弈的最优战略组合为$(c,\beta)$。
考虑更现实的例子，当很多情况下占优策略不明显时，我们需要逆行寻找劣策略，通过反复剔除劣策略达到战略目的。
定理3：强劣战略
若$\bar s_i$是玩家$i$的强劣策略，$S_j$是玩家$j$的战略集合，则其应满足如下的性质
$$
\forall s_i\in S_i \
\forall s_j \in S_j \
U_i(\bar s_i,s_j)<U(s_i,s_j)
$$
例4 考虑一博弈$G=\{I,S_A,S_B,\mathbf M_I\} $，其中玩家A和B各有战略$S_A=\{a,b,c\}$，$S_B=\{\alpha, \beta\}$ 利得矩阵为 $$ \mathbf M_A=\begin{bmatrix} 5 & 4 \\ 6 & 3 \\ 6 & 4 \end{bmatrix} \ \mathbf M_B= \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 4 & 4 \end{bmatrix} $$定理4：弱劣战略
若$\bar s_i$是玩家$i$的弱劣策略，$S_j$是玩家$j$的战略集合，则其应满足如下的性质
$$
\forall s_i\in S_i \
\forall s_j \in S_j \
U_i(\bar s_i,s_j)\leq U(s_i,s_j)
$$
对于玩家A，首先剔除弱劣战略$b$，玩家B考虑剔除劣战略$\beta$，玩家A再考虑剔除弱劣战略$a$，此时场上只剩下战略组合$(c,\alpha)$，因此再根据定理1可得博弈的最优战略组合为$(c,\alpha)$。但如果先剔除战略$a$，玩家B则会考虑剔除劣战略$\alpha$，则最后的最有战略组合为$(c,\beta)$。注意到剔除弱劣战略顺序不同会导致最后的结果不同。
我们所得到的最优策略组合，也同样是一种纳什均衡。纳什均衡的定义在于，对应这样的一个结果，任何一个玩家独自改变战略， 他的利得不会增加。数理定义为
定理5：纳什均衡
若战略组合$(s_i^*,s_j^*)$是纳什均衡，$S_i$是玩家$i$的战略集合，则其应满足如下的性质
$$
\forall s_i \in S_i \
U(s_i^*,s_j^*)\geq U(s_i,s_j^*)
$$