关于布雷斯悖论例题中收费和禁行的讨论

于同奎

西南大学计算机与信息科学学院

在导教班课程中，李老师提出一个问题：在解决布雷斯悖论时可以采用“禁行”和“收费”两种，哪个方法更好呢？

李老师给的例子是：在如图1所示的交通网络中，有4000辆车需要通过A地到D地，每个路段旁所标注的数字为通过此路段所需时间，其中A-C段、B-D段和B-C段所需时间不因通过此段的车辆数发生改变，分别是45分钟、45分钟和0分钟（B-C段高速通行不需花费时间），而A-B段和C-D段所需时间为通过该段车辆数x除以100（注意：这两个x不一定相等）。

图1 交通网络及通行时间

1 博弈均衡

每辆车有三个策略可以选择，A-B-D、A-B-C-D、A-C-D，假设采用三类策略的车辆数分别是x1,x2,x3。则策略1（A-B-D）所需时间为t1=(x1+x2)/100+45，策略2（A-B-C-D）所需时间为t2=(x1+x2)/100+(x2+x3)/100，策略3（A-B-C-D）所需时间为t3=45+(x2+x3)/100。由于x1+x2+x3≤4000，所以(x1+x2)/100≤40，(x2+x3)/100≤40，所以t2≤t1，t2≤t3，所以策略2是一个占优策略，所以所有车辆会选择采用策略2，即x1=0,x2=4000,x3=0。每辆车从A到D的时间为t2=80分钟，4000辆车从A到D的总时间为320000分钟。

2 禁行方案（布雷斯悖论）

我们可以通过将B-C段禁行的办法降低社会总通行时间。当B-C段禁行后，交通网络如图2所示。此时，每辆车的策略只有两个，A-B-D、A-C-D，假设采用两类策略的车辆数分别是x1,x3。策略1（A-B-D）所需时间为t1=x1/100+45，策略3（A-B-C-D）所需时间为p3=45+x3/100。此时t1和t3无法直接比较，不存在占优策略。 

图2 禁行后交通网络

那么博弈的均衡就应该这么理解：当有x1辆车从A-B-D走，x3辆车从A-C-D走时，对于每一辆车都没有动机改变路径。这就是“无差异原则”，即两条路的通行时间相等，t1= t3。由此可得x1= x3。又因为x1+x3=4000，所以x1=x3=2000。此时t1= t3=65分钟。所以，社会中4000辆车从A到D的总时间为65*4000=260000分钟。

可见，禁行可以提高交通网络通行能力。这就是所谓的“布雷斯悖论”，减少通行路径反而提高社会总通行效率。

3 收费方案

李老师还提出一个非常有启发性的思路，通过对B-C段收费来解决布雷斯悖论。

3.1 例题

假设车辆可以在B-C段通行，通行时间为0分钟。但是对于每辆从此段通行的车辆收费20元（这个费用从车主转移到政府，对整个社会福利而言没有发生变化）。假设对于每辆车而言，支出1元钱的效用和延长1分钟的效用相等。收费后的交通网络如图3所示。

图3 收费后交通网络

此时，每辆车仍有三个策略可以选择，A-B-D、A-B-C-D、A-C-D。但是三条路线的效用发生了变化。假设采用三类策略的车辆数分别是x1,x2,x3。策略1（A-B-D）只花时间不花钱，其效用就定义为其所需时间p1=t1=(x1+x2)/100+45。策略3（A-B-C-D）与之类似，其效用定义为p3=t3=45+(x2+x3)/100。策略2（A-B-C-D）既花时间又花钱，所花时间为t2=(x1+x2)/100+(x2+x3)/100，所花路费为20元，根据假设，支出1元钱与延长1分钟等效，定义其效用函数为p2=t2+20=(x1+x2)/100+(x2+x3)/100+20。

