多ａｇｅｎｔ兩階段多屬性協(xié)商模型

(1.北京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院， 北京 100124；2. 哈爾濱工業(yè)大學(xué) 管理學(xué)院， 哈爾濱 150001)

摘 要：多議題模型中，在議題的評(píng)價(jià)機(jī)制上買賣雙方大多采用多屬性效用理論或其變形理論，如距離函數(shù)等。提出了多屬性效用理論實(shí)際應(yīng)用中的悖論問(wèn)題，分析了造成理論應(yīng)用偏差的原因和B2C領(lǐng)域電子商務(wù)活動(dòng)交易的特點(diǎn)，進(jìn)而提出了一個(gè)協(xié)商拍賣模型。該模型分兩個(gè)階段來(lái)進(jìn)行，提高了協(xié)商效率，而且允許賣方體現(xiàn)商品的特色，差異化自己的商品。

關(guān)鍵詞：多代理;多議題;多屬性效用理論;兩階段協(xié)商

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)02057304



Two stage negotiation model for multiissue between multiagent 

WANG Ying1，JIANG Guorui1，HUANG Tiyun1，2

(1.School of Economics Management， Beijing University of Technology， Beijing 100124， China；2.School of Management， Harbin Institute of Technology， Harbin 150001， China)Abstract:MAUT(multiattribute utility theory) or the derived theory from it is mostly used as the evaluation method in the multiissue model， such as distance function.This paper presented a paradox using MAUT in the practical application， analysed the reason to introduce this paradox and the character of the electronic business activity in the B2C field， so presented a negotiation auction model. This model could be divided into two stages to improve the negotiation efficiency and permitted the seller to discriminate their products in order to reflect the product itself.

Key words:multiagent; multiissue; multiattribute utility theory(MAUT); two stage negotiation 

0 引言

本文從買方角度入手研究B2C領(lǐng)域一對(duì)多的多議題協(xié)商談判。協(xié)商是兩方或多方之間在價(jià)格或其他交易款項(xiàng)上達(dá)成一致以便達(dá)到雙贏。一對(duì)多問(wèn)題協(xié)商談判已有不少研究成果，專家學(xué)者們提出了各種解決方案。許多相關(guān)研究[1，2]采用了進(jìn)化方法尋找效用空間中的最優(yōu)解;有的學(xué)者將多議題協(xié)商問(wèn)題轉(zhuǎn)換成多目標(biāo)問(wèn)題來(lái)解決，提出了多目標(biāo)談判模型[3]；有的專家學(xué)者把多個(gè)議題分開(kāi)來(lái)談，形成了多階段談判模型[4]；還有學(xué)者采用并行談判來(lái)解決多議題多方談判的問(wèn)題[5]。文獻(xiàn)[6]中提出了基于加權(quán)近似的選擇方法來(lái)簡(jiǎn)化議題的效用空間，此方法適用于議題相關(guān)的情況。

很多研究[2，7，8，9]使用多屬性效用理論或其變型理論（距離函數(shù)等）[10]作為解決多議題協(xié)商的決策機(jī)制。多屬性效用理論（MAUT）是一種涉及到基于不確定性和偏好分析的多個(gè)不相關(guān)目標(biāo)的決策工具[11]。MAUT是由效用理論發(fā)展而來(lái)的， 它的基本原理是綜合評(píng)分， 分?jǐn)?shù)高低反映決策者對(duì)決策目標(biāo)的滿意程度。自從Bichler第一個(gè)將權(quán)重的概念引入多屬性拍賣決策模型中以后，絕大多數(shù)的模型研究者都在決策模型中使用權(quán)重，也就為多屬性效用的使用提供了方便。但是在實(shí)踐中，這種方法會(huì)產(chǎn)生很大的偏差，其最大的問(wèn)題是出現(xiàn)多屬性效用悖論。下面舉例說(shuō)明。

表1是消費(fèi)者購(gòu)買筆記本電腦時(shí)賣方agent提供的信息。從表中可以看出，需要談判的議題為價(jià)格、保質(zhì)期和交貨期。議題權(quán)重值為[0.6，0.3，0.1]。

