考慮屬性關(guān)聯(lián)的兩階段獲勝者確定模型

楊 娜，廖貅武，雷宏振

(1.陜西師范大學國際商學院，陜西 西安 710119；2.西安交通大學管理學院，過程控制與效率工程教育部重點實驗室，陜西 西安 710049)

1 引言

逆向拍賣是一種由買方發(fā)起并主導，多個賣方參與競價的拍賣機制。實踐表明，企業(yè)采用這種方式采購產(chǎn)品和服務不僅可以提升采購效率，還能大幅度降低采購成本。近年來，逆向拍賣日益成為一種重要的采購解決方案。它與正向拍賣最主要的區(qū)別在于其多屬性特征。例如，在運輸服務采購中，托運商不僅根據(jù)運輸價格來選擇承運人，還需考慮及時性、設備的合適性以及業(yè)務的熟悉程度等其他因素。這種多屬性特征引出了一個關(guān)鍵的研究問題——獲勝者確定問題(winner determination problem, WDP)，即如何綜合多個屬性評價投標人的報價。

目前主要的研究思路是采用評分函數(shù)進行打分。Bichler和Kalagnanam[1]以標準的加性價值函數(shù)為評分規(guī)則，研究了多單位采購情形下的獲勝者確定問題，建立了混合整數(shù)規(guī)劃模型篩選獲勝者。Kameshwaran等[2]在此基礎上，將存在交易約束以及投標人成本函數(shù)具有批量折扣特點的單一產(chǎn)品大規(guī)模采購下的報價評價問題歸結(jié)為一個混合整數(shù)優(yōu)化問題，提出采用目標規(guī)劃技術(shù)進行求解。Cheng Chibin[3]將密封多屬性逆向拍賣機制下買方的獲勝者確定問題歸結(jié)為一個多屬性決策問題，并使用TOPSIS方法對投標人的報價進行評價。Ray等[4,5]使用了擬線性評分函數(shù)，研究了中標者實際交付與承諾報價不一致情形下的獲勝者確定問題。王明喜等[6]基于加權(quán)和評分函數(shù)，提出了一種贏者決策方案，并給出了風險中性者和風險規(guī)避者的均衡投標策略。在這些以評分函數(shù)為基礎的研究中，Pham等[7]指出加性效用函數(shù)是目前最為普遍使用的評分函數(shù)。該函數(shù)必須以屬性相互偏好獨立為前提，這在現(xiàn)實中很難滿足。

針對這一不足，已有一些學者進行了改進。Talluri等[8]基于數(shù)據(jù)包絡分析思想提出了一個考慮屬性之間相互關(guān)聯(lián)的價值函數(shù)。但該函數(shù)只能反映部分屬性之間的交互關(guān)系，具有一定的局限性。呼大永等[9]采用數(shù)據(jù)包絡分析中的C2R模型確定最終獲勝供應商，在解決傳統(tǒng)指標體系評價方法中假設屬性不相關(guān)以及人為設定權(quán)重等不足方面做出了有益嘗試。Huang Min等[10]考慮到拍賣屬性之間的沖突性，引入了BOCR框架，并在其中嵌入前景理論刻畫拍賣人的風險規(guī)避行為。所提出的PT-BOCR方法首先采用Choquet積分得到下層的評價值，再使用CCSD方法求解上層模型的權(quán)重，最后綜合二者得到總評價值。劉衛(wèi)鋒等[11]還提出了一種Heronian平均算子來刻畫屬性間的相互作用。在多準則決策領(lǐng)域，除了這些模型和方法，可反映屬性間交互關(guān)系的偏好函數(shù)還有兩類：一類是帶懲罰和獎勵的一般加性效用函數(shù)[12, 13]；另一類是模糊積分，其中建立在k-可加模糊測度上的Choquet積分最為常用。Choquet被廣泛應用于管理領(lǐng)域的現(xiàn)實問題[14-16]。這一類型的偏好函數(shù)在應用上的最大困難是參數(shù)值的獲得。雖然文獻中提出了一些方法，如Marichal熵方法[17]、菱形成對比較法[18]以及序關(guān)系分析法與施密特正交馬田系統(tǒng)相結(jié)合的方法[19]，但這些方法過于強調(diào)理論推演，計算過程復雜，不適合應用于多屬性逆向拍賣的現(xiàn)實問題。

