融合非稀疏信任網(wǎng)絡(luò)的時(shí)間底限變動(dòng)的智能體協(xié)商模型

王金迪 童向榮

(煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院 山東煙臺(tái) 264005)(wangjindi117@163.com)

Agent協(xié)商越來(lái)越廣泛地應(yīng)用在電子商務(wù)、資源分配等許多領(lǐng)域[1].在協(xié)商問(wèn)題的研究中，從單議題協(xié)商模型[1]到多議題協(xié)商模型[2-4]，研究的熱點(diǎn)是如何選擇更好的協(xié)商策略使得協(xié)商更快地達(dá)成一致.同時(shí)，還應(yīng)該保證協(xié)商參與者能夠獲得更大的效用.多議題協(xié)商的研究考慮了不同Agent之間的偏好差異，從而可以進(jìn)行多議題之間的折中優(yōu)化，使得協(xié)商更快地達(dá)成一致，獲得更優(yōu)的協(xié)商效用.

實(shí)際上，Agent協(xié)商是一個(gè)擬人化的過(guò)程.人類在進(jìn)行協(xié)商時(shí)會(huì)帶有自己的主觀因素，其中一個(gè)主觀因素是對(duì)對(duì)方的信任，而信任會(huì)對(duì)協(xié)商達(dá)成一致所用時(shí)間和效用有直接的影響.直觀上，信任值高的協(xié)商者之間的合作底限可適當(dāng)變長(zhǎng)，而信任值低則會(huì)適當(dāng)縮短.同時(shí)，調(diào)整后的底限又會(huì)對(duì)協(xié)商成功率和協(xié)商效用產(chǎn)生影響，進(jìn)而會(huì)造成信任值高的協(xié)商者之間成功率更高，效用亦更大，同理，Agent之間會(huì)傾向于維持較大的信任值，此時(shí)系統(tǒng)就是一個(gè)良性循環(huán)的整體.

有學(xué)者將信任關(guān)系用來(lái)選擇協(xié)商對(duì)手[5]，從而提高協(xié)商效用，但是并沒(méi)有對(duì)協(xié)商模型和協(xié)商策略，尤其是回價(jià)函數(shù)進(jìn)行相應(yīng)的改進(jìn)，缺少進(jìn)一步的研究.

之前的研究中，有學(xué)者將直接信任或間接信任應(yīng)用于協(xié)商中[6-9].但是存在直接信任關(guān)系的Agent較少，可用的信任值缺失較多，導(dǎo)致了稀疏的信任網(wǎng)絡(luò)[10]，這樣就容易出現(xiàn)信任關(guān)系難以計(jì)算的情況，對(duì)于已有的數(shù)據(jù)也無(wú)法很好地利用.在密集的信任網(wǎng)絡(luò)下，信任關(guān)系是比較好構(gòu)建的.但是在稀疏的信任網(wǎng)絡(luò)中，只通過(guò)直接信任的方式難以算出Agent之間的信任值.

針對(duì)以上問(wèn)題，本文考慮了信任對(duì)協(xié)商過(guò)程的影響，將信任值作為一個(gè)參數(shù)加入到協(xié)商中.首先通過(guò)信任傳遞將間接信任與直接信任一起考慮，從而形成了非稀疏的信任網(wǎng)絡(luò)；然后通過(guò)信任值來(lái)選擇協(xié)商對(duì)手，并將信任值融入到協(xié)商的時(shí)間底限和回價(jià)函數(shù)中，通過(guò)對(duì)協(xié)商時(shí)間底限(即協(xié)商輪次底限)的適當(dāng)改動(dòng)，使得協(xié)商輪次的底限在信任值的影響下彈性變動(dòng);再次，本文重新定義了協(xié)商出價(jià)模型中的回價(jià)讓步函數(shù)，信任關(guān)系好的協(xié)商者可以讓步幅度大一些，信任關(guān)系不好的協(xié)商者讓步幅度小一些，使得協(xié)商中的回價(jià)策略更加符合現(xiàn)實(shí)情況;最后，本文通過(guò)大量的實(shí)驗(yàn)驗(yàn)證了所提方法的優(yōu)越性，驗(yàn)證了信任值對(duì)協(xié)商效用和協(xié)商達(dá)成一致所用時(shí)間的影響.

本文的主要貢獻(xiàn)有3個(gè)方面:

1)之前的研究中，一般假設(shè)協(xié)商時(shí)間底限是固定的，實(shí)際上該底限與雙方的容忍度有很大的關(guān)系，信任關(guān)系好，可以適當(dāng)延長(zhǎng)底限，信任關(guān)系不好，則必然縮短底限.本文提出的融合信任的時(shí)間底限變動(dòng)的協(xié)商模型，信任值高的協(xié)商對(duì)手會(huì)有更長(zhǎng)的協(xié)商輪次底限，更符合實(shí)際的協(xié)商情形，因而提高了協(xié)商成功率和協(xié)商效率.

2)將信任因素加入到回價(jià)函數(shù)，重新定義了回價(jià)讓步函數(shù).根據(jù)Agent對(duì)協(xié)商對(duì)手的信任值不同，其在協(xié)商中做出的回價(jià)以及協(xié)商中的讓步也是不相同的，根據(jù)信任值的大小將Agent分為3種類型，不同的類型會(huì)有不同風(fēng)格的回價(jià)方式.通過(guò)這種方式來(lái)優(yōu)化回價(jià)策略，從而保障協(xié)商可以得到更好的結(jié)果.

