基于交叉效率和合作博弈的決策單元排序方法

劉文麗, 王應明 , 呂書龍

(1. 福州大學經濟與管理學院，福建 福州 350116; 2. 福州大學數學與計算機科學學院，福建 福州 350116)

1 引言

數據包絡分析(Data envelopment analysis，簡稱DEA)是用來對一組具有多投入和多產出的決策單元(decision making units，簡稱DMUs)進行效率評價的一種非參數方法。1978年Charnes等[1]提出了CCR模型，并給出CCR效率的概念，實現了對決策單元有效性的評價。CCR效率雖然很好地將決策單元分為了CCR有效單元和無效單元，但在一組決策單元中往往會存在多個CCR有效單元，因此CCR效率通常不能對所有決策單元進行完全排序。 Sexton等[2]進一步實現了交叉效率評價，即在實現某個決策單元CCR效率的同時，用其投入和產出變量的權重計算它對其它決策單元的交叉效率評價，從而利用平均交叉效率得分對所有決策單元進行排序。由于交叉效率評價綜合考慮了決策單元的自我評價與相互之間的同行評價，其公正合理性使得該方法被廣泛應用，例如應用在R&D項目選擇[3]、柔性制造系統的選擇[4]、奧運會中參賽國的效率評價[5]等方面。

由于CCR模型最優解解的不唯一，從而導致了交叉效率可能被隨意產生。因此，許多學者提出了不同的二次目標模型來確定投入產出變量的權重。例如1994年Doyle和Green[6]提出的仁慈型和對抗型模型，即在保持決策單元的效率為CCR效率時使剩余決策單元聯合起來得到的效率達到最大或最小來求解權重。另外，1995年Doyle和Green[7]再次提出四組二次目標模型，其中較為特別的是為每一個其它決策單元實施針對性的仁慈型和對抗型模型。Liang Liang等[8]以減小交叉效率評價與其CCR效率的偏差為目標實現了三個二次目標模型。進一步地，Liang Liang等[9]又提出了博弈交叉效率模型，并以迭代算法實現了一個穩定的博弈交叉效率評價。Wang Yingming和Chin[10]并不考慮二次目標模型對其他決策單元的影響，給出了一個中立模型，即在保持每個決策單元CCR效率的同時盡可能地提高每一個產出變量單獨的效率。李春好等[11]提出了一種基于理想決策單元參照的交叉評價求解策略，并也給出了對應的交叉效率評價模型。

近些年來，許多學者研究對交叉效率矩陣進行深入分析與整合，并進一步改進原有的平均交叉效率得分。例如Wang Yingming等[12]考慮決策人的樂觀狀態并利用順序加權平均算子[13]對交叉效率矩陣進行整合計算。Yang Feng等[14]基于對抗型和仁慈型交叉效率評價模型得到區間交叉效率矩陣，并利用隨機多準則可接受分析[15]求解每個決策單元的可接受性指標并排序決策單元。Wu Jie等[16-17]利用合作博弈中的核仁理論及信息熵對交叉效率矩陣進行加權平均。另外，Wang Yingming等[18]也提出了三種方法來確定各決策單元在交叉效率矩陣中的重要性從而實施加權交叉效率評價。進一步地，張啟平等[19]應用自適應群評價方法，同步迭代調整各決策單元在整合交叉效率矩陣時的權重以及決策單元用來評價其他決策單元的投入產出指標的權重，從而得到一種穩定的評價結果。

在交叉效率評價中，大量的二次目標模型已被提出，然而如何選擇二次目標模型卻少有文獻研究。本文將考慮用合作博弈的方法來研究交叉效率評價中的二次目標模型的選取，并利用Shapley值[20]分配各決策單元的收益并對決策單元進行評價排序，最后通過數值實例中驗證了合作博弈與交叉效率相結合的評價方法的合理性。

2 DEA 交叉效率評價

假設有n個待評價的決策單元DMUk(k=1,2,…,n)，每個決策單元分別有m個投入變量和s個產出變量，即x1k,x2k,…,xmk，y1k,y2k,…,ysk,k=1,2,…,n。對于DMUk，其CCR效率可通過下面CCR模型[1]求解:

(1)

其中v1k,v2k,…,vmk與u1k,u2k,…,usk分別代表投入與產出變量對應的權重。若Ekk=1，則DMUk被稱為CCR有效，否則DMUk為CCR無效決策單元。

(2)

對于k=1,2,…,n,分別求解模型(1)，每個決策單元將得到一個CCR效率與n-1個交叉效率，從而得到交叉效率矩陣:

(3)

其中第k行效率值為DMUk對所有決策單元的效率評價，而第j列元素為所有決策單元對DMUj的交叉效率評價。對交叉效率矩陣每列元素求平均，于是得到各決策單元的平均交叉效率得分:

(4)

由于交叉效率評價在考慮各決策單元的自我評價即CCR效率的同時，又綜合分析了所有決策單元之間的相互評價，具有一定的公平與綜合性，因此交叉效率評價方法被廣泛地應用于評價決策問題。然而，當DMUk是CCR有效決策單元時，模型(1)的通常存在多組最優解，則計算得到的交叉效率以及平均交叉效率得分具有不唯一性。為了防止交叉效率被任意產生，許多學者提出二次目標模型來唯一確定投入產出的權重變量。例如Doyle和Green[7]從仁慈型和對抗型兩種不同策略各提出了四種二次目標模型，其中一種針對單個決策單元的仁慈型二次目標模型如下：

(5)

(6)

(7)

(8)

3 基于Shapley值的交叉效率排序方法

下面用合作博弈方法來考慮交叉效率評價中的二次目標模型選取問題。若所有決策單元都不結盟，從自私自利的角度，每個決策單元在保證自我評價是CCR效率的情況下，通常會選擇對抗型二次目標模型給每個其它決策單元實施盡可能低的評價。為了得到更高的交叉效率評價，決策單元相互結盟，并選擇仁慈型二次目標模型對同在聯盟內的決策單元進行交叉效率評價。具體地，假設n個決策單元在進行交叉效率評價時達成協議參與如下博弈：

定義1n個決策單元組成參與者集合N={1,2,…,n}，對于集合N的任一子集S，定義聯盟S對應的特征函數為：

(9)

其中

(10)

在交叉效率評價中，DMUj對應的平均交叉效率得分反映了所有決策單元對它的綜合評價，也影響著它在所有決策單元中的排序位置。因此，我們定義合作博弈(N,v)中聯盟S得到的收益是該聯盟內的所有參與者的平均交叉效率得分總和。為了追求該聯盟更大的收益和突出的地位，聯盟S內的任一個決策單元將會對同在該聯盟內的每個其它決策單元進行盡可能高的交叉效率評價，于是選擇仁慈型模型。相反，對于未結盟的決策單元選擇對抗型模型進行盡可能低的交叉效率評價。反過來，對于聯盟S內的DMUj, 將得到同屬于該聯盟的每一個決策單元所作的最大交叉效率評價以及不在該聯盟內的決策單元實施的最小交叉效率評價，于是聯盟S內的DMUj得到的平均交叉效率得分如式(10)。

性質1 對于任意S1,S2?N,S1∩S2=Φ,有

v(S1∪S2)≥v(S1)+v(S2)

證明：由定義1， 我們有：

(11)

由于S1∩S2=Φ，則式(11)可表示為：

因此，v(S1∪S2)≥v(S1)+v(S2)。

性質1意味著定義1中的特征函數v具有超可加性，因此每個決策單元都愿意結盟以期獲得更高的收益。另外由性質1易得到：

對于所有參與者在合作后收益如何分配，通常有多種不同的解，如核心、核子、穩定集和Shapley值等，其中Shapley值是滿足有效性公理、對稱性公理、合理性公理和可加性公理的唯一解，它表現為參與者在合作博弈中的平均貢獻。自1953年Shapley值[20]被提出來后，它已成為了合作博弈中最常使用的一種收益分配方式。現在我們也將計算每一個參與者的Shapley值，由此來分配各決策單元在合作博弈(N,v)中的收益，其中DMUk(k∈{1,2,…,n})的 Shapely值為：

(12)

正如前所述，每個決策單元以最小平均交叉效率得分作為相互不合作時各自的收益，大聯盟形成后的共同收益是所有決策單元最大平均交叉效率得分總和，而部分決策單元形成聯盟時的共同收益同時考慮了最小交叉效率評價和最大交叉效率評價。因此該合作博弈(N,v)兼顧了最小交叉效率和最大交叉效率兩種評價方式。另外，Shapley值是決策單元在合作博弈(N,v)的平均貢獻，也即是合作后各決策單元應得到的收益。綜合而言，基于Shapley值排序決策單元是綜合考慮了最小、最大交叉效率評價以及合作博弈的一種合理分配收益的排序方法。

考慮n個決策單元進行定義1中的合作博弈，下面定理給出了該合作博弈中各決策單元Shapley值的簡化結果。

定理1對于定義1中的合作博弈(N,v)， DMUk(k∈{1,2,…,n})的Shapley值為:

(13)

證明：對于DMUk，考慮包含它的聯盟S，即滿足k∈S，由定義1有:

因此DMUk在聯盟S中的貢獻為:

(14)

由式(10)，有:

且對于j∈S-{k}有:

則式(14)可化簡為:

v(S)-v(S-{k})=