文獻中有一類研究涉及到拍賣人的偏好揭示。它們大都強調(diào)了揭示拍賣人偏好并構(gòu)造恰當?shù)脑u分函數(shù)的重要性[1, 20]。最新的多屬性在線逆向拍賣的綜述性文章[7]還專門將偏好揭示列為一項重要的研究內(nèi)容。于紅巖和劉仲英[21]通過設定多屬性的期望值和保留值作為投標參考點，提出了一種基于拍賣方偏好揭示的多屬性網(wǎng)上拍賣模型。Karakaya和K?ksalan[22]在多輪次的多屬性拍賣框架下提出了一種交互式?jīng)Q策方法，從拍賣人的歷史偏好信息中間接地估計其偏好函數(shù)。拍賣過程中不斷將新的偏好信息加入偏好約束集，從而進一步精確對偏好函數(shù)的估計。Yang Na等[23]進一步擴展了這一研究，設計了交互式偏好引出框架，并提出了相應的偏好揭示方法。這些方法都為獲得拍賣人的偏好函數(shù)進而確定獲勝者提出了新的思路。

本文將從拍賣人偏好揭示的角度構(gòu)造Choquet積分形式的評分函數(shù)。在獲勝者確定方法的選擇上，文獻中有一些學者研究了兩階段拍賣機制[24]，這種方式有利于降低拍賣的復雜性并易于被拍賣人所接受，受到這些研究的啟發(fā)，本文采用一種兩階段的方法確定獲勝者。這一方法首先考慮所有與拍賣人主觀偏好一致的參數(shù)值篩選可能獲勝報價，再以與整體評價結(jié)果最為接近的報價排序為依據(jù)確定穩(wěn)健獲勝報價。該方法的理論貢獻主要反映在：以模糊測度和模糊積分表達拍賣人評價屬性之間的關(guān)聯(lián)性，避免了屬性相互偏好獨立的強假設，擴展了現(xiàn)有研究；以所有與主觀偏好相一致的參數(shù)集表示拍賣人的評分函數(shù)，避免人為選擇的隨意性；側(cè)重分析拍賣人更關(guān)注的潛在獲勝報價，避免分析大量不可能獲勝報價的偏好關(guān)系，提升了評價效率；提出了選擇穩(wěn)健獲勝報價的規(guī)則。

2 問題的提出

多屬性逆向拍賣中，拍賣人的評價屬性集記為G={g1,g2,…,gn}，其中g(shù)i表示第i個屬性。考慮到屬性之間的關(guān)聯(lián)性，引入模糊測度和模糊積分表示拍賣人的偏好。相關(guān)的基本知識[25]介紹如下：

定義1：P(G)表示G的冪集，如果集函數(shù)μ:P(G)→[0,1]滿足以下非負有界性條件和單調(diào)性條件：

(a-1)μ(?)=0，μ(G)=1；

(a-2)?A,B∈P(G)，A?B，有μ(A)≤μ(B)，

則稱μ是G上的模糊測度。

對每個屬性集A?G，μ(A)可理解為A的權(quán)重或重要程度。

定義2：模糊測度μ可由其默比烏斯變換唯一地表示為：

(1)

其中，集函數(shù)m(B)反映出忽略任意gi?B與gj∈B之間的關(guān)聯(lián)時，集合B中屬性之間的關(guān)聯(lián)程度。任意集函數(shù)m：p(G)→不一定對應一個模糊測度的默比烏斯變換形式。根據(jù)條件(a-1)、(a-2)以及式(1)，以下兩個條件保證了m(·)能唯一地確定集合G上的一個模糊測度：

