考慮偏好序且權重未知的群雙邊匹配決策

林 楊，王應明

(1．福州大學經濟與管理學院，福建福州350116;2．福建師范大學經濟學院，福建福州350117)

0 引言

雙方互為決策的匹配問題，即雙邊匹配(bilateral matching)是決策科學的重要研究內容．其理論和方法在經濟管理領域有廣泛的應用背景，如電子商務背景下的供需雙方匹配問題［1］，風險投資基金與創業公司的選擇問題［2］，高校招生與學生升學的雙向選擇問題［3］，男女雙方婚姻匹配問題［4］等．

雙邊匹配是指在兩個不相交的主體集合中，各方主體根據已有的信息對潛在的匹配方給出偏好判斷，并依此進行匹配．合理滿意的匹配方案是管理實踐追尋的目標．在雙邊匹配決策中，通常需要考慮雙方的偏好序信息．有關這方面的研究，多年來得到國內外學者的廣泛關注．Gale和 Shapley［5］最早研究了男女婚配問題并提出穩定匹配的概念，給出經典的G－S匹配算法．隨后，Roth［6］和Balinski［7］等對G－S匹配算法進行全面討論，提出一般意義下雙邊匹配的概念并證明雙方均具有嚴格偏好時，存在Pareto最優的匹配方案;Abdulkadiroglu等［8］研究了弱偏好條件下的雙邊匹配及其特性，提出有效適應延期接受機制．Irving和Manlove［9］針對美國醫學院畢業生與實習醫院存在的現實問題，研究了不完全和不嚴格偏好序的匹配方法．樊治平、樂琦等［10－12］研究考慮完全偏好序以及穩定匹配條件的雙邊滿意匹配，并建立優化模型求解最優匹配結果．梁海明等［13］針對主體給出弱偏好序形式的偏好信息的雙邊匹配問題，使用變步長算法求解優化模型．陳圣群等［14］針對高校課程與教學人員的匹配問題，使用證據推理求出雙方的匹配度并構建優化模型．萬樹平等［15］針對風險投資商與企業匹配問題，考慮決策主體的風險規避的心理特征，基于前景理論和TODIM量化雙方的匹配感知價值，并構建了評價指標為不同類型信息的匹配模型．以往研究為解決基于偏好序的雙邊匹配決策問題打下良好的理論基礎．

需要指出的是，已有的研究都是局限于匹配主體在單人環境下進行決策．現實中，隨著管理實踐活動的日趨復雜，及力圖避免個人認知偏差造成的決策失誤，決策往往由多名人員共同參與［16］．例如在金融投資領域，面對眾多的申請項目，投資公司必須擁有十分出眾的智囊團對項目進行專業的甄別、調查論證及評價．遺憾的是，迄今鮮有對決策主體是多名成員，即群雙邊匹配進行深入研究．因此，群雙邊匹配是決策分析理論亟待解決的實際問題之一．鑒于此，本研究從雙邊匹配和群決策理論的綜合視角，提出一種基于偏好序信息且權重未知的群雙邊匹配的決策方法．先由雙方主體的每位群成員給出對另一方的偏好序信息和對匹配的樂觀程度指數．再將偏好序轉化為滿意度，由樂觀程度指數演算可得到群成員權重，并用OWA算子對個人滿意度進行集結，生成主體群的綜合滿意度，并以雙邊主體群滿意度最大為目標，建立單目標優化模型．最后，求解模型獲得匹配方案．

1 相關概念

1．1 群雙邊匹配

群雙邊匹配可視為在雙邊匹配決策理論的基礎上進行拓展延伸．匹配主體由單人增至多人，下面給出群雙邊匹配的定義．存在參與匹配的甲乙雙方，甲方主體群為A={A1，A2，…，Am}，乙方主體群為B={B1，B2，…，Bn}(m，n≥2);不失一般性，令m≥n．其中:Ai表示甲方第i個主體群，Ai=(a1i，a2i，…，aipi)，=pi(pi≥2)，aik表示主體Ai中第k個成員，Bj表示乙方第j個主體群，Bj=(b1j，b2j，…，bjqj)，=qj(qj≥2)，bjl為主體Bj的第l個成員．

