段歆瑋　詹文杰　楊　潔

(1. 華中科技大學(xué)管理學(xué)院； 2. 武漢紡織大學(xué)會(huì)計(jì)學(xué)院)

?

多屬性雙邊匹配模型及其應(yīng)用研究

段歆瑋1詹文杰1楊潔2

(1. 華中科技大學(xué)管理學(xué)院； 2. 武漢紡織大學(xué)會(huì)計(jì)學(xué)院)

摘要：針對(duì)婚配問(wèn)題中序數(shù)滿(mǎn)意值信息無(wú)法衡量偏好強(qiáng)度關(guān)系，以及經(jīng)典雙邊匹配Gale-Shapley算法只能求解男/女單方最優(yōu)穩(wěn)定解這兩個(gè)問(wèn)題，首先通過(guò)分析在線(xiàn)相親網(wǎng)站上的會(huì)員信息，分別建立了男/女基數(shù)滿(mǎn)意值的多屬性評(píng)價(jià)模型，然后提出了基于滿(mǎn)意值基數(shù)信息的雙邊匹配線(xiàn)性規(guī)劃模型及其相應(yīng)算法，最后通過(guò)一個(gè)算例比較了新算法與已有算法的差異。結(jié)果顯示，所提出的新算法明顯優(yōu)于其他算法。

關(guān)鍵詞：雙邊匹配； 婚配問(wèn)題； 多屬性決策； 滿(mǎn)意度； 基數(shù)信息

隨著“剩男剩女”的大量出現(xiàn)，男女婚配問(wèn)題已經(jīng)成為一個(gè)亟待解決的社會(huì)問(wèn)題。在現(xiàn)實(shí)生活中，凡是涉及兩組不同利益主體，每個(gè)主體盡量匹配到其滿(mǎn)意的另一邊主體，并使雙方滿(mǎn)意度最大，都屬于雙邊匹配問(wèn)題。男女婚配就是典型的雙邊匹配問(wèn)題，除此之外，買(mǎi)方與賣(mài)方匹配、員工與崗位匹配、大學(xué)招生錄取等問(wèn)題都屬于雙邊匹配的范疇[1]。通常，在雙邊匹配過(guò)程中，需要考慮雙邊主體的偏好信息。

目前，針對(duì)偏好序數(shù)信息的雙邊匹配問(wèn)題的研究受到了國(guó)內(nèi)外學(xué)者的關(guān)注[2～14]。GALE等[2]最早提出了穩(wěn)定匹配的概念，并在男女雙方對(duì)異性有著嚴(yán)格偏好序的條件下，給出了獲取男方(或女方)最優(yōu)穩(wěn)定匹配解的Gale-Shapley算法(簡(jiǎn)稱(chēng)G-S算法)；MCVITE等[3]基于雙邊偏好序數(shù)信息提出了“Breakmarriage Operation”的遞歸算法，該算法可以求出雙邊匹配問(wèn)題中全部穩(wěn)定匹配解；ROTH[4,5]針對(duì)美國(guó)醫(yī)學(xué)院畢業(yè)生和醫(yī)院的雙邊匹配問(wèn)題，在雙方嚴(yán)格偏好序的條件下，給出了Hospital-Resident算法進(jìn)行匹配；KNOBLAUCH[6]探討了男女雙方偏好序值信息隨機(jī)分布情況下G-S算法的性質(zhì)；MCVITE等[7]研究了男女雙方人數(shù)不相等的婚姻匹配問(wèn)題，并給出了求解該問(wèn)題下的穩(wěn)定匹配算法；VATE等[8]運(yùn)用基于偏好序數(shù)信息，構(gòu)建了一個(gè)線(xiàn)性規(guī)劃模型來(lái)求解雙方均衡的穩(wěn)定雙邊匹配結(jié)果；樊治平等[9]和樂(lè)琦等[10]考慮雙邊主體的最高可接受偏好序，給出了一種嚴(yán)格雙邊匹配決策方法及其相應(yīng)求解算法以及同時(shí)考慮整體序值和最大及中介收益最大情況下構(gòu)建雙邊匹配模型。針對(duì)不完全偏好序數(shù)信息的雙邊匹配問(wèn)題，MANLOVE等[11]給出了求解偏好信息不完全和序數(shù)信息不嚴(yán)格情況下的雙邊匹配問(wèn)題的一種二次逼近算法；IWAMA等[12]探討了同時(shí)在考慮雙方主體不完全偏好信息以及序數(shù)不嚴(yán)格情形下，雙邊穩(wěn)定匹配算法的復(fù)雜性；樂(lè)琦等[13]針對(duì)基于不完全序數(shù)信息的雙邊匹配問(wèn)題，從完全雙邊匹配的視角提出了一種新的決策方法；梁海明等[14]在主體弱偏好序信息條件下，構(gòu)建了同時(shí)考慮滿(mǎn)意度和穩(wěn)定性的雙邊匹配模型。

