李曉明

（北京大學(xué) 計算機系，北京 100871）

這些年，在上本科生的一門課“社會科學(xué)中的計算思維方法”，同時也不時地以“社會科學(xué)中的計算思維淺賞”為題，給其他學(xué)校作些講座。學(xué)生和聽眾的表現(xiàn)經(jīng)常給我?guī)眢@喜。因此，本文標(biāo)題中的“樂”其實不是給了學(xué)生，而主要是于我本人而言了，這也算是對那名句含義的曲解吧。

一個例子是關(guān)于匹配市場均衡價格的性質(zhì)。問題是這樣定義的：給定n×n矩陣V，其中元素按慣例記為vij，要求得一組稱為“清倉價格”的值p=(p1,p2, …,pn)，和一個[n]上的映射 σ，滿足對所有i=1, 2, …,n，

上課的時候不宜上來就是這么一個定義，用一個具體例子往往更加有效。如圖1所示，右邊是一個3×3矩陣（V），左邊則是一組價格（p）。中間放上了一個二部圖（稱為“偏好賣家圖”），其中的邊對應(yīng)在給定價格下的“最大差價”，也就是上面的公式（1），而其中3條較粗的邊，對應(yīng)的就是映射關(guān)系（σ）。這樣的映射關(guān)系也稱為二部圖的一個完美匹配。

圖1 體現(xiàn)匹配市場概念的一個示例

可以想象，一般地給定V，要找到這樣一組p不是件容易的事，同時，也可能想象，這樣的p也不一定是唯一的，如(5, 2, 0)就是另一組。在我們的課上，一般也就講到這里，然后是介紹一個利用“物以稀為貴”的觀念保證能求出一組清倉價格p的算法。

拓展一些，會提到學(xué)術(shù)文獻中關(guān)于清倉價格集合的一個性質(zhì)（凸性），即若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)也是一組清倉價格（有興趣的讀者可以檢驗一下）。關(guān)于這個性質(zhì)的證明，一般教材都沒有，我想大概是因為其要求的背景知識比較多。為此特別咨詢了這個領(lǐng)域的專家鄧小鐵教授，問他“哪里能找到比較通俗的證明？”他答：“約束條件是凸的。兩個最優(yōu)解的效用函數(shù)是相等的。目標(biāo)函數(shù)是線性的。所以，兩個最優(yōu)解的凸組合滿足約束條件，與最優(yōu)解等值。即得。”

精辟！但這段話要有多深厚的積累才能理解啊。

這時候，本故事的主人公出場了，選修本學(xué)期課程的林濤同學(xué)說可以提供一個初等證明。下面就來看他的證明。

引理：設(shè)p=(p1,p2, …,pn)和q=(q1,q2, …,qn)為兩個清倉價格向量。記A和B為分別由p和q引起的完美匹配集合（即符合要求的σ的集合），則A=B。

證明：用G(p)和G(q)表示對應(yīng)p和q的偏好賣家圖（即圖1中間的那種二部圖）。

考 慮G(p)中 任 一 完 美 匹 配M={（i1,j1）， （i2,j2），…，（in,jn）}。我們將通過證明M中的每一條邊也在G(q)中，來說明M也是G(q)中的一個完美匹配。

假設(shè)（i1,j1）不在G(q)中。因q是清倉價格，于是至少有一個完美匹配N在G(q)中。由于假設(shè)（i1,j1）不在G(q)中，i1在N中一定與某個其他的j匹配，不失一般性，設(shè)i1和j2匹配；這樣，i2也就沒有和j2匹配，設(shè)它與j3匹配……直到某一個k，ik與j1匹配；也就是（i1,j2），（i2,j3），…， （ik,j1）∈N。

考慮（i1,j1）和（i1,j2）。因為（i1,j1）是M中的一條邊，按清倉價格的定義，有vi1j1-pj1≥vi1j2-pj2，而因為（i1,j2）是N中的一條邊且（i1,j1）不是N中的，就有vi1j1-qj1＜vi1j2-qj2。將上述兩個不等式相減，得

qj2-qj1＜pj2-pj1

類似考慮其他的邊，就有

qj3-qj2＜pj3-pj2

……

qj1-qjk＜pj1-pjk

把它們相加，就得到矛盾的0＜0。這個矛盾說明前面“假設(shè)（i1,j1）不在G(q)中”是不成立的。于是，p的任一完美匹配的所有邊都在G(q)中，即為q的一個完美匹配。對稱地，q的每一個完美匹配也都是p的完美匹配。證畢。

現(xiàn)在我們可以看為什么r=λp+(1-λ)q也是清倉價格了。由引理，p和q有共同的完美匹配N。假設(shè)i在N中與j匹配，對任何k≠j，有

vij-pj≥vik-pk和vij-qj≥vik-qk

分別乘以系數(shù)λ和（1-l）就是

λvij-λpj≥λvik-λpk

和

(1-λ)vij-(1-λ)qj≥(1-λ)vik-(1-λ)qk

相加得

vij-(λpj+(1-λ)qj)≥vik-(λpk+(1-λ)qk)

即對于任何k≠j

vij-rj≥vik-rk

這就是說r是一組清倉價格。至此，就完成了關(guān)于清倉價格凸性的一個初等證明。