定義1 群雙邊匹配定義為映射μ:A∪B→A∪B，?Ai∈A，?Bj∈B，滿足如下:① μ(Ai)∈B∪{Ai};② μ(Bj)∈A;③ μ(Ai)=Bj，當且僅當μ(Bj)=Ai，則稱μ為群雙邊匹配．

定義2 若 μ(Ai)=Bj，則 μ(Bj)=Ai，稱(Ai，Bj)是μ確定的一個主體群匹配對．若μ(Ai)=Ai，則稱Ai在μ中未匹配．由μ確定的所有主體群匹配對的集合稱為一個匹配方案．

1．2 偏好序與OWA算子

雙邊匹配是主體互相決策、擇優選擇潛在對象的過程．考慮雙方給出偏好序形式的匹配信息．設Gi={g1i，g2i，…，gin}(i=1，2，…，m)為Ai給出的關于B的偏好序信息，其中:gik=(φ1ij，φ2ij，…，φipji)(j=1，2，…，n)，φikj表示 Ai第 k個成員 aik把 Bj排在第 φikj位．同理，Hj={h1j，h2j，…，hjm}，(j=1，2，…，n)為Bj給出的關于A的偏好序信息，其中:hjl=(φ1ji，φ2ji，…，φjpii)(i=1，2，…，m)，φjli表示Bj第l個成員 bjl把Ai排在第 φjli位．例如，φ233=1表示A2第3個成員a23把B3排在第1位．h21=(3，2，1，4)，表示B2共有4位成員，依次把A1排在第3，2，1，4位．

如上所述，群雙邊匹配的主體是由若干名成員組成，各成員關于潛在方的偏好可能不同．根據群決策理論，為確定最優匹配方案，必須將成員的個人偏好轉化、集結為一種可以表示主體群作為獨立單位的匹配信息．本研究使用OWA算子進行集結．OWA算子由美國著名學者Yager［17］提出，是一種介于最大與最小算子間的信息集結算子，為不同的決策準則提供了統一框架，定義如下:

定義3 設fw:Rn→R，W=(w1，w2，…，wn)T是與fw有關的加權向量，滿足wj=1(0 ≤wj≤1，j=1，2，…，n)，若fw(a1，a2，…an)= wibi，其中bi是a1，a2，…an中第i個最大的數，則稱fw是n維OWA算子．

1．3 綜合滿意度及滿意匹配

為便于后續優化模型的建立，將給定的偏好序轉化為滿意度信息．

定義4 Ai成員aik對Bj的滿意度為αikj，Bj成員bjl對Ai的滿意度為βjli，記αikj=Sα(φikj)，βjli=Sβ(φjli);其中，Sα(·)，Sβ(·)是單調遞減的非線性函數，均滿足 S(·)≥0且 S(·)=1．根據文獻［10］，Sα(·)和Sβ(·)可取:

其中:i=1，2，…，m;j=1，2，…，n;k≤ pi;l≤ qj．

定義5［18］群雙邊匹配 μ，?Ai1，Ai2，Bj1，Bj2，i1≠ i2，j1≠ j2，其中 μ(Ai1)= μ(Bj1)，μ(Ai2)=μ(Bj2);若αi1j2+αi2j1≤αi1j1+αi2j2，βi1j2+βi2j1≤βi1j1+βi2j2且等式不同時成立，則μ是不滿意匹配，否則是滿意匹配．

本文要解決的問題是，考慮匹配雙方的主體群各成員給出的偏好序信息且成員權重未知，運用何種決策方法，確定最優滿意匹配方案．

2 群雙邊匹配方法

2．1 計算主體的綜合滿意度

得到主體群成員的個人滿意度后，需對其進行集結并生成主體群的綜合滿意度．集結是聯合個體的不同建議、評價并產生關于群的量值［19］．在群決策理論中，信息集結一般會涉及成員的權重．受環境、知識、經驗等因素的局限，一般群成員不易直接給出準確的權重，而權重影響最終匹配方案的滿意度和可靠性．因此，如何合理、有效地確定群成員權重是群雙邊匹配的一個關鍵環節．