總之，現(xiàn)有的研究成果主要基于序數(shù)偏好信息和G-S算法及其改進(jìn)。然而，基于序數(shù)偏好信息的做法，實(shí)質(zhì)上假設(shè)主體對(duì)于匹配結(jié)果的滿(mǎn)意程度與偏好序值呈逆線(xiàn)性關(guān)系，這在一些現(xiàn)實(shí)匹配問(wèn)題中顯得不盡合理[15]。因?yàn)樾驍?shù)偏好信息并不能反映男女雙方滿(mǎn)意程度的強(qiáng)度差異，偏好序值的增加(減少)與滿(mǎn)意程度的降低(增加)之間不一定呈線(xiàn)性關(guān)系。例如，某男士對(duì)排名第1與排名第2的兩位女士之間滿(mǎn)意程度的差距可能要比排名第2和排名第3的兩位女士之間的差距要大。此外，基于穩(wěn)定匹配的G-S算法是從單邊主體最優(yōu)的視角提出的，即求解男方最優(yōu)穩(wěn)定解或女方最優(yōu)穩(wěn)定解，不能使匹配主體雙方的滿(mǎn)意程度都盡可能大[13]。有鑒于此，本研究首先通過(guò)分析在線(xiàn)相親網(wǎng)站上的會(huì)員信息，分別建立了男/女基數(shù)滿(mǎn)意值的多屬性評(píng)價(jià)模型，然后提出了基于滿(mǎn)意值基數(shù)信息的雙邊匹配線(xiàn)性規(guī)劃模型及其相應(yīng)算法。

1滿(mǎn)意度評(píng)價(jià)指標(biāo)體系

1.1評(píng)價(jià)指標(biāo)及量化

近年來(lái)，有學(xué)者嘗試把基數(shù)偏好信息引入雙邊匹配模型。樊治平等[15]認(rèn)為序數(shù)偏好信息與主體滿(mǎn)意值之間存在倒數(shù)關(guān)系，將序數(shù)信息轉(zhuǎn)化為基數(shù)滿(mǎn)意值，來(lái)求解雙邊匹配中的“既穩(wěn)定，又滿(mǎn)意”解；李銘洋等[16]將偏好序值信息轉(zhuǎn)化為主體心理感知效用，建立雙邊匹配模型；QI[17]將語(yǔ)言評(píng)價(jià)信息轉(zhuǎn)變?yōu)榛鶖?shù)值，來(lái)求解雙邊匹配問(wèn)題。與上述方法不同，本研究通過(guò)分析世紀(jì)佳緣網(wǎng)站上真實(shí)的會(huì)員信息，來(lái)獲得婚配問(wèn)題中的基數(shù)滿(mǎn)意值信息。具體步驟如下：①通過(guò)指標(biāo)的相關(guān)性分析及多指標(biāo)綜合評(píng)價(jià)加乘混合法，分別建立男/女滿(mǎn)意度評(píng)價(jià)指標(biāo)體系；②通過(guò)熵權(quán)法獲得各指標(biāo)權(quán)重；③通過(guò)比較主體的擇偶條件與異性的自身?xiàng)l件之間的差異，得到每個(gè)主體在各項(xiàng)指標(biāo)中的滿(mǎn)意值以及整體滿(mǎn)意值(詳見(jiàn)下節(jié))。