3)一般認(rèn)為信任網(wǎng)絡(luò)應(yīng)該是具有大規(guī)模節(jié)點(diǎn)分布的，這樣可以保證數(shù)據(jù)的可信性.在之前的基于信任的協(xié)商研究中，一般只考慮了直接信任關(guān)系，較少考慮信任傳遞形成的間接信任，這就造成了信任網(wǎng)絡(luò)的稀疏性，可用數(shù)據(jù)較少.本文考慮了信任傳遞形成的信任網(wǎng)絡(luò)，從而將間接信任納入信任關(guān)系，使得信任關(guān)系矩陣更稠密，形成了非稀疏的信任矩陣網(wǎng)絡(luò)，提高了數(shù)據(jù)的可利用性，由此可以有效地提高融合信任的Agent協(xié)商成功率和效率.

1 相關(guān)工作

協(xié)商一直是多Agent系統(tǒng)中的一個(gè)熱點(diǎn)研究問(wèn)題，其目的是在面對(duì)共同的利益需求時(shí)，通過(guò)妥協(xié)某些問(wèn)題達(dá)成相互有利的一致.而在如何達(dá)成這種一致上存在著很多矛盾，協(xié)商研究重點(diǎn)問(wèn)題之一即為平衡這些矛盾使得協(xié)商參與者都得到盡可能大的利益.

Jennings等人[1]提出Agent協(xié)商研究問(wèn)題時(shí)，將協(xié)商根據(jù)議題個(gè)數(shù)分為單議題協(xié)商和多議題協(xié)商.協(xié)商主要有3個(gè)內(nèi)容：協(xié)商協(xié)議、協(xié)商均衡目標(biāo)和協(xié)商策略，其中協(xié)商策略是之后研究的熱點(diǎn).后續(xù)研究中Fatima等人[2-3]提出了多種方法將協(xié)商的效用、策略等問(wèn)題進(jìn)行了相應(yīng)完善.

(1)

當(dāng)協(xié)商輪數(shù)(negotiation round)t超過(guò)最大協(xié)商輪數(shù)Ta時(shí)，說(shuō)明雙方?jīng)]有在要求時(shí)間內(nèi)達(dá)成一致，協(xié)商失敗.如果在第t輪Agenti對(duì)Agentj的出價(jià)使得Agentj得到的效用比在接下來(lái)第t+1輪Agentj對(duì)Agenti出價(jià)得到的效用高，Agentj接受出價(jià)，協(xié)商成功.若協(xié)商沒(méi)有成功且沒(méi)有達(dá)到時(shí)間底限，則Agentj提出新的出價(jià)，重新進(jìn)行效用比較，直到協(xié)商成功或到達(dá)時(shí)間底限失敗.這種協(xié)商方式是博弈論中的經(jīng)典交替報(bào)價(jià)的方式.

(2)

(3)

在Fatima等人[2]的文章中提出的出價(jià)函數(shù)為

(4)

通過(guò)式(4)可以看出，回價(jià)策略是根據(jù)初始出價(jià)和保留出價(jià)決定以及協(xié)商讓步函數(shù)決定的，買(mǎi)賣(mài)雙方具有不同的回價(jià)策略.協(xié)商讓步函數(shù)為

(5)

其中，ka為[0，1]的1個(gè)常數(shù)，ka的值控制Agent的初始出價(jià).θ取值不同，代表協(xié)商者的類型不相同，在之前的研究中是將協(xié)商者分為了Boulware，Linear，Conceder三類，不同的協(xié)商者在面對(duì)對(duì)手協(xié)商時(shí)所做出的讓步也有所不同.

Ren等人[12]也提出了不同的出價(jià)函數(shù)，在Ren等人的研究中，考慮到了協(xié)商環(huán)境對(duì)于出價(jià)的影響.利用協(xié)商買(mǎi)賣(mài)雙方的數(shù)量計(jì)算出市場(chǎng)情況，市場(chǎng)情況不同，協(xié)商買(mǎi)賣(mài)雙方的優(yōu)勢(shì)也不相同.Agent會(huì)根據(jù)自己的優(yōu)勢(shì)情況在協(xié)商中做出不同的回價(jià)策略，cot′為Agent在下一輪t′時(shí)提出的回價(jià).具體回價(jià)函數(shù)為

(6)

童向榮等人[13]在對(duì)Agent信任模型的研究中，考慮到時(shí)間分段與協(xié)商歷史共同對(duì)信任模型的影響，通過(guò)這些影響因素可以優(yōu)化Agent選擇對(duì)手或合作伙伴的方式，使得Agent的交互活動(dòng)更加合理化.Ren[11-12]等人在單議題協(xié)商上進(jìn)行了更深入的研究，與以往大部分研究線性效用函數(shù)不同，Ren等人充分考慮了非線性效用函數(shù)和離散型效用函數(shù)，提出了3D-協(xié)商模型.并且在協(xié)商時(shí)充分考慮協(xié)商的市場(chǎng)環(huán)境，根據(jù)市場(chǎng)供求關(guān)系來(lái)制定Agent的出價(jià)方式.