根據行為理論［20］相關研究，在決策過程中，主體自身的樂觀程度測度相對容易假定．針對匹配中群成員權重未知的特點，使用筆者提出的基于OWA算子的極大極小離差法［21－22］，一種給定ORNESS測度下，通過最小化任意兩個相鄰成員之間的權重差值求得一組最優權重．在雙邊匹配中，ORNESS測度可看成主體群對當前匹配的樂觀程度傾向．因此，當已知主體群對匹配方的樂觀程度傾向，運用極大極小離差法就得到群成員基于OWA算子的權重，過程如下:

設 Ai，Bj給出的 ORNESS值分別為εi，λj∈［0，1］，aik，bjl的權重分別是ωik，ωjl，根據極大極小離差法，ωik，ωjl可由式(3a)，(3b)確定:

從式(3)可知，ORNESS值越接近于1/0，主體群對當前匹配越傾向于樂觀∕悲觀．ORNESS=0．5表示主體持中立態度，且每位成員的權重均為1 pi．

例1 主體群Ai由5位決策者組成，經協商給出的ORNESS值ε=0．7．則依據式(3)，基于OWA算子的群成員權重(ωik)k=(0．36，0．28，0．20，0．12，0．04)(k=1，2，…，5)．

得到各組群成員的權重后，使用OWA算子進行集結．設已知aik對 Bj的滿意度 αikj，bjl對Ai的滿意度βjli，

k≤ pi，l≤qj，i=1，2，…，m，j=1，2，…，n;ωik，ωjl分別是αikj和βjli的權重，Ai對Bj的綜合滿意度αij，及Bj對Ai的綜合滿意度βji為:

2．2 優化模型的建立

得到雙方主體群的綜合滿意度后，以最大化雙方的綜合滿意度之和為目標，建立優化模型．設xij是0～1變量，若μ(Ai)=Bj，則xij=1，否則xij=0．建立優化模型(5):

式(5)中φk(k=1，2)為各方參與匹配的重要程度，滿足0≤φ1，φ2≤1，φ1+φ2=1，可由專家或權威部門確定．一般而言，參與雙方地位平等時，為體現公平合作，取φ1=φ2=0．5．c1ij(c2ij)為Ai(Bj)對Bj(Ai)的綜合滿意度，(5a)為決策目標，(5b)表示最大化雙方綜合滿意度之和．(5c)、(5d)的含義是主體群Ai或與某一個主體群Bj匹配，或未匹配，主體群Bj至多與A方某一個主體群匹配．

2．3 模型的求解

該模型存在最優解［10］．模型(5)是0～1單目標整數規劃模型．目標函數和約束條件均為線性的，可采用線性規劃方法求解;當問題規模不大時(i，j≤50)，也可使用Lingo、Excel Solver對模型(5)進行建模求解．當問題規模較大，則不宜直接采用上述方法．近年來發展起來的智能優化算法適用于這種情況［23－24］．根據文獻［23］的思路，經修改設計如下的可行解有界排序法，可用于求解當問題規模較大(50≤i，j≤500)時的情形．

設fy為目標函數，X={x1，x2，…，xn}為fy的可行解集，x*∈X是所求的最優解．根據文獻［23］，存在線性有界函數fb(z)，fb(z)=φi(zi－z~)且fb(z)≤fy(z)，其中:z是向量評價函數，z=λixi，λi＞0且 λi=1;z~是隨機選取的參考向量評價函數， φi=1，k=2．

算法:可行解有界排序法

① 選取fb(z)的一個初始可行解，記為x1，x*=x1，i←1;

②i=i+1;

③ 求fb的第i位最優解xi;

④如果fy(xi)＞fy(x*)，則 x*=xi，否則x*=x*i－1;

⑤重復步驟② ～④，直到fy(x*)＞=fb(xn);

⑥返回最優解x*．

綜上所述，考慮偏好序信息且權重未知的群雙邊匹配方法步驟如下:

步驟1 根據式(1)和(2)，將雙方主體群成員偏好序φikj、φjli分別轉化為個人滿意度αikj和 βjli;

步驟2 根據式(3)，由各主體群給定的ORNESS值，計算群成員的權重;

步驟3 由步驟1和2得到的個人滿意度和權重，根據式(4)、(5)求出雙方各主體群的綜合滿意度;

步驟4 依雙方綜合滿意度，以最大化雙方綜合滿意度之和為目標，建立0～1單目標優化模型(5);

