博弈论又称对策论的入门及在军事博弈问题上的简单实战
学习知识要实时简单回顾,我把学习的博弈论简单梳理一下,方便入门与复习。
博弈论模型
博弈论简介
社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾,应用科学的方法来解决这样的问题开始于 17 世纪的科学家,如 C.,Huygens 和 W.,Leibnitz 等。现代对策论起源于 1944 年 J.,Von Neumann 和 O.,Morgenstern 的著作《Theory of Games and Economic Behavior》。对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。
一般认为,它既是现代数学的一个新分支,也是运筹学中的一个重要学科。对策论发展的历史并不长,但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系,并且处理问题的方法又有明显特色。所以日益引起广泛的注意。
在日常生活中,经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动方案,并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案,以及如何找到这个合理的行动方案的数学理论和方法。
对策问题
对策问题的特征是参与者为利益相互冲突的各方,其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。先考察一个实际例子。
例 1(囚徒的困境) 警察同时逮捕了两人并分开关押,逮捕的原因是他们持有大量伪币,警方怀疑他们伪造钱币,但没有找到充分证据,希望他们能自己供认,这两个人都知道:如果他们双方都不供认,将被以持有大量伪币罪被各判刑 18 个月;如果双方都供认伪造了钱币,将各被判刑 3 年;如果一方供认另一方不供认,则供认方将被从宽处理而免刑,但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列于表 。
表中每对数字表示嫌疑犯 BA、 被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚,最保险的办法自然是承认制造了伪币。
从这一简单实例中可以看出对策现象中包含有的几个基本要素。
- 局中人
在一个对策行为(或一局对策)中,有权决定自己行动方案的对策参加者,称为局中人。通常用 I 表示局中人的集合.如果有 n 个局中人,则 I = 1,2, … ,n I=\text{{1,2,\dots,n}} I=1,2,…,n。一般要求一个对策中至少要有两个局中人。在例 1 中,局中人是 A、B两名疑犯。 - 策略集
一局对策中,可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人 i i i, i ∈ I i\in I i∈I,都有自己的策略集 S i S_{i} Si。一般,每一局中人的策略集中至少应包括两个策略。 - 赢得函数(支付函数)
在一局对策中,各局中人所选定的策略形成的策略组称为一个局势,即若 S i S_{i} Si是第 i个局中人的一个策略,则 n 个局中人的策略组
s = ( s 1 , s 2 , ⋯ , s n ) s=\left(s_{1},s_{2},\cdots,s_{n}\right) s=(s1,s2,⋯,sn)
就是一个局势。全体局势的集合 S 可用各局中人策略集的笛卡尔积表示,即 S = S 1 × S 2 × ⋯ × S n S=S_1\times S_2\times\cdots\times S_n S=S1×S2×⋯×Sn
当局势出现后,对策的结果也就确定了。也就是说,对任一局势, s ∈ S s\in S s∈S ,局中人i 可以得到一个赢得 H i ( s ) H_{_i}(s) Hi(s) 。显然, H i ( s ) H_{_i}(s) Hi(s)是局势 s 的函数,称之为第 i 个局中人的赢得函数。这样,就得到一个向量赢得函数。
本节我们只讨论有两名局中人的对策问题,其结果可以推广到一般的对策模型中去。
零和对策(矩阵对策)
零和对策是一类特殊的对策问题。在这类对策中,只有两名局中人,每个局中人都只有有限个策略可供选择。在任一纯局势下,两个局中人的赢得之和总是等于零,即双方的利益是激烈对抗的。
设局中人I、II的策略集分别为
S
1
=
{
α
1
,
⋯
,
α
m
}
,
S
2
=
{
β
1
,
⋯
,
β
n
}
S_1=\{\alpha_1,\cdots,\alpha_m\},S_2=\{\beta_1,\cdots,\beta_n\}
S1={α1,⋯,αm},S2={β1,⋯,βn}
当局中人I选定策略
α
i
\alpha_{i}
αi和局中人II选定策略
β
i
\beta_{i}
βi后,就形成了一个局势
(
α
i
,
β
j
)
(\alpha_{i},\beta_{j})
(αi,βj),可见这样的局势共有 mn 个。对任一局势
(
α
i
,
β
j
)
(\alpha_{i},\beta_{j})
(αi,βj),记局中人I的赢得值为
a
i
j
a_{_{ij}}
aij,并称
A
=
[
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
.
.
.
⋯
⋯
⋯
a
m
1
a
m
2
⋯
a
p
n
]
A=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\...&\cdots&\cdots&\cdots\\ a_{m1}&a_{m2}&\cdots&a_{pn}\end{bmatrix}
A=
a11a21...am1a12a22⋯am2⋯⋯⋯⋯a1na2n⋯apn
为局中人I的赢得矩阵(或为局中人II的支付矩阵)。由于假定对策为零和的,故局中人II的赢得矩阵就是 -A。
当局中人I、II和策略集
S
1
、
S
2
S_1、S_2
S1、S2及局中人I的赢得矩阵 A 确定后,一个零和对策就给定了,零和对策又可称为矩阵对策并可简记成
G
=
{
S
1
,
S
2
;
A
}
G=\{S_1,S_2;A\}
G={S1,S2;A}
零和对策的混合策略
具有稳定解的零和问题是一类特别简单的对策问题,它所对应的赢得矩阵存在鞍点,任一局中人都不可能通过自己单方面的努力来改进结果。然而,在实际遇到的零和对策中更典型的是
μ
+
ν
≠
0
\mu+\nu\neq0
μ+ν=0的情况。由于赢得矩阵中不存在鞍点,此时在只使用纯策略的范围内,对策问题无解。下面我们引进零和对策的混合策略。
设 局 中 人 I 用 概率
x
i
\mathcal{x}_{i}
xi 选 用 策策略
α
i
\alpha_{i}
αi , 局 中 人 II 用 概 率
y
i
\mathcal{y}_{i}
yi选 用 策 略
β
j
\beta_{j}
βj,
∑
i
=
1
m
x
i
=
∑
j
=
1
n
y
j
=
1
\sum\limits_{i=1}^m x_i=\sum\limits_{j=1}^n y_j=1
i=1∑mxi=j=1∑nyj=1,记
x
=
(
x
1
,
⋯
,
x
m
)
T
,
y
=
(
y
1
,
⋯
,
y
n
)
T
x=(x_1,\cdots,x_m)^T,y=(y_1,\cdots,y_n)^T
x=(x1,⋯,xm)T,y=(y1,⋯,yn)T,则局中人I的期望赢得为
E
(
x
,
y
)
=
x
T
A
y
E(x,y)=x^T A y
E(x,y)=xTAy。
分别称 S 1 ∗ S_{1}^{\ast} S1∗与 S 2 ∗ S_{2}^{\ast} S2∗为局中人I和II的混合策略。
下面简单地记
S
1
⋆
=
{
(
x
1
,
⋯
,
x
m
)
T
∣
x
i
≥
0
,
i
=
1
,
⋯
,
m
i
∑
i
=
1
m
x
i
=
1
}
,
S
2
⋆
=
{
(
y
1
,
⋯
,
y
n
)
T
∣
y
j
≥
0
,
j
=
1
,
⋯
,
m
,
∑
j
=
1
n
y
j
=
1
}
\begin{array}{l}S_1^\star=\{(x_1,\cdots,x_m)^T\mid x_i\geq0,i=1,\cdots,m_i\sum_{i=1}^m x_i=1\},\\ \\ S_2^\star=\{(y_1,\cdots,y_n)^T\mid y_j\geq0,j=1,\cdots,m,\sum_{j=1}^n y_j=1\}\end{array}
S1⋆={(x1,⋯,xm)T∣xi≥0,i=1,⋯,mi∑i=1mxi=1},S2⋆={(y1,⋯,yn)T∣yj≥0,j=1,⋯,m,∑j=1nyj=1}
定义 若存在 m 维概率向量
x
‾
\overline{x}
x 和 n 维概率向量
y
‾
\overline{y}
y ,使得对一切 m 维概率向量 x 和 n 维概率向量 y 有
x
‾
T
A
y
‾
=
max
x
x
T
A
y
‾
=
min
y
x
‾
T
A
y
\overline{x}^T A\overline{y}=\max\limits_x x^T A\overline{y}=\min\limits_y\overline{x}^T A y
xTAy=xmaxxTAy=yminxTAy
则称
(
x
‾
,
y
‾
)
(\overline{x},\overline{y})\text{}
(x,y)为混合策略对策问题的鞍点。
定理 设
x
‾
∈
S
1
∗
,
y
‾
∈
S
2
∗
\overline{x}\in S_1^{\ast},\overline{y}\in S_2^{\ast}
x∈S1∗,y∈S2∗则
(
x
‾
,
y
‾
)
(\overline{x},\overline{y})\text{}
(x,y)为
G
=
{
S
1
,
S
2
;
A
}
G=\{S_{1},S_{2};A\}
G={S1,S2;A}的解的充要条件是:
[
∑
j
=
1
n
a
v
y
‾
j
≤
x
‾
T
A
y
‾
,
i
=
1
,
2
,
⋯
,
m
∑
j
=
1
m
a
i
j
x
‾
i
≥
x
‾
T
A
y
‾
,
j
=
1
,
2
,
⋯
,
n
]
\begin{bmatrix}\sum_{j=1}^n a_v\overline{y}_j\le\overline{x}^T A\overline{y},&i=1,2,\cdots,m\\\\ \sum_{j=1}^m a_{ij}\overline{x}_i\ge\overline{x}^T A\overline{y},&j=1,2,\cdots,n\end{bmatrix}
∑j=1navyj≤xTAy,∑j=1maijxi≥xTAy,i=1,2,⋯,mj=1,2,⋯,n
定理 任意混合策略对策问题必存在鞍点,即必存在概率向量
x
‾
\overline{x}
x 和
y
‾
\overline{y}
y ,使得:
x
‾
T
A
y
‾
=
max
x
min
y
x
T
A
y
=
min
y
max
x
x
T
A
y
\overline{x}^TA\overline{y}=\max\limits_x\min\limits_y x^TAy=\min\limits_y\max\limits_x x^TAy
xTAy=xmaxyminxTAy=yminxmaxxTAy。
使用纯策略的对策问题(具有稳定解的对策问题)可以看成使用混合策略的对策问题的特殊情况,相当于以概率 1 选取其中某一策略,以概率 0 选取其余策略。
军事博弈问题
A、B 为作战双方, A 方拟派两架轰炸机I和II去轰炸 B 方的指挥部,轰炸机I在前面飞行,II随后。两架轰炸机中只有一架带有炸弹,而另一架仅为护航。轰炸机飞至 B 方上空,受到 B 方战斗机的阻击。若战斗机阻击后面的轰炸机II,它仅受II的射击,被击中的概率为 0.3(I来不及返回攻击它)。若战斗机阻击I,它将同时受到两架轰炸机的射击,被击中的概率为 0.7。一旦战斗机未被击中,它将以 0.6 的概率击毁其选中的轰炸机。请为 BA、 双方各选择一个最优策略,即:对于 A 方应选择哪一架轰炸机装载炸弹?对于 B 方战斗机应阻击哪一架轰炸机?
求解
编写不易,求个点赞!!!!!!!
“你是谁?”
“一个看帖子的人。”
“看帖子不点赞啊?”
“你点赞吗?”
“当然点了。”
“我也会点。”
“谁会把经验写在帖子里。”
“写在帖子里的那能叫经验贴?”
“上流!”
cheer!!!