教学相长和寓教于乐的两个故事

李晓明

（北京大学 计算机系，北京 100871）

这些年，在上本科生的一门课“社会科学中的计算思维方法”，同时也不时地以“社会科学中的计算思维浅赏”为题，给其他学校作些讲座。学生和听众的表现经常给我带来惊喜。因此，本文标题中的“乐”其实不是给了学生，而主要是于我本人而言了，这也算是对那名句含义的曲解吧。

一个例子是关于匹配市场均衡价格的性质。问题是这样定义的：给定n×n矩阵V，其中元素按惯例记为vij，要求得一组称为“清仓价格”的值p=(p1,p2, …,pn)，和一个[n]上的映射 σ，满足对所有i=1, 2, …,n，

上课的时候不宜上来就是这么一个定义，用一个具体例子往往更加有效。如图1所示，右边是一个3×3矩阵（V），左边则是一组价格（p）。中间放上了一个二部图（称为“偏好卖家图”），其中的边对应在给定价格下的“最大差价”，也就是上面的公式（1），而其中3条较粗的边，对应的就是映射关系（σ）。这样的映射关系也称为二部图的一个完美匹配。

图1 体现匹配市场概念的一个示例

可以想象，一般地给定V，要找到这样一组p不是件容易的事，同时，也可能想象，这样的p也不一定是唯一的，如(5, 2, 0)就是另一组。在我们的课上，一般也就讲到这里，然后是介绍一个利用“物以稀为贵”的观念保证能求出一组清仓价格p的算法。

拓展一些，会提到学术文献中关于清仓价格集合的一个性质（凸性），即若p和q是清仓价格，那么λp+ (1-λ)q也是清仓价格，其中λ在0和1之间。就上面的例子而言，取p=(3,1,0)，q=(5,2,0)，λ=0.2，有0.2×3+0.8×5=4.6，0.2×1+ 0.8×2=1.8，即(4.6,1.8,0)也是一组清仓价格（有兴趣的读者可以检验一下）。……