步驟5 求解模型(5)，得到滿意匹配方案．

3 算例

2014年6·18海交會上，有5家臺資高新企業來閩，尋求有技術需求的陸資企業共拓閩臺合作新優勢．經初步了解磋商，有6家陸資企業表達了潛在的合作意向．為保證雙方共同利益，需使配對成功的企業滿意度最高．組委會決定每家企業的決策層先進行內部商討，對潛在的合作方給出偏好信息．再集結成員的偏好信息作為企業的滿意度評價．然后，組委會以雙方滿意度最大為目標撮成意向雙方．5家臺資企業記為集合T={T1，T2，…，T5}，6家陸資企業記為集合L={L1，L2，…，L6};臺資企業Ti主要從企業規模、信用評級、技術能力建設和風險規避能力等指標評價陸資企業．陸資企業Lj重點考察臺資企業的技術轉讓成本、技術轉化風險、創新體制建設和信用評級等指標．此外，根據政策環境，交易成本等因素，雙方給出對本輪閩臺合作的樂觀程度(ORNESS)值．組委會收到雙方的偏好序信息和樂觀程度指數如表1、2所示(第一列括號內為ORNESS值):

表1 臺資企業給出關于陸資企業的偏好序(Ti)Tab．1 The preference ordinals provided by Taiwanese enterprises(Ti)

表2 陸資企業給出關于臺資企業的偏好序(Lj)Tab．2 The preference ordinals provided by China Mainland’s enterprises(Lj)

根據式(3)，可求得雙方主體群各成員權重，其中，5家臺資企業的成員權重分別為:wT1=(0．433，0．333，0．233)，wT2=(0．333，0．333，0．333)，wT3=(0．8，0．2)，wT4=(0．43，0．31，0．19，0．07)，wT5=(0．25，0．25，0．25，0．25);

6 家陸資企業的成員權重依次為:wL1=(0．25，0．25，0．25，0．25)，wL2=(0．433，0．333，0．233)，wL3=(0．633，0．333，0．333)，wL4=(0．5，0．5)，wL5=(0．533，0．333，0．133)，wL6=(0．4，0．6);由式(1)、(2)轉化得到的個人滿意度見表3、4;在此基礎上使用OWA算子進行集結，得到雙方主體群的綜合滿意度，如表5、6所示．

表3 轉化后各臺資企業的群成員個人滿意度Tab．3 The satisfaction degree of each group member of Taiwanese enterprises

依據表5、6雙方的綜合滿意度信息C1，C2，將其表示為矩陣形式并且C2轉置，建立如下0～1單目標優化模型:

由于雙方合作建立在平等互信基礎上，組委會取φ1=φ2=0．5．使用Matlab軟件包求解得δ=3．09，最優解X*為:

即匹配方案為:{(T1，L3)，(T2，L6)，(T3，L1)，(T4，L5)，(T5，L2)}．L4未匹配成功．下面對匹配方案進行驗證．以匹配對(T1，L3)和(T2，L6)為例，根據定義5，α16+ α23=1．43，α13+ α26=0．77，β31+ β62=1．37，β32+ β61=1．04;即 α13+ α26≤ α16+ α23，β32+ β61≤ β31+ β62．類似的，對匹配方案中的匹配對兩兩驗證，可知該匹配方案滿足定義5．故該方案為滿意匹配．

表4 轉化后各陸資企業的群成員個人滿意度Tab．4 The satisfaction degree of each group member of China Mainland’s enterprises

表5 臺資企業對陸資企業的綜合滿意度Tab．5 The comprehensive satisfaction degree of Taiwanese enterprises

表6 陸資企業對臺資企業的綜合滿意度Tab．6 The comprehensive satisfaction degree of China Mainland’s enterprise

4 結語

針對考慮偏好序信息且權重未知的群雙邊匹配問題，提出一種匹配決策方法．該方法結合雙邊匹配和群決策的理論方法．先由雙方主體群的每個成員給出對另一方主體群的偏好序信息．再將偏好序轉化為滿意度，根據主體群給定的樂觀程度指數，求出群成員基于OWA算子的權重，并生成主體群的綜合滿意度．以雙方的主體群綜合滿意度最大為目標建立匹配決策模型，并進一步闡述當問題規模較大時，用可行解邊界排序法進行求解，得到匹配方案．本文提出的群雙邊匹配方法，計算量適中，不僅豐富了雙邊匹配決策理論，而且有較強的應用背景，為管理活動中遇到的群雙邊匹配問題提供決策理論支持．