根據(jù)世紀(jì)佳緣網(wǎng)站會(huì)員的自身信息及擇偶標(biāo)準(zhǔn)，本研究選取地區(qū)、年齡、身高、學(xué)歷、民族、婚史狀況等6個(gè)評(píng)價(jià)指標(biāo)(見(jiàn)表1)。男女會(huì)員的注冊(cè)信息構(gòu)成如下4張表格：男性自身?xiàng)l件表(簡(jiǎn)稱(chēng)T1)；男性擇偶條件表(簡(jiǎn)稱(chēng)T2)；女性自身?xiàng)l件表(簡(jiǎn)稱(chēng)T3)；女性擇偶條件表(簡(jiǎn)稱(chēng)T4)。對(duì)于每一位男性來(lái)說(shuō)，他對(duì)任意女性的滿(mǎn)意值是該女性自身?xiàng)l件與其擇偶條件的差值(即T3與T2的差值)，差值越小，表示女性越接近該男性的擇偶條件，滿(mǎn)意值也越高。同樣，每位女性的滿(mǎn)意值為男性自身?xiàng)l件與其擇偶條件的差值(即T1與T4的差值)。

為了知道這6個(gè)指標(biāo)對(duì)整體滿(mǎn)意值的影響強(qiáng)度以及指標(biāo)之間的組成關(guān)系，又從世紀(jì)佳緣網(wǎng)站上隨機(jī)選取了男性和女性各500個(gè)樣本作為研究對(duì)象，分別對(duì)男性/女性擇偶條件表(T2/T4)中的6個(gè)指標(biāo)進(jìn)行相關(guān)性分析。在T2/T4表中，除了年齡和身高為區(qū)間型數(shù)值變量(相關(guān)性分析時(shí)取中值)外，其余4個(gè)指標(biāo)均為字符型分類(lèi)變量，需轉(zhuǎn)化為數(shù)值型分類(lèi)變量，具體處理方法見(jiàn)表1。

表1　指標(biāo)定量處理

1.2男性擇偶條件相關(guān)性分析

表2是對(duì)T2中6個(gè)指標(biāo)進(jìn)行相關(guān)性分析的結(jié)果。忽略相關(guān)性極弱或無(wú)相關(guān)(相關(guān)系數(shù)絕對(duì)值小于0.3)的相關(guān)關(guān)系，在男性擇偶條件中，學(xué)歷和婚史、民族和婚史之間在99%的置信區(qū)間上顯著相關(guān)。

表2　男性樣本擇偶條件各指標(biāo)相關(guān)性分析

注：**表示在0.01的顯著水平上顯著相關(guān)，下同。

根據(jù)多指標(biāo)綜合評(píng)價(jià)加乘混合法，本研究把相關(guān)性較為緊密的指標(biāo)作為一類(lèi)，做乘法處理，而把相關(guān)性不強(qiáng)的指標(biāo)做加法處理，得到如下男性擇偶滿(mǎn)意度評(píng)價(jià)模型

(學(xué)歷滿(mǎn)意值×民族滿(mǎn)意值×婚史滿(mǎn)意值)，

(1)

式中，WML、WMA、WMH、WGGNM分別表示男性的地區(qū)、年齡、身高以及(學(xué)歷×民族×婚史)的權(quán)重。然后，運(yùn)用熵值法求出這4個(gè)權(quán)重值，分別是：WML= 0.248、WMA= 0.251、WMH=0.249、WMGNM= 0.252。

1.3女性擇偶條件相關(guān)性分析

同理，表3是對(duì)T4中6個(gè)指標(biāo)進(jìn)行相關(guān)性分析的結(jié)果。研究發(fā)現(xiàn)，女性在進(jìn)行擇偶判斷時(shí)，男性的年齡和身高、學(xué)歷和婚史之間存在顯著相關(guān)性，其余各指標(biāo)之間相互獨(dú)立。

表3　女性樣本擇偶條件各指標(biāo)相關(guān)性分析

同樣，根據(jù)多指標(biāo)綜合評(píng)價(jià)加乘混合法，得到如下女性擇偶滿(mǎn)意度評(píng)價(jià)模型

(2)

式中， WFL、WFAH、WFGM、WFN分別表示女性的地區(qū)、(年齡×身高)、(學(xué)歷×婚史)以及民族的權(quán)重。然后，運(yùn)用熵值法求出這4個(gè)權(quán)重值，分別是：WFL= 0.249，WFAH=0.249；WFGM=0.249，WFN= 0.253。

