面向議題關聯的雙邊多議題協商模型研究

摘 要：在Agent雙邊協商過程中往往包含對多個議題的協商.針對以往的基于議程、相似度、案例等協商方法中大部分都忽略了議題取值之間可能存在的依賴關系，提出一種面向議題關聯的雙邊多議題協商模型.首先模型結合了多議題順序協商思想和局部接受協商策略；其次引入離線學習機制，對協商成功的歷史記錄進行分區離線學習，利用離線學習機制產生的議題關聯規則與預測神經網絡實現對關聯議題可能接受取值的預測；最后模型提出一種基于關聯預測值的分段時間協商策略.實驗結果表明，該模型在一定程度上提高了協商的總體效用值和效率.

關鍵詞：多Agent系統;多議題協商;關聯規則;分段時間策略

中圖分類號：TP309 文獻標識碼：A

Research on Interdependence-oriented Bilateral 

Multi-issue Negotiation Model

HU Jun， DENG Lei， SONG Ying-hui

(College of Information Science and Engineering， Hunan Univ， Changsha， Hunan 410082， China)

Abstract:In bilateral negotiation procedures， there often exist a number of issues. Models based on agenda， similarity or cases， ignore in most cases the interdependence of values of each issue. This paper proposes an interdependence-oriented bilateral multi-issue negotiation model. Firstly， the model adopts the thoughts of sequential procedure and local acceptance strategy for multi-issues negotiation. Secondly， it introduces off-line learning mechanism to partition the successful historical records of learning and uses these association rules and neural networks， which are generated from off-line learning to predict the acceptable values of interdependent issues. Lastly， this model presents a segmentation time strategy， which is based on the interdependent predicted value. The experiment results have shown that this model can improve the overall utility and efficiency to some extent.

Key words: multi Agent systems； multi-issue negotiation; association rules;segmentation time strategy



雙邊多議題協商是多Agent系統的一個重要研究課題，其模型研究以多屬性效用理論［1］為基礎進行展開，傳統模型［2-3］通常忽略議題取值之間可能存在的關聯依賴性，而在實際協商過程中，議題取值之間往往存在關聯依賴性，從而也增加了多議題協商問題的復雜性.近年來，針對多議題關聯協商問題研究者們也提出了一些解決方案，文獻［4］通過引入一種加權平均的近似求解方法來降低議題之間的關聯依賴度，從而降低效用空間的復雜度，文獻［5］則引入模擬退火方法搜索Pareto最優解，雖然文獻［4-5］從一定程度上體現出了議題取值之間的關聯依賴性，但模型并沒有給出相關的形式化描述.而Robu［6］等人提出基于效用圖的協商模型，利用效用圖來描述議題之間存在的關聯關系，但模型中議題取值只能是二元取值0或1，因此很大程度上限制了該模型的實際應用范圍；文獻［7］則通過利用GAI網來描述議題之間存在的依賴性，其中議題可取多值，同時模型通過效用值來度量議題取值之間的依賴程度，但當議題的取值為連續或取值空間較大時，基于GAI網模型的應用將受到限制.針對基于效用圖和GAI網協商模型中存在的問題，本文提出一種新穎的面向議題關聯的雙邊多議題協商模型.通過對協商成功的歷史記錄進行分區離線學習，并利用學習產生的議題關聯規則來形式化描述議題取值之間的關聯依賴性.結合相應的議題關聯規則，模型給出了一種基于關聯預測值的分段時間協商策略.通過實驗對比分析，驗證了該模型的可行性與有效性，并且該模型從一定程度上提高了協商總體效用值與效率.

1 雙邊多議題協商模型

協商模型主要包括：協商策略、效用評估機制和協商協議等，本文提出的雙邊多議題協商模型BMINM(Bilateral Multi-Issues Negotiation Model)形式化定義如下：

BMINM=<A， TALL， I， Ev， OLM， S， P>

A：表示協商Agent集合，假設A={c，s}，Agents代表服務方，Agentc代表客戶方.