［1］Sarne D，Kraus S．Managing parallel inquiries in agents’two－ sided search［J］．Artificial Intelligence，2008，172(4/5):541－569．

［2］Elitzur R，Gavious A．A multi－period game theoretic model of venture capitalists and entrepreneurs［J］．European Journal of Operational Research，2003，144(2):440－453．

［3］Pais J．Random matching in the college admissions problem［J］．Economic Theory，2008，35(1):99 －116．

［4］Teo C P，Sethuraman J，Tan W P．Gale － Shapley stable marriage problem revisited strategic issues and applications［J］．Management Science，2001，47(9):1 252．

［5］Gale D，Shapley L．College admissions and the stability of marriage［J］．American Mathematical Monthly，1962，69(1):9 －15．

［6］Roth A E．Common and conflicting interests in two－sided matching markets［J］．Economic Review，1985，27(1):75－96．

［7］Balinski M，Snmez T．A tale of two mechanisms:student placement［J］．Journal of Economic Theory，1999，84(1):73 －94．

［8］Abdulkadiroglu A，Pathak PA，Roth A E．Strategy－proofness versus efficiency in matching with indifferences:redesigning the New York City high school match［R］．New York:National Bureau of Economic Research，2009．

［9］Irving R W，Manlove D F，Scott S．The hospitals－residents problem with ties［J］．Lecture Notes in Computer Science，2000，1 851:259－271．

［10］樊治平，李銘洋，樂琦．考慮穩定匹配條件的雙邊滿意匹配決策方法［J］．中國管理科學，2009，17(4):113－118．

［11］樊治平．基于完全偏好序信息的嚴格雙邊匹配方法［J］．管理科學學報，2014，17(1):21－34．

［12］Fan Z P，Yue Q，Bo F．An approach to group decision making with uncertain preference ordinals［J］．Computers＆ Industrial Engineering，2007，58(1):51－57．

［13］梁海明，姜艷萍．一種基于弱偏好序信息的雙邊匹配決策方法［J］．系統工程學報，2014，22(9):154－159．

［14］陳圣群．高校課程與教學人員的匹配決策方法［J］．福州大學學報:自然科學版，2013，41(6):986－989．

［15］萬樹平．具有不同類型信息的風險投資商與投資企業多指標雙邊匹配決策方法［J］．中國管理科學，2014，22(2):40－47．

［16］尤天慧，李洪燕，劉彩娜．一種具有不確定偏好序信息的多指標群決策方法［J］．中國管理科學，2013，21(5):110－114．

［17］Yager R．On ordered weighted averaging aggregation operators in multicriteria decision making［J］．IEEE Transactions on Systems，Man and Cybernetics，1988，18(1):183 －190．

［18］Vicki K．Marriage matching and gender satisfaction［J］．Social Choice Welfare，2009，32(1):15 －27．

［19］Wang Y M，Fan Z P．Fuzzy preference relations:aggregation and weight determination［J］．Computers＆ Industrial Engineering，2007，53(1):163－172．

［20］Gavetti G．PERSPECTIVE:toward a behavioral theory of strategy［J］．Organization Science，2012，23(1):267－285．

［21］Wang Yingming，Parkan C．A minimax disparity approach for obtaining OWA operator weights［J］．Information Sciences，2005，175(1/2):20－29．

［22］Wang Yingming，Parkan C．A preemptive goal programming method for aggregating OWA operator weights in group decision making［J］．Information Sciences，2007，177(8):1 867 －1 877．

［23］Lucie G，Patrice P，Olivier S．Choquet－ based optimisation in multi－objective shortest path and spanning tree problems［J］．European Journal of Operational Research，2010，204(2):303－315．

［24］蔣忠中，樊治平，汪定偉．電子中介中具有模糊信息且需求不可分的多屬性商品交易匹配問題［J］．系統工程理論與實踐，2011，31(12):2 355－2 366．