吳威讓，陳金陽(yáng)，殷 威

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

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

吳威讓，陳金陽(yáng)，殷 威

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

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

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

0 引言

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

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

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

例1 假設(shè)有四對(duì)男女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.

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

w1w2w3w4w1w2w3w4w1w2w3w4

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

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

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

我們可以算出前一個(gè)完美匹配μ1是穩(wěn)定的，但是后一個(gè)完美匹配μ2不是穩(wěn)定的，因?yàn)樵诘诙N完美匹配中，男士m2和女士w4不滿意這個(gè)匹配的安排，他們會(huì)各自離開自己先前的匹配安排 (m2,w2)和 (m4，w4)組成 (m2,w4)這個(gè)新的配對(duì)，這是一個(gè)阻止對(duì).所以該匹配不穩(wěn)定.

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

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

由于男女雙方最終要互相接受(不僅男士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積，他表示把它們對(duì)應(yīng)元素相乘所得.我們可以得到最終偏好矩陣P也是一個(gè)0-1 矩陣.由于做了上面的二元化處理，這樣的匹配必然是穩(wěn)定的.我們簡(jiǎ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é)婚，仍維持單身.但是對(duì)于這樣的匹配，仍然是有意義的，至少他讓部分參與者獲得了理想中的伴侶.于是，對(duì)于不是完美匹配的匹配，我們尋找這樣的匹配，使得在這個(gè)匹配安排下，盡可能多的男女雙方能夠找到自己理想中的伴侶.我們稱之為極大匹配.

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

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

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

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

定義3 對(duì)于矩陣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)于二元偏好完美婚姻匹配個(gè)數(shù)|SP(M,W)| 的估值，我們有如下一些結(jié)論.

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

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

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

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

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

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

h

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

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

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

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

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

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

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

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

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

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

3 小結(jié)

本文在對(duì)婚姻問題所做二元化處理之后，考慮問題的情況更直觀，便于采用矩陣的方式研究，最終我們得到了在一般實(shí)際問題中難以回答的問題，如穩(wěn)定完美婚姻匹配個(gè)數(shù)的計(jì)數(shù)，極大匹配的估值范圍.但是由于本文做了二元化處理，對(duì)于婚姻問題的穩(wěn)定性考慮就被忽略了，而且，在二元化處理時(shí)，在第二節(jié)的引文中做了如下假設(shè)：對(duì)可接受的潛在配偶是以相同概率匹配的.這對(duì)于我們就最終結(jié)果的預(yù)測(cè)的變得困難，我們希望能夠得到一個(gè)好而確定的預(yù)測(cè).這對(duì)實(shí)際的研究是很有價(jià)值的.值得我們關(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]董寶民,王運(yùn)通,郭桂霞. 合作博弈論[M]. 北京: 中國(guó)市場(chǎng)出版社, 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

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

吳威讓(1990— )，男，湖北洪湖人，碩士研究生，研究方向?yàn)椴┺恼?

O225

A

1009-2714(2014)04- 0074- 05

10.3969/j.issn.1009-2714.2014.04.016