博弈论算法
一、博弈的战略式表述及纳什均衡的定义
在博弈论里,一个博弈可以用两种不同的方式来表述:一种是战略式表述(strategic form
representation),另一种是扩展式表述(或译为“展开式表述”)(extensive form representation)。
从分析的角度看,战略式表述更适合于静态博弈,而扩展式表述更适合于讨论动态博弈。
1.1 博弈的战略式表述
战略式表述又称为标准式表述(normal form representation)。在这种表述中,所参与人同时选择各自
的战略,所有参与人选择的战略一起决定每个参与人的支付。
i
战略式表述给出:
1,2,
,
。
1.博弈的参与人集合:
1,2,
2.每个参与人的战略空间: ,
iS i
。
,
,
(
n
i
u s s
3.每个参与人的支付函数: 1
2
i
,
u
代表战略式表述博弈。
我们用
例如在两个寡头产量博弈里,企业是参与人,产量是战略空间,利润是支付;战略式表述博弈为:
G S
1
。
n
n
),
,
,
s
n
;
S u
1
n
1,2,
,
,
,
,
,
n
0;
1
(
,
q q
1
2
),
2
(
,
q q
1
2
)
(1.1)
,
,战略组合
s
s
1
i
,
u
n
s
1
s
1
i
s
,
,
,
,
i
,
s
i
1 ,
s
是一个纳
,
s
的情况下第 个参与人
n
s
n
,
,
0,
q
2
这里 iq 、 i别表示第 i 个企业的产量和利润。
1.2 纳什均衡的定义
G q
1
有 n 个参与人的战略式表述博弈
;
S u
1
n
什均衡。如果对于每一个i 、 is 是给定其他参与人选择
的最优战略,即
G S
1
,
,
,
u s s
i
i
或者用另一种表述方式, is 是下述最大化问题的解:
(
u s
i
i
s
)
(
,
i
i
),
S
,
s
i
i
i
1, 2,...,
我们用这个定义来检查一个特定的战略组合是否是一个纳什均衡。
argmax
,
s s
1
i
i
(
u s
1
i
,...,
,...,
s
1
i
s
i
),
s
n
i
,
(1.2)
(1.3)
;
n s
i
S
i
1.3 囚徒困境
两个嫌疑犯作案后补警察抓住,被分别关在不同的房间里审讯。警察知道两人有罪,但缺乏足够的证
据定罪,除非两人当中至少有一个人坦白。警察告诉每个人:如果两个都不承认,每个人都以轻微的犯罪
判刑 1 年;如果两人都坦白,各判刑 8 年;如果两人中一个人坦白另一个人抵赖,坦白的释放出去,抵赖
的判刑 10 年。这样,每一个嫌疑犯面临四个可能的后果:获释(自己坦白同伙抵赖);被判刑 1 年(自己
抵赖同伙也抵赖);被判刑 8 年(自己坦白同伙也坦白);被判刑 10 年(自己抵赖但同伙坦白)。
囚徒困境
囚犯 B
表 1
坦白
抵赖
囚犯 A
坦白 (-8,-8)
(0,-10)
抵赖 (-10,0)
(-1,-1)
在这个博弈中,每个囚徒都有两种可选择的战略:坦白或抵赖。显然,不论同伙选择什么战略,每个
囚徒的最优战略是“坦白”,比如说,如果 B 选择坦白,A 选择坦白时支付为-8,选择抵赖时的支付为-10,
因而坦白比抵赖好;如果 B 选择抵赖,A 坦白时的支付为 0,抵赖时的支付为-1,因而坦白还是比抵赖好。
就是说,“坦白”是囚徒 A 的占优战略。类似的,“坦白”也是 B 的占优战略。
在囚徒困境里,(坦白,坦白)是一个纳什均衡,而(抵赖,抵赖)不是一个纳什么均衡,因为给定
同伙选择抵赖,自己选择抵赖时得到-1,选择坦白时得到 0,因而抵赖不是自己的最优战略,类似的,(坦
白,抵赖)和(抵赖,坦白)也不是纳什均衡。
二、矩阵对策
2.1 纯零和对策
矩阵对策也叫零和对策,是一类特殊的对策问题。在这类对策中,只有两名局中人,每个局中人都只
有有限个策略可供选择。在任一纯局势下,两个局中人的赢得之和总是等于零,即双方和利益是激烈对抗
的。
设局中人 I 、 II 的策略集分别为:
S
1
m
,
,
1
,
S
2
1
n
,
,
(2.1)
当局中人 I 选定策略 i和局中人 II 选定策略 j 后,就形成了一个局势 (
j ,可见这样的局势共有
i
)
,
mn 个,对任一局势 (
i
,
)
j ,记局中人 I 的赢得值为 ija ,并称
a
a
1
12
a
a
22
2
a
a
a
11
a
21
a
A
1
m
m
2
n
n
mn
为局中人 I 赢得矩阵(或为局中人 II 的支付矩阵)。由于假定对策为零和的,故局中人 II 的赢得矩阵就是
A 。
当局中人 I 、 II 和策略集 1S 、 2S 及局中人 I 的赢得矩阵 A 确定后,一个零和对策就给定了,零和对
策又可称为矩阵对策,并可简记成:
1
双方都应考虑到对方有使自己损失最大的动机。
G S S A
;
,
2
定义 1 鞍点
)
设 ( ,
y B ,有
f x y 为一个定义在 A y B
及
x
上的实值函数,如果存在
x
,
A y
使得一切 x A 和
B
( ,
f x y
)
(
,
f x y
)
(
,
f x y
)
(2.2)
,
x y
为函数 f 的一个鞍点。
)
则称 (
Mathematica 画图说明鞍点
定义 2 赢得矩阵的鞍点
设
G S S A
;
,
1
2
a
i
j
)
相对应的元素 i
V
成立,记 G
阵中与 (
,
j
定理 1 极大极小原理
,记
G S S A
设
;
,
i
1
2
,
,
S
1
,
1
为矩阵对策,其中
max min
j
2
m
min max
a
a
ij
ij
S
1
2
n
a
i
j
,
,则称 GV 为对策G 的值,使式成立的纯局势 (
j
(2.3)
)
为对策G 鞍点或稳定解,赢得矩
ja 称为赢得矩阵的鞍点, i 和 j 分别称为局中人 I 与 II 的最优纯策略。
,
A
(
)
a
ij n m
。若等式
,
,
,
,
2
j
i
i
i
max min ij
a
,
min max ij
a
i
j
j
i
,则必有
0
定理 2 零和对策解的判定
零和对策G 具有稳定解的充要条件是
0
2.2 零和对策的混合策略
定义 3 混合策略
设局中人 I 用概率 ix 选用策略 ia ,局中人 II 用概率 jy 选用策略 j ,
1(
x
,
x
那么
,
x
m
)T
,
y
1(
y
,
,
y
n
)T
,则局中人 I 的期望赢得为 ( ,
E x y
)
y
j
1
,记
n
m
x
i
1
i
T
x Ay
。
1
j
1 :S 策略
概率
, m
1,
1,
x
, m
x
:S 策略
2
概率
1,
n
,
1,
y
,
y
n
分别称 1S 与 2S 为局中人 I 和 II 的混合策略。一般的记法如下:
,
m
0,
) |
T
{(
1,
i
,
,
S
1
x
m
x
1
x
i
;
S
2
{(
y
1
,
,
y
n
) |
T
y
j
0,
j
1,
,
;
n
m
i
1
n
j
1
x
i
1}
y
j
1}
定义 4 混合策略对策问题的鞍点
若存在 m 维概率向量 x 和 n 维向量 y ,使得对一切 m 维向量 x 和 n 维向量 y 有
T
x Ay
x y 为混合策略对策问题的鞍点。
)
则称 ( ,
定理 3 鞍点的判定
设
x
S ,
1
y
S ,则( ,
2
max
x
T
x Ay
min
y
T
x Ay
的解的充要条件是:
2
1
,
;
)
x y 为
G S S A
n
T
x Ay
T
x Ay
a x
ij
i
a y
ij
1
m
1
j
j
i
,
i
,
j
1,2,
,
m
1,2,
,
n
定理 4 鞍点的存在性
任意混合策略对策问题必存在鞍点,即必存在概率向量 x 和 y ,使得:
T
x Ay
下面是三个关于零和对策解集的定理,设零和对策G 的解集为 (
T G
T
x Ay
min
y
T
x Ay
max
x
)
定理 5 加法律
设两个零和对策
G
1
S S A G
1
2
;
,
,
2
1
(2.4)
(2.5)
定理 6 乘法律
设两个零和对策
G
1
S S A G
1
2
;
,
,
2
{ },
a
ij
A
2
{
a
ij
},
L L
为任一常数。则
2
;
,
S S A
2
1
(i)
V
V
G
G
2
1
)
(ii) (
T G
1
A
,其中 1
L
(
T G
2
)
0 为任一常数。则
,
S S
1
2
(i)
V
G
2
(ii) (
T G
1
;
A
,其中
V
G
1
)
T G
2
(
)
定理 7 对称律
G S S A
设
;
,
1
2
为一零和对策,且
A
A 为反对称矩阵(亦称这种对策为对称对策)。则
T
GV
(
T G T G
1
T G 为局中人 I 和 II 的最优策略集。
(i)
(ii)
0
)
)
(
2
)
)
T G 和 2(
其中 1(
2.3 零和对策的线性规划解法
2m 且 2n 时,通常采用线性规划方法求解零和对策问题
当
局中人 I 选择混合策略 x 的目的是使得
T
x Ay
T
x Ay
max min
y
x
max min
y
x
(
T
x A
n
j
1
y e
j
j
) max min
y
x
n
j
1
E y
j
j
其中 je 为只有第 j 个分量为 1 而其余分量均为零的单位向量,
y
E y
j
0(
jy
,
在
1
j
n
n
j
j
min
Y
j
1
于
j
时达到最小值u ,故 x 应为线性规划问题。
k
)
E
j
T
x Ae
j
。记
u E
k
min
j
E
j
,由
a x
ij
i
,
u j
1,2,
,
n
E
即
j
E
k
1
u
m
ky ,
max
1
i
x
i
. .
s t
1
m
x
i
i
1
0,
i
1,2,
,
m
(2.6)
(2.7)
(2.8)
解。
同理, y 应为线性规划
max
. .
s t
v
n
j
1
n
1
j
y
j
a y
ij
j
,
u i
1,2,
,
m
y
j
1
0,
j
1,2,
,
n
由线性规划知识,和两个互为对偶线性规划,它们具有相同的最优目标函数值。
不妨设 0u ,对变换
则线性规划问题化为
x
'
i
x
i
u
,
i
1,2,
,
m
m
i
1
m
1
i
'
x
i
min
. .
s t
x
'
i
a x
ij
'
i
1,
j
1,2,
,
n
0,
i
1,2,
,
m
同理,对作变换
则线性规划问题化为
y
'
j
y
j
v
,
j
1,2,
,
n
max
y
'
i
m
1
i
n
. .
s t
1
j
'
y
j
a y
ij
'
j
1,
i
1,2,
,
m
0,
j
1,2,
,
n
(2.9)
三、双矩阵对策
双矩阵对策又叫二人非常数和对策。
所谓常数和对策是指局中人 I 和局中人 II 所赢得的值之和为一常数。显然,二人零和对策是二人常数
和对策的特例,即常数为零。
对于二人常数和对策,有纯策略对策和混合策略对策,其求解方法与二人零和对策是相同的。二人非
常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。
3.1 纯策略问题
囚徒困境是一个典型的二人非常数和对策,每人的赢得矩阵是不相同的。
对于一般纯策略问题,局中人 I 、 II 的赢得矩阵如表 2 所示。其中局中人 I 有 m 个策略 1
, , ,
m
局中人 II 有 n 个策略 1
1
(
C
{ ,
1
n
G S S C C
1
)ij
c
m
1
,
,
2
n
, , ,分别记为
{
,
S
=
1
1
m
为局中人 I 的赢得矩阵, 2
2
)ij
(
C
c
2
}
,
=
2
, }
{ ,
1
n
},
S
为局中人 II 的赢得矩阵。因此,双矩阵对策记为
m
n
表2
)
)
(
1
c
22
2
,
c
22
2
,
c
m
1
2
,
c
11
1
c
11
(
)
(
2
1
2
,
c
c
12
12
(
1
c
21
)
2
,
c
21
2
,
c
1
m
(
1
c
1
m
)
(
1
c
m
2
)
2
策略
1
2
m
min max
j
i
n
2
,
c
1
n
1
c
1
n
(
)
(
1
c
2
n
1
c
mn
2
,
c
2
n
2
,
c
mn
)
)
(
2
c
ij
定义 5 双矩阵对策的 Nash 平衡点
设
G S S C C
{ ,
1
,
,
2
1
2
}
是一双矩阵对策,若等式
1
c
j
i
min max
1
c
ij
2
,
c
j
i
j
i
(3.1)
)
为
成立,则记
v
1
1
c
i
j
,并称 1v 为局中人 I 的赢得值,记,并称 2v 为局中人 II 的赢得值,称 (
j
,
i
G 在纯策略下的解(或 Nash 平衡点),称 i 和 j 分别为局中人 I , II 的最优纯策略。
实际上,定义 5 也同时给出了纯策略问题的求解方法。
因此,对于囚徒困境的例子, ((1,0),(1,0)) 是 Nash 平衡点,这里 (1,0) 表示以概率 1 取第一个策略,
也就是说,坦白是他们的最佳策略。
3.2 混合对策问题
如果不存在使式成立的对策,则需要求混合对策。类似于二人零和对策情况,需要给出混合对策的最
优解。
混合对策问题的基本概念
定义 6 非合作平衡点
G S S C C
在对策
}
{ ,
1
,
,
1
2
2
中若存在策略对
x
,
S y
1
使得
S
2
1
T
x C y
2
T
x C y
,
v
x y 为 G 的一个非合作平衡点。记
1
)
1
T
,
x C y
x
2
T
,
y
x C y
1
2,
T
x C y v
S
1
S
2
2
T
x C y
(3.2)
,则称 1
2,v v 分别为局中人 I ,II 的
对称 (
赢得值。
对于混合对策问题有以下三个定理。
定理 8 双矩阵对策非合作平衡点的存在性
每个双矩阵对策至少存在一个非合作平衡点。
定理 9 双矩阵对策非合作平衡点的判定
G S S C C
,
,
1
2
}
的平衡点的充分必要条件是
1
c y
ij
j
1
T
x C y
,
i
1,2,
m
…,
2
c x
ij
i
2
T
x C y
,
j
1,2,
n
…,
(3.3)
2
)
混合策略 (
,
x y 为对策
{ ,
1
n
混合对策问题的求解方法
1
n
1
j
i
由定义 6 可知,求解混合对策就是求非合作对策的平衡点,进一步由定理 8 得到,求解非合作对策的
平衡点,就是求解满足不等式约束的可行点。因此,混合对策问题的求解问题就转化为求不等式约束的可
行点,而 LINGO 软件可很容易做到这一点。
举例:对抗赛
有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员(甲队为李,
乙队为王),在三个项目中成绩都很突出,但规则准许他们每人只能参加两项比赛,每队的其他两名运动
员可参加全部三项比赛。已知各运动员平时成绩(秒)见表 3。
100 米蝶泳
100 米仰泳
100 米蛙泳
赵
59.7
67.2
74.1
甲队
钱
63.2
68.4
75.5
王
58.6
61.5
72.6
乙队
张
61.4
64.7
73.4
孙
64.8
66.5
76.9
假定各运动员在比赛中都发挥正常水平,又比赛第一名得 5 分,第二名得 3 分,第三名得 1 分,问教
练员应决定让自己队健将参加哪两项比赛,使本队得分最多?(各队参加比赛名单互相保密,定下来后不
准变动)
解 分别用 1 、 2 和 3 表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略,
分别用 1、 2 和 3 表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。
当甲队采用策略 1,乙队采用策略 1时,
在 100 米蝶泳中,甲队中赵获第一、钱获第三得 6 分,乙队中张获第二,得 3 分;
在 100 米仰泳中,甲队中李获第二,得 3 分,乙队中王获第一、张获第三,得 6 分;
在 100 米蛙泳中,甲队中李获第一,得 5 分,乙队中王获第二、张获第三,得 4 分。
也就是说,对应于策略 1
表 4 给出了在全部策略下各队的得分。
(
) 甲、乙两队各自的得分为 (14,13) 。
,
2
表3
李
57.7
63.2
70.3
表4
策略
1
2
3
1
(14,13)
(13,14)
(12,15)
计算支付矩阵的 Matlab 程序,运行
2
(13,14)
(12,15)
(12,15)
3
(12,15)
(12,15)
(13,14)
按照定理 8,求最优混合策略,就是求不等式约束的可行解,
求解最优混合策略的 LINGO 程序。
求得甲队采用的策略是 1 、 3 方案各占 50%,乙队采用的策略是 2 、 3 方案各占
50%,甲队的平均得分为 12.5 分,乙队的平均得分为 14.5 分。如表 5 所示。
策略
1 0.5
2 0.0
3 0.5
四、N 人合作博弈
1 0.0
(14,13)
(13,14)
(12,15)
表5
2 0.5
(13,14)
(12,15)
(12,15)
3 0.5
(12,15)
(12,15)
(13,14)
五、博弈的扩展式表述和动态博弈
5.1 博弈论的扩展式表述
,
n
i
,此外,我们将用 N 来表示虚拟参与人“自然”;
具体来讲,博弈的扩展式表述包括以下要素:
1. 参与人集合: 1,
2. 参与人的行动顺序:谁在什么时候行动;
3. 参与人的行动空间:在每次行动时,参与人有些什么选择;
4. 参与人的信息集:每次行动时,参与人知道些什么;
5. 参与人的支付函数:在行动结束之后,每个参与人得到些什么(支付是所有行动的函数);
6. 外生事件(即自然的选择)的概率分布。
5.2 博弈树的构造
设想你是一家房地产开发商(为了讨论方便,我们称你为“开发商 A”,正在考虑是否要在北京的某一
地段开发一栋新的写字楼。你面临的选择是开发或不开发。如果决定开发,你必须投入 1 亿资金;当然,
如果决定不开发,你的资金投入为 0。在做这个决定时,你关心的当然是开发是否有利可图。
像房地产这样的市场充满了风险。风险首先来自市场需求的不确定性。需求可能大,也可能小。风险
的另一个来源是你的竞争对手,房地产开发商 B。让我们假定开发商 B 也面临与你同样的决策问题:是否
投入 1 亿资金开发一栋同样的写字楼。
假定,如果市场上有两栋楼出售,需求大时,每栋售价可达 1.4 亿,需求小时,售价为 7 千万;如果
市场上只有一栋楼出售,需求大时售价为 1.8 亿,需求小时为 1.1 亿。这样,有以下 8 种可能的结果:
1. 需求大,你开发,他不开发;你的利润为 8 千万,他的利润为 0。
2. 需求大,你不开发,他开发;你的利润为 0,他的利润为 8 千万。
3. 需求大,你开发,他也开发;你的利润为 4 千万,他的利润为 4 千万。
4. 需求大,你不开发,他也不开发;你和他的利润为都为 0。
5. 需求小,你开发,他不开发;你的利润为 1 千万,他的利润为 0。
6. 需求小,你不开发,他开发;你的利润为 0,他的利润为 1 千万。
7. 需求小,你开发,他也开发;你的利润为-3 千万,他的利润为-3 千万。
8. 需求小,你不开发,他也不开发;你和他的利润为都为 0。
在这个例子中,无论开发商 A 还是开发商 B,在决定是否开发时,不仅要考虑市场需求的大小,而且
要考虑对方的行动。
我们假定该博弈的行动顺序如下:
(1) 开发商 A 首先行动,选择开发或不开发;
(2) 在 A 决策后,自然选择市场需求的大小;
(3) 开发商 B 在观测到 A 的决策和市场需求后,决定开发或不开发。
博弈树的基本建筑材料包括结(nodes)、枝(branches)和信息集(information sets)。
结(nodes)
图1 房地产开发博弈I
''
,
,
x
x
x
x 意味着 x 在 ''x 之前。
结包括决策结(decision nodes)和终点结(terminal nodes)两类;决策结是参与人采取行动的时点,
终点结是博弈行动路径的终点。
一般地,我们用 X 来表示所有结的集合, x X 表示某个选定的结。用 表示定义在 X 上的顺序关
系(precedence relation):
定义 ( )P x 为 x 之前的所有结的集合,简称为 x 的前列集(the set of precedene);
定义 ( )T x 为 x 之后的所有结点的集合,简称为 x 的后续集(the set of successors)。
如果 ( )
P x
如果 ( )
T x
除终点结之外的所有结都是决策结。
每一个终点结完全决定了博弈树的路径,我们可以用函数 ,( )
与人的支付函数。
枝(branches)
称为初始结(initial nodes)
称为终点结(terminal nodes)。
u z 表示对应的博弈路径所导致的第 i 个参
在博弈树上,枝是从一个决策结到它的直接后续结的连线(有时用箭头表述),每一个枝代表参与人
的一个行动选择。
一般地,对于一个给定的决策结, x X ,存在一个有限的行动集合 ( )A x 和一个一一对应的函数
: ( )
a t x
t x 是 x 直接后续结的集合。
,这里 ( )
( )
A x
信息集(information sets)
博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策结集合的一个子集。该子集包括所
有满足下列条件的决策结:
(1) 每一个决策结都是同一参与人的决策结;
(2) 该参与人知道博弈进入该集合的某个决策结,但不知道自己究竟处于哪一个决策结,引入信息
集的目的是描述下列情况:当一个参与人要作出决策时他可能并不知道“之前”发生的所有事
情。
为了给出信息集的直观解释:
在图 1 中,假定开发商 B 是在知道 A 的选择和自然的选择之后决策的,此时,博弈树的 7 个决策结分
割成 7 个信息集,其中一个(初始结)属于 A,两个属于 N,四个属于 B;每个信息集只包含一个决策结,
意味着所有参与人在决策时准确地知道自己处于哪一个决策结。
如果对上述假设作一个小小的改动,假定行动顺序不变,但 B 在决策时并不确切地知道自然的选择。
此时,B 的信息集由原来的四个变成两个,每个信息集包含两个决策结。两个信息集分别对应着 B 必须作
出的两个不同的决策:如果 A 开发,自己开发;如果 A 不开发,自己是否开发。在图 2 中,我们用虚线将
属于同一信息集的两个决策结连接起来(或用虚线圈起来)。