對(duì)各個(gè)要素統(tǒng)一量綱和數(shù)量級(jí)以及歸一化（成本和收益按不同標(biāo)準(zhǔn)核算），如表2所示。

表1 賣方產(chǎn)品信息表

agent價(jià)格/元保質(zhì)期/年交貨期/天

16 50023

27 00022

37 50021

表2 賣方產(chǎn)品信息歸一化表

agent價(jià)格保質(zhì)期交貨期

10.360.330.18

20.320.330.27

30.310.330.55

采用多屬性效用函數(shù)計(jì)算公式計(jì)算：

EU=3i=1Vji×ρi（1）

其中：i表示議題；j表示agent；ρ為議題的權(quán)重。利用式（1）得到計(jì)算結(jié)果：[0.333，0.318，0.34]。

筆者發(fā)現(xiàn)一個(gè)有悖于想像的結(jié)果：agent3對(duì)應(yīng)的產(chǎn)品效用比agent1高。盡管價(jià)格很重要，賦予它很大的權(quán)重，而交貨期并不重要，則權(quán)重值也很小，0.6與0.1的差距也能體現(xiàn)出它們重要程度的區(qū)別，但按照式(1)的計(jì)算結(jié)果得出1 000元的差價(jià)比不上交貨期推遲兩天重要。現(xiàn)實(shí)中的情況結(jié)論卻恰好相反。事實(shí)上，真正的緣由是簡(jiǎn)化了多屬性效用理論。出于效率的考慮，本文沒(méi)有為每個(gè)議題的各個(gè)取值給定它們真實(shí)的效用值，而是直接使用實(shí)際的數(shù)值計(jì)算，這樣也就相當(dāng)于假定效用值與議題值成正比，而真實(shí)的情況卻是呈現(xiàn)曲線變化。直接或間接議題值的計(jì)算大都存在同樣的悖論。比如，按照文獻(xiàn)[8]中多效用的計(jì)算方法，只要 ΔIi/ρi（第i個(gè)議題的差值與權(quán)重的商）與ΔIj/ρj（第j個(gè)議題的差值與權(quán)重的商）不一致，類似的悖論依然會(huì)出現(xiàn)。

多屬性效用悖論問(wèn)題促使人們更深入地分析電子商務(wù)活動(dòng)本身，尤其是B2C領(lǐng)域。下面主要從時(shí)間成本和信息可知度兩個(gè)方面來(lái)比較買賣雙方的行為特點(diǎn)。

從時(shí)間成本上講，買賣雙方是不對(duì)等的，B2C領(lǐng)域買賣雙方為1:n的協(xié)商。就同一種商品而言，假設(shè)買賣雙方為協(xié)商準(zhǔn)備的時(shí)間分別為Tb與Ts，買方買1件產(chǎn)品，而賣方賣n件產(chǎn)品，則買賣雙方相對(duì)于同一商品而言，準(zhǔn)備時(shí)間之比為Tb:Ts/n。上面的悖論問(wèn)題也正是因?yàn)闇?zhǔn)備時(shí)間的原因才用議題值來(lái)代替效用值。一個(gè)好的協(xié)商模型應(yīng)該簡(jiǎn)化買方的協(xié)商準(zhǔn)備時(shí)間，而讓賣方有更多的時(shí)間來(lái)差異化自己的商品。

從信息可知度的角度上講，B2C領(lǐng)域買賣雙方的關(guān)系類似于現(xiàn)實(shí)世界，消費(fèi)者對(duì)商品價(jià)值的判斷取決于消費(fèi)者的比較和自己感知上的滿意度，而對(duì)商品具體的信息不很清楚。現(xiàn)實(shí)生活中大多情形都是賣方定價(jià)，因?yàn)樗麄儷@悉更多的商品信息，可以從成本上來(lái)衡量。也正因如此，很難讓消費(fèi)者為每個(gè)議題值設(shè)定它的效用值。



