得分信息下考慮多種形式主體期望的雙邊匹配方法

張笛,孫濤,閆超棟,萬良琪,陳洪轉(zhuǎn)

(南京航空航天大學(xué) 經(jīng)濟與管理學(xué)院, 江蘇 南京 211106)

得分信息下考慮多種形式主體期望的雙邊匹配方法

張笛,孫濤,閆超棟,萬良琪,陳洪轉(zhuǎn)

(南京航空航天大學(xué) 經(jīng)濟與管理學(xué)院, 江蘇 南京 211106)

針對得分信息下帶有多種形式主體期望的雙邊匹配問題,考慮主體的心理行為因素,提出了一種基于前景理論的雙邊匹配方法.首先,以主體期望為參照點將雙邊主體給出的得分信息轉(zhuǎn)化為相對于參照點的收益和損失;然后,考慮主體對待收益和損失不同的風(fēng)險態(tài)度,依據(jù)前景理論計算每個主體的前景值,在此基礎(chǔ)上,建立雙邊匹配多目標(biāo)優(yōu)化模型,使用極大極小法求解該模型,獲得雙邊匹配方案;最后,通過一個算例驗證了該方法的可行性和有效性.

雙邊匹配;得分信息;多種形式期望;心理行為;前景理論

0 引 言

GALE等[1]基于學(xué)生入學(xué)和穩(wěn)定婚姻匹配提出了雙邊匹配問題,證明了穩(wěn)定匹配的存在性并提出了著名的遞延接受“Gale-Shapley”算法,為雙邊匹配奠定了理論基石.隨后,雙邊匹配問題引起了學(xué)者們的廣泛關(guān)注并取得了豐碩的研究成果[2-19].值得注意的是，2012年諾貝爾經(jīng)濟學(xué)獎頒給了研究雙邊匹配理論和市場機制設(shè)計的SHAPLEY和ROTH,進(jìn)一步激發(fā)了學(xué)者對雙邊匹配的研究熱情.

近年來,基于得分信息和考慮主體心理行為的雙邊匹配問題引起了學(xué)者們的重視[11-19].在得分匹配研究上[11-15],針對完全得分信息的雙邊匹配問題： 樂琦[11]通過構(gòu)造滿意度測度函數(shù),建立了以最大化每方主體滿意度為目標(biāo)的匹配優(yōu)化模型;YUE[12]提出一種嚴(yán)格完全得分信息下的穩(wěn)定雙邊匹配方法;樂琦[13]研究了帶有主體期望的雙邊匹配問題,以主體期望為參照點,構(gòu)建基于TODIM理論的雙邊匹配模型.針對不完全不確定得分信息的雙邊匹配問題，樂琦[14]通過將不完全得分信息轉(zhuǎn)化為不完全匹配滿意度,建立了匹配優(yōu)化模型;他還將文獻(xiàn)[14]的方法推廣至不完全不確定得分信息的情形[15].在行為匹配研究上[16-19],針對完全序值信息的雙邊匹配問題，文獻(xiàn)[16]以主體期望序值為參照點,構(gòu)建基于累積前景理論的匹配優(yōu)化模型;文獻(xiàn)[17-18]考慮了主體心理行為因素,提出一種基于TODIM理論的雙邊匹配方法;文獻(xiàn)[19]將文獻(xiàn)[17]的方法拓展至不確定偏好序的情形.

上述研究豐富、發(fā)展并完善了雙邊匹配理論,但需要指出的是： 目前針對得分信息下帶有主體期望的雙邊匹配研究,主體期望形式單一,較少考慮具有多種形式期望的情形.例如，在基于評價得分的婚姻匹配問題中,男方某主體期望與女方中評價得分不低于某一數(shù)值的主體相匹配;男方某主體期望與女方中評價得分在某一區(qū)間內(nèi)的主體相匹配;男方某主體期望與女方中評價得分不高于某一數(shù)值的主體相匹配.即主體給出的期望形式分別為“不低于某一得分值”“在某一離散區(qū)間得分內(nèi)”和“不高于某一得分值”.因此,研究得分信息下帶有多種形式主體期望的雙邊匹配問題具有重要的理論和現(xiàn)實意義.鑒于此,本文針對3種形式主體期望的雙邊匹配問題,考慮主體的心理行為因素,提出一種基于前景理論的雙邊匹配方法.