將上式代入式(12)，則有:

將上式整理成如下形式：

φk(v)=a·Ekk+

(15)

其中

(16)

(17)

(18)

(19)

(20)

(21)

將式(19)、(20)和(21)代入式(15)中可得:

4 實例分析

下面我們對含有兩個投入變量四個產出變量的12個柔性制造系統[4]進行評價與排序，其中投入變量分別是年度經營折舊成本和各系統所需的占地空間大小；四個產出變量測量的是各系統分別在質量效益、WIP、平均誤工和平均產量上的改進。具體數據見表1。

表2展示了這12個決策單元的CCR效率、兩種平均交叉效率得分、本文合作博弈的Shapley值，另外也給出了Shang和Sueyoshi[4]基于權重約束DEA方法[21]評價的結果。在表2中，CCR效率不能很好地完全排序所有決策單元，因為有7個決策單元的CCR效率為最大值1。在文獻4中，Shang和Sueyoshi[4]基于AHP方法得到各投入產出變量相對重要性的區間范圍，并應用權重約束DEA方法[21]評價了這12個決策單元的效率，然而DMU5和DMU7的效率都依然是最大值1，依然無法完全排序，另外比較異常的是DMU9的效率評價結果是0.1148，這個效率值與其CCR效率值1相比，變化幅度太大。并且DMU9的最小評價交叉效率都達到了0.4852，可見Shang和Sueyoshi[4]采用的權重約束方法對DMU9過于苛刻，有失公允。

表1 12個柔性制造系統的數據

由于交叉效率評價方法在排序決策單元方面的突出能力，故我們基于交叉效率評價方法來排序這12個柔性制造系統。表2中的最右三列是最小平均交叉效率得分、最大平均交叉效率得分和基于交叉效率與合作博弈計算得到的Shapley值。明顯地，每個決策單元的Shapley值均大于其最小平均交叉效率。特別地，DMU3、DMU8、DMU10、DMU11和DMU12這五個決策單元的Shapley值恰是最小平均交叉效率和最大平均交叉效率的平均值。以DMU3為例，其Shapley值是0.8537，正是它的最小平均交叉效率0.7703和最大平均交叉效率0.9371的平均值。事實上，這五個決策單元的CCR效率均小于1，即它們都是CCR 無效決策單元。由于CCR無效決策單元對應的CCR模型通常存在唯一解，因此每個CCR無效決策單元對任意決策單元的最大交叉效率評價和最小交叉效率評價是相同的。根據定理1，這5個CCR無效決策單元的Shapley值將退化為最小平均交叉效率和最大平均交叉效率的平均值。相反，另外7個CCR有效決策單元的Shapley值均大于其最小平均交叉效率和最大平均交叉效率的平均值，甚至很多決策單元的Shapley值還超過了最大平均交叉效率。特別地，在12個決策單元中DMU5的Shapley值最大，同時我們也看到最小交叉效率評價和Shang和Sueyoshi[4]也都將DMU5排在了效率最高的位置。相反，DMU12的Shapley值是所有決策單元中最小的，這與在CCR效率和最大平均交叉效率中的排序位置也是一致的。另外注意到這12個決策單元的Shapley值之和與最大平均交叉效率之和是完全相同的，即Shapley值完全地分配了所有決策單元聯盟的總收益。但Shapley值不同于最大平均交叉效率得分，而是基于合作博弈中各決策單元的平均貢獻來進行評價。

為了綜合比較表2中各種評價方法對12個決策單元排序的相似度，我們計算了各種效率評價結果的秩相關系數，見表3。從表3第一行可以看到，與兩種交叉效率和Shang和Sueyoshi[4]評價相比，Shapley值與CCR效率的評價結果最相似，即秩相關系數達到0.8500。表3第五行顯示的是12個決策單元合作博弈的Shapley值與其他四種效率評價的秩相關系數。顯然合作博弈的Shapley值與其他四種效率評價都很相似，其中合作博弈的Shapley值與Shang和Sueyoshi[4]評價的最相似。另外可以看到對抗型和仁慈型兩種不同策略得到的平均交叉效率排序的秩相關系數只有0.7413。而合作博弈的Shapley值與這兩者平均交叉效率評價的秩相關系數都較高，分別是0.8531和0.8461。可見Shapley值綜合考慮了最小交叉效率和最大交叉效率兩種評價，用它排序決策單元具有一定的綜合性與合理性。

表2 12個柔性制造系統的評價結果

表3 五種評價的秩相關系數

5 結語