定義3: 如果一個模糊測度μ的默比烏斯變換滿足：對任意A?G，若|A|>k，有m(A)=0，并存在A?G，|A|=k，使得m(A)≠0，則該模糊測度被稱為k-可加模糊測度。

k-可加模糊測度可表示任意復雜度的模糊測度。k值越大，模型表現(xiàn)力越強，但參數(shù)越多。由于現(xiàn)實拍賣問題中三個及三個以上的屬性之間的關(guān)聯(lián)并不多見，本文為簡化建模，采用定義在2-可加模糊測度上的Choquet積分作為拍賣人的評分函數(shù)。該積分由默比烏斯變換表示為[26]：

(2)

其中，b表示投標人的報價，gi(b)表示該報價在屬性gi上的評價值。

圖1 多輪次拍賣流程

3 兩階段獲勝者確定模型

3.1 定義與偏好信息一致的評分函數(shù)

關(guān)聯(lián)程度大于gk和gl之間的關(guān)聯(lián)程度。

根據(jù)拍賣人所提供的偏好信息可推測得到2-可加模糊測度的參數(shù)值。如果由這些估計值所確定的偏好關(guān)系與拍賣人的主觀判斷相吻合，稱這樣的2-可加模糊測度與偏好信息相一致。這樣，所有一致的2-可加模糊測度可由以下約束所定義：

(3)

其中，前三個不等式約束分別表示在拍賣人給出的三種形式的報價比較信息下報價得分所應滿足的條件。δ是拍賣人的無差異閾值，δ≥0。若兩個報價得分值之差低于該閾值，拍賣人不能區(qū)分它們的優(yōu)劣。反之，若拍賣人明確給出優(yōu)于關(guān)系，則得分值之差必然超過該閾值。因此，ε1取略大于δ的數(shù)。第四個不等式反映的是屬于較強偏好強度類的兩個報價的得分差值也較大。屬性權(quán)重滿足第五個約束式，其中Iμ({gi})表示單個屬性gi的相對重要程度。屬性集A(A?G)中各屬性之間的關(guān)聯(lián)程度用I(A)表示。由于文中只考慮屬性兩兩關(guān)聯(lián)，當|A|>2時，I(A)=0。第六至第八個約束式分別表示當屬性之間存在互補性、替代性和相互獨立時關(guān)聯(lián)系數(shù)需滿足的條件，其中ε2是較小的正數(shù)，目的在于保證嚴格不等式成立。第九個約束式對應屬性關(guān)聯(lián)程度比較信息。以上各式中的Cμ(·)和I(·)可由集函數(shù)m(·)表示。根據(jù)Grabisch對關(guān)聯(lián)系數(shù)的定義及該系數(shù)與默比烏斯變換的關(guān)系[27]，單個屬性的相對重要程度以及屬性兩兩關(guān)聯(lián)系數(shù)分別表示為：

(4)

I({gi,gj})=m({gi,gj}),?{gi,gj}?G

(5)

3.2 獲勝者選擇分析

3.2.1 可能獲勝報價

根據(jù)這一定義，建立如下的線性規(guī)劃模型LP1確定備選獲勝報價集。

LP1(bi):Maxyi

(6)

定理1如果bi?Wt-1，必有bi?Wt。

推論1：如果bi?Wt，則對任意k>t，bi?Wk。

該定理表明這種確定獲勝者的方式保證了在某一輪不可能獲勝的報價也不可能在以后各輪中獲勝。因此，每一輪篩選可能獲勝者時只需考慮上一輪的潛在獲勝報價和本輪的新報價，即Wt?(Wt-1∪Bt)。

3.2.2 穩(wěn)健獲勝報價

