靜態(tài)二元偏好婚姻匹配問題

吳威讓，陳金陽，殷 威

(湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，湖北 黃石 435002)

靜態(tài)二元偏好婚姻匹配問題

吳威讓，陳金陽，殷 威

(湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，湖北 黃石 435002)

主要研究了傳統(tǒng)婚姻匹配問題二元化處理的模型.得到了在二元化處理的情況下，完美匹配的計數(shù)表達(dá)式，且證明了在參與人可接受的潛在配偶越來越接近于n的情況下，其有穩(wěn)定完美匹配的概率趨近1.

婚姻匹配;二元偏好;完美匹配

0 引言

本文主要研究的靜態(tài)婚姻匹配模型，該模型包括：兩個非空集合M={m1,m2,…,mn} 和W={w1,w2,…,wn} 分別表示未婚男士和未婚女士的集合.我們在集合M和W定義如下的偏好關(guān)系：如果對于某個男士m而言，w1比w2要好，就記作w1?mw2，如果該男士認(rèn)為w1至少和w2一樣好，就記作w1mw2.類似的對于女士w而言，可以定義m1?wm2和m1wm2.其它有關(guān)婚姻匹配的一些概念，如穩(wěn)定婚配，完美婚配等均可參考文獻(xiàn)[1]和[2].

假設(shè)存在一個婚姻介紹所，要求上述集合M∪W中的未婚男士和未婚女士均需提供自己的私人信息和偏好.然后由婚姻介紹所根據(jù)這些信息進(jìn)行匹配.現(xiàn)假設(shè)婚姻介紹所要求每一位男士和女士都必須根據(jù)對其潛在配偶的偏好程度給每位異性排序.并且不允許并列的名次出現(xiàn)，我們用數(shù)字 1,2,…,n表示這些男女對其潛在配偶的偏好程度，某一位男士(女士)對應(yīng)的數(shù)字越小表明該排序者對其偏愛程度越高.

這樣我們就得到對于男士和女士而言的兩個n×n的排名矩陣，分別記為M=(mij)n×n和W=(wij)n×n，其中mij表示男士i對女士j的排序；wij表示女士j對男士i的排序.我們定義P=M×W=((mij,wij))n×n，我們稱雙變量矩陣P為優(yōu)先排名矩陣.為了便于理解上述概念，我們看如下一個例子：

例1 假設(shè)有四對男女m1,m2,m3,m4和w1,w2,w3,w4，他們相應(yīng)的偏好排名如下：

m1:w1?w2?w3?w4;w1:m4?m3?m1?m2;

m2:w1?w4?w3?w2;w2:m2?m4?m1?m3;

m3:w2?w1?w3?w4;w3:m4?m1?m2?m3;

m4:w4?w2?w3?w1.w4:m3?m2?m1?m4.

則該問題對應(yīng)的矩陣M和W以及其優(yōu)先排名矩陣P如下：

w1w2w3w4w1w2w3w4w1w2w3w4

如上，在其優(yōu)先排名矩陣P中，我們給出了這個例子的兩個完美匹配，如下：

μ1:(m1,w3),(m2,w4),(m3,w1),(m4,w2)

μ2:(m1,w1),(m2,w2),(m3,w3),(m4,w4)

我們可以算出前一個完美匹配μ1是穩(wěn)定的，但是后一個完美匹配μ2不是穩(wěn)定的，因為在第二種完美匹配中，男士m2和女士w4不滿意這個匹配的安排，他們會各自離開自己先前的匹配安排 (m2,w2)和 (m4，w4)組成 (m2,w4)這個新的配對，這是一個阻止對.所以該匹配不穩(wěn)定.

1 二元偏好完美婚姻匹配及其計數(shù)問題

在實際生活中，進(jìn)行婚姻匹配的男女往往無法對他們的潛在配偶擁有一個完全偏序的喜好，往往認(rèn)為對異性的偏好近僅僅分為幾個等級，且處于同一偏好等級的潛在配偶偏好關(guān)系是無差異的(即以相同概率選擇其中的一個進(jìn)行匹配).如“很喜歡”、“喜歡”，“一般”、“不喜歡”和“很不喜歡”等等，或許還有其它的衡量標(biāo)準(zhǔn)，我們?yōu)榱撕喕幚?，這里只考慮一個簡單的情況就是只考慮兩種偏好：“愿意接受”和“不愿意接受”.于是對于前面討論的問題我們可以把它作如下二元化處理：

由于男女雙方最終要互相接受(不僅男士i愿意和女士j結(jié)婚，而且女士j愿意和男士i結(jié)婚)，最終的偏好構(gòu)成的矩陣我們記為矩陣P，我們可知最終偏好矩陣P滿足：