綜觀以上的論述，基于多屬性效用悖論這一難題，本文提出兩階段多屬性協(xié)商模型來(lái)優(yōu)化一對(duì)多多議題談判問(wèn)題。

1 兩階段協(xié)商模型

定義1 議題重要度。談判議題在所有議題中的比重用η表示，其中η∈(0，1]。

定義2 關(guān)鍵議題。當(dāng)單個(gè)議題重要度η≥0.6時(shí)，該議題被稱為關(guān)鍵議題。

定義3 關(guān)鍵議題組合。當(dāng)所有要談判議題中沒(méi)有關(guān)鍵議題，按照議題重要度排序，從第一個(gè)議題開(kāi)始，將議題重要度相加，當(dāng)議題重要度的加和首次大于等于0.6時(shí)，則參與運(yùn)算的所有議題組成關(guān)鍵議題組合。

1.1 模型描述

兩階段談判模型議題定義為八元組{A，I，ρ，Ω，T，S，P，AC｝。其中:A表示協(xié)商參與的agent；I表示談判議題；ρ是議題重要度；Ω表示協(xié)商議題值的取值范圍空間；T是談判時(shí)間點(diǎn)的集合；S表示談判策略；P表示協(xié)商協(xié)議；AC={proposal，reproposal， accept， reject， terminate， deal}表示參與談判的agent的行為原子集合（其中：proposal 表示向?qū)κ痔岢鲆粋€(gè)報(bào)價(jià)；reproposal表示拒絕接受對(duì)手的報(bào)價(jià)后向其提出一個(gè)新報(bào)價(jià)；accept表示談判者一方接受另一方的提議，此時(shí)如果提議方也滿意可以deal；reject表示談判的一方不接受另一方的提議，期待對(duì)方新的提議； terminate表示agent中止談判；deal表示雙方進(jìn)行交易。

1.2 協(xié)商議程

文獻(xiàn)[12]把協(xié)商議程分為分散、同時(shí)、順序三類。分散議程是指協(xié)商的多個(gè)問(wèn)題分開(kāi)同時(shí)協(xié)商(可以看做n個(gè)序?qū)Γ總€(gè)序?qū)Υ硪粋€(gè)問(wèn)題，每次提出的協(xié)商提議都是一個(gè)序?qū)?；同時(shí)是指多個(gè)問(wèn)題同時(shí)協(xié)商(把兩個(gè)問(wèn)題看做一個(gè)整體)；順序協(xié)商是指n個(gè)問(wèn)題一個(gè)接一個(gè)地順序協(xié)商，也就是分布協(xié)商。對(duì)于多議題協(xié)商， Fatima等人[13]已經(jīng)證明了順序?qū)崿F(xiàn)方式的協(xié)商結(jié)果不會(huì)比同時(shí)協(xié)商的結(jié)果差。

兩階段多屬性協(xié)商模型是基于以下原則：第一階段協(xié)商關(guān)鍵議題或關(guān)鍵議題組合，得到買方滿意解集；第二階段按照議題重要度從小到大的順序排序，以淘汰的賣方agent數(shù)為評(píng)價(jià)標(biāo)準(zhǔn)逐個(gè)議題反向拍賣，直到最后達(dá)成一致協(xié)議。圖1描繪了協(xié)商過(guò)程。

a）選取關(guān)鍵議題或關(guān)鍵議題組合。

b）按照系統(tǒng)的定義初始化所有議題的值。

c）第一階段協(xié)商開(kāi)始，如果協(xié)商的是關(guān)鍵議題，問(wèn)題也就轉(zhuǎn)換為單議題協(xié)商；否則，關(guān)鍵議題組合中的多個(gè)議題同時(shí)協(xié)商。

d）第一階段協(xié)商結(jié)束，得到第一階段協(xié)商滿意解集和最終提議值。

e）第二階段協(xié)商開(kāi)始，初始化第二階段拍賣向量。

f）按照議題重要度升序的順序逐個(gè)議題反向拍賣，直到最終達(dá)成協(xié)議。