當存在多個可能獲勝報價時，進一步對這些報價進行分析，選擇其中的穩(wěn)健獲勝者推薦給拍賣人。穩(wěn)健獲勝報價是這樣的一個報價：該報價為獲勝者時其他的可能獲勝報價也排在盡可能靠前的位置；當存在多個這樣的報價使得其他可能獲勝報價排序最靠前時，選擇其中使得所有可能獲勝報價與不可能獲勝報價得分總差值最大的報價。圖2以一個示例說明了挑選穩(wěn)健獲勝者的思路。該例中，報價集合中共有5個報價，其中b2、b3和b5為可能獲勝報價。當b2為獲勝者時，其他兩個可能獲勝報價b3和b5分別排在第4位和第2位；當b3為獲勝者時，b2和b5分別排在第3位和第2位；當b5為獲勝者時，b2和b3可能排在第2、3位，也可能排在第3、4位?？梢?，b3和b5為獲勝者時可保證其他可能獲勝報價排在最靠前的位置(即依次排在第2、3位)。接下來，再考慮二者分別為獲勝者時所有可能獲勝報價與不可能獲勝報價之間的整體得分差異。在示例數(shù)據(jù)下，b5為獲勝者時得分總差值更大，因此選擇b5為穩(wěn)健獲勝者。在這一規(guī)則下，使穩(wěn)健獲勝報價得分最高的評分函數(shù)的評價結(jié)果與所有一致的評分函數(shù)的評價結(jié)果最為接近。在所有可能獲勝報價都有最好的評價時，穩(wěn)健獲勝報價為最優(yōu)中的最優(yōu)。

圖2 穩(wěn)健獲勝報價選擇示意圖

根據(jù)這一思路，建立如下的混合整數(shù)規(guī)劃MIP2挑選穩(wěn)健獲勝者。

bj∈BWt

(7)

(8)

(9)

3.3 獲勝者確定方法的基本步驟

通過上述分析，文中確定獲勝者的基本步驟概括如下。

步驟1：拍賣初始時刻(t=0)，拍賣人提出評價屬性集，以及能反映自身偏好的參考報價信息和相應偏好信息；

步驟2：根據(jù)3.1節(jié)中的方法確定與拍賣人偏好一致的2-可加模糊測度集；

步驟3：檢查拍賣結(jié)束條件是否已滿足。若已滿足，輸出當前獲勝者為最終獲勝者，拍賣結(jié)束；若未滿足，拍賣進入下一輪(t=t+1)；

步驟4：投標人進行投標；

步驟5：利用模型LP1確定本輪的備選獲勝報價集Wt；

4 算例分析

4.1 仿真實驗

某企業(yè)因業(yè)務需求要采購一批臺式機用于日常辦公。其采購部門擬通過一個網(wǎng)上拍賣項目采購這批商用臺式機。根據(jù)企業(yè)的現(xiàn)實應用需求，該部門(即拍賣人)將以四個指標(即屬性)評價供應商(即投標人)提供的臺式機，分別是：價格(g1)、處理器性能(g2)、內(nèi)存容量(g3)和硬盤容量(g4)。拍賣活動正式開始之前，他們考察了市場上部分商用臺式機產(chǎn)品(即參考報價，如表1所示)，并向拍賣網(wǎng)站提交了一些關(guān)于這些臺式機的評價信息(即偏好信息, 如表2所示)表達其采購偏好，期望拍賣網(wǎng)站根據(jù)這些信息篩選出符合其要求的報價。

表1 參考報價信息

注：產(chǎn)品信息來自太平洋電腦網(wǎng)產(chǎn)品報價頻道

表2 采購部門提交的偏好信息

u1(3599)+u2(i34170)+u3(4G)+u4(1000G)>u1(5499)+u2(i74770)+u3(4G)+u4(1000G)

(10)

同時，根據(jù)r6?r1，有：

u1(10499)+u2(i74770)+u3(2G)+u4(500G)>u1(3599)+u2(i34170)+u3(2G)+u4(500G)

(11)

由(10)得到：

u1(3599)+u2(i34170)>u1(5499)

+u2(i74770)

(12)

而由(11)得到：

u1(3599)+u2(i34170)

+u2(i74770)

(13)

根據(jù)邊際價值函數(shù)u1(·)的單調(diào)非遞增性質(zhì)，即價格越高拍賣人的邊際效用越低，有：

u1(10499)≤u1(5499)

