Video在线视频

大家好 欢迎来到

网络 群体与市场的在线课堂

我是这门课的主讲老师——石兵

来自武汉理工大学

接下来的这一讲我们将会介绍

博弈论的一些简单应用

我们将以交通网络流量为例

来分析博弈论在其中的应用

我们看这样一个场景

假设十一长假要到了

你要出门旅行 想自驾游

在出门之前你会考虑该走哪条路

还会考虑到如果走这条路

其他人会怎么办

他们是不是也会走这条路

还是会走其它路

这其实就是一个典型的

公路交通网的博弈问题

我们可以以一个简化的例子

来看待这样一个问题

假设有这样一个交通网

其中有四条路

分别是AC CB AD DB

还规定了每条路上的行驶时间

比如从C到B的行驶时间是固定的

是45

从A到C的行驶时间

与这条路上的车辆的数量相关

等于车辆数除以100

现在假设有4000辆车

要从A到B

这个时候作为4000辆车的

司机就要考虑该选取什么样

的路线比较合适

这其实就是一个典型的博弈问题

这博弈问题里的三要素

分别是什么

首先这个博弈问题的参与人就是

这4000个司机

它的策略就是他选取什么样的

行驶路线

显然这里面有两个策略

可以选择从上面走也就是ACB

或者选择从下面走ADB

他的回报是什么呢

他的回报显而易见

就是每个司机的行驶时间

而且这个时间是越小越好

这个回报取决于司机本身的

路线选择

也取决于其他司机的路线的选择

在均衡状态下司机该怎么办呢

大家回忆一下均衡的概念

纳什均衡是指一种没有人

要调整的选择状态

也就是说在这个博弈问题里面

在纳什均衡状态下

没有任何司机会愿意

改变自己的路线

因为他发现当他单方面改变的时候

他的行驶时间不会变小

那么在纳什均衡状态下

这个司机应该选择什么样

的路线呢 我们可以看到

在均衡状态下

每条路上会有2000辆车

也就是说有2000辆车会

选择从A C到B

然后还有2000辆车会

选择从A到D到B

而且我们还可以计算出

在这个均衡状态下每辆车

的行驶时间是多少

比如从A到C到B这条路线

行驶时间等于

2000/100

（A到C花费的时间）＋45

就得到了这个司机从

A到C到B花的时间

同样的我们可以计算出司机

选择下面的路线的时候

花费的时间也是65

我们现在看这个是不是纳什均衡

我们可以验证一下

回忆一下纳什均衡的概念

没有人愿意改变

改变的话行驶时间不会变少

现在假设某位司机要改变

他想从ADB这条路线换到ACB

我们这个时可以算一下

它的行驶时间有没有变少呢

当他换到ACB的时候

这个时候AC这条路线上的

车辆数是多少

从A到C就有2001辆车

这时候所花的时间是

2001/100

整个这条路线花的时间是

2001/100＋45

显然我们可以看到是大于65的

我们发现当这个司机

单方面改变自己的路线的时候

它的行驶时间没有变少反而增加了

所以2000个司机从上面走

2000个司机从下面走

就是一个纳什均衡状态

现在假设政府准备改善民生

准备修一条快速路

假设准备修一条从C到D的路线

而且这条路很快

所以它的行驶时间假设是0

在这个交通网络稍微变了的情况下

这些司机应该怎么办

它们会保持原来的均衡路线吗

还是说他们会变化

我们会发现所有的司机会选择

从A到C到D到B

也就是说在纳什均衡的状态下

所有司机的路线变成了ACDB

这是不是纳什均衡

在目前ACDB的路线下

每个人的行驶时间是

4000/100＋0

＋4000/100

=80

这是不是纳什均衡

现在假设某个人想改变这条路线

他选择从A到D到B

这个时候它的行驶时间变成

45＋4000/100

> 80

当他改变的时候

他的行驶时间会变长

所以他不会改变

因此可以发现ACDB

这条路线是一个纳什均衡策略

但是在没有修C到D

这条路线的时候

在纳什均衡状态下每个司机

的行驶时间是65

也就是说增加了资源

情况反而变坏了