Braynov等人[14]提出如果協(xié)商雙方的信任值達(dá)到對(duì)方的要求，那么協(xié)商效用、社會(huì)福利、交易量等都會(huì)相比之前的協(xié)商方式有所提升.王黎明等人[5]提出了一個(gè)信任-聲譽(yù)模型，通過(guò)協(xié)商歷史等信息通過(guò)信任度和聲譽(yù)度去選擇協(xié)商的對(duì)手.在協(xié)商歷史信息不足的情況下，利用機(jī)器學(xué)習(xí)中經(jīng)典的K臂賭博機(jī)問(wèn)題結(jié)合信任值進(jìn)行協(xié)商對(duì)象的選擇，以達(dá)到更好的協(xié)商結(jié)果.利用2種方式選擇協(xié)商對(duì)象，提高了方法的實(shí)用性和有效性.Khayyam等人[15]提出了啟用社交網(wǎng)絡(luò)的協(xié)商服務(wù)，通過(guò)計(jì)算服務(wù)節(jié)點(diǎn)之間的信任度和相似度作為協(xié)商對(duì)象選擇的重要因素，在選擇對(duì)手后進(jìn)行的協(xié)商策略和結(jié)果都有了一定程度的優(yōu)化.

Sanzi等人[6]的研究通過(guò)將信任因素加入?yún)f(xié)商過(guò)程，改變了Agent的訪問(wèn)權(quán)限，信任值高或者有固定身份標(biāo)簽的Agent可以訪問(wèn)協(xié)商過(guò)程中的歷史信息，使得協(xié)商信任時(shí)間減少，在解決一些時(shí)間緊急的協(xié)商事件中取得了較好的成果.Pérez等人[16]在對(duì)協(xié)商問(wèn)題的研究中提出，應(yīng)當(dāng)將協(xié)商中的決策環(huán)境建立成為一個(gè)動(dòng)態(tài)環(huán)境，在以往的研究中影響決策動(dòng)態(tài)性的參數(shù)一般是對(duì)議題的偏好，而Pérez等人提出應(yīng)當(dāng)將多個(gè)不同參數(shù)作為動(dòng)態(tài)協(xié)商的調(diào)整因素，對(duì)后續(xù)的協(xié)商研究有很好的啟發(fā)性.

之前的學(xué)者分別對(duì)Agent信任、協(xié)商或信任與協(xié)商結(jié)合等問(wèn)題進(jìn)行了深入的研究，但是鮮少有文章指出信任值對(duì)于參與者的決策以及協(xié)商的結(jié)果具體會(huì)產(chǎn)生什么樣的影響.本文提出的融合信任的協(xié)商模型詳細(xì)闡述了信任值對(duì)于協(xié)商模型中協(xié)商輪數(shù)和協(xié)商決策的影響，改進(jìn)了Jennings等人[1-3]關(guān)于Agent協(xié)商的工作.

2 基本定義

本節(jié)中分別介紹了直接信任和間接信任值的計(jì)算方式，以及融合信任的協(xié)商模型的基本內(nèi)容.我們先給出5個(gè)基本定義.

定義1.協(xié)商參與者集合.將A={a1,a2,…,an}作為參與協(xié)商的Agent集合，Agent之間可能存在直接信任關(guān)系，也可能存在間接信任關(guān)系.

(7)

其中，時(shí)間節(jié)點(diǎn)之差以月為單位進(jìn)行運(yùn)算.由于信任具有時(shí)效性，則當(dāng)前時(shí)間節(jié)點(diǎn)與最后一次協(xié)商時(shí)間節(jié)點(diǎn)的差值越大，意味著信任值會(huì)越小.

定義4.信任.信任是2個(gè)人之間的一種關(guān)系，我們也可以將這種關(guān)系應(yīng)用在多Agent系統(tǒng)之中.為了方便計(jì)算Agent之間的信任關(guān)系(relationship)，本文使用概率表示信任值的大小.信任值的取值在[0,1]范圍內(nèi)，0表示完全不信任的關(guān)系，1表示完全信任的關(guān)系，值越大則信任程度越大.在本文設(shè)定中，直接信任受協(xié)商歷史的影響，只有曾經(jīng)發(fā)生過(guò)協(xié)商的Agent之間才具有直接信任值.直接信任值的計(jì)算和時(shí)間影響函數(shù)有關(guān)，根據(jù)協(xié)商場(chǎng)景的不同，時(shí)間影響函數(shù)也會(huì)有不同的表達(dá)方式，需要根據(jù)實(shí)際場(chǎng)景對(duì)Dij進(jìn)行改動(dòng).

1)直接信任.Agent之間的直接信任值與協(xié)商歷史中的次數(shù)信息和交易時(shí)間相關(guān)，協(xié)商歷史中的成功次數(shù)占比越高，協(xié)商時(shí)間差越短，則信任值越大.定義符號(hào)Xij為Agenti與Agentj之間的信任值(trust value)，直接信任Xij的計(jì)算：

(8)

2)間接信任.對(duì)沒(méi)有發(fā)生過(guò)協(xié)商交易的Agent之間的信任值可以用間接信任來(lái)表示.間接信任的取值方式是根據(jù)Agent之間的信任值的傳遞性決定的.如圖1所示，在信任網(wǎng)絡(luò)中，Agenti與Agentj沒(méi)有發(fā)生過(guò)協(xié)商交易，但Agenti與Agentm發(fā)生過(guò)協(xié)商交易，Agentm與Agentn發(fā)生過(guò)協(xié)商交易，Agentn與Agentj發(fā)生過(guò)協(xié)商交易，即Agenti與Agentm有間接信任關(guān)系.圖1表示的是Agent之間的間接信任關(guān)系圖.信任值將根據(jù)中間Agent數(shù)量的增加而不斷減小.若Agent之間沒(méi)有任何關(guān)系，則Xij=0.5.

Fig.1 Indirect trust relationship diagram圖1 間接信任關(guān)系圖

間接信任值的計(jì)算:

(9)

其中,Agentm和Agentn為Agenti與Agentj信任路徑中有直接信任關(guān)系的Agent，其信任值為Xmn.