TALL表示Agent對于所有議題的總協商時間，如TjALL表示Agentj所對應的總協商時間，而協商過程的時間由總協商時間較短的Agent決定.

I表示協商議題集合，I=I1，…，In，Iji代表Agentj中第i個議題，I可以定義為四元組： 

I=

其中W表示議題權重值集合，而wji為Agentj中議題i的權重值，wji<1且∑ni=1wji=1；D表示議題取值區間，Dji={［MinVji，MaxVji］|i∈I，j∈A}則表示Agentj中議題i的協商取值區間，其中MinVji表示Agentj對于議題i可接受的最小值，而MaxVji為對應可接受的最大值；X表示Agent的提議值集合，Xji={xji|i∈I，j∈A}為Agentj中議題i的提議值集合，且xji∈Dji，xji表示Agentj對議題i的提議值；T表示協商時間，Tji表示Agentj所對應議題i的協商時間Tji=wji*TjALL，且TjALL=∑ni=1Tji .

Ev表示效用評估函數，Evji(xji)為Agentj對議題i的提議值xji進行評估，其中如果評估函數值關于提議值遞增，定義如下：

Evji(xji)=xji－MinVjiMaxVji－MinVji，i∈I，j∈A（1）

評估函數值關于提議值遞減，定義如下：

Evji(xji)=MaxVji－xjiMaxVji－MinVji，i∈I，j∈A（2）

而Agent的總體效用計算，定義如下：

Utility=∑ni=1wji*Evjixji.（3）

P表示協商協議，協商采用議價交互方式，過程中Agent可能的取值結果集Res∈{accept，reject，propose，success}；accept表示接受當前提議值，議題協商成功，reject表示拒絕當前提議值，協商失敗，結束協商過程；propose表示提出新的提議值，協商Agent根據各自的協商策略產生出新的提議值，并利用式（1）或式（2）對提議值進行評估，從而確定相應提議值并與對方進行下一輪協商；success表示所有議題都協商成功，協商成功結束.OLM離線學習機制及S協商策略在下文中分別進行了詳細敘述.

2 OLM離線學習機制

OLM(Off-line Learning Mechanism)離線學習機制主要目的是為了構建議題關聯規則庫和形成較精確的關聯預測神經網絡結構，利用預測神經網絡來有效預測關聯議題可能接受的取值.通過利用協商成功的歷史記錄，本文提出了一種分區離線學習機制，主要包括兩部分：議題關聯規則產生機制與GNN(Genetic Algorithm-Neural Network)算法.下面分別對這兩部分進行描述.

2.1 關聯規則產生機制

在多議題協商過程中，議題與議題之間的取值往往可能存在關聯依賴性，當某個議題（多個議題）協商成功后，與之關聯的議題的取值往往可能屬于某個確定的取值區間，本文將此區間定義為關聯取值子區間.

假設Δj表示議題集合Ij的子集，即ΔjIj，且議題集合Ij=∪nset=1Δjset；Agentj中議題i的協商取值子區間表示為dj，其中sub表示對應議題取值子區間的標識符，對于djDji，且dj=［min vj，max vj］，有Dji=∪nsub=1dj.綜合上述假設，對于Δjs1，Δjs2，Δjs3Ij（s1，s2，s3分別表示議題子集標識符），針對關聯依賴性的相關性質定義如下：

定義1 關聯依賴性.假設Δjs2中議題的取值依賴于Δjs1中議題的取值，則稱Δjs2關聯依賴于Δjs1，即Δjs1|= Δjs2；假設Δjs2中議題的取值不依賴于Δjs1中議題的取值，則Δjs1|≠Δjs2.

a)不相交性.已知Δjs1|=Δjs2，且s1≠s2，則Δjs1∩Δjs2=.

b)分解依賴性.已知Δjs1|=Δjs2，對于Iji'∈ Δjs2，則Δjs1|=Iji′.

c)完全依賴性.已知Δjs1|=Δjs2，對于δs1 Δjs1，且

瘙 綈 (δs1)|=Δjs2，則Δjs2完全依賴于Δjs1.