2 第一階段協(xié)商

2.1 第一階段提議初始值

提議初始值是協(xié)商關(guān)鍵議題時(shí)，系統(tǒng)對(duì)所有議題設(shè)定的初始值，由兩部分組成：關(guān)鍵議題的值或關(guān)鍵議題組合向量；所有非關(guān)鍵議題的值。關(guān)鍵議題的初始值是其最優(yōu)值，為兩個(gè)邊界值中的一個(gè)，如果議題是成本型的，選邊界值小的量作為其初始值。關(guān)鍵議題組合的初始向量選取類似于關(guān)鍵議題值的選取，它是組合中各個(gè)議題最優(yōu)值組合而成的向量。

對(duì)于非關(guān)鍵議題，系統(tǒng)會(huì)按照以下方法為每個(gè)議題生成一個(gè)初始值。如果議題的取值區(qū)間為[a，b]，η為談判議題重要度。如果議題是收益類議題，當(dāng)議題值為連續(xù)型時(shí)，初始值λ0=η(b-a)2+a，當(dāng)議題值為離散型時(shí)，λ0=[η(b-a)2+a];如果議題是成本類議題，當(dāng)議題值為連續(xù)型時(shí)，λ0=b-η(b-a)2，當(dāng)議題值為離散型時(shí)，初始值λ0=[b-η(b-a)2]+1。所有議題的初始值構(gòu)成提議初始值。

2.2 決策判斷函數(shù)

對(duì)于多議題協(xié)商，不像單議題協(xié)商時(shí)只是找到最優(yōu)解時(shí)的單個(gè)賣方agent，而是求解出一個(gè)多個(gè)賣方agent的集合。求解的依據(jù)是決策判斷函數(shù)，本文沒(méi)有采用MAUT理論作為評(píng)判的依據(jù)，而是以協(xié)商滿意解集中agent的數(shù)量和提議議題值與首次收到賣方agent的accept回答時(shí)議題值的偏差作為判斷標(biāo)準(zhǔn)。

以下的討論中均假定議題類型為收益類類型。

假設(shè)初始談判時(shí)賣方agent的個(gè)數(shù)為n，當(dāng)前的agent數(shù)量為m，議題i的取值為[ai，bi]；對(duì)于關(guān)鍵議題i，假定首次收到賣方agent的accept答復(fù)時(shí)買方agent的協(xié)商提議值為i0，當(dāng)前的提議值為i′，對(duì)于關(guān)鍵議題組合I，假定首次收到賣方accept回復(fù)時(shí)提議向量為I0={i01，i02，…，i0k}，k為組合中議題的數(shù)目，當(dāng)前的提議向量為I′={i′1，i′2，…，i′k}。

n0為系統(tǒng)設(shè)定的agent數(shù)量參考標(biāo)準(zhǔn)，其中

2.3 第一階段協(xié)商算法

a）買方agent將提議初始值發(fā)送給所有賣方agent。

b）賣方agent接到買方agent的提議值后，根據(jù)自己的約束條件檢查買方的提議是否在自己可接受的范圍內(nèi)，如果在提議的范圍內(nèi)，則發(fā)送accept；否則發(fā)送reject轉(zhuǎn)入下一輪協(xié)商。

c）如果買方agent沒(méi)有收到任何賣方agent的accept回答，則改變自己的提議值或提議向量，重新發(fā)送給賣方agent。

d）買方agent首次收到賣方agent的答復(fù)時(shí)，記錄此時(shí)的協(xié)商議題值i0或協(xié)商向量I0，并把該賣方agent或agent組合加入到協(xié)商滿意解集中，然后改變議題值或議題向量。如果判斷函數(shù)為真，則發(fā)送修改后的議題值或議題向量給剩余的賣方agent，轉(zhuǎn)向b）；否則發(fā)送修改前的議題值或議題向量給剩余的賣方agent，將回復(fù)accept的賣方agent加入到滿意解集中，結(jié)束第一階段協(xié)商。