R為Agenti與Agentj之間信任路徑(path)的跳數(shù)，根據(jù)斯坦利·米爾格蘭姆提出的6度分割理論，設(shè)定R∈[0,6] ，即超過(guò)6歩的信任路徑則沒(méi)有計(jì)算價(jià)值，視為無(wú)聯(lián)系的Agent.wmn為每條路徑的權(quán)重值(weight)，根據(jù)艾賓浩斯遺忘曲線[17]和距離衰減函數(shù)設(shè)定了每條信任路徑的權(quán)重值，即Agentj之間距離Agenti越遠(yuǎn)，連接的路徑權(quán)重越低，兩者之間的信任值也越低.權(quán)重函數(shù)為

(10)

權(quán)重函數(shù)曲線如圖2所示:

Fig.2 Weight function curve in indirect trust model圖2 間接信任模型中的權(quán)重函數(shù)曲線

例1.如圖1所示，Agenti和Agentj分別為協(xié)商參與者的買(mǎi)方與賣(mài)方.Agenti和Agentj無(wú)直接信任的關(guān)系，但兩者通過(guò)2個(gè)相關(guān)聯(lián)的Agent連接，分別是Agentm和Agentn.相關(guān)參數(shù)如表1所示：

Table 1 Parameter List of Trust Calculation表1 信任計(jì)算相關(guān)參數(shù)表

計(jì)算Xij：

定義5.協(xié)商者信息.每個(gè)參與協(xié)商Agent的參數(shù)集合為C={IP,RP,Xij,Ta}.包含的信息有Agent的初始出價(jià)、保留出價(jià)以及對(duì)對(duì)手的信任值和時(shí)間底限.

3 融合信任的協(xié)商模型

3.1 協(xié)商對(duì)象選擇與時(shí)間底限調(diào)整模型

本節(jié)詳細(xì)介紹了融合信任后的協(xié)商模型中的相關(guān)內(nèi)容.

在協(xié)商過(guò)程的最開(kāi)始，可以先對(duì)協(xié)商對(duì)象進(jìn)行初始選擇，通過(guò)選擇合作對(duì)象可以提高效益.例如消費(fèi)者想去美食廣場(chǎng)就餐，若飯店評(píng)論很差便會(huì)降低消費(fèi)者想要光顧的欲望，若評(píng)論很好則會(huì)提升消費(fèi)者的光顧欲望.

同樣地，在本文融合信任的協(xié)商模型中也考慮到了協(xié)商對(duì)象的選擇問(wèn)題，與顧客喜歡選擇高評(píng)分店家一樣，Agent會(huì)優(yōu)先選擇擁有較高信任值的對(duì)手進(jìn)行協(xié)商.后續(xù)實(shí)驗(yàn)驗(yàn)證了，Agent優(yōu)先與信任值高的對(duì)手合作，協(xié)商的成功率更高，同時(shí)，達(dá)成協(xié)商所用的輪次更少.合作對(duì)手E的選擇策略：

(11)

完成協(xié)商對(duì)象的選擇后，則正式開(kāi)始進(jìn)行協(xié)商.在本文中，根據(jù)雙方信任關(guān)系的不同，將最大協(xié)商輪數(shù)進(jìn)行了適當(dāng)?shù)恼{(diào)整，具體調(diào)整方式：

(12)

在時(shí)間底限調(diào)整函數(shù)中，運(yùn)用了神經(jīng)網(wǎng)絡(luò)中的Sigmoid改進(jìn)函數(shù)來(lái)進(jìn)行調(diào)整，根據(jù)信任值Xij的不同，函數(shù)會(huì)呈現(xiàn)一個(gè)分段狀態(tài).

當(dāng)Xij∈(0，0.5)時(shí)，由于Agent雙方的信任值較低，所以設(shè)定協(xié)商者對(duì)對(duì)手的忍耐度會(huì)降低，因此協(xié)商的時(shí)間底限也會(huì)有所縮減.為了防止協(xié)商輪數(shù)太少，將函數(shù)中的最小輪數(shù)的閾值設(shè)為初始輪數(shù)Ta的1/2.

當(dāng)Xij=0.5時(shí)，雙方信任值為1個(gè)折中值，協(xié)商的時(shí)間底限不會(huì)有所改變，依然是Ta.

當(dāng)Xij∈(0.5,1]時(shí)，協(xié)商雙方的信任值較高，我們?cè)O(shè)定協(xié)商者對(duì)協(xié)商對(duì)手的容忍度較高，因此協(xié)商的時(shí)間底限可以有所增加.

根據(jù)信任值的大小程度進(jìn)行了時(shí)間底限調(diào)整函數(shù)的計(jì)算，根據(jù)信任值的不同，最終協(xié)商的時(shí)間底限也會(huì)有所改變.最終時(shí)間底限的變動(dòng)與信任值的關(guān)系如圖3所示：

Fig.3 Round limit change chart圖3 時(shí)間底限變動(dòng)圖

改進(jìn)后的協(xié)商決策模型：

(13)

與以往相關(guān)研究不同，本文將時(shí)間底限設(shè)置成一個(gè)變量，參考在生活中交往的2人的情況，若是對(duì)交易的對(duì)手有較高的信任程度，在直覺(jué)上會(huì)認(rèn)為交易成功的概率較大，往往也會(huì)有比較高的容忍度，可以接受的協(xié)商輪次也會(huì)有所增加，反之亦然.因此本文利用時(shí)間底限調(diào)整函數(shù)將時(shí)間底限做了調(diào)整，使得協(xié)商環(huán)境中的最大協(xié)商輪次將根據(jù)信任值進(jìn)行彈性變動(dòng)，使其更加符合真實(shí)情況.針對(duì)此問(wèn)題，我們?cè)诤罄m(xù)實(shí)驗(yàn)中選擇了1組數(shù)據(jù)，驗(yàn)證了改動(dòng)后的時(shí)間底限模型的優(yōu)越性.具體示例情況如表2所示：