1 雙邊匹配問題的描述

定義1設(shè)S={Sτ：τ=1,2,…,T},其中Sτ和T是正整數(shù),τ1,τ2∈{1,2,…,T},若S滿足條件：

1) 若τ1>τ2,則Sτ1>Sτ2；

2) 若Sτ1=Sτ2當(dāng)且僅當(dāng)τ1=τ2,則稱S為一離散得分集.假定Sτ越大,其所對應(yīng)的主體排在越前面或越優(yōu).

在雙邊匹配問題中,設(shè)X方主體集為X={X1,X2,…,XM},其中Xi表示第i個X方匹配主體,i∈I={1,2,…,M},M≥2;Y方主體集為Y={Y1,Y2,…,YN},其中Yj表示第j個Y方匹配主體,j∈J={1,2,…,N},N≥2.

定義3[1-3,10]設(shè)μ：X∪Y→X∪Y上的映射,若N>M≥2,對?Xi∈X,Yj∈Y,滿足條件： 1)μ(Xi)∈Y,μ(Yj)∈X∪{Yj};2)μ(Xi)=Yj,μ(Yj)=Xi,則稱主體Xi和Yj在μ中匹配,記為(Xi,Yj),稱(Xi,Yj)為μ中的雙邊匹配主體對.若(Xi,Yj)是μ中的任意雙邊匹配主體對,且滿足μ(Xi)≠Yj′,Yj′∈Y,Yj′≠Yj,μ(Yj)≠Xi′,Xi′∈X,Xi′≠Xi,則稱μ是一對一雙邊匹配.特別地,μ(Yj)=Yj表示主體Yj在μ中未匹配.

設(shè)S是預(yù)先給定的離散得分集,下面給出雙邊匹配的基本設(shè)置.

設(shè)Ri=(Ri1,Ri2,…,RiN)是X方主體Xi給出的關(guān)于Y方主體的完全得分偏好向量,其中Rij表示主體Xi給出的關(guān)于Yj的評價得分,Rij∈S,且Rij越大,表明Xi對Yj的滿意程度越高,ei是主體Xi的期望得分,表示主體Xi期望與Y方中評價得分為ei的某一主體相匹配,ei∈S;Lj=(L1j,L2j,…,LMj)是Y方中主體Yj給出的關(guān)于X方主體的完全得分偏好向量,其中Lij表示主體Yj給出的關(guān)于Xi的評價得分,Lij∈S,且Lij越大,表明Yj對Xi的滿意程度越高,fj是主體Yj的期望得分,表示主體Yj期望與X方中評價得分為fj的某一主體相匹配,fj∈S.其中i∈I,j∈J.

本文考慮如下3種形式的主體期望信息：

本文需要解決的問題是： 依據(jù)雙邊主體給出的評價得分信息Rij和Lij以及主體期望信息ei和fj,i∈I,j∈J,通過一個有效的匹配方法,建立雙邊匹配優(yōu)化模型,獲得雙邊匹配方案.

2 雙邊匹配方法

2.1 前景值

在本文的雙邊匹配問題中,依據(jù)前景理論[20-21],將雙邊主體的期望作為參照點,通過測度評價得分與參照點之間的感知差異來獲得主體的收益和損失,考慮主體對待收益和損失的不同風(fēng)險態(tài)度,計算每個主體的前景值.

以主體Xi的期望ei為參照點,設(shè)評價得分Rij相對于參照點ei的損益值為Fij,具體為:

(1)

(2)

(3)

考慮主體Xi對待收益和損失的不同風(fēng)險態(tài)度,評價得分Rij的前景值V(Rij)的計算公式為

(4)

其中,參數(shù)αi,βi分別是價值函數(shù)收益區(qū)域和損失區(qū)域的凹凸系數(shù)[22],表示主體Xi對待收益和損失的不同風(fēng)險態(tài)度,αi,βi∈(0,1). 參數(shù)λi是主體Xi的損失規(guī)避系數(shù),λi>1,且λi越大表明主體Xi的損失規(guī)避程度越大[23].

以主體Yj的期望fj為參照點,設(shè)評價得分Lij相對于參照點fj的損益值為Gij,具體為:

(5)

(6)

(7)

考慮主體Yj對待收益和損失的不同風(fēng)險態(tài)度,評價得分Lij的前景值V(Lij)的計算公式為

