文档介绍：云南大学软件学院 2008 年秋季学期
系统设计与实现项目——网络生成博弈
指导教师:李劲
一、博弈论简介
通过一个博弈的实例,介绍博弈论的相关概念。
例 如图 所示的囚徒博弈
囚徒 2
招供沉默
-6,-6 0,-9
招供
囚徒 1
-9, 0 -1,-1
沉默
图 囚徒博弈
囚徒博弈讲述的是如下一个情形:警方抓住了两个犯罪嫌疑人,囚徒 1、囚徒 2,
但警方掌握的证据不足,因而需要将进一步审讯提取口供。警方将两个囚徒分别置于
不同的房间,但告诉两囚徒相同的信息,即如果一方沉默,而另一方招供,那么招供
方立即释放,沉默方将被判入狱 9 个月;如果双方都沉默,那么两人将在一个月后因
证据不足而释放;如果双方都招供,那么两人都将被判 6 个月。如果每个囚徒都假设
对方将置自己于最不利(即博弈双方为非合作关系),此时对任一个囚徒来说,他是
选择“招供”,还是选择“沉默”呢?
上例虽然简单,但它给出了一个博弈情形的生动实例。博弈问题一般含有五个要
素:局中人、每个局中人的可行方案集、局中人决策的先后顺序、每个局中人的收益
函数、信息。
所谓局中人,是指在问题中为自己的利益进行决策的各方,如上例中的两个囚徒。
特别地,在后文中我们把局中人称作 Agent。
可行方案集是 Agent 可以采取的行动方案的全体,如上例中每个囚徒都有两个可
选的行动集{“招供”、“沉默”} 。在博弈问题中,Agent 在其可行方案上的选择,便
是决策分析。许多学者把 Game Theory 称为对策论,就是由于在对抗冲突的条件下进
行决策分析。
决策的先后顺序是实际问题动态性质的反映,任何一种博弈的规则都要明确各个
Agent 进行决策分析的时间先后。如果各个 Agent 是同时进行决策,问题便是静态博
弈。还有一种情形也是静态博弈,那就是不同 Agent 决策时间由先后顺序,但后决策
的 Agent 并不知道前于其决策的 Agent 选择了什么行为方案。除开上述两种情形,问
题都是动态博弈。囚徒博弈就是一个静态博弈的例子。
收益函数是博弈最后结果中各个 Agent 利益的表示。在上面的囚徒博弈中,我们
用效用矩阵来表示每种博弈结果下两个囚徒的收益,例如,如果囚徒博弈最终的博弈
格局(结果)是<“沉默”,“沉默”>(表示两个囚徒都选择“沉默”),那么囚徒 1 的利
益是-1,囚徒 2 的利益是-1;如果博弈格局是<“沉默”,“招供”>,那么囚徒 1 的利益
是-9,而囚徒 2 的利益是 0,如此等等。需要注意的是当问题中出现不确定性时,收
益通常是估值,比方说行为结果的数学期望。
信息指的是 Agent 在决策时对其决策条件的知识。信息包括两类,一类是有哪些
Agents,他们的可行方案集是什么,所有 Agents 的收益函数是怎样的;另一类是 Agent
决策前已作过的决策结果。在博弈中,如果所有 Agents 对前一类信息有确切的了解,
就称之为完全信息的博弈,否则称之为不完全信息博弈。而在博弈中如果所有 Agents
对后一类信息有确切的了解,就称之为完美信息博