d)部分依賴性.已知Δjs1|=Δjs2，對于δs1 Δjs1，且(δs1)|=Δjs2，則Δjs2部分依賴于Δjs1；而通過將議題子集Δjs1進一步分解，可將部分依賴轉化為相應的完全依賴.

e)非傳遞依賴性.已知Δjs1|=Δjs2，并且Δjs2 |=Δjs3，而Δjs1|≠Δjs3，則Δjs3非傳遞依賴于Δjs1.

定義2 議題關聯規則.已知Δjs1|=Δjs2，Iji∈Δjs1，Iji'∈Δjs2，依據b)的分解依賴性與c)的完全依賴性，對于Δjs1|=Iji′所產生的關聯規則γ定義如下：

γjΔji|=Iji′=(∏ni=1dj)→dj.（4）

其中∏ni=1dj=dj<1，sub>∧…∧dj表示議題子集對應的關聯取值子區間集合，dj表示Iji′對應的關聯取值子區間，n表示議題子集Δjs1中議題的數量.

假設R表示議題子集之間的關聯規則集合，則RjΔs1|=Δs2表示由議題子集Δs1與Δs2所產生的關聯規則集合；對于Iji∈Δjs1，Iji′∈Δjs2，結合a)的不相交性，則(Iji)∈Δjs2∧(Iji′)∈Δjs1，排除了議題自身依賴于自身的關聯性.同時根據定義2中議題關聯規則的定義，RjΔs1|=Δs2定義如下：

RjΔjs1|=Δjs2={∪ni′=1γjΔjs1|=Iji′}，j∈A(5)

其中n表示Δjs2中議題的數量.依據e)可知各議題子集之間不存在傳遞依賴性，因此議題關聯規則庫即為所有R的并集，定義如下：