傳統的交叉效率評價是基于CCR模型與二次目標模型實現決策單元之間的自我評價與相互評價，并利用平均交叉效率得分對決策單元進行排序。本文基于Doyle和Green[7]提出的對抗型和仁慈型兩個交叉效率模型，用合作博弈的方法來研究這兩個模型的選取，即對于聯盟內的決策單元，相互之間用仁慈型模型進行最大交叉效率評價，而對于聯盟外的決策單元采用對抗型模型實現最小交叉效率評價。最后利用該合作博弈的 Shapley值即每個決策單元在該合作博弈中的平均貢獻對決策單元進行排序。經證明，該合作博弈中的Shapley值可化簡為最大交叉效率評價和最小交叉效率評價的一個綜合結果。在實例分析中，我們看到Shapley值在最小平均交叉效率評價的基礎上對最大平均交叉效率總和進行了重新合理分配，且Shapley值完全排序了所有決策單元，評價排序結果與其它四種方法也均有較高的秩相關系數，具有公平合理性與一定的綜合能力。

參考文獻：

[1] Charnes A, Cooper W W, Rhodes E. Measuring efficiency of decision making units [J]. European Journal of Operational Research, 1978, 2(6): 429-444.

[2] Sexton T S, Silkman R H, Hogan A J. Data envelopment analysis: Critique and extensions [J]. New Directions for Program Evaluation, 1986, 1986(32): 73-105.

[3] Oral M, Kettani O, Lang P. A methodology for collective evaluation and selection of industrial R&D projects [J]. Management Science, 1991, 37(7): 871-885.

[4] Shang J, Sueyoshi T. A unified framework for the selection of flexible manufacturing system [J]. European Journal of Operational Research, 1995, 85(2): 297-315.

[5] Wu Jie, Liang Liang, Chen Yao. DEA game cross-efficiency approach to Olympic rankings [J]. Omega, 2009, 37(4): 909-918.

[6] Doyle J, Green R. Efficiency and cross efficiency in DEA: Derivations, meaning and the uses [J]. The Journal of the Operational Research Society, 1994, 45(5): 567-578.

[7] Doyle J, Green R. Cross-evaluation in DEA: Improving discrimination among DMUs [J]. INFOR: Information Systems and Operational, 1995, 33(3): 205-222.

[8] Liang Liang, Wu Jie, Cook W D, et al. Alternative secondary goals in DEA cross-efficiency evaluation [J]. International Journal of Production Economics, 2008, 113(2): 1025-1030.

[9] Liang Liang, Wu Jie, Cook W D, et al. The DEA game cross efficiency model and its Nash Equilibrium [J]. Operations Research, 2008, 56(5): 1278-1288.

[10] Wang Yingming, Chin K S. A neutral DEA model for cross-efficiency evaluation and its extension [J]. Expert Systems with Applications, 2010, 37(5): 3666-3675.

[11] 李春好, 蘇航, 佟軼杰, 孫永河基于理想決策單元參照求解策略的DEA交叉效率評價模型[J]. 中國管理科學, 2015, 23(2): 116-122.

[12] Wang Yingming, Chin K S. The use of OWA operator weights for cross-efficiency aggrega-tion [J]. Omega: 2011, 39(5): 493-503.

[13] Yager R R. On ordered weighted averaging aggregation operators in multicriteria decision making [J]. IEEE Transactions on Systems Man and Cybernetics, 1988, 18(1): 183-190.

[14] Yang Feng, Ang Sheng, Xia Qiong, et al. Ranking DMUs by using interval DEA cross efficiency matrix with acceptability analysis [J]. European Journal of Operatio-nal Research, 2012, 223(2): 483-488.

[15] Lahdelma R, Salminen P. SMAA-2: Stochastic multicriteria acceptability analysis for group decision making [J]. Operations Research, 2001, 49(3): 444-454.

[16] 吳杰, 梁樑, 查迎春. 基于核子解的最終交叉效率權系數確定方法 [J]. 系統工程理論與實踐, 2008, 28(5): 92-97.

[17] Wu Jie, Sun Jiasen, Liang Liang, et al. Determination of weights for ultimate cross efficiency using Shannon entropy[J]. Expert Systems with Applications, 2011, 38(5): 5162-5165.

[18] Wang Yingming, Wang S. Approaches to determining the relative importance weights for cross-efficiency aggregation in data envelopment analysis [J]. Journal of the Operational Research Society, 2013, 64(1): 60-69.

[19] 張啟平, 劉業政, 姜元春. 決策單元交叉效率的自適應群評價方法 [J]. 中國管理科學, 2014, 22(11): 62-71.

[20] Shapley LS. A value for n-person games[M]//Kuhn H W, Tucker A W. Contributions to the Theory of Games, Princeton University Press, Princeton, NJ, 1953.

[21] Wong Y H, Beasley J E. Restricting weight flexibility in Data Envelopment Analysis [J]. Journal of the Operational Research Society, 1990, 41(9): 829-835.