2.4 第一階段協(xié)商滿意解集

第一階段協(xié)商滿意解集是第一階段協(xié)商結(jié)束時(shí)所有發(fā)送accept的賣方agent的集合。

3 第二階段協(xié)商

第二階段協(xié)商只與第一階段協(xié)商滿意解集中的賣方agent進(jìn)行協(xié)商。首先生成拍賣初始向量，隨后按議題重要度從小到大的順序逐議題拍賣，直到最終只剩下一個(gè)賣方agent為止。拍賣協(xié)議采用改進(jìn)的first price sealedbid協(xié)議，不過(guò)不是選擇最優(yōu)值，而是按照?qǐng)?bào)價(jià)逆序的順序排除部分賣方agent。

3.1 拍賣初始向量

初始拍賣向量是第二階段拍賣開(kāi)始時(shí)，買方agent發(fā)送給賣方agent的初始向量，它包含所有議題的初始拍賣值。其中，關(guān)鍵議題或關(guān)鍵議題組合的初始值為第一階段協(xié)商結(jié)束時(shí)關(guān)鍵議題的提議值或議題組合的提議向量，非關(guān)鍵議題的值為第一階段協(xié)商的提議初始值中的議題值。

3.2 判斷函數(shù)

對(duì)于議題i，假設(shè)當(dāng)前滿意解集中的agent個(gè)數(shù)為k，1≤k≤n，判斷函數(shù)φ(i)=[n×ηi]。其中ηi為i的議題重要度。

3.3 算法描述

a)買方agent將所有議題按議題重要度遞增的順序排序，發(fā)送初始拍賣向量給第一階段協(xié)商滿意解集中的所有賣方agent。

b)賣方agent收到買方agent的初始值，按照買方的請(qǐng)求比較自己的目標(biāo)決策函數(shù)，在規(guī)定的議題i上作出讓步，并將新的值發(fā)送給買方agent。

c)買方agent收到賣方agent的提議值后，比較賣方agent的各個(gè)提議值，按照提議值逆序的順序排列賣方agent，以第φ(i)個(gè)agent的提議值作為第i個(gè)議題新的議題值并以此更新拍賣向量，同時(shí)將提議值低于第φ(i) 個(gè)agent的提議值的φ(i)-1個(gè)賣方agent剔出協(xié)商滿意解集。

d)買方agent發(fā)送新的拍賣向量給協(xié)商滿意解集中的所有賣方agent，然后轉(zhuǎn)向b），直到最終滿意解集中只有一個(gè)賣方agent為止。

4 實(shí)例

本文以一個(gè)簡(jiǎn)單的例子說(shuō)明整個(gè)協(xié)商的步驟。買方agent B想購(gòu)買一個(gè)筆記本電腦，需要協(xié)商的議題是價(jià)格、保質(zhì)期、交貨期和重量。其中消費(fèi)者選擇的重要程度依次為很重要、重要、不重要和一般；各個(gè)議題的取值依次為[5500，6800]，[1，3]，[0，14]，[1.8，2.7]；議題類型依次為成本類、收益類、成本類和成本類。表3中列出了目標(biāo)權(quán)重與隸屬函數(shù)之間的關(guān)系。

表3 Buyer 的談判目標(biāo)權(quán)重及隸屬函數(shù)

目標(biāo)權(quán)重隸屬函數(shù)三角模糊數(shù)

D()=（l+m+n）/4（2）

根據(jù)式（2）可以計(jì)算出各個(gè)議題的權(quán)重，依次為0.95，0.7，0.25和0.5；得出各個(gè)議題的重要度為0.40，0.29，0.10，0.21；沒(méi)有關(guān)鍵議題；關(guān)鍵議題組合為價(jià)格和保質(zhì)期；非關(guān)鍵議題為重量和交貨期；第一階段初始提議值為〈5500，3，2.29，10〉。表4列出了賣方agent的信息。

表4 賣方agent信息表