(14)

因此不等式(12)和(13)明顯地不一致，這表明拍賣人的偏好信息違反了偏好獨立假設，傳統(tǒng)的加性效用函數(shù)失效。

本例采用Choquet積分表達采購部門的偏好。首先對初始偏好信息進行預處理。以權(quán)威IT產(chǎn)品評測機構(gòu)Pconline發(fā)布的處理器橫向測評結(jié)果為依據(jù)，采取3Dmake Vantage得分值作為處理器性能的評價值。再根據(jù)目前太平洋電腦網(wǎng)所有商用臺式機產(chǎn)品在各屬性上的取值范圍，將參考報價各指標值轉(zhuǎn)換到[0,100]統(tǒng)一標度上，0表示該指標上的最差得分，100表示最好得分。

以下采用仿真實驗進行分析。可能對計算結(jié)果有影響的因素主要包括每次拍賣的輪數(shù)和每輪的報價數(shù)目，為方便表述，分別記為r和b。首先設定每一次采購進行3輪(即r=3)，每一輪參與競價的報價數(shù)目10個(即b=10)。隨機生成各報價在各屬性上的評價值。重復進行100次拍賣(即重復計算100次)，可能獲勝報價的比例如圖3所示。單次運算中最多有36.67%的報價可能獲勝，最少僅有13.33%，100次運算的平均值為21.93%?？刂泼恳惠唴⑴c競價的報價數(shù)目不變(b=10)，拍賣輪數(shù)由1輪增加到10輪，每種實驗設置仍重復執(zhí)行100次，平均可能獲勝報價比例如圖4所示。如圖，可能獲勝報價的比例基本上與拍賣輪數(shù)無關(guān)。在每輪報價數(shù)目為10的規(guī)模下，可能獲勝報價所占的比例在22.14%左右。

圖3 可能獲勝報價比例

圖4 不同拍賣輪數(shù)下平均可能獲勝報價比例

控制每一次拍賣的輪數(shù)為3輪(r=3)，每一輪參與競價的報價數(shù)目發(fā)生變化時，運算執(zhí)行100次的平均可能獲勝報價比例如圖5所示。如圖，可能獲勝報價的比例將隨著報價個數(shù)的增加而遞減。當報價數(shù)目為3時，平均有52.44%的報價為可能獲勝報價，但當報價數(shù)目增加到12個，可能獲勝報價比例降低至18.58%。這與拍賣實踐中的已有經(jīng)驗一致，當報價增多時，意味著供應商之間的競爭增強，將導致具有相對領(lǐng)先優(yōu)勢的報價減少。從圖中還可以看到，這種遞減趨勢在報價數(shù)目持續(xù)增多時減緩，報價數(shù)目分別為10、11和12時，平均的可能獲勝報價比例分別為21.93%、20.12%和18.58%。

圖5 不同報價個數(shù)下平均可能獲勝報價比例

綜上，盡管可能獲勝報價的比例會隨著報價數(shù)目的變化而變化，但整體上，實驗表明大量的報價為不可能獲勝報價。即便在每一輪僅有3個報價的情形下，仍有超過45%的報價不可能獲勝，且隨著報價數(shù)目的增多，不可能獲勝報價的比例持續(xù)增加，當一輪報價增加到10個時，不可能獲勝報價高達80%。這說明本文提出的獲勝者確定方法在第一階段篩選出可能獲勝報價非常必要，而且參與競價的供應商越多，本文的方法越適用。

4.2 方法比較

設置一次拍賣進行3輪(r=3)，且保持相同的初始偏好信息、相同的隨機報價信息和相同的反饋信息。報價數(shù)目在b=3到b=12之間變動時，兩種方法在“可識別比例”和“未知報價比例”兩個指標上的變化情況如表3所示。其中，“可識別比例”指的是在所有100次運算中，TSA可識別出由ROR方法確定的被占優(yōu)報價的平均比例。從表中可以看到，由ROR兩兩比較所確定出的必然被占優(yōu)報價100%地被TSA方法識別為不可能獲勝報價，表明了TSA方法的有效性。此外，ROR方法的兩兩比較分析還可能產(chǎn)生一類“未知報價”，即既不必然優(yōu)于其他報價、也不必然被其他報價占優(yōu)的報價，這類報價無法確定其是否可能獲勝。如表3所示，當一輪中參與競價的報價數(shù)目較少時，未知報價的平均比例較高。因此，整體來說，在計算效果上TSA略優(yōu)于ROR。