通過(guò)以上相關(guān)分析可以發(fā)現(xiàn)，男/女在擇偶評(píng)價(jià)時(shí)存在顯著差異：①對(duì)于年齡和身高兩個(gè)生物屬性指標(biāo)，男性往往將它們單獨(dú)考慮，而女性則放在一起考慮，說(shuō)明女性比男性更強(qiáng)調(diào)生物指標(biāo)的一致性，傾向于所謂“男才女貌”的理論解釋?zhuān)虎趯?duì)于學(xué)歷、民族和婚史這3個(gè)社會(huì)屬性指標(biāo)，男性將它們一起考慮，而女性則單獨(dú)考慮民族，說(shuō)明男性在擇偶時(shí)更強(qiáng)調(diào)異性社會(huì)屬性的一致性，傾向于所謂“門(mén)當(dāng)戶(hù)對(duì)”的理論解釋。

2滿(mǎn)意度評(píng)價(jià)模型

2.1各項(xiàng)滿(mǎn)意值計(jì)算

本研究計(jì)算各項(xiàng)滿(mǎn)意值的基本思路是：通過(guò)比較男性(女性)的擇偶條件與異性的自身?xiàng)l件之間的差異，即通過(guò)逐一比較T3與T2的6個(gè)指標(biāo)的差值，得到每個(gè)男性對(duì)每個(gè)女性各項(xiàng)指標(biāo)的滿(mǎn)意值；同樣，逐一比較T4與T1的6個(gè)指標(biāo)的差值，得到每個(gè)女性對(duì)每個(gè)男性各項(xiàng)指標(biāo)的滿(mǎn)意值。但是，由于以上6個(gè)指標(biāo)有的屬于字符分類(lèi)變量，有的屬于區(qū)間數(shù)值變量，因此本研究采用如下處理方法來(lái)具體計(jì)算各項(xiàng)指標(biāo)的滿(mǎn)意值。下面以計(jì)算第i個(gè)男性(表示為Mi)對(duì)第j個(gè)女性(表示為Fj)的滿(mǎn)意值為例，具體計(jì)算方法如下。

(1)地區(qū)滿(mǎn)意值由表1可知，原始的字符型地區(qū)變量轉(zhuǎn)化為1～32分類(lèi)變量，分別代表我國(guó)32個(gè)省、直轄市、自治區(qū)。如果男性(或女性)在其擇偶需求條件中不限地區(qū)，則變量取值為0。令LMi_T2表示男性擇偶條件中的地區(qū)需求變量，LFj_T3表示女性自身?xiàng)l件中的地區(qū)變量，SLMi2Fj表示i男性對(duì)j女性的地區(qū)滿(mǎn)意值，其計(jì)算方法見(jiàn)式(3)。具體如下：如果i男性在擇偶需求條件中不限地區(qū)(即LMi_T2=0)，則無(wú)論LFj_T3的取值多少，該男性的滿(mǎn)意值始終為1；如果LFj_T3=LMi_T2，表明j女性滿(mǎn)足i男性的地區(qū)需求，則其滿(mǎn)意值為1；如果LMi_T2≠0且LFj_T2≠LMi_T3，表明j女性不滿(mǎn)足i男性的地區(qū)需求，則其滿(mǎn)意值為0.5；如果i男性設(shè)定擇偶條件地區(qū)需求為必要指標(biāo)且LFj_T2≠LMi_T3，則對(duì)應(yīng)地區(qū)滿(mǎn)意值為0。由此可見(jiàn)，地區(qū)滿(mǎn)意值取值范圍為[0, 1]

(3)

(2)年齡滿(mǎn)意值令[LAMi_T2,RAMi_T2]為男性擇偶條件中的年齡需求區(qū)間，LO_AMi和UP_AMi分別表示該男性可以接受的女性年齡下限和上限，SAMi2Fj表示i男性對(duì)j女性的年齡滿(mǎn)意值，其計(jì)算方法見(jiàn)式(4)。如果AFj_T3[LAMi_T2,RAMi_T2]，其滿(mǎn)意值為1；如果AFj_T3(LO_AMi,LAMi_T2)或AFj_T3(RAMi_T2,UP_AMi)，滿(mǎn)意值均在區(qū)間范圍內(nèi)呈線(xiàn)性變化；如果AFj_T3≤LO_AMi或AFj_T3≥UP_AMi，其滿(mǎn)意值均為0；如果i男性設(shè)定擇偶條件年齡需求為必要指標(biāo)，且AFj_T3?[LAMi_T2,RAMi_T2]，則對(duì)應(yīng)年齡滿(mǎn)意值為0