Table 2 Example Table of Negotiation Round Adjustment表2 出價(jià)模型示例表

通過(guò)表2可以發(fā)現(xiàn)，在初始設(shè)定的協(xié)商輪次較低時(shí)，傳統(tǒng)的NDF(negotiation decision function)方法[2]由于協(xié)商底限的固定性，導(dǎo)致協(xié)商在達(dá)到最大輪次時(shí)沒(méi)有達(dá)成一致而失敗.而通過(guò)本文對(duì)協(xié)商底限模型的彈性改動(dòng)，較高的信任值使得協(xié)商底限延長(zhǎng)，讓雙方有機(jī)會(huì)進(jìn)一步協(xié)商，進(jìn)而使得協(xié)商成功.

3.2 協(xié)商出價(jià)模型

通過(guò)式(13)可以看出，協(xié)商能否成功與協(xié)商對(duì)手的出價(jià)有關(guān).如果對(duì)手的出價(jià)帶來(lái)的效用能夠滿足Agent自身的要求，那么協(xié)商很容易成功.協(xié)商中的出價(jià)方式是一種協(xié)商策略，在以往研究中都是一個(gè)非常重要的影響因素，如何出價(jià)才能更快、更好地達(dá)成協(xié)商一直是研究者們考慮的問(wèn)題.

在Fatima等人[2]所提出的式(5)的基礎(chǔ)之上，本文進(jìn)行了一些改進(jìn)，將信任因素加入，重新定義了出價(jià)讓步函數(shù).根據(jù)Agent對(duì)協(xié)商對(duì)手的信任值不同，那么他在協(xié)商中做出的出價(jià)以及協(xié)商中的讓步也是不相同的.本文提出一個(gè)新的出價(jià)讓步函數(shù)，在函數(shù)中引入信任值，通過(guò)信任值的大小將Agent分為3種類型，不同的類型會(huì)有不同風(fēng)格的出價(jià)方式，通過(guò)這種方式來(lái)優(yōu)化出價(jià)策略以使得協(xié)商可以得到更好的結(jié)果.綜合各種參考因素，出價(jià)函數(shù)是根據(jù)初始出價(jià)、保留出價(jià)、協(xié)商時(shí)間底限以及協(xié)商雙方之間的信任值決定的.融合信任后的出價(jià)讓步函數(shù):

(14)

出價(jià)讓步函數(shù)根據(jù)雙方信任值的不同，會(huì)有不同的回價(jià)策略.分析3個(gè)方面：

1)0

2)Xij=0.5 時(shí)，雙方信任值為1個(gè)折中值，雙方的讓步比較平緩，沒(méi)有大規(guī)模的增加，時(shí)間底限也是1個(gè)不輕易變的屬性.

3)Xij>0.5 時(shí)，雙方信任值比較高，使得協(xié)商時(shí)協(xié)商者之間的初始協(xié)商出價(jià)讓步比較大，在協(xié)商后期會(huì)將讓步逐步減小一些.在多次讓步?jīng)]有取得結(jié)果時(shí)，時(shí)間底限由于信任值的較高而增加，協(xié)商可以持續(xù)的時(shí)間長(zhǎng)久一些.

在后續(xù)實(shí)驗(yàn)中選擇了1組數(shù)據(jù)以驗(yàn)證本文提出方法的優(yōu)越性.具體實(shí)驗(yàn)數(shù)值如表3所示：

Table 3 Example Table of Bidding Model表3 出價(jià)模型示例表

為了方便觀察信任值對(duì)出價(jià)讓步以及協(xié)商輪次的影響，本例選取的實(shí)驗(yàn)數(shù)據(jù)為在其他參數(shù)相同且協(xié)商全部成功的情況下，信任值不同會(huì)導(dǎo)致協(xié)商者的讓步方式不同.如果對(duì)于協(xié)商對(duì)手的信任值較高，則協(xié)商者讓步較大，所以協(xié)商達(dá)成一致的輪數(shù)也會(huì)降低；當(dāng)信任值中等時(shí)，讓步會(huì)稍小一些，協(xié)商輪數(shù)有小的增加；而信任值較低時(shí)，協(xié)商者的讓步較小，所以協(xié)商達(dá)成一致的輪數(shù)會(huì)增加.通過(guò)本例也可以發(fā)現(xiàn)，如果在協(xié)商時(shí)優(yōu)先選擇信任值高的對(duì)手，會(huì)使得協(xié)商在取得更高成功率的同時(shí)減少協(xié)商輪次以達(dá)到降低時(shí)間成本的作用.

3.3 協(xié)商流程

算法1.融合信任的協(xié)商算法.

輸入：買(mǎi)方Agent信息Ci、賣(mài)方Agent信息Cj；

輸出：isSuccess協(xié)商是否成功.

① 計(jì)算Tai，Taj；

②Tn←min(Tai,Taj)；

③ Agentf←Random(Ci,Cj)；/*隨機(jī)產(chǎn)生第1輪出價(jià)方*/