當(dāng)然，系統(tǒng)還允許賣方agent加約束條件。比如，agent1可以加約束條件，價(jià)格增加550元，保質(zhì)期增加1年；agent2可以設(shè)置約束條件，當(dāng)交貨期為7天以上時(shí)，價(jià)格可以便宜100元，保質(zhì)期為2年時(shí)，優(yōu)惠500元等，如表5所示。

表5 賣方agent約束信息表

商品價(jià)格/元保質(zhì)期/年重量/kg交貨期/天

第一階段協(xié)商后，協(xié)商滿意解集為（agent1，agent2，agent4，agent7）。

第二階段初始拍賣向量為（6100，2，2.29，10）。

最后，協(xié)商的最優(yōu)解為agent4，成交協(xié)商議題值為（6050，2，2.0，5）。

5 結(jié)束語(yǔ)

本文提出了多agent多議題的兩階段協(xié)商模型，第一階段協(xié)商關(guān)鍵議題或關(guān)鍵議題組合；第二階段采用拍賣方法按照議題重要度從小到大的順序逐個(gè)議題拍賣，直到最終達(dá)成最優(yōu)解。該模型不僅解決了多屬性效用判斷的難題，同時(shí)允許賣方體現(xiàn)出自己的產(chǎn)品特色，產(chǎn)品屬性的決定權(quán)交給有成本核算能力的賣方。兩階段模型由于其初始階段的淘汰機(jī)制和第二階段拍賣時(shí)的不斷淘汰使得協(xié)商的效率大大提高。

參考文獻(xiàn)：

［1］

FATIMA S，WOOLDRIDGE M，JENNINGS N R.Comparing equilibria for game theoretic and evolutionary bargaining models[C]//Proc of the 5th Int’l Workshop on AgentMediated Ecommerce.2003:7077.

[2]GERDING E H，SOMEFUN D J A，LAPOUTRE H J A.Multiattribute bilateral bargaining in a onetomany setting[C]//Proc ofthe 6th Workshop on AgentMedicated Ecommerce.2005:129142.

[3]李一軍，丁偉，曹榮增.交互式多目標(biāo)協(xié)商模型在談判領(lǐng)域中的應(yīng)用研究[J].管理工程學(xué)報(bào)，2002，16(4):13.

[4]王黎明，黃厚寬.一個(gè)基于多階段的多agent多問(wèn)題協(xié)商框架[J].計(jì)算機(jī)研究與發(fā)展，2005，42(11):18491855.

[5]ZHANG Xiaoxuan，GHOSE S，JO G S.An agentbased multiissue negotiation model in ecommerce[C]//Proc of International Conference on Intelligent Computing.2006:484489.

[6]HINDRIKS K，JONKER C M，TYKHONOV D.Eliminating interdependencies between issues for multiissue negotiation[C]//Proc of the 10th Int’l Workshop on Cooperative Information Agents.2006:301316.

[7]GUTTMAN R H，MAES P.Agentmediated integrative negotiation for retail electronic commerce[C]//Proc ofthe 1st Int’l Workshop on AgentMediated Etrading.1998:7090.

[8]武妍，曾建潮，白尚旺.一種多agent多議題的協(xié)商模型[J].計(jì)算機(jī)工程與科學(xué)，2007，29(6)：135139.

[9]LIMJ L H.Multistage negotiation support:a conceptual framework[J].Information and Software Technology，1999，41(5):249255.

[10] 謝安石，李一軍，尚維，等.拍賣理論的最新進(jìn)展多屬性網(wǎng)上拍賣研究[J].管理工程學(xué)報(bào)，2006，20（3）:1722.

[11]KENNY R，RAIFFA H.Decisions with multiple objectives[M].New York:Wiley，1976.

[12]張虹，李瑞，邱玉輝.雙邊多問(wèn)題自治協(xié)商的發(fā)展研究[J].計(jì)算機(jī)科學(xué)，2005，32(5):124127.

[13]FATIMA S S，WOOLDRIDGE M，JENNINGS N R.An agentbased framework for multiissue negotiation[J].Artificial Intelligence，2004，152(1):145.