表3 不同報價數(shù)目下TSA的可識別比例和ROR的未知報價比例

為比較兩種方法的計算效率，首先設置報價個數(shù)b=10，每次拍賣由1輪增加到10輪時，分別運算100次，兩種方法平均每一輪的運行時間如圖6所示。設置拍賣輪數(shù)r=3，報價數(shù)目由3個增加到12個時，同樣執(zhí)行運算100次，平均每一輪的運行時間如圖7所示。可以看到，在r和b變化時，兩種方法的運行時間變化呈現(xiàn)相似的規(guī)律。首先，TSA和ROR方法的平均運行時間都隨著r和b的增加而增大。這是因為，當拍賣輪數(shù)增加時，各輪要處理的反饋信息增多；當報價數(shù)目增多時，每一輪的計算量增加。雖然兩種方法都呈現(xiàn)出遞增趨勢，但在相同的問題規(guī)模下，TSA花費的時間代價總是比ROR小。尤其是當拍賣輪數(shù)和報價數(shù)目較大時，TSA在計算效率上的優(yōu)勢更為明顯。

圖6 拍賣輪數(shù)變化時平均每輪運行時間

圖7 報價數(shù)目變化時平均每輪運行時間

綜上，無論是在計算效果還是計算效率上，本文方法均優(yōu)于Angilella等的方法。通過仿真實驗，表明了本文方法更適用于拍賣輪數(shù)較多、報價規(guī)模較大的拍賣項目。

5 結(jié)語

多屬性逆向拍賣日益廣泛地應用在采購活動中，其中的關(guān)鍵問題是獲勝者確定問題。目前主要的方法是采用評分函數(shù)進行打分，但是現(xiàn)有研究假設屬性不相關(guān)，具有局限性。本文根據(jù)模糊測度和模糊積分理論，提出了一種考慮屬性兩兩關(guān)聯(lián)的獲勝者確定方法。由于參數(shù)值眾多且拍賣人難以直接提供，文中從拍賣人提供的偏好信息中推測Choquet積分形式的評分函數(shù)。與偏好信息一致的評分函數(shù)可能不唯一，不同的評分函數(shù)可能導致不同的決策結(jié)果，因此文中考慮了所有一致的評分函數(shù)集確定獲勝者。首先根據(jù)拍賣人的主觀偏好定義了與其一致的2-可加模糊測度集，其次根據(jù)該評分函數(shù)集合挑選出備選獲勝報價集，最后以與所有一致評分函數(shù)的評價結(jié)果最為接近的報價排序為依據(jù)，選出得分最高者作為穩(wěn)健獲勝報價推薦給拍賣人。拍賣人確認最終獲勝者，產(chǎn)生的反饋信息進入下一輪的偏好信息集，進一步精確方法的推薦結(jié)果。

經(jīng)過隨機數(shù)據(jù)驗證，拍賣中不可能獲勝報價的比例遠高于可能獲勝報價比例，且隨著供應商競價增多呈增長趨勢，因此在第一階段篩選出少量的可能獲勝報價非常重要。與Angilella等提出的方法進行比較發(fā)現(xiàn)，文中方法可將全部的必然被占優(yōu)報價識別為不可能獲勝報價，且Angilella等的方法總會存在一小部分的報價無法確知其是否可能獲勝，因此在計算效果上本文方法略優(yōu)。從運算效率上，在相同的問題規(guī)模下文中方法花費的時間更短，且隨著拍賣輪數(shù)和報價數(shù)目的增多，該方法的優(yōu)勢更為明顯。