(8)

2.2 雙邊匹配優(yōu)化模型

設(shè)xij為0-1變量,當(dāng)xij=0時,表示主體Xi和Yj不匹配;當(dāng)xij=1時,表示主體Xi和Yj匹配,以最大化每方主體的前景值和最小化雙邊主體前景值的差異,建立雙邊匹配多目標(biāo)優(yōu)化模型：

(9)

(10)

(11)

(12)

(13)

(14)

上述模型中,式(9)表示X方主體的前景值之和最大;式(10)表示Y方主體的前景值之和最大;式(11)表示雙邊主體前景值的差異之和最小;式(12)表示每個X方主體至多與Y方中一個主體匹配;式(13)表示每個Y方主體至多與X方中一個主體匹配;式(14)表示匹配數(shù)量約束.

(15)

(16)

(17)

(18)

(19)

(20)

令α=min{μzk：k=1,2,3},則多目標(biāo)優(yōu)化模型(15)～(20)可轉(zhuǎn)化為以下單目標(biāo)規(guī)劃模型：

maxα，

(21)

s.t.μzk≥α,k=1,2,3，

(22)

(23)

(24)

(25)

模型(21)～(25)為離散且可行域非空的0～1整數(shù)規(guī)劃模型,必存在最優(yōu)解.

3 實證分析

考慮青年男女婚姻匹配問題,南京某婚介公司收到5名未婚女士X1,X2,X3,X4,X5和7名未婚男士Y1,Y2,Y3,Y4,Y5,Y6,Y7的求偶信息.女士依據(jù)收入、職業(yè)、年齡和學(xué)歷等對男士進(jìn)行綜合評價,給出7名男士的評價得分信息和期望信息,如表1和表3所示.男士依據(jù)外貌、年齡、身高、職業(yè)和學(xué)歷等對女士進(jìn)行綜合評價,給出5名女士的評價得分信息和期望信息,如表2和表3所示.婚介公司依據(jù)雙邊主體的評價得分信息和期望信息進(jìn)行決策,確定雙邊匹配方案.預(yù)先給定的離散得分集為S={S1=1,S2=2,S3=3,S4=4,S5=5,S6=6,S7=7,S8=8,S9=9},其中S1表示最不滿意;S2表示極不滿意;S3表示很不滿意;S4表示不滿意;S5表示一般;S6表示滿意;S7表示很滿意;S8表示極滿意;S9表示最滿意.

表1 女士給出的關(guān)于男士的評價得分信息

Table 1 Evaluation score information on the men provided by the women

為了解決上述匹配問題,下面給出采用前文方法的計算過程和結(jié)果.

以雙邊主體期望為參照點,首先依據(jù)式(1)～(3)

表2 男士給出的關(guān)于女士的評價得分信息

Table 2 Evaluation score information on the women provided by the men

和式(5)～(7)分別計算評價得分Rij和Lij相對于參照點ei和fj的收益和損失,其中由女方主體的損益值構(gòu)成的矩陣為[Fij]M×N,由男方主體的損益值構(gòu)成的矩陣為[Gij]M×N,具體如下：

表3 雙邊主體給出的期望信息

Table 3 Aspiration information provided by the agents on both sides

建立雙邊匹配多目標(biāo)優(yōu)化模型(9)～(14),采用極大極小法將其轉(zhuǎn)化為模型(21)～(25),并使用LINGO11.0求解得

x11=x27=x34=x43=x55=1,其余xij=0.

獲得的雙邊匹配方案為： 女士X1和男士Y1配對,女士X2和男士Y7配對,女士X3和男士Y4配對,女士X4和男士Y3配對,女士X5和男士Y5配對,男士Y2,Y6未匹配.

將本文方法與文獻(xiàn)[13]的方法相比較,得到：

1) 主體期望形式方面： 文獻(xiàn)[13]的主體期望形式單一,僅考慮具有不確定得分(離散區(qū)間得分)的情形,因此該方法難以處理具有多種形式主體期望的雙邊匹配問題;本文考慮了3種形式的主體期望,彌補了主體期望形式單一的不足.

2) 雙邊匹配模型構(gòu)建方面： 本文不僅考慮了最大化每方主體的前景值,而且考慮了最小化雙邊主體前景值的差異;而文獻(xiàn)[13]未考慮雙邊主體前景值的差異.