Rulesj=∪ρ=nρ=1Rjρ，j∈A，(Δjs|=Δjs')∈ρ（6）

其中s與s’分別表示Agentj中議題子集的標識符.

為實現對關聯規則庫的構建，模型采用K-Means算法對協商成功的歷史記錄進行聚類分析，根據產生的關聯數據簇對關聯議題的取值區間進行合理劃分并產生出對應的區間到區間的關聯規則，結合公式（6）完成關聯規則庫的構建.其中，K-Means聚類算法使用距離作為相似性評價指標，例如，計算數據點(v1(1)， v2(1)，…， vu(1))（u是屬性的個數）與 (v1(2)， v2(2)，…， vu(2))之間的距離dis，定義如下：

dis(v(1)，v(2))=∑ui=1ωi(v(1)i－v(2)i)p1p（7）

式中ω表示屬性的權重.模型采用歐幾里得距離計算方法（p=2），并用絕對誤差標準來進行度量，其定義如下：

ES=∑kj=1∑v∈Cj|v-Centerj|(8)

其中ES表示絕對誤差之和，v表示數據簇Cj中的具體對象，Centerj表示Cj的中心點.算法采用循環迭代，直到每個數據點對象都屬于某一確定的數據簇且ES不發生改變或小于指定閾值.

2.2 GNN算法

通過上述關聯規則產生機制完成了關聯規則庫的構建，從而實現了對關聯議題可能接受的取值子區間的預測，為進一步實現對關聯議題可能接受的最終取值的預測，模型引入GNN算法（神經網絡與遺傳算法相結合［8］）.依據神經網絡的特點，對聚類分析所形成的數據簇分別進行分區離線學習，得到對應取值子區間的預測神經網絡，從而實現關聯議題取值預測功能.在GNS［9］（遺傳算法-神經網絡系統）中，通過使用基因（GA）串最小化輸出預測誤差來實現系統優化.下面對GNN算法進行詳細描述，神經網絡的3層結構：輸入層I、隱層H和輸出層O，假設各層神經元的個數分別為Q、M、R，神經網絡結構如圖1所示：

依據圖1，假設vmij表示輸入層第i個神經元和隱層第j個神經元之間的連接權值，wmjk表示隱層第j個神經元和輸出層第k個神經元之間的連接權值，則輸入層與隱層之間的權值矩陣表示如下：

V_MatrixQ，M=vm11…vm1MvmQ1…vmQM

隱層與輸出層之間的權值矩陣表示如下：

W_Matrix［M，R］=wm11…wm1RwmM1…wmMR

假設神經網絡各層的傳遞函數fθ(θ={I，H，O})為：輸入層為線性函數，隱層為Log-Sigmoid函數，輸出層為Tan-Sigmoid函數；同時對于神經網絡各層結點的輸出計算，定義如下：

Outθk=fθ(∑numj=1Inθjθjk+bθk)（9）

其中num∈Q，M，R；In表示對應結點的輸入矩陣；表示權重矩陣集合，∈{V_Maxtrix，W_Matrix}；bθ表示各層的偏置值集合.

結合遺傳算法，通過GA串最小化神經網絡的輸出誤差，其中GA串的適應度函數f定義如下（TOk表示輸出層O第k個神經元的目標輸出，OutOk為對應的預測輸出）：

f=1N1R∑Nn=1∑Rk=1TOkn－OutOkn2（10）

其中N表示訓練模式的數量.

綜合上述關聯規則產生機制與GNN算法，分區離線學習機制(OLM)算法描述如下：

offlineLearingMechanism(){

samples=getSuccessRecord();//獲取成功歷史記錄

clusters=K-MEANS(sample);//聚類分析

saveRules(clusters);//構建并保存關聯規則庫

init(gnn); //初始化GNN算法相關參數

for each cluster in clusters//分區離線學習開始

if (存在數據)

do while(gen

//計算每個基因串關于樣本的適應度值

for each gaStr in GAStrs

//初始化神經網絡相應參數矩陣值

initNeuralNetworkParam(gaStr);

for each case in cases//循環簇中每個樣本

//計算當前輸入樣本的預測輸出

outputValues［case］=calPredictOutput(neuralNetwork，gaStr，case);

endfor

//計算適應度值公式（10）

calGaFitness(gaStr，outputValues，cases);

endfor

//收集所有GA串的適應度值

allFitness=collectAllFitness(GAStrs);

//通過選擇、交叉、變異產生下一代種群

generateNewGAStrs(GAStrs，allFitness);

gen++;

enddo//遺傳算法結束

best=getBestGAStr();//獲取最優串

saveNeuralNetwork(best);//保存關聯預測神經網絡

endif

endfor//離線學習結束

}

綜合上述，OLM離線學習機制首先利用K-Means算法對協商成功的歷史記錄進行離線聚類分析，產生出相應的議題關聯數據簇，從而實現對關聯議題取值區間的合理劃分，并完成對議題關聯規則庫的構建；其次模型結合GNN算法分別對每個數據簇進行離線學習，形成對應的關聯預測神經網絡，從而實現對關聯議題可能接受取值的有效預測.

3 協商策略

協商策略是Agent在協商過程中根據當前可知信息從而確定當前議題提議值的機制，而策略的選擇將直接影響協商的效率及總體效用值，本文提出一種基于預測值的分段時間依賴策略，同時結合了最終時間點讓步策略.首先，基于預測值的分段時間依賴策略以時間依賴策略為基礎，時間依賴策略［10］的類型主要包括快速型、緩慢型、線性型等；S(Strategy)協商策略中時間依賴函數φ(t)定義如下：

φji(t)=λj+(1－λj)(tTji)1Γ（11）

式中 λ為常數，Γ為時間依賴因子，根據Γ的不同取值，3種策略定義如下：Γ＞1，為快速型；0＜Γ＜1，為緩慢型；Γ=1，為線性型.依據式（11）定義的時間依賴函數φ，Agent在t時刻對議題i的提議值x，定義如下(t≤Tji)：

xji(t)=MinVji+φji(t)Dji

MinVji+(1－φji(t))Dji（12）

式中Dji=MaxVji－MinVji為議題i協商取值區間的模.依據離線學習產生的議題關聯規則庫，假設t<sub>表示議題取值子區間d<sub>=［min v<sub>，max v<sub>］對應的協商時間；t表示議題i在對應取值子區間上的協商時間，其中Tji=∑constsub=1tj，則tj定義如下：

tj=dj*TjiDji（13）

式中dj=max vj－min vj為議題i對應取值子區間的模.通過結合離線學習產生的關聯預測神經網絡，假設對于議題i的關聯預測值pv存在，由式（11）可得φ(t)的逆函數φ－1(t)，結合式（12）可計算出服務方提議值近似為預測值的預測時間點ζ.因此，基于預測值的分段時間依賴策略定義如下.

Agent在t時刻對議題i的提議值為x，當t≤ζ時：

xsi(t)=min vs+φsi(t)dsmin vs+(1－φsi(t))ds.（14）

當t>ζ時，t′=［0，ts－ζ］，同時調整相應的議題取值區間（xsi(0)=pvsi）和相應的時間依賴因子Γ，提議策略定義如下：

xsi(t′)=min vs+φsi(t′)d′smin vs+(1－φsi(t′))d′s（15）

其中d′s=max v′s－min vs.

在協商過程中，協商雙方引入基于最終時間點讓步策略，策略定義如下：假設對于議題i的最后一次提議值為x(Tji)，Agent將通知對方當前提議為最后一次提議，對方收到提議值后判斷是否屬于可接受的取值區間之內，如果屬于則接受最終提議值，否則當前議題協商失敗，結束協商.

4 實驗設計與分析

實驗采用Eclipse平臺，通過實驗模擬實現雙邊多議題協商交互過程，實驗模型包括：基于議程的協商模型ANM(An Agenda-based Negotiation Model)、基于關聯規則的協商模型ARNM(An Association Rule-based Negotiation Model)和BMINM協商模型.其中ANM模型采用文獻［3］的思想，利用外生議程與內生議程相結合的方式進行協商并忽略各議題取值之間存在的依賴性；ARNM模型則在ANM模型基礎上引入前述章節中的議題關聯規則產生機制，采用普通的時間依賴策略（公式（12）），并結合最終時間點讓步策略；BMINM模型則結合OLM離線學習機制與基于預測值的分段時間依賴策略，同時引入最終時間點讓步策略.在實驗過程中，定義UI為模型M1相對于模型M2提高（減少）的協商效用，結合公式（3）定義如下：

UI=Utility(M1)－Utility(M2)*100%（16）

同時定義EI為模型M1相對于模型M2提高（減少）的協商效率，定義如下：

EI=(Times(M1)－Times(M2))TALL*100%（17）

其中Times(M1)與Times(M2)分別表示模型M1，M2在協商過程中的總體協商交互次數.

實驗主要針對服務方展開討論，假設議題集合I={價格，交付時間，質保時間}；各議題的取值連續，對應權重值集合W={0.4，0.2，0.4}；取值區間分別為：價格∈［3 000，4 500］，交付時間∈［3，15］，質保時間∈［180，720］，協商時間TALL=300.議題基本屬性設置完成后，對OLM離線學習機制的相關參數進行設置：假設議題子集Δs1={價格}，Δs2={交付時間，質保時間}，Δs2完全依賴于Δs1，Δs1|=Δs2；同時設置K-Means算法參數k=10；GNN算法參數設置如表1所示.

依據表1，對所有參數設置完成后，服務方對11 000條協商成功的歷史記錄進行分區離線學習，

完成議題關聯規則庫及相應的關聯預測神經網絡的構建.取200個客戶請求實例，根據不同類型的協商策略分別對實驗涉及的3種協商模型進行實驗，協商的平均總體效用值與平均總體交互次數的實驗結果如表2所示.

結合表2分析，基于表中的3種策略，引入了議題關聯規則產生機制的ARNM模型相對于ANM模型的平均協商效用值與協商效率都得到了明顯提高；而對于引入了基于預測值的分段時間協商策略的BMINM模型相對于ARNM模型在平均交互次數變化不大的基礎上平均效用值卻得到了進一步提高；當采用緩慢型協商策略時，BMINM模型獲取的平均效用值比基于其它兩種策略獲取的平均效用值高，而具體的協商總體效用對比圖（結合公式（3））和總體交互次數對比圖如圖2、圖3所示（含50個客戶請求實例）.

客戶請求編號

結合表2對3種不同策略類型的樣例實驗結果進行具體分析如下：在平均總體效用值方面（結合公式（16）），BMINM模型相對于ARNM模型分別提高了1.7%，0.9%，2%，相對于ANM模型分別提高了11.4%，15.8%，18.4%；而對于平均協商效率方面（結合公式（17）），雖然BMINM的協商效率略低于ARNM模型，但相對于ANM模型分別提高了21.7%，12.7%，8.3%.同時結合圖4，針對實驗給出的測試樣例，當未采用最終時間點讓步策略時，BMINM，ARNM，ANM的協商成功率分別為92.5%，92.5%，100%，而采用最終時間點讓步策略后，3種模型的協商成功率均為100%，因此驗證了最終時間點讓步策略的有效性.綜合上述對比實驗，驗證了BMINM模型的可行性與有效性，同時表明采用BMINM模型進行雙邊多議題協商從一定程度上可提高協商的總體效用值和協商效率.

5 總 結

本文提出一種面向議題關聯的雙邊多議題協商模型，首先，通過引入OLM離線學習機制完成議題關聯規則庫及關聯預測神經網絡的構建，實現對關聯議題可能接受取值的有效預測；其次提出一種基于預測值的分段時間協商策略，最后通過實驗對比分析，驗證了該模型的可行性與有效性.

參考文獻

［1］ MIHAI Barbuceanu， WAI-KAU L O. A multi-attribute utility theoretic negotiation architecture for electronic commerce［C］//Proceedings of the Fourth International Conference on Autonomous Agents. Barcelona， Spain: ACM Press， 2000：239-247.

［2］ FATIMA S S， WOOLDRIDGE M，JENNINGS N R. Optimal agendas for multi-issue negotiation［C］//Proceedings of 2nd International Joint Conference on Autonomous Agents and Multi-Agent Systems. Melbourne， Australia: The MIT Press， 2003:129-136.

［3］ 童向榮， 黃厚寬， 張偉.一種基于案例的Agent多議題協商模型［J］.計算機研究與發展， 2009， 46(9):1508-1514. 

TONG Xiang-rong， HUANG Hou-kuan， ZHANG Wei. A case based agent multi-issue negotiation model ［J］. Journal of Computer Research and Development， 2009， 46(9): 1508-1514.(In Chinese)

［4］ HINDRIKS K， TYKHONOV D， JONKER C. Reducing complexity of all agent's utility space for negotiating interdependent issues［C］//Proceedings of the 18th BeNeLux Conference on Artificial Intelligence. Namur， 2006:383-384.

［5］ KARDAN A， JANZADEH H. A multi-issue negotiation mechanism with interdependent negotiation issues［C］//Proceedings of Second International Conference on the Digital Society (ICDS 2008). Washington， DC， USA: IEEE Computer Society， 2008:55-59.

［6］ ROBU V， LA POUTRE J A. Learning the structure of utility graphs used in multi-issue negotiation through collaborative filtering［C］//Lecture Notes in Computer Science. Berlin: Springer， 2009，4078:192-206.

［7］ GONZALES C， PERNY P. GAI networks for decision making under certainty［C］//Proc of the 19th International Joint Conference on Artificial Intelligence. Edinburgh， UK， 2005:100-105.

［8］ PRATIHAR D K. 軟計算［M］.王攀， 馮帥， 張堅堅， 譯.北京: 科學出版社， 2009:152-155.

PRATIHAR D K.Soft computing［M］.Translated by WANG Pan， FENG Shuai，ZHANG Jian-jian.Beijing:Science Press， 2009:152-155.(In Chinese)

［9］ PRATIHAR D K.Evolutionary robotics-a review ［J］. Sadhana， 2003， 28(6): 999-1009.

［10］FARATIN P， SIERRA C A，JENNINGS N R. Negotiation decision functions for autonomous agents ［J］. International Journal of Robotics and Autonomous Systems， 1997， 24(3):159-182.