博弈论1:为什么囚徒困境是一个困境?

All materials come from Coursera《Game Theory》by Stanford University & The University of British Columbia

囚徒困境

两个囚犯现在被捕,警察将他们两个分别关在了不同的房间(囚犯之间互相无法交谈),警察为了让他们招供,对两个人分别说了这样一番话:

  1. 若你和他都选择不招供,则在我们目前已有证据的基础上,我们有信心将你们两个都判1年
  2. 若你选择招供告发他,而他不招供,那么我们将直接无罪释放你并且他会被判3年
  3. 若你和他都选择了招供,那问题就很简单了,你们将都被判2年

现在我们将上述规则以更简练的矩阵形式表示出来

其中C表示囚犯选择与对方合作(Cooperate)即不招供,D表示囚犯选择欺骗对方(Defect)即选择招供,左边的C和D代表囚犯1可以做的两个选择,同理上方的C和D代表囚犯2可以做的两个选择。举个例子,对于右上角的方格,表示囚犯1选择不招供(C)而囚犯2选择招供(D),结果囚犯1被判了3年而囚犯2无罪释放

为了进一步说明这个问题,我们先引入一些博弈论的基本概念


博弈的基本定义

博弈的基本元素有以下几个:

  • 玩家(Players):做出决定的个体
  • 行动(Actions):每个玩家可以做出怎样的行动
  • 奖励/代价(Payoff):玩家做出每个行动之后会有怎样反馈(例如商人在股票最高点抛售这一行动可以获得最高的收益)
  • 时序(Timing):事件发生的顺序(例如大家下棋时轮流交替移动棋子)
  • 信息(information):当玩家做出行动时他们都知道什么信息(参与者对其他参与者的了解程度)

所以有限n人标准博弈的数学定义表示为\(<N, \mathbf{A}, u>\)其中元素分别表示如下含义:

    1. 玩家的集合\(N = \{1, 2, ..., n\}\) 是一个大小为n的有限集合,用\(i\)标识
    1. 行动组合的全集\(\mathbf{A} = A_1 \times A_2 \times ... \times A_n\),其中\(A_i\)表示玩家\(i\)的行动集合,若用\(a\)表示一个行动组合(action profile),则有\(a = (a_1, a_2, ..., a_n) \in \mathbf{A}\)
    1. 效用(代价)函数组\(u = (u_1, u_2, ..., u_n)\),其中对于玩家\(i\)\(u_i: \mathbf{A} \rightarrow \mathbb{R}\),特别注意 ,此处的\(u_i\)表示一个从行动组合集合\(a \in A\)到实数\(\mathbf{R}\)的映射

支配策略

我们在参与游戏的时会有一个要实现的目标(goal),通常情况下的目标为最大化自己的收益(payoff),但是也可以有别的目标(比如以让对方获得最小收益为目标)

为实现这个目标我们会有一个对应的策略(strategy),策略指导玩家该做出什么行动(或选择什么行动)。比如在囚徒困境中,囚犯的策略就是:做出怎样的选择(招供或不招供),以使自己被判的时间最短。这里每个囚犯有两个选择:与另一个囚犯合作(Cooperate)和欺骗另一个囚犯(Deceive),选择合作意味着不招供而欺骗意味着招供,所以每个囚犯都会思考,如果对方招供的话我该怎么选,如果对方不招供的话我又该怎么选?从而我们这里引入一个概念支配策略(dominant strategy)

支配策略:A dominant strategy for a player is one that produces the highest payoff of any strategy available for every possible action by the other players。通俗点讲就是:不管别人做出怎样的行动,我所做的选择都可以让我得到最大收益。还以囚徒困境举例

情况一:当囚犯2选择C不招供(下图红框),那么对于囚犯1来说:选C不招供那么自己会被判1年,而D招供那么自己可以无罪释放(下图绿框)。所以很显然,此时选D招供是最好的选择

情况二:当囚犯2选择D招供(下图红框),那么对于囚犯1来说:选C不招供那么自己会被判3年,而D招供那么自己会被判2年(下图绿框)。所以很显然,此时选D招供是最好的选择

综合上述两种情况,我们可以得出结论:不论囚犯2如何选择,囚犯1的最佳选择都是D招供(也就是囚犯1的支配策略)。同样的道理,由于囚犯1和囚犯2的地位是对称的,所以囚犯2的支配策略也是D招供

关于囚徒困境的结论

根据之前的支配策略的分析,两个囚犯的支配策略都是D招供,从而两个人都被判2年。而囚徒困境的令人诧异的地方也就出现于此,我们如果从一个上帝视角来看,很明显,两个囚犯的最佳选择明明是选择都不招供,这样两个人加起来判的时间是最少的,是全局最优解,但是如果从个人角度来分析,就会发现,无论如何他们两个都不会去选择一起合作不招供。这恰恰就是囚徒困境的背景————两个人无法交流即非合作博弈,其所谓的上帝视角其实是不存在的,因为将其推广到繁杂的现实,就会发现没有“上帝”可以看到整个全局,没有人的信息是全局的,从而从这个思想出发,反驳了亚当斯密的一个基本观点:所有人的最优选择会形成整个群体的最优选择,因为当所有人做到自己的最优时,对于整个社会来说可能是最坏的(两个囚犯加起来一共判了4年)

补充

囚徒困境的标准通式满足: \[c > a > d > b\]