3) 雙邊匹配優(yōu)化模型求解方面： 文獻(xiàn)[13]使用線性加權(quán)法將多目標(biāo)匹配優(yōu)化模型轉(zhuǎn)化成單目標(biāo)規(guī)劃模型進(jìn)行求解,目標(biāo)權(quán)重系數(shù)的確定主觀性強,且權(quán)重系數(shù)的取值不同,對應(yīng)的匹配解亦不同;本文采用極大極小法求解多目標(biāo)匹配優(yōu)化模型,無須確定目標(biāo)函數(shù)的權(quán)重系數(shù),獲得的匹配解不僅唯一且更為客觀.

4 結(jié) 語

針對得分信息下帶有多種形式主體期望的雙邊匹配問題,將前景理論引入雙邊匹配中,提出了一種考慮主體心理行為的雙邊匹配方法.依據(jù)前景理論,以主體期望為參照點,將雙邊主體的評價得分信息轉(zhuǎn)化為相對于參照點的損益值,考慮主體對待風(fēng)險的不同態(tài)度,計算每個主體的前景值,建立雙邊匹配多目標(biāo)優(yōu)化模型,并使用極大極小法進(jìn)行求解.拓展了雙邊匹配理論,為解決得分信息下帶有主體期望的雙邊匹配問題提供了一種新的方法,具有一定的理論和實際應(yīng)用價值.

[1] GALE D, SHAPLEY L S. College admissions and the stability of marriage[J].TheAmericanMathematicalMonthly, 1962, 69(1)： 9-15.

[2] ROTH A E. The college admissions problem is not equivalent to the marriage problem[J].JournalofEconomicTheory, 1985, 36(2)： 277-288.

[3] ROTH A E, ROTHBLUM U G. Stable matchings optimal assignment and linear programming[J].MathematicsofOperationsResearch, 1993, 18(4)： 803-828.

[4] JIAO Z H, TIAN G Q. The stability of many to many matching with max-min preferences[J].EconomicsLetters, 2015, 129(4)： 52-56.

[5] JIANG Z Z, TAN C, CHEN X, et al. A multi-objective matching approach for one-shot multi-attribute exchanges under a fuzzy environment[J].InternationalJournalofFuzzySystems, 2015, 17(1)： 53-66.

[6] CHEN X, LI Z, FAN Z P, et al. Matching demanders and suppliers in knowledge service： A method based on fuzzy axiomatic design[J].InformationSciences, 2016, 346/347： 130-145.

[7] CHEN S Q, WANG Y M, SHI L H, et al. Two-sided matching decision making with uncertain information under multiple states[J].JournalofSystemsScienceandInformation, 2016, 4(2)： 186-194.

[8] YUE Q, ZHANG L, PENG Y S, et al. Decision method for two-sided matching with interval-valued intuitionistic fuzzy sets considering matching aspirations[J].JournalofIntelligent&FuzzySystems, 2016, 31(6)： 2903-2910.

[9] JIAO Z H, TIAN G Q. The blocking lemma and strategy-proofness in many to many matchings[J].Games&EconomicBehavior, 2017, 102(3)： 44-55.

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

FAN Z P, YUE Q. Strict two-sided matching method based on complete preference ordinal information[J].JournalofManagementSciencesinChina, 2014, 17(1)： 21-34.

[11] 樂琦. 基于得分信息的雙邊匹配決策方法[J].模糊系統(tǒng)與數(shù)學(xué),2014,28(1)： 106-112.

YUE Q. Decision method for two-sided matching based on score information[J].FuzzySystemsandMathematics, 2014, 28(1)： 106-112.

[12] YUE Q. Decision method for stable matching based on strict score information[J].AdvancesinInformationSciences&ServiceSciences, 2013, 10(5)： 1018-1025.

[13] 樂琦. 得分信息下考慮不確定心理行為的雙邊匹配[J].浙江大學(xué)學(xué)報：理學(xué)版, 2016,43(2)： 242-246.

YUE Q. Two-sided matching considering uncertain psychological behavior with score information[J].JournalofZhejiangUniversity：ScienceEdition, 2016, 43(2)： 242-246.

[14] 樂琦. 基于不完全得分信息的雙邊匹配決策方法[J].系統(tǒng)工程, 2013, 31(9)： 79-83.