④ while (t

⑨isSuccess=True；

⑩ break；

算法1的計(jì)算復(fù)雜度為多項(xiàng)式級(jí)，即：

O(n)=6n+5.

4 實(shí)驗(yàn)與結(jié)果

本節(jié)對(duì)多個(gè)協(xié)商模型的協(xié)商結(jié)果進(jìn)行了驗(yàn)證和對(duì)比：基礎(chǔ)實(shí)驗(yàn)的實(shí)驗(yàn)設(shè)置、對(duì)比驗(yàn)證不同信任情況下的協(xié)商結(jié)果、介紹新提出的融合信任的協(xié)商模型與NDF協(xié)商模型[2]和OMIA(opponent modeling with information adaptation)協(xié)商模型[18]的協(xié)商結(jié)果對(duì)比.

4.1 基礎(chǔ)實(shí)驗(yàn)設(shè)置

為了更好地去驗(yàn)證實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)設(shè)置了最大Agent數(shù)為30個(gè)，其中買(mǎi)方Agent有15個(gè)，賣(mài)方Agent有15個(gè).每次協(xié)商都是隨機(jī)抽取1個(gè)買(mǎi)方Agent與1個(gè)賣(mài)方Agent進(jìn)行交易.每選取50對(duì)為1組，共進(jìn)行了8組實(shí)驗(yàn).協(xié)商的議題為衣服的價(jià)格.對(duì)于買(mǎi)方Agent來(lái)說(shuō)，它的初始出價(jià)在1 500～4 500元的范圍內(nèi)隨機(jī)選擇，保守出價(jià)在5 000～15 000元的范圍內(nèi)隨機(jī)選擇.對(duì)于賣(mài)方Agent來(lái)說(shuō)，它的初始出價(jià)在5 000～15 000元的范圍內(nèi)隨機(jī)選擇，它的保守出價(jià)在1 500～4 500元的范圍內(nèi)隨機(jī)選擇.所有Agent的初始協(xié)商輪數(shù)在5～20輪的范圍內(nèi)隨機(jī)選擇.本文中分析了6種評(píng)價(jià)指標(biāo)[12]，分別是買(mǎi)方Agent平均效用BAU(buyers’ average utility)、賣(mài)方Agent平均效用SAU(sellers’ average utility)、所有成功Agent平均效用AAU(all agents’ average utility)、協(xié)商成功率SR(success rate)、總效用AU(all utility)、協(xié)商達(dá)到成功時(shí)的輪數(shù)Round.其中AU是綜合了AAU和SR的總效用，在計(jì)算總效用時(shí)考慮了總體協(xié)商的成功率，將成功率作為一種獎(jiǎng)勵(lì)算進(jìn)了總體效用之中.評(píng)價(jià)指標(biāo)中的相關(guān)參數(shù)有：所有協(xié)商成功買(mǎi)方Agent的效用Uasb、所有協(xié)商成功買(mǎi)方Agent的個(gè)數(shù)numberasb、所有協(xié)商成功賣(mài)方Agent的效用Uass、所有協(xié)商成功賣(mài)方Agent的個(gè)數(shù)numberass、所有協(xié)商成功Agent的效用Uasa、所有協(xié)商成功Agent的個(gè)數(shù)numberasa、協(xié)商成功次數(shù)NTsuccess、協(xié)商總次數(shù)NTall、協(xié)商成功時(shí)的輪數(shù)ts.評(píng)價(jià)指標(biāo)的具體計(jì)算：

4.2 不同信任情況下的實(shí)驗(yàn)對(duì)比

1)對(duì)手選擇

本實(shí)驗(yàn)驗(yàn)證了根據(jù)信任值的高低優(yōu)先對(duì)協(xié)商對(duì)手進(jìn)行選擇的協(xié)商情況.實(shí)驗(yàn)設(shè)定了1個(gè)買(mǎi)方Agent和30個(gè)賣(mài)方Agent，買(mǎi)方Agent對(duì)30個(gè)賣(mài)方Agent的信任值各不相同，由低到高分別標(biāo)號(hào)為1～30，賣(mài)方Agent對(duì)買(mǎi)方Agent的信任值都設(shè)為中間值0.5.表5顯示了實(shí)驗(yàn)的相關(guān)數(shù)據(jù).在實(shí)驗(yàn)中，優(yōu)先選擇出信任值最高的10個(gè)Agent進(jìn)行序號(hào)排序，之后使買(mǎi)方Agent與30個(gè)賣(mài)方Agent全部進(jìn)行協(xié)商，將協(xié)商后的買(mǎi)方獲得的效用按大小進(jìn)行排序并記錄序號(hào).利用推薦系統(tǒng)中的評(píng)價(jià)指標(biāo)，我們計(jì)算了選擇對(duì)手這一過(guò)程的準(zhǔn)確率P、召回率R以及綜合指標(biāo)F值.

通過(guò)本組實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)，實(shí)驗(yàn)的準(zhǔn)確率P能夠達(dá)到0.9，綜合指標(biāo)F值達(dá)到0.45.通過(guò)表4中的位次排序也可以發(fā)現(xiàn)排序與最優(yōu)結(jié)果有一定誤差，通過(guò)數(shù)據(jù)比較可以發(fā)現(xiàn)位次的誤差率是比較小的，這個(gè)結(jié)果可以驗(yàn)證我們的選擇是有效的，即在優(yōu)先選擇信任值高的協(xié)商對(duì)手后，交易雙方可以獲得的效用也越高.

Table 4 Negotiation Parameter Sorting Table After Selecting an Opponent表4 選擇對(duì)手后的協(xié)商參數(shù)排序表

2)成功次數(shù)