SAMi2Fj=

(4)

(3)身高滿(mǎn)意值令[LHMi_T2,RHMi_T2]表示男性擇偶條件中的身高需求區(qū)間，LO_HMi和UP_HMi分別表示該男性可以接受的女性身高下限和上限，SHMi2Fj表示i男性對(duì)j女性的身高滿(mǎn)意值，具體計(jì)算方式與年齡滿(mǎn)意值計(jì)算方式相似

SHMi2Fj=

(5)

(4)學(xué)歷滿(mǎn)意值由表1可知，原始的學(xué)歷變量轉(zhuǎn)化為1/7～7/7分類(lèi)變量，由低到高分別表示中專(zhuān)(或相當(dāng)學(xué)歷)至博士后。如果不限學(xué)歷，則該變量為0/7。令GMi_T2表示男性擇偶條件中的學(xué)歷需求下限，GFj_T3表示女性自身?xiàng)l件中的學(xué)歷變量，SGMi2Fj表示i男性對(duì)j女性的學(xué)歷滿(mǎn)意值，其計(jì)算方法為

(6)

如果該男性認(rèn)為女性學(xué)歷為非必要條件，則滿(mǎn)意值為女性自身學(xué)歷與男性擇偶需求差值(如果女性達(dá)到男性學(xué)歷要求的下限，其學(xué)歷滿(mǎn)意值為負(fù))；如果學(xué)歷為必要條件且女性學(xué)歷低于男性需求，則其對(duì)該女性學(xué)歷的滿(mǎn)意值為-6/7(=1/7-7/7。即學(xué)歷滿(mǎn)意值最差條件是女性自身學(xué)歷為1/7，而男性需求條件為7/7)；如果學(xué)歷為必要條件且女性學(xué)歷達(dá)到男性需求下限，則滿(mǎn)意值為女性自身學(xué)歷與男性擇偶需求差值。由此可見(jiàn)，學(xué)歷滿(mǎn)意值取值范圍為[-6/7, 1]。

(5)民族滿(mǎn)意值令NMi_T2表示男性擇偶條件中的民族需求變量，NFj_T3表示女性自身?xiàng)l件中的民族變量，SNMi2Fj表示i男性對(duì)j女性的民族滿(mǎn)意值，具體計(jì)算方式與地區(qū)滿(mǎn)意值計(jì)算方式相似

(7)

(6)婚史滿(mǎn)意值由表1可知，原始的婚史變量轉(zhuǎn)化為1/3～3/3分類(lèi)變量，由低到高分別表示喪偶、離異和未婚。令，GMi_T2表示男性擇偶條件中的婚史需求下限，GFj_T3表示女性自身?xiàng)l件中的婚史變量，SGMi2Fj表示i男性對(duì)j女性的婚史滿(mǎn)意值，其計(jì)算方法與學(xué)歷滿(mǎn)意值類(lèi)似

(8)

婚史滿(mǎn)意值取值范圍為[-2/3, 1]。類(lèi)似的，可以分別得到j(luò)女性對(duì)i男性的各項(xiàng)指標(biāo)滿(mǎn)意值。

2.2整體滿(mǎn)意值計(jì)算及其歸一化

假設(shè)參與婚配的男性的個(gè)數(shù)為NM(1≤i≤NM)，女性的個(gè)數(shù)為NF(1≤j≤NF)。首先，根據(jù)式(3)～式(8)分別計(jì)算得到i男性對(duì)j女性的各項(xiàng)指標(biāo)滿(mǎn)意值，然后根據(jù)式(1)分別求出i男性對(duì)每個(gè)女性的整體滿(mǎn)意值

SMi2Fj=0.248SLMi2Fj+0.251SAMi2Fj+0.249SHMi2Fj+

(9)

(10)

類(lèi)似的，首先仿照式(3)～式(8)分別計(jì)算得到j(luò)女性對(duì)i(1≤i≤NM)男性的各項(xiàng)指標(biāo)滿(mǎn)意值，然后根據(jù)式(2)分別求出j女性對(duì)每個(gè)男性(1≤i≤NM)的整體滿(mǎn)意值

SFj2Mi=0.249SLFj2Mi+0.249(SAFj2MiSHFj2Mi)+

(11)

