0:00
上一节我们看到了所谓的网络交换实验的一些
简单的例子，我们能够体会到啊，那么，那样一类实验由于是有人的参与
的，那么那个结果实际上很难精确的预测
不过，另一方面，我们也能够感到呢，那个，网络的结构不一样，以及，这个参与的人在结构的，
不同的位置，它的表现呢，好像也有一定的规律可循
我们这一段呢，就来看看，我们怎么来 讨论这个结果中，啊，
有某些规律，让我们先从数学上
定义一个结果， 的概念，给定一个图，或者说呢，我们想象
它是，啊，做实验的那么一个 网络，我们现在只是考虑，在每一条边上面呢是
一个单位价值，啊，因为前面,iii,几节里头，我们有时用10块钱，啊，几块钱
我们现在呢，就用单位价值，都是1，来讨论这个
价值的分配，按照实验的规则，啊，那么最后啊，会在一些个边上呢达成
协议，那么在一些边上达不成协议，达成协议的，那些 个边呢涉及的节点啊是无冲突的，也就是
不会有某些节点与两条边都有关系，
我们称这样的边的集合呢，为图的
一个匹配，啊，为图的一个匹配，注意
这个匹配的概念，和我们前面学过的二部图的完美匹配有关系，但不
完全一样，这里的匹配呢，规定涉及到 每一个节点，啊，我们前面那个完美匹配，二部图完美匹配，是每一个节点
都会被覆盖到，那么按照这种思路，我们
定义，结果，就是这个图中的一个
匹配，加上一定的条件，这个条件就是每一个节点在[0,1]的一个赋值
满足这么两条，第一条啊，说的是
如果两个节点它们对应的是匹配中的一条边
那么它们俩加起来的赋值之和就要
是1，这个对应我们这个实验的时候，达成协议，它俩分这么一个单位价值这种情况
如果，节点它不涉及到匹配中的任何边，就是那个边呢，它最后没有达成
协议，那么，那么 这个节点U，它没有涉及到任何量的边，那么它的赋值呢，就为0，
这就对应呢，一个节点跟谁没有达成协议，它的价值就是0，这么一个情况
这样的定义，实际上，就是对网络这个交换规则的一种表达，它
是一个，啊，很数学上精确的概念，好了，下面我们就来看看几个例子
是不是满足这样一个概念，啊
第一个，是长这样子的，啊， 我们一共有4个例子，这个粗的黄线
啊，表示我们想象中，达成协议的那些个边，啊，细的白线呢，就
没有达成协议，好了，我们看看，这第一个例子它是不是满足刚才那个结果
的概念呢，我们一看，它应该满足的，是吧，你看这，达成协议的，这个
俩个节点的赋值，都是0.5，加起来等于1，其他的都是0，
没有问题，第二个例子，我们看看第二个例子，第二个例子，一看，啊，有两条边，一条在这，
一条在这，这匹配中的，它们的赋值之和，这是0.6
0.4，ok，等于1, 0.5,0.5，也行，啊，这个也没问题
第三个，看看，啊，第三个在这，第三个在这，
这个什么情况，这个一上来，它就有问题了， 比方说，这一条边，这一条边，它们在这个节点d上面，
是冲突的，它根本就没满足，我们，我们这个网络实验定义的一个基本要求，就是，每一个节点，只能
和最多另一个节点，啊，达成协议，不能跟
两个，所以这个就不是，最后一个，第四个 什么情况呢，有一条边没问题，但是，我们发现，有其他的问题，比方说
这个a啊，它没在任何达成协议的边里头，可是呢，它的，现在它的赋值是0.5，
这个不符合我们的结果的要求，所以它也不是，
好了，那我们现在干嘛呢？我们现在就是要看看啊，在
实验中，哪些个结果，刚才那个结果是一个数学上的一个描述，
定义，我们看看，实验中，哪些个结果可能是 出现的，哪些个结果其实在实验中不可能
出现的，也就是说，我们希望利用某种理论，仅仅
来通过对网络结构的判断，而不用做实验，就能够对实验结果有一个粗略的，
估计，下面我们通过这几个例子，来找点感觉
这一共有5个例子啊，这有5个，这是1个，2个，
3个，4个，5个例子，都是，啊，很简单的，
网络结构，那么，如果现在有人说，奥，这5个例子，都是产生于，
啊，某些网络实验的，
结果，你会相信吗？你如果不相信，你有什么理由 呢？你比方，我们先看第一个，第一个，有人说，啊，最后出来
是这个样子，3个人做，做那种网络这个交换实验，a和b达成协议，它俩各分
一半，啊，c撂在一边，它隔离 你大概会觉得，这个好像，他们没有把话说透，或者
说，这个谈判啊，并没有谈的充分，因为现在这个b，
是1/2,c是0，c看见这个情况，c完全可以给b一个新的建议，说，哎，我就给你2/3,
啊，我就得1/3就行， 给这个建议，那么，这个建议呢，就可以把这个b，从
它和a的协议中拉过来，因为那个b现在能得到了新的好处，那么对c来说，当然，比刚才
那0要好，所以我们说，哎，这个呢，它就，它就，它就不是一个
实验中，可能看见的这种结果
或者说，我们就能够有这样一种观点，啊，这个观点，也当然 也基本是对的，好，我们再看看第二个，第二个这个样子，
这个样子看起来好像没什么问题了，啊，因为，b和c之间，已经没有新的空间
可以讨论，那么b和a之间呢，也是个0,1分配，没有问题， 所以它是a，再
看第三个，这个第三个里头，a、b达成协议，c和d达成协议，它俩都有协议，啊，它俩
都有协议，b、c之间没协议，但是，我们又看到呢，b和c之间，它俩的这，当前的这个值
的分配，加起来是小于1的，也就是说，在它俩中间，还存在新的安排，这个安排，
使得这个b和c，分别都比现在要更好， 啊，完全可以做到，因为它这个，加起来不等于1，说明它们之间还是有空间，
那么，这个情况下，我们说谈判也还不充分，啊，这个情况
在实验中，它不太可能出现，好，第四个看一看
好像问题不大，啊，b、c之间也没有新的空间了
那第5个，第5个，看看问题也不大，b、c之间也没有
新的空间，当然b和c加起来不一定就等于1了，啊，这
地方就是这个样子，啊，这是，这是允许的，恩，那么，只是说，它们现在没有新的空间，我们看看它是符合
结果定义的，这个认识，其实就导致了下面这么一个重要的概念，这个概念
就叫稳定结果，我们看到了刚才那种情况， 啊，所谓的，不太可能出现，就是因为有一条
不在结果中的边，它们两边的价值之和是小于1的，
我们就管那样的边的存在呢，叫做
那样的边叫做，一个结果中的不稳定因素
那样的边，就造成一种新的机会，就破坏已有的这种达成的协议
好，那么什么叫稳定结果呢，稳定结果就 是不存在不稳定因素的结果，我们刚才那个例子中有3个
它都是不存在不稳定因素，我们就说那些东西是稳定的
结果，那么不稳定的结果或者说不稳定因素的存在，就意味着它
谈判还不 够充分，因此结果不太可能，好了，我们针对网络
交换实验这一节啊，我们先是按照这个实验的规则，定义了结果的
概念，然后我们体会到，由于参加实验的是人，那么在追逐利益的过程中，并不是所有结果都是实验
可见的，抓住其中一个条件，就是那些没有达成协议的一个关系两方的价值之和不应该小于1，
否则，就可以认为谈判不充分，因此呢，我们又定义了稳定结果的概念，啊，这么一个稳定结果的
概念呢，它是结果概念的一个子集
可以说呢，不稳定的结果在实验中是不太可能看到的
于是，这样就可以缩小我们考虑的范围，啊，或者说，我们预
测的范围，但是，稳定结果都是可能出现
的结果吗？啊，还是这个例子，我们看到，有3个稳定的结果，3个稳定的结果，我们看
一看，似乎会觉得有一些区别，比方说，这个
例子，和这个例子，哪 一个更像实验中可能出现的
呢？啊，我们稍微看一看，你会觉得这个好像更像一点，这个
呢，不是很像，不是很像，尽管它是稳定啊，刚才那个稳定结果意义上，它是
稳定，因为什么呢？你就会看到，这个b和a之间达成的协议1+1/2
好像没有把b的这个地位体现出来啊，
啊，所以，这就是，我们下两节要讨论的内容 也就是说，我们要来刻画
稳定结果中那些也不是很可能的那么一些情况。
李晓明 （Li Xiaoming）教授（Professor）
邱泽奇 （Qiu Zeqi）教授 (Professor)
王卫红（Wang Weihong）lecturer