这个就叫做布雷斯悖论

我们现在分析

为什么在新增加资源之后

行驶时间会发生变化

而且比原来的情况要恶化

现在假设你是走

上面这条路线的人之一

刚开始在均衡状态下

你的路线是从A到C到B

在政府部门新修了CD这条路之后

你会怎么办

这个时候你会很自然地想

会选择ACDB这条路线

因为这时候的行驶时间变成了

2000/100＋0

＋2001/100

< 65

（即走ACB的时间）

在这种情况下

你会毫不犹豫的改变自己的路线

原先的纳什均衡状态被破坏了

这个时候你还会考虑

会不会变成有

2000人走ACDB

也就是说原来走ACB的人

换成了走ACDB

剩下的2000人还是

继续走ADB呢 也不会

当上面的2000人路线

变成ACDB的时候行驶时间

也发生了变化

这个时候走ADB行驶时间是

45＋4000/100= 85

85大于ACDB所花的时间80

因此所有的人最终都会变成

走ACDB这条路线

我们现在来看一下这个问题的

一般性是怎样的

如果在一个交通网络中每条边的

通行时间都是一个线性的

通行时间函数

可以表达成

Te(x) = ax＋b

a b是常数

x是在这条路上的车辆数目

现在给定 任意交通网

以及 线性通行时间 函数

可以证明肯定会存在

一个纳什均衡策略

在司机所选择的行驶路线模式下

任何司机都不可能改变路线

来缩短自己的通行时间

这个结论怎么证明呢

证明思路其实很简单：

我们可以任意给定一个

初始的交通模式

如果它不是均衡的

那么肯定会存在某个司机通过

改变自己的路线可以缩短自己的

通行时间 假设他这样做了

这时候会得到一个新的交通模式

如果这个新的交通模式

仍然不是均衡的

那么还是会存在这样一个司机

他会通过改变路线来

缩短自己的通行时间

这样一个过程可以不停的进行下去

如果到某一轮停止了

就说明了任何司机都发现

通过改变路线

他的行驶时间不会缩短

也就是说达到了纳什均衡

这样一个模式会不会终止呢

我们可以在网络交通模式上

定义一个适当的量

使得当一个司机选择缩短

自己行驶时间的路线后

新模式的这个量会严格减小

这个量不能是所有车辆的

行驶时间之和

因为一辆车缩短了

其他司机的时间可能会加长了

因此总时间的变化难以说清楚

我们可以定义这样一个量

叫做势能 势能是什么呢

对于一条边来说

它的势能等于一辆车在

它上面行驶的时间

加上两辆车在它上面行驶的时间

一直加到x

对于一个交通模式来说

它的势能是所有边的势能之和

现在只要说明司机每一次

在选择路线之后

缩短的行驶时间的路线都会

使得这个模式的势能下降

这样一个势能是不可能小于0的

它肯定是大于等于0的

我们就可以说它不停的下降

总会在某一次会停止

我们就可以证明出肯定会找到

一个纳什均衡状态

这样一个势能是不是真的

一直在下降呢

当一个司机放弃原来的路线

走一条新路时间肯定是减少的

假设e是原来路线上的一条边

放弃了这条边意味着在这上面的

车辆数从x变成了x－1

这个时候这个边的势能变化

什么呢

这个边降低的势能恰好是他在

这条边上的行驶时间

这个司机放弃了这条边

走一条新的路

在这条新的边上引起了势能的

增加等于Te(y＋1)

y是这条新的边上原来的车辆数

因为这个司机选择了改变路线

改变路线的前提是他会发现

行驶时间会变少

所以我们显然有这样一个式子成立

也就是说新的势能肯定要

严格小于先前的

这样就证明了在每一次司机变换

路线之后势能都是在递减

而这个势能是有下界的

肯定是大于0的

这样一个过程肯定会停止

在停止的时候我们

就达到了纳什均衡

在本讲我们介绍了博弈论

在交通流网络中的应用

而且我们发现在每个人追求

个人利益最大化的情形下

我们增加社会资源有时候

反而使得情况变坏

这就是典型的布雷斯悖论

本讲就进行到这里 谢谢大家