最后，分別找出j女性最滿(mǎn)意和最不滿(mǎn)意的男性，仿照式(10)對(duì)每個(gè)男性(1≤ i ≤NM)的整體滿(mǎn)意值進(jìn)行歸一化處理。處理過(guò)后的滿(mǎn)意值也轉(zhuǎn)化為j女性對(duì)每個(gè)男性的滿(mǎn)意值百分比。

3雙邊匹配模型

3.1模型建立

以男性和女性整體平均滿(mǎn)意程度為目標(biāo)建立雙邊匹配模型

(12)

在模型中，式(12)為目標(biāo)函數(shù)，由男性平均滿(mǎn)意程度與女性平均滿(mǎn)意程度組成，其含義為盡可能使男女性平均滿(mǎn)意程度最大。變量kij為決策變量，取值0或1，表示 i男性與j女性是否進(jìn)行匹配。約束(13-1)、(13-2)、(13-3)、(13-4)均為匹配約束，分別規(guī)定一名男性最多只能匹配一名女性，一名女性也最多只能匹配一名男性，最終匹配數(shù)量為min(NM,NF)。約束(13-5)為穩(wěn)定性約束，規(guī)定在得到的匹配解中，不存在不穩(wěn)定情況，即任意兩組匹配解(i男-j女；i′男-j′女)，i男對(duì)j′女的滿(mǎn)意度以及j′女對(duì)i男的滿(mǎn)意度不可能同時(shí)高于他們對(duì)現(xiàn)有對(duì)象的滿(mǎn)意度；i′男對(duì)j女的滿(mǎn)意度以及j女對(duì)i′男的滿(mǎn)意度也不可能同時(shí)高于他們對(duì)現(xiàn)有對(duì)象的滿(mǎn)意度。

3.2模型求解

由于上述匹配模型的目標(biāo)函數(shù)和約束條件均為線(xiàn)性，所以匹配模型是線(xiàn)性規(guī)劃問(wèn)題，本研究采用C++編譯程序求解該模型，算法的偽代碼見(jiàn)圖1。