P=(pij)n×n=M°W=(mij×wij)n×n,(i,j=1,…,n)

其中矩陣M°W為矩陣M和W的 Hadamard積，他表示把它們對應(yīng)元素相乘所得.我們可以得到最終偏好矩陣P也是一個0-1 矩陣.由于做了上面的二元化處理，這樣的匹配必然是穩(wěn)定的.我們簡記上述二元化處理的婚姻匹配為P(M,W,P;μ).

例如，在前面所舉的例1中，我們假定男士mi和女士wi(i=1,2,…,4)均只接受排名在前兩位的異性作為其理想的配偶，被接受的異性之間不存在差異，即認(rèn)為和其中之一結(jié)婚都是相同偏好的.則其偏好矩陣如下：

w1w2w3w4w1w2w3w4w1w2w3w4

我們可以看到，在這種情況下，不存在完美婚姻匹配.不過可以形成如下的匹配： .

μ3:(m2,w4),(m3,w1),(m4,w2),m1,w3

即m1和w3沒有在匹配μ3的安排下結(jié)婚，仍維持單身.但是對于這樣的匹配，仍然是有意義的，至少他讓部分參與者獲得了理想中的伴侶.于是，對于不是完美匹配的匹配，我們尋找這樣的匹配，使得在這個匹配安排下，盡可能多的男女雙方能夠找到自己理想中的伴侶.我們稱之為極大匹配.

在前面的分析中，我們看到二元偏好婚姻問題P(M,W,P;μ)是否具有完美匹配以及完美匹配的計數(shù)問題，與其相應(yīng)的最終偏好矩陣P有著密切的關(guān)系，我們注意到這樣一個事實，在最終偏好矩陣P中，若該婚姻匹配問題有完美匹配，那么在P中必然存在n個1，這n個1不僅兩兩不在同一個行，而且兩兩不在同一列.反之亦然.即這種對應(yīng)是一一對應(yīng)的，為了研究二元偏好完美婚姻匹配的計數(shù)問題，我們給出如下的定義：

定理1 二元偏好婚姻匹配P(M,W,P;μ)的完美穩(wěn)定匹配的個數(shù) |SP(M,W)|等于其最終偏好矩陣的積和式的值，即

2 二元偏好完美婚姻匹配計數(shù)的估值問題

前面我們把一個一般的婚姻匹配問題進(jìn)行了二元化處理，得到了有關(guān)其完美婚姻匹配的一個美妙的結(jié)論(即定理1)，其核心問題就是最終偏好矩陣P的積和式perP的確定，但是在實際計算中，當(dāng)匹配男女雙方的基數(shù)n逐漸增大，perP的計算就變得難以在計算機(jī)中實現(xiàn)，于是使得我們轉(zhuǎn)而研究在某種特殊的限定情況下， perP的計算或是一些估計的結(jié)果.這就是本節(jié)所要討論的結(jié)果.

定義3 對于矩陣Am×n我們記RA=(r1,r1,…rm)和CA=(c1,c2,…cn)分別表示矩陣A的行和向量以及列和向量，其中ri(i=1,…,m)和cj(j=1,…,n)分別表示矩陣A的第i行行和以及矩陣A的第j列列和.關(guān)于二元偏好完美婚姻匹配個數(shù)|SP(M,W)| 的估值，我們有如下一些結(jié)論.

定理2 設(shè)在P(M,W,P;μ)中，對于其最終偏好矩陣Pn×n，其行和向量RP≥k，即ri≥k(i=1,…,n)，

若其至少存在一個完美婚姻匹配，則其完美婚姻匹配的個數(shù)滿足|SP(M,W)|≥k! .同理，對于其列和向量Cp也有類似結(jié)論.

證明 由定理1，|SP(M,W)|=perP，我們對n采用數(shù)學(xué)歸納法.

當(dāng)n=1 時，k=1.結(jié)論是平凡的，成立.假設(shè)n>1，且對一切行列

由于其至少存在一個完美婚姻匹配，則perP>0 .由Frubenius-konig定理(參見文獻(xiàn)[3])，知P不含t×(n-t+1)的零子矩陣，于是P的每個t×n子矩陣至少含有t個非零列.

情形1 對某個h(1≤h≤n-1)，P存在一個恰好有一個h×(n-h)的零子矩陣，則P置換相抵于

h

這個矩陣的前h行的所包含的k個1必然在B中，于是我們知道B的每一行至少有k個1，且k≤h≤m-1 .此外perP=perB·perD>?perB>0,perD>0.于是有歸納假設(shè)有perB≥k! .于是