我沒有查到是否前面有人給出過這個證明。鑒于清倉價格概念在匹配市場問題中的核心地位，以及林濤這個證明的優(yōu)雅，我以為它是可以放到未來的面向非數(shù)學(xué)專業(yè)的本科生教材中的。這樣一個證明，完全不需要有凸優(yōu)化知識，只需要了解匹配市場模型，有初等數(shù)學(xué)程度上的成熟和較好的邏輯思維能力，就可以理解。

第二個故事與最近在一所獨立學(xué)院的幾個講座有關(guān)。我一直認為“社會科學(xué)中的計算思維”是一個廣譜的話題，應(yīng)該讓更多的學(xué)子有所接觸，且相信年輕人都能在一定程度上體會和理解，也許就能影響他們今后的職業(yè)生涯和對生活的態(tài)度。

這次安排的是一個系列講座的形式，對學(xué)生們來說算16個課時合1個學(xué)分。講課過程中，總有一些兩眼放光能跟上我節(jié)奏的學(xué)生。第一次課后我布置了幾個習(xí)題，其中包括要計算下面這個網(wǎng)絡(luò)節(jié)點的Pagerank，并且我給了參考答案（即可以通過計算得到的均衡值）：0, 1/3, 1/3, 1/3（如圖2所示）。

圖2 學(xué)習(xí)Pagerank性質(zhì)的一個例圖

第二次課上，有學(xué)生站起來質(zhì)疑，說按照課上介紹的Pagerank算法，得不到我給的這個結(jié)果，除了A=0，其他3個節(jié)點的值是在1/2, 1/4, 1/4之間輪轉(zhuǎn)。更進一步地，他說查資料了，要用一種稱為“阻尼”的方法才能使迭代收斂（只是還沒明白那種方法是什么，希望能知道）。

這一方面讓我大喜——孺子可教！另一方面讓我有些為難——不太可能在那種場合把話題展開。更重要的是，當(dāng)時我雖然能猜到他說的“阻尼”是怎么回事，但對Pagerank的收斂性，我還沒有用自己的語言歸納出一種完整的說法。于是我告訴他，課后給我發(fā)郵件，我一定回復(fù)。

后來那學(xué)生真的給我發(fā)郵件了，而我呢，回來后把與Pagerank的收斂性相關(guān)的問題認真梳理了一遍，得到結(jié)論如下：

從教學(xué)的角度，總是先講Pagerank基本算法（單純用“入向節(jié)點的值/度數(shù)”之和作更新，在我的講座中只是提到了這個基本算法），然后根據(jù)需要講縮減與補償算法（即那個同學(xué)說的“阻尼”方法，其中用到一個參數(shù)s∈(0,1)）。

由佩龍定理（關(guān)于正矩陣的結(jié)論）保證，縮減與補償算法總是收斂的，且結(jié)果唯一（與初值無關(guān)）。

基本算法的情況就要復(fù)雜許多。雖然在Pagerank意義下的均衡值總是存在的（佩龍定理關(guān)于非負矩陣的結(jié)論），但取決于網(wǎng)絡(luò)結(jié)構(gòu)，可能收斂，也可能不收斂。收斂結(jié)果可能與初值無關(guān)，也可能與初值有關(guān)。例如，圖3（1）總是收斂的，但收斂結(jié)果與初值有關(guān)；另一方面，如果網(wǎng)絡(luò)圖是強連通的，雖然也不保證收斂，但是若收斂則是唯一的。圖3（2）就是一個例子，它一般來說不收斂，但若收斂，結(jié)果就是1/4，1/4，1/4，1/4。

進而，我們可以估計到，如果一個網(wǎng)絡(luò)結(jié)構(gòu)和初值設(shè)定在基本算法下不會收斂，則在縮減與補償算法下收斂的速度與s有關(guān)，越大收斂得越慢。

圖3 Pagerank基本算法收斂性討論例圖

可以說，Pagerank是這些年可以用“風(fēng)靡”來形容的一個概念，許多場合都用到過，熟悉的讀者也一定不少。在這里，也希望與其他老師探討，我上面的說法是否還有漏洞？

類似這樣的故事，在過去這些年的教學(xué)過程中經(jīng)歷不少，幾乎每學(xué)期都有。講課的內(nèi)容能引起學(xué)生的思考，他們的反饋也讓我有所提高，實為快哉。例如這一次在該獨立學(xué)院，整個課程講完之后做了一個問卷，其中一個問題是：

你認為在本校是否應(yīng)該開這種內(nèi)容的課程：

□ 很不應(yīng)該 □ 不應(yīng)該 □ 無所謂

□ 應(yīng)該 很應(yīng)該

184個學(xué)生提交的結(jié)果如圖4所示。

圖4 一門交叉學(xué)科課程是否應(yīng)該在獨立學(xué)院開設(shè)的問卷結(jié)果

這個問卷結(jié)果讓我很受鼓舞。前面也提到，上課的時候總能看到一些兩眼放光跟上我節(jié)奏的學(xué)生。當(dāng)然，也不可避免地有一些低頭族，而且有學(xué)生向他們的老師反饋說我布置的作業(yè)太難，不會做，提交上來的作業(yè)基本就是我給的參考答案，但這個問卷結(jié)果很說明問題，代表了大多數(shù)同學(xué)的支持態(tài)度，而那些反饋問題的情況也屬于“正常范圍”。同時，這個問卷結(jié)果也再一次支持了這樣一個信念：愛學(xué)習(xí)是年輕人的特質(zhì)，問題可能在于學(xué)什么和怎么學(xué)，同時也延伸出一個學(xué)習(xí)環(huán)境怎樣以及怎樣教的問題。