在驗(yàn)證雙方信任值不同情況下對(duì)Agent協(xié)商結(jié)果的影響實(shí)驗(yàn)中，延續(xù)使用了4.1節(jié)中的實(shí)驗(yàn)設(shè)置，不同的是本實(shí)驗(yàn)將所有可能出現(xiàn)的信任值組合進(jìn)行了協(xié)商實(shí)驗(yàn)，即對(duì)買(mǎi)方Agent與賣(mài)方Agent分別取信任值{0，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1}時(shí)的協(xié)商類型，共有121組組合，每種類型各實(shí)驗(yàn)50次，取其成功次數(shù)來(lái)驗(yàn)證買(mǎi)賣(mài)雙方不同信任值下協(xié)商的成功率.實(shí)驗(yàn)結(jié)果如圖4所示:

Fig.4 Number of negotiation success times under different trust values圖4 不同信任值情況下的協(xié)商成功次數(shù)圖

通過(guò)圖4可以明顯地發(fā)現(xiàn)成功次數(shù)的增長(zhǎng)趨勢(shì).在信任值交互較低的區(qū)域內(nèi)，成功次數(shù)也非常少，出現(xiàn)這種情況的原因與新定義的協(xié)商底限變動(dòng)模型和出價(jià)讓步模型有關(guān).因?yàn)樾湃沃递^低，協(xié)商底限也會(huì)變短，其主要目的是為了避免耗時(shí)多、效用低的低質(zhì)量協(xié)商.隨著信任值的增加，成功次數(shù)開(kāi)始逐步增加.我們發(fā)現(xiàn)當(dāng)信任值高達(dá)0.8以上時(shí)，成功次數(shù)幾乎達(dá)到了最大值.在新定義的時(shí)間底限調(diào)整模型中，設(shè)置的信任值高的雙方更具耐心，可以適當(dāng)增加協(xié)商的輪數(shù)底限，而在協(xié)商過(guò)程中，信任值高的雙方讓步也更大，這2種方式都增加了協(xié)商的成功次數(shù).

本實(shí)驗(yàn)驗(yàn)證了不同信任值對(duì)協(xié)商成功率會(huì)有不同的影響:當(dāng)協(xié)商雙方的信任值較低時(shí)協(xié)商的成功率會(huì)比較低；相反，協(xié)商雙方的信任值較高時(shí)協(xié)商的成功率會(huì)比較高.

3)協(xié)商輪數(shù)

本實(shí)驗(yàn)驗(yàn)證了雙方信任值不同情況下對(duì)協(xié)商輪數(shù)的影響.實(shí)驗(yàn)中的數(shù)據(jù)根據(jù)信任值的不同分為4種情況：Random，High，Middle，Low.其中Random表示本組所有Agent對(duì)對(duì)手的信任值的大小是從[0,1]范圍內(nèi)隨機(jī)設(shè)定的；High表示本組所有Agent對(duì)對(duì)手的信任值大小是從[0.6,1]范圍內(nèi)隨機(jī)設(shè)定的；Middle表示本組所有Agent對(duì)對(duì)手的信任值大小設(shè)定為0.5；Low表示本組所有Agent對(duì)對(duì)手的信任值大小是從[0,0.4]范圍內(nèi)隨機(jī)設(shè)定的.對(duì)4種不同情況的Agent組分別進(jìn)行了50組的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表5所示:

Table 5 Average Number of Negotiated Rounds表5 不同實(shí)驗(yàn)類型的平均協(xié)商輪數(shù)表

通過(guò)表5可以發(fā)現(xiàn)不同信任值類型的Agent組的協(xié)商輪數(shù)也并不相同，實(shí)驗(yàn)中只選取了所有成功協(xié)商過(guò)程的平均協(xié)商輪數(shù).對(duì)比3組數(shù)據(jù)可以發(fā)現(xiàn)，High組即信任值比較高的Agent組的平均協(xié)商輪次較少，Middle組即信任值為中間值0.5的Agent組平均協(xié)商輪數(shù)要比High組稍高而比Low組稍低.Low組即信任值比較低的Agent組協(xié)商成功時(shí)的協(xié)商輪次最高.出現(xiàn)這種實(shí)驗(yàn)結(jié)果的原因是重新定義的出價(jià)讓步函數(shù)與信任值有關(guān).信任值越高，出價(jià)時(shí)的讓步越高，導(dǎo)致協(xié)商達(dá)成一致的時(shí)間也會(huì)縮短；信任值越低，出價(jià)時(shí)的讓步越少，協(xié)商達(dá)成一致的時(shí)間就會(huì)增加.這模擬了交易者在現(xiàn)實(shí)生活中的討價(jià)還價(jià)心理：對(duì)于常常交易的老顧客，賣(mài)家更喜歡直接給一個(gè)優(yōu)惠的價(jià)格；而對(duì)于新光顧的顧客，賣(mài)家會(huì)多次少量的給出優(yōu)惠.

本實(shí)驗(yàn)驗(yàn)證了Agent的信任值會(huì)影響最終的協(xié)商輪數(shù)，買(mǎi)賣(mài)雙方的信任值越高，協(xié)商達(dá)成一致的時(shí)間越短，買(mǎi)賣(mài)雙方的信任值越低，協(xié)商達(dá)成一致的時(shí)間越長(zhǎng).

4.3 與NDF模型的對(duì)比實(shí)驗(yàn)

1)成功率