perP=perB·perD≥k!perD≥k!

情形2P不是置換相抵于(2)的形式，則P的每個t×n子矩陣 (1≤t≤n-1)至少含有t+1個非零列，設(shè)劃去P某一非零元所在的行和列得到的矩陣為P′，則perP>0?perP′>0，且P′的每行至少有k-1個1，由歸納假設(shè)知perP′≥(k-1)!.由于P的每行至少有k個1，我們把perP按照第一行展開得到

定理2給出了 |SP(M,W)|的一個下界，利用矩陣的行和的估值，Bregman在1973年給出了0-1 矩陣積和式的一個上界，于是我們可以利用這種方法估計|SP(M,W)| 的上界，我們先看如下的引理：

引理1[4](Minc-Bregman)設(shè)A為n階0-1 方陣且行和為r1，…,rn,則

上面的結(jié)論，均是在給出P行和向量的具體形式，然后給出了完美婚姻匹配的個數(shù)|SP(M,W)| 的一個估值，下面的定理給出了，在P中0和1的數(shù)量關(guān)系給定的情況下對|SP(M,W)| 的一個估值的結(jié)果，如下：

定理4 在P(M,W,P;μ)問題中，對于其最終偏好矩陣Pn×n，且P含有τ個0，σ個1，且τ≤n2-n，則其完美婚姻匹配的個數(shù)滿足

證明 由定理1知|SP(M,W)|=perP，對于0-1 矩陣我們采用Brualdi， Coldwasser和 Michael在1988的一篇論文發(fā)表的結(jié)論的證法即得結(jié)論，具體證明參見文獻(xiàn)[5].

由上面的分析，我們可以得到如下結(jié)論.

定理5 在P(M,W,P;μ)問題中，對于其最終偏好矩陣Pn×n，其行和向量Rp=k→n，即ri=k→n(i=1,…，n)其有完美匹配μ的概率趨近于1.

3 小結(jié)

本文在對婚姻問題所做二元化處理之后，考慮問題的情況更直觀，便于采用矩陣的方式研究，最終我們得到了在一般實際問題中難以回答的問題，如穩(wěn)定完美婚姻匹配個數(shù)的計數(shù)，極大匹配的估值范圍.但是由于本文做了二元化處理，對于婚姻問題的穩(wěn)定性考慮就被忽略了，而且，在二元化處理時，在第二節(jié)的引文中做了如下假設(shè)：對可接受的潛在配偶是以相同概率匹配的.這對于我們就最終結(jié)果的預(yù)測的變得困難，我們希望能夠得到一個好而確定的預(yù)測.這對實際的研究是很有價值的.值得我們關(guān)注.

[1]Noam Nisan, Tim Roughgarden, Eva Tardos, et al. Algorithmic Game Theory[M]. New York : Cambridge University press, 2007.

[2]Brualdi Richard A .Introductory Combinations[M]. Beijing: China Machine Press, 2009.

[3]詹興致. 矩陣論[M]. 北京:高等教育出版社, 2008.

[4]Bregman L M. Certain properties of nonnegative matrices and their permanents[J]. Dok Akad NaukSSSR, 1973,211: 27～30.

[5]Brualdi R A, Coldwasser J L,Michael S T. Maximum permanents of matrices of zeros and ones[J]. Combin Theory, Ser A, 1988, 49: 207～245.

[6]柳柏廉. 組合矩陣論[M]. 北京:科學(xué)出版社,2005.

[7]董寶民,王運通,郭桂霞. 合作博弈論[M]. 北京: 中國市場出版社, 2008.

[8]Gale D, Shapley L S. College admission and the stability of marriage[J]. American Mathematical Monthly, 1962, 69: 9～15.

[9]Bondy J A, Murty U S R. Graph theory and its applications[M]. New York: Academic Press, 1976.

Staticbinary-preferencemarriagematchingproblem

WU Wei-rang，CHEN Jin-yang,YIN Wei

(College of Mathematics and statistics, Hubei Normal University, Huangshi 435002, China)

In this paper, the traditional marriage matching problem under binary processing model have been considered. We got the count expression for perfect matching in binary-preference case. And it is proved that the number of acceptable potential spouses close ton, the probability of perfect matching reaching 1.

marriage matching; binary-preference; perfect matching

2014—07—01

國家自然科學(xué)基金項目(61304057);湖北省教育廳重點項目(D20122204);青年項目(Q20102508);校級創(chuàng)新團(tuán)隊項目.

吳威讓(1990— )，男，湖北洪湖人，碩士研究生，研究方向為博弈論.

O225

A

1009-2714(2014)04- 0074- 05

10.3969/j.issn.1009-2714.2014.04.016