此时无法比较p1、p2、p3大小，不存在占优策略。博弈均衡的概念就应该理解为：当有x1辆车从A-B-D走，x2辆车从A-B-C-D走，x3辆车从A-C-D走时，对于每一辆车都没有动机改变路径，即“无差异原则”，p1=p2=p3。则有：(x1+x2)/100+45=(x1+x2)/100+(x2+x3)/100+20=45+(x2+x3)/100，另外有x1+x2+x3=4000。三个一次方程三个未知数，计算可得x1=1500，x2=1000，x3=1500。

这意味着1500辆走A-B-D，1000辆车走A-B-C-D，1500辆车走A-C-D。三条路分别所需通行时间为t1=(x1+x2)/100+45=70分钟，t2=(x1+x2)/100+(x2+x3)/100=50分钟，t3=45+(x2+x3)/100=70分钟。

所以，社会中4000辆车从A到D的总时间为T=70*1500+50*1000+70*1500=260000分钟。这正好与禁行方案中的社会总通行时间相等。

3.2 例题拓展

从上面看，对B-C段通行车辆收费20元可以达到与禁行方案相同的效果。李老师启发我们思考，采用不同的收费标准是否可以进一步提高社会福利呢？

我把上面例题中的20元替换为10元、15元、25元（后面分析会知道25是一个最大合理取值），按照上述方法分别计算博弈均衡以及在博弈均衡下的社会总通行时间，分别为290000、270000、260000分钟。大致看到递减的趋势，最小是260000分钟。似乎说明收费策略的最小通行时间就是禁行方案的通行时间。

但是仅仅这几个数字并不能得出结论。我就在Matlab中编写程序，为每个大于0小于25的值求得一个社会总通行时间，代码如下。

TValues=15:0.01:25;

dataSize=length(TValues);

data=zeros(dataSize,2); 

for i=1:dataSize

   T=TValues(i);

   carNum=[100*T-500 5000-200*T 100*T-500];

   travelTime=[90-T 90-2*T 90-T];

   totalTime=carNum*travelTime';

   data(i,:)=[T totalTime];

end 

plot(data(:,1),data(:,2))

xlabel('收费标准');

ylabel('社会总通行时间');

绘制收费标准和博弈均衡下的社会总通行时间关系如图4所示。我们可以看到，当B-C段的收费标准定在大约22元-23元之间时，社会总通行时间最小，且最小值小于禁行策略时的社会总通行时间（260000分钟）。

图4 收费对博弈均衡下社会总通行时间影响

3.3 精确理论解

为了得到更精确的结果，我们希望求出提供最小社会总通行时间的最优收费标准的具体数值。我们设对每辆在B-C段通行车辆收费F元，然后带着F求出博弈均衡以及博弈均衡下的社会总通行时间（带F的表达式），然后对其求最优化，即可得到最优收费标准。

类似上面的分析，我们可以求出三类策略的效用。策略1（A-B-D）的效用仍然为p1=t1=(x1+x2)/100+45。策略3效用仍然为p3=t3=45+(x2+x3)/100。策略2效用函数为p2=t2+20=(x1+x2)/100+(x2+x3)/100+F。

令p1=p2=p3且x1+x2+x3=4000，可求得x1=100F-500，x2=5000-200F，x3=100F-500；每个策略所需时间t1=90-F，t2=90-2F，t3=90-F。

那么，社会总通行时间T就可以计算为：T=x1t1+x2t2+x3t3=2(100F-500)(90-F)+(5000-200F)(90-2F)。有求其最小值，把T对F求导数并令其等于0，得到dT/dF=2(90-F)-2(F-5)-2(50-2F)-2(90-2F)=0，求得F=90/4=22.5。所以，最优收费标准为F*=22.5元。此时，社会总通行时间为T=2(100F-500)(90-F)+(5000-200F)(90-2F)=258750分钟。这个数据小于禁行策略下的社会总通行时间260000分钟。

4 总结

布雷斯悖论提供了一个反直觉的结论：减少通行资源反而可以提高社会总通行效率。

李老师关于通过收费来提高社会通行效率的启示引出对这个问题更丰富更有趣的思考，尤其是社会政策（收费）的分析。

针对李老师的题目，经过稍微耐心细致的计算和分析，我们可以看到，通过合理制定收费标准，收费策略可以提供比禁行策略更优的结果。