設(shè)置 循環(huán)總數(shù)當(dāng)time從1到循環(huán)總數(shù)循環(huán)隨機(jī)匹配N(xiāo)M:NF名對(duì)象對(duì)于每一個(gè)男性i:如果他已匹配女性j 搜索所有其余女性j'如果女性j已匹配男性i'如果 (SMi2Fj

4算例分析

本研究從前面500個(gè)男/女會(huì)員中，隨機(jī)選取了50名男性和50名女性進(jìn)行匹配。令男/女性擇偶需求條件可接受年齡下限LO_AMi=80%LAMi_T2，上限UP_AMi=120%RAMi_T2；可接受身高下限LO_HMi=95%LHMi_T2，上限UP_HMi=105%RHMi_T2。首先，根據(jù)男/女滿(mǎn)意度評(píng)價(jià)模型，分別計(jì)算這50名男會(huì)員和50名女會(huì)員各自對(duì)異性的滿(mǎn)意值百分比；然后，采用本研究提出的基數(shù)線(xiàn)性規(guī)劃模型求解，并與其他算法的結(jié)果進(jìn)行對(duì)比。需要說(shuō)明的是，其他算法中只要求滿(mǎn)意值的序數(shù)信息，本研究根據(jù)基數(shù)滿(mǎn)意值百分比的大小進(jìn)行了相應(yīng)排序。

表4給出了基數(shù)線(xiàn)性規(guī)劃模型與經(jīng)典G-S算法的最終匹配結(jié)果，其中Fj列中的第1個(gè)數(shù)字表示基數(shù)線(xiàn)性規(guī)劃模型中相應(yīng)男性匹配的女性編號(hào)；第2個(gè)數(shù)字表示G-S算法中男方表白獲得的與之匹配的女性編號(hào)(即man-optimal)；第3個(gè)數(shù)字表示G-S算法中女方表白獲得的與該男性匹配的女性編號(hào)(即woman-optimal)。從表4中可以看出，不同的算法所得到的匹配結(jié)果有明顯差異。例如，男1在基數(shù)線(xiàn)性規(guī)劃模型下的匹配結(jié)果是女21，而在G-S算法下的匹配結(jié)果分別是女46(man-optimal)和女49(woman-optimal)；以此類(lèi)推*在基于序數(shù)的匹配算法中，當(dāng)滿(mǎn)意值相同時(shí)本研究采取了隨機(jī)排序，可能導(dǎo)致匹配結(jié)果的略微區(qū)別，因此表4中只給出了其中一種匹配結(jié)果，而圖2給出了10次求解的平均滿(mǎn)意值。。

表4　基數(shù)線(xiàn)性規(guī)劃模型與G-S算法匹配結(jié)果

圖2給出了本研究算法與其他算法在平均滿(mǎn)意值方面的差異，可以看出：基數(shù)線(xiàn)性規(guī)劃模型計(jì)算出來(lái)的匹配結(jié)果的平均滿(mǎn)意值是最高的，超過(guò)0.85；其次，是序數(shù)線(xiàn)性規(guī)劃模型，平均滿(mǎn)意值在0.75附近波動(dòng)；接下來(lái)，是樊治平等[15]提出一種將序數(shù)信息求倒數(shù)從而獲得簡(jiǎn)單基數(shù)信息的算法(簡(jiǎn)稱(chēng)“樊治平模型”)，平均滿(mǎn)意值在0.68～0.72區(qū)間波動(dòng)；最后是經(jīng)典G-S算法，其滿(mǎn)意值在0.5～0.652區(qū)間波動(dòng)。

圖1　基數(shù)、序數(shù)線(xiàn)性規(guī)劃模型與G-S算法、　　樊治平模型的平均滿(mǎn)意值對(duì)比

5結(jié)論

本研究通過(guò)對(duì)在線(xiàn)相親網(wǎng)站的會(huì)員信息數(shù)據(jù)分析，分別構(gòu)建了男/女擇偶滿(mǎn)意度評(píng)價(jià)模型，并提出了基于滿(mǎn)意值基數(shù)信息的雙邊匹配線(xiàn)性規(guī)劃模型及其相應(yīng)算法。研究結(jié)果顯示，該方法在保證穩(wěn)定匹配的條件下，整體滿(mǎn)意度水平達(dá)到85%以上，在整體滿(mǎn)意值和匹配結(jié)果的穩(wěn)定性方面均優(yōu)于已有算法。此外，本研究還發(fā)現(xiàn)男/女性擇偶價(jià)值觀(guān)念存在顯著差異，男性較女性更強(qiáng)調(diào)社會(huì)屬性的一致性，而女性較男性則更強(qiáng)調(diào)生物屬性的一致性。

理論方面，本研究提出的基于基數(shù)信息的雙邊匹配模型和算法，彌補(bǔ)了基于序數(shù)信息的匹配算法中滿(mǎn)意度為序數(shù)信息無(wú)法衡量偏好強(qiáng)度關(guān)系的缺點(diǎn)，豐富和發(fā)展了雙邊匹配模型。應(yīng)用方面，婚姻中介可以利用此模型為約會(huì)雙方事先安排好匹配對(duì)象，從而節(jié)約時(shí)間和提高匹配成功率；另外，該算法還可以應(yīng)用到其他多屬性雙邊匹配問(wèn)題，如學(xué)校與新生的匹配、公司與員工的匹配、電子中介下的買(mǎi)賣(mài)雙方的匹配等。

本研究也存在一些不足，需要在今后的研究中逐步完善：①受在數(shù)據(jù)來(lái)源以及量化方面的制約，本研究的滿(mǎn)意度評(píng)價(jià)指標(biāo)模型只考慮了6個(gè)因素，在后續(xù)的研究中，可以適當(dāng)增加其他因素(如相貌、性格等)；②今后還可以和相關(guān)相親網(wǎng)站合作，用真實(shí)的相親匹配結(jié)果數(shù)據(jù)來(lái)進(jìn)一步檢驗(yàn)本研究模型的有效性。

參考文獻(xiàn)

[1] 陳希, 樊治平. 雙邊匹配決策的研究現(xiàn)狀與展望[J]. 管理評(píng)論, 2012, 24(1): 57～63

[2] GALE D, SHAPLEY L S. College Admissions and the Stability of Marriage[J]. The American Mathematical Minthly, 1962, 69(1): 9～15

[3] MCVITE D G, WILSON L B. The Stable Marriage Problem[J]. Communications of the Association for Computing Machinery, 1971, 14(7): 486～492

[4] ROTH A E. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets[J]. Econometrica, 1986, 54(2): 425～427

[5] ROTH A E. Common and Confictiong Interests in Two-Sided Matching Markets[J]. European Economic Review, 1985, 27(1): 75～96

[6] KNOBLAUCH V. Marriage Matching and Gender Satisfaction[J]. Social Choice and Welfare, 2009, 32(1): 15～27

[7] MCVITE D G, WILSON L B. Stable Marriage Assignment for Unequal Sets[J]. Bit Numerical mathematics, 1970, 10(3): 295～309

[8] VATE V, JOHN H. Linear Programming Brings Marital Bliss[J]. Operations Research Letters, 1989, 8(3): 1～23

[9] 樊治平, 樂(lè)琦. 基于完全偏好序信息的嚴(yán)格雙邊匹配方法[J]. 管理科學(xué)學(xué)報(bào), 2014, 17(1): 21～34

[10] 樂(lè)琦, 樊治平. 基于不完全序值信息的雙邊匹配決策方法[J]. 管理科學(xué)學(xué)報(bào), 2015, 18(2): 23～35

[11] MANLOVE D F, IRVING R W, IWAMA K, et al. Hard Variants of Stable Marriage[J]. Theoretical Computer Science, 2002, 276(1/2): 261～279

[12] IWAMA K, MANLOVE D, MIYAZAKI S, et al. Stable Marriage with Incomplete Lists and Ties[C]//GIORGIO A, MARIANGIOLA D C, SIMONETHA R. Proceedings ICALP’ 99: The 26thInternational Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Springer, Berlin, 1999, 1 644: 443～452

[13] 樂(lè)琦, 樊治平. 一種具有序值信息的雙邊匹配決策方法[J]. 系統(tǒng)工程學(xué)報(bào), 2012, 27(2): 185～192

[14] 梁海明, 姜艷萍. 一種考慮中介交易態(tài)度的買(mǎi)賣(mài)雙邊匹配決策方法[J]. 運(yùn)籌與管理, 2013, 22(5): 128～133

[15] 樊治平, 李銘洋, 樂(lè)琦. 考慮穩(wěn)定匹配條件的雙邊滿(mǎn)意匹配決策方法[J]. 中國(guó)管理科學(xué), 2014, 22(4): 112～118

[16] 李銘洋, 樊治平, 樂(lè)琦. 考慮雙方主體心理行為的穩(wěn)定雙邊匹配方法[J]. 系統(tǒng)工程理論與實(shí)踐, 2014, 34(10): 2 591～2 599

[17] QI Y. Two-Sided Matching Decision with Two-Granularity Uncertain and Incomplete Linguistic Terms[J]. International Journal of Multimedia & Ubiquitous Engineering, 2015, 10(2): 121～127

(編輯劉繼寧)

Research of Marriage Matching Problem Based on Multiple-Attribute Two-Sided Matching Model

DUAN Xinwei1ZHAN Wenjie1YANG Jie2

(1. Huazhong University of Science and Technology, Wuhan, China;2. Wuhan Textile University, Wuhan, China)

Abstract：The ordinal information of satisfaction using in the marriage matching cannot measure the intensity of the preferences, and the classic Gale-Shapley algorithm can get one-sided optimal matching result only, i.e. man-optimal or woman-optimal. According to the above defects, this study firstly comes up with two cardinal satisfaction evaluation models for male and female respectively by analyzing the members data from an online dating website. Then, a linear programming model and its solution are given to solve the two-sided matching problem based on the cardinal satisfaction. Finally, a numerical example is presented to illustrate the feasibility and validity of the new model. It is found that the result is significantly better than that of other algorithms under the condition of stable matching.

Key words：two-sided matching; marriage problem; multiple-attribute decision making; degree of satisfaction; cardinal information

作者簡(jiǎn)介：KANJANA JANSUKPUM(1978～)，女，泰國(guó)人。武漢大學(xué)(武漢市430072)信息管理學(xué)院博士研究生。研究方向?yàn)槁糜坞娮由虅?wù)。E-mail：kanjana@whu.edu.cn

DOI編碼：10.3969/j.issn.1672-884x.2016.06.013

收稿日期：2016-01-19

基金項(xiàng)目：湖北省人文社會(huì)科學(xué)重點(diǎn)研究基地資助項(xiàng)目(2013WZ005)

中圖法分類(lèi)號(hào)：C93

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-884X(2016)06-0899-07