為了展示協(xié)商模型的實(shí)驗(yàn)結(jié)果，本文分別選取經(jīng)典的NDF協(xié)商模型[2]、OMIA模型[1]與融合信任的協(xié)商模型進(jìn)行了實(shí)驗(yàn)對(duì)比.其中，融合信任的協(xié)商模型根據(jù)信任值的不同又分為了4種情況，分別是：Random，High，Middle，Low.其分組依據(jù)與4.2節(jié)的實(shí)驗(yàn)中相同.通過(guò)圖5可以觀察到6種協(xié)商模型的成功率.

Fig.5 Negotiation success rate result chart圖5 協(xié)商成功率結(jié)果圖

通過(guò)對(duì)比可以看出，High組融合信任的協(xié)商模型成功率比NDF協(xié)商模型高出8.0%，比OMIA模型高出13.25%.因?yàn)锳gent雙方的信任值增加，使得協(xié)商輪數(shù)底限也相應(yīng)增加，使得協(xié)商的成功率明顯提升.

Low組融合信任的協(xié)商模型成功率比NDF協(xié)商模型低71.75%，比OMIA模型低66.50%.這種結(jié)果在直覺(jué)上是很好理解的，當(dāng)交易者對(duì)對(duì)方信任程度低時(shí)，協(xié)商交互的耐心也會(huì)明顯變低.因此，信任值變低時(shí)，協(xié)商成功率也會(huì)大幅度降低.

Random組融合信任的協(xié)商模型成功率比NDF協(xié)商模型低35.50%，比OMIA模型低30.25%.在Random組中，因?yàn)樾湃沃档拇笮≡赱0,1]區(qū)間內(nèi)隨機(jī)選擇，也使得協(xié)商的成功率在50.0%左右，因?yàn)榈托湃沃档腁gent在協(xié)商時(shí)會(huì)拉低協(xié)商成功率.

Middle組融合信任的協(xié)商模型成功率低于NDF協(xié)商模型0.25%，高于OMIA模型5.0%.成功率相差較小.Middle組的信任值取值為0.5，是一種折中情況，與不考慮信任值的NDF協(xié)商模型的協(xié)商結(jié)果比較相似.

通過(guò)6組實(shí)驗(yàn)協(xié)商成功率的對(duì)比，可以發(fā)現(xiàn)，在考慮信任因素后，Agent的協(xié)商方式更加貼合人類在對(duì)待不同對(duì)手時(shí)的交互方式，使得Agent的決策更加細(xì)化和擬人化.

2)效用

協(xié)商者的效用也是協(xié)商問(wèn)題中的一個(gè)重要參數(shù)，在本文中融合信任的協(xié)商模型中，買(mǎi)方與賣(mài)方的效用函數(shù)是根據(jù)初始出價(jià)和保留出價(jià)以及雙方的最終協(xié)商價(jià)格決定的，數(shù)值比實(shí)際上是實(shí)際成交價(jià)格與預(yù)期價(jià)格的一個(gè)預(yù)期比，比值越高說(shuō)明協(xié)商者對(duì)交易價(jià)格越滿意.表6表示5種實(shí)驗(yàn)計(jì)算出的4種效用的具體數(shù)值，我們可以看出：實(shí)驗(yàn)中效用差距不太明顯.通過(guò)細(xì)微的差距可以發(fā)現(xiàn)在未考慮成功率前，Low組的AAU的反而更高.通過(guò)分析實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)在Low組取得成功的協(xié)商中，隨機(jī)數(shù)據(jù)初始出價(jià)IP和保留出價(jià)RP的差距比較小，所以成交價(jià)格也可以使Agent達(dá)到更高的效用值.但是當(dāng)初始出價(jià)IP和保守出價(jià)RP的差距比較大時(shí)，Low組的信任值影響了時(shí)間底限，導(dǎo)致協(xié)商容易失敗，所以在計(jì)算總效用AU時(shí)，Low組的總效用較低.而NDF方法和High組由于協(xié)商成功率較高，總效用也隨之提高.

Table 6 Relevant Utility of Different Types of Experiments表6 不同實(shí)驗(yàn)類型的相關(guān)效用表

5 總 結(jié)

本文提出了融合非稀疏信任網(wǎng)絡(luò)的時(shí)間底限變動(dòng)的Agent協(xié)商模型，主要解決的問(wèn)題是電子商務(wù)中交易雙方Agent的協(xié)商問(wèn)題.從2個(gè)方面對(duì)模型進(jìn)行了改進(jìn):1)通過(guò)融合信任值的方法對(duì)傳統(tǒng)協(xié)商模型中的協(xié)商底限函數(shù)進(jìn)行了改動(dòng).與以往固定的協(xié)商底限不同，改動(dòng)后的協(xié)商底限將根據(jù)信任值進(jìn)行彈性變動(dòng).2)將協(xié)商中的回價(jià)函數(shù)與信任值進(jìn)行了融合，使得Agent的協(xié)商方式更加貼合現(xiàn)實(shí)中的協(xié)商交互情況.本文通過(guò)多組實(shí)驗(yàn)也驗(yàn)證了所提方案的合理性.

本文通過(guò)對(duì)協(xié)商底限的改動(dòng)，有效地避免了多耗能、低效率的協(xié)商，從而可以節(jié)省時(shí)間，促進(jìn)更多低耗能、高效率的協(xié)商.本文提出的融合信任值的回價(jià)函數(shù)，可以使Agent的回價(jià)行為更加擬人化，從而提高了協(xié)商的成功率和協(xié)商效用.

由于協(xié)商問(wèn)題的多樣性和復(fù)雜性，仍有許多問(wèn)題值得深入探討.例如如何將深度學(xué)習(xí)與協(xié)商結(jié)合得到更好的協(xié)商結(jié)果、如何將信任應(yīng)用于多議題的協(xié)商等.