YUE Q. Decision method for two-sided matching based on incomplete score information[J].SystemsEngineering, 2013, 31(9)： 79-83.

[15] 樂琦. 不完全不確定得分信息下的雙邊匹配決策[J].浙江大學(xué)學(xué)報：理學(xué)版,2015,42(3)： 293-297.

YUE Q. Two-sided matching decision with the incomplete score and uncertain score information[J].JournalofZhejiangUniversity：ScienceEdition, 2015, 42(3)： 293-297.

[16] 樂琦, 樊治平. 基于累積前景理論的雙邊匹配決策方法[J].系統(tǒng)工程學(xué)報, 2013, 28(1)： 38-46.

YUE Q, FAN Z P. Decision method for two-sided matching based on cumulative prospect theory[J].JournalofSystemsEngineering, 2013, 28(1)： 38-46.

[17] 樂琦. 考慮主體心理行為的雙邊匹配決策方法[J].系統(tǒng)工程與電子技術(shù), 2013, 35(1)： 120-125.

YUE Q. Decision method for two-sided matching considering agents psychologicalbehavior[J].SystemsEngineeringandElectronic, 2013, 35(1)： 120-125.

[18] 樂琦. 不確定心理行為下的雙邊匹配[J].系統(tǒng)工程, 2016, 34(5)： 55-59.

YUE Q. Two-sided matching with uncertain psychological behavior[J].SystemsEngineering, 2016, 34(5)： 55-59.

[19] 樂琦, 張磊, 張莉莉. 不確定偏好序信息下考慮主體心理行為的雙邊匹配決策方法[J].運籌與管理, 2015, 24(2)： 113-120.

YUE Q, ZHANG L, ZHANG L L. Decision method for two-sided matching considering agents’ psychological behavior with uncertain preference ordinal information[J].OperationsResearchandManagementScience, 2015, 24(2)： 113-120.

[20] KAHNEMAN D, TVERSKY A. Prospect theory： An analysis of decision making under risk[J].Econometrica, 1979, 47(2)： 263-291.

[21] TVERSKY A, KAHNEMAN D. Advances in prospect theory： Cumulative representation of uncertainty[J].JournalofRiskandUncertainty, 1992, 5(4)： 297-323.

[22] BROMILEY P. A prospect theory model of resource allocation[J].DecisionAnalysis, 2009, 6(3)： 124-138.

[23] AVINERI E. The effect of reference point on stochastic network equilibrium[J].TransportationScience, 2006, 40(4)： 409-420.

[24] ZIMMERMANN H J. Fuzzy programming and linear programming with several objective functions[J].FuzzySets&Systems, 1978, 1(1)： 45-55.

ZHANG Di, SUN Tao, YAN Chaodong, WAN Liangqi, CHEN Hongzhuan

(CollegeofEconomicsandManagement,NanjingUniversityofAeronautics&Astronautics,Nanjing211106,China)

Methodfortwo-sidedmatchingconsideringmulti-styleaspirationofagentsbasedonscoreinformation. Journal of Zhejiang University(Science Edition), 2017, 44(6): 735-741

Considering psychological behavior of agents, a method is proposed based on prospect theory to solve the two-sided matching problems with multi-style aspiration of agents under the score information. Firstly, the aspiration of agents is chosen as the reference point, then score information of agents on both sides are transformed into the gains or losses relative to the reference point. Secondly, considering the agents’ different risk attitudes toward gains and losses, the prospect values of each agents are calculated based on prospect theory. Furthermore, a multi-objective optimization two-sided matching model is constructed. The maxmin method is proposed to solve this model, and the two-sided matching result can be obtained. Finally, an example is given to prove the feasibility and validity of the proposed method.

two-sided matching; score information; multi-style aspiration; psychological behavior; prospect theory

2017-03-01.

國家自然科學(xué)基金資助項目(71372080，71471087)；國家社會科學(xué)基金資助項目(15BGL056)；山東省社會科學(xué)規(guī)劃研究項目(16CJJJ15).

張笛(1987—)，ORCID： http： //orcid.org/0000-0002-0041-3521，男，博士研究生，主要從事管理決策分析和供應(yīng)鏈管理研究，E-mail： bengbuzhangdi@163.com.

10.3785/j.issn.1008-9497.2017.06.013

C 934

A

1008-9497(2017)06-735-07