基于時(shí)間和資源約束的多Agent雙邊動態(tài)協(xié)商模型

王燦,梁永全

基于時(shí)間和資源約束的多Agent雙邊動態(tài)協(xié)商模型

王燦1,2,梁永全1

1.山東科技大學(xué),山東青島266590
2.山東商業(yè)職業(yè)技術(shù)學(xué)院,山東濟(jì)南250103

雙邊交易Agent協(xié)商中因時(shí)間、資源的約束和信息的不完整，常會導(dǎo)致協(xié)商失敗和較差的協(xié)商收益。本文提出一種基于時(shí)間和資源雙重約束下的多Agent動態(tài)協(xié)商模型，使用出價(jià)函數(shù)和出價(jià)曲線來設(shè)定Agent的策略，采用特定協(xié)議來描述協(xié)商資源對心理狀態(tài)的影響。同時(shí)，定義了折中、保守和急躁三種協(xié)商策略以及心理狀態(tài)對策略的動態(tài)改變規(guī)則。通過實(shí)驗(yàn)?zāi)M發(fā)現(xiàn)“多買方、單賣方”條件下，采用提出的協(xié)商策略和動態(tài)協(xié)商算法能夠提高協(xié)商效率、降低成交價(jià)格和提升協(xié)商滿意度。

動態(tài)協(xié)商；協(xié)商策略；協(xié)商算法

Agent技術(shù)已被越來越多的應(yīng)用在工業(yè)和經(jīng)濟(jì)等領(lǐng)域[1]。協(xié)商已成為一種重要Agent之間的交互形式。自動協(xié)商則是Mulit-Agent之間就共同關(guān)注問題達(dá)成一致時(shí)所進(jìn)行的行動過程。Agent所能采取的行動包括：提議、反提議、讓步、退出和同意等。通過智能Agent技術(shù)能夠在買賣雙方交易中更好的做出決定和減少資源消耗已經(jīng)被很多研究證明[2]。然而，由于信息不完整和時(shí)間、資源約束會經(jīng)常導(dǎo)致agent的交易策略很難被設(shè)計(jì)。同時(shí)，交易策略不僅會影響協(xié)商的效率，也會影響到買賣雙方的收益。

在以前研究中，一些關(guān)于協(xié)商的理論背景已經(jīng)廣泛被討論，特別是在博弈論中[3]。一些研究[4]采用效用函數(shù)來衡量協(xié)商效果，從而達(dá)到協(xié)商的一致。Kraus在1995年提出時(shí)間約束下的Mulit-agent協(xié)商，把時(shí)間折算因子和延時(shí)損耗作為協(xié)商策略進(jìn)行研究[5]。P.Faratin和N.R.Jennings則使用了出價(jià)函數(shù)結(jié)合策略因子來進(jìn)行價(jià)格協(xié)商[6]。Kraus在原有研究基礎(chǔ)上，把心理模型引入到協(xié)商談判中[7]，認(rèn)為協(xié)商高效的條件是能夠理解和影響其他Agent的信念、愿望、目標(biāo)和意圖。蔣國瑞、黃梯云等提出了一個(gè)Agent的多目標(biāo)優(yōu)化模型談判過程控制，使用狀態(tài)機(jī)協(xié)議以及基于沖突解決策略進(jìn)行辯論協(xié)商[8]。張宏、何華燦把協(xié)商策略分為了急躁型、節(jié)約型和折中型，并使用可連續(xù)變化的曲線簇來描述基于BDI理論的協(xié)商策略[9]。

綜觀上述研究，本文在構(gòu)建在信息不完整條件下“單賣方、多買方”雙邊自動協(xié)商模型中，考慮時(shí)間約束和資源約束的影響，關(guān)注買方退出行為對賣方心理狀態(tài)的改變，使用出價(jià)函數(shù)來進(jìn)行決策。重點(diǎn)研究協(xié)商策略、算法和協(xié)議，從而提高協(xié)商效率和協(xié)商滿意度。

1 多Agent協(xié)商策略和算法

1.1出價(jià)函數(shù)

在自動協(xié)商中，Agent一般會有兩種出價(jià)方式：一種是根據(jù)他們的效用函數(shù)，另一種是根據(jù)帶策略因子（Tactic factor）的出價(jià)函數(shù)。本文我們采用后者，雙方Agent按照輪次進(jìn)行出價(jià)來完成協(xié)商。引入文獻(xiàn)[6]中P.Faratin給出的Time-dependent tactics的指數(shù)函數(shù)形式，出價(jià)函數(shù)可定義如下：

并且

IPb，RPb和Db來分別表示買方（Buyer）的初始價(jià)、保留價(jià)和協(xié)商最長忍耐時(shí)間。同理，IPs，RPs和Ds分別表示賣方（Seller）的初始價(jià)、保留價(jià)和最大協(xié)商忍耐時(shí)間。fb(t)和fs(t)分別表示買賣雙方Agent的協(xié)商決策函數(shù)，其中φb和φs是雙方協(xié)商時(shí)間t與最大協(xié)商忍耐時(shí)間Di比值的指數(shù)，用來決定Agent的類型以及讓步的策略，稱為策略因子。

1.2協(xié)商策略

參與協(xié)商的Agent會根據(jù)剩余的協(xié)商時(shí)間[10～12]和協(xié)商資源[6]去改變自己的策略。對于不同的Agent協(xié)商時(shí)間有可能會不同，最大協(xié)商忍耐時(shí)間（Di）越大，Agent的協(xié)商壓力越小，價(jià)格讓步越小；協(xié)商時(shí)間距離Di越近，協(xié)商壓力越大，價(jià)格讓步越快。根據(jù)價(jià)格隨時(shí)間變化的趨勢，我們對協(xié)商所采用的讓步策略定義如下。

定義1折中策略：買賣雙方在協(xié)商過程中隨著時(shí)間的消耗，價(jià)格呈近似線性的增加和減少，期望在中期能夠達(dá)成一致。策略因子φi∈(0.5,2)。

定義2保守策略：在整個(gè)協(xié)商過程中，前期價(jià)格隨時(shí)間消耗變化緩慢，后期變化迅速，期望在預(yù)定的時(shí)間內(nèi)達(dá)成一致。策略因子φi∈[2,∞)。

定義3急躁策略：在整個(gè)協(xié)商過程中，價(jià)格在前期隨時(shí)間的消耗變化迅速，期望能在最短的時(shí)間內(nèi)達(dá)成一致，后期則變化趨于緩慢。策略因子φi∈(0,0.5]。

圖1 買方Agent不同策略下的出價(jià)曲線Fig.1 Offer curve of buyer Agent under different tactics

圖2 賣方Agent不同策略下的出價(jià)曲線Fig.2 Offer curve of saler Agent under different tactics

依據(jù)定義1～3，交易中Agent采用不同策略將會產(chǎn)生相應(yīng)的三種心理狀態(tài)：折中心理狀態(tài)、保守心理狀態(tài)和急躁心理狀態(tài)。心理狀態(tài)的變化很容易影響到Agent的最大協(xié)商忍耐時(shí)間。例如，急躁心理的變化將會促使Agent想要盡快結(jié)束協(xié)商，相應(yīng)的Di將會變小。同時(shí)，協(xié)商資源的多少也會對價(jià)格讓步策略產(chǎn)生影響。在多Agent協(xié)商中，最重要的協(xié)商資源就是參與協(xié)商的Agent。也就是說，與一個(gè)給定的Agent a進(jìn)行協(xié)商的Agent數(shù)目越多，Agent a可以達(dá)成交易的協(xié)商壓力越小。資源的變化將會在交易過程中影響和改變Agent心理狀態(tài)。

為了證明上面的觀點(diǎn)，我們考慮下面的例子。給定一個(gè)Agent a處于保守狀態(tài)，在交易開始階段有10個(gè)Agent試圖與a協(xié)商并達(dá)成交易，a使用保守策略來進(jìn)行報(bào)價(jià)。當(dāng)有1個(gè)Agent因?yàn)閳?bào)價(jià)或時(shí)間原因退出了交易，Agent a會感覺到協(xié)商的一點(diǎn)不順利，但不足以改變自己的策略和狀態(tài)。當(dāng)有4個(gè)Agent退出交易后，Agent a明顯的感到了協(xié)商的壓力，為了能夠與剩余的某一Agent達(dá)成最終的交易，它將會改變自己的狀態(tài)為折中狀態(tài)，并使用折中策略來進(jìn)行報(bào)價(jià)。若7個(gè)Agent退出時(shí)還未達(dá)成協(xié)議，Agent a心理狀態(tài)將會變得急躁，很想早些達(dá)成交易，則會采用急躁策略來進(jìn)行報(bào)價(jià)。

1.3協(xié)商協(xié)議

我們借助于基礎(chǔ)的回合制輪流出價(jià)協(xié)議[3]和Rahwan等人采用的一對多協(xié)商框架[13]。本文意在研究賣方信息不完全情況下的協(xié)商策略，我們假定買方Agent b可以準(zhǔn)確得知賣方Agent s每輪出價(jià)的信息，而賣方Agent s不能獲得Agent b每輪的出價(jià)信息。在一對一的協(xié)商中，規(guī)定買賣雙方在t∈T,T={0,1,…,min(Db,Ds)}的時(shí)間節(jié)點(diǎn)上根據(jù)出價(jià)函數(shù)Offerb(t)和Offers(t)分別給出價(jià)格pb(t)和ps(t)，由Agent b來決定是否接受Agent s提出價(jià)格。如果pb(t)≥ps(t)，協(xié)議達(dá)成一致；反之，如果pb(t)＜ps(t)，則沒有達(dá)成一致，雙方進(jìn)入下一輪。這種只基于時(shí)間約束的一對一出價(jià)規(guī)律相對簡單，并有很多相關(guān)研究[5,6]，故不在本文討論。

本文重點(diǎn)研究在賣方無法獲得買方價(jià)格的情況下，單賣方、多買方依據(jù)自己的協(xié)商策略在各輪次中進(jìn)行比價(jià)協(xié)商。前面一對一協(xié)商協(xié)議仍然可以應(yīng)用于一對多的情況。另外，我們還規(guī)定買方可以在協(xié)商最長忍耐時(shí)間Db到達(dá)后單方面退出協(xié)商。而買方的退出行為被賣方視為資源損失，當(dāng)達(dá)到某一臨界點(diǎn)（剩余Agent數(shù)量與總數(shù)量的比例）時(shí)，Agent s會改變自己的心理狀態(tài)，從而導(dǎo)致出價(jià)策略的改變。因此，買方動作Ab(t)被定義為：

我們把剩余的還處于談判狀態(tài)的買方Agent數(shù)量用|Nb(t)|2表示，那么賣方動作As(t)被定義為：1.4協(xié)商算法

根據(jù)上面提出的協(xié)商策略，給出一種“多買方單賣方”多Agent并發(fā)執(zhí)行的賣方協(xié)商算法如下：

Step1:多個(gè)買方Agent分別設(shè)置自己的初始價(jià)IPbi、保留價(jià)RPbi、協(xié)商策略Sbi以及最大協(xié)商忍耐時(shí)間Dbi。

Step2:賣方Agent設(shè)置自己的初始價(jià)IPs、保留價(jià)RPs、協(xié)商策略Ss[]、最大協(xié)商忍耐時(shí)間Ds、狀態(tài)變化臨界點(diǎn)Ci。其中賣方最初選擇協(xié)商策略Ss為保守策略，Ds大于所有的Dbi。然后Agent s最先選擇IPs報(bào)價(jià)，并告知所有的買方Agent，置時(shí)間t=1。

Step3:所有買方Agent接收到賣方報(bào)價(jià)后，根據(jù)自己的策略和出價(jià)函數(shù)選擇自己的動作Ab(t)：若t≥Db則退出寄存器中總數(shù)（count）加一，然后退出；若pb(t)≥ps(t)則接受報(bào)價(jià)，把協(xié)商次數(shù)、初始價(jià)、讓步過程和最終交易價(jià)格存入達(dá)成交易隊(duì)列，并向賣方發(fā)送成交消息；要不然，則把協(xié)商次數(shù)信息存入待協(xié)商隊(duì)列。

Step4:賣方Agent接受所有買方Agent消息，若得到成交消息則選擇最終交易價(jià)格最高的成交，然后結(jié)束談判。要不然檢查待協(xié)商隊(duì)列中是否還存在買方Agent，若存在則計(jì)算待協(xié)商Agent的總數(shù)（precount），并準(zhǔn)備與相應(yīng)的買方Agent進(jìn)行下一步協(xié)商，置時(shí)間t=t+1。

Step5:若，檢查count/(count+precount)是否達(dá)到臨界點(diǎn)Ci，來決定是否改變自己的狀態(tài)，從而改變策略因子的值。若狀態(tài)改變則把新策略加入Ss[]中，并采用新的出價(jià)函數(shù)計(jì)算報(bào)價(jià)，若狀態(tài)沒有改變則采用原出價(jià)函數(shù)計(jì)算報(bào)價(jià)，然后轉(zhuǎn)向Step3。

買方的協(xié)商算法簡單，只需要根據(jù)t時(shí)刻賣方的報(bào)價(jià)來選擇退出還是繼續(xù)談判。

2 算例分析

2.1參數(shù)設(shè)定與計(jì)算

在單賣方、多買方協(xié)商環(huán)境中，為了便于討論，我們假設(shè)買方對協(xié)商達(dá)成一致的積極性不高，因此心理狀態(tài)在協(xié)商過程中不改變；賣方在信息不完全情況下，有義務(wù)和耐心對買方進(jìn)行全程的服務(wù)，因此Ds不隨心理狀態(tài)改變而改變。這種假設(shè)也符合現(xiàn)實(shí)交易中買賣雙方所處的服務(wù)和被服務(wù)地位。算例數(shù)據(jù)是對Pillatt[14]中四個(gè)Agent參與協(xié)商（單買家，多賣家）的數(shù)據(jù)分析變換后得到的。

設(shè)定多個(gè)買方采用相同的IPb=550，RPb=650。采用不同的φb和Db分別為：Agent b1中φb1=0.2，Db1=10，策略Sb1=急躁；Agent b2中φb2=1，Db2=20，策略Sb2=折中；Agent b3中φb3=4，Db3=40，策略Sb3=保守。

為了分析賣方心理狀態(tài)改變對協(xié)商的影響效果，我們使用下面2個(gè)算例進(jìn)行比較：

算例1:設(shè)定賣方的IPs=700，RPs=450，Ds=40，初始策略Ss=保守策略,φs=4，無臨界點(diǎn)和策略的改變。

從圖3中可以看出：賣方Agent s以φs=4的出價(jià)函數(shù)分別向三個(gè)買方提供出價(jià)。協(xié)商過程簡單，最終Agent b1和Agent b2沒有能與Agent s達(dá)成交易，紛紛退出，Agent b3在t=34時(shí)接受ps(t)=569.50，達(dá)成交易。

算例2:設(shè)定賣方的IPs=700，RPs=450，Ds=40，初始策略Ss[0]=保守策略，φs=4，臨界點(diǎn)Ci有兩個(gè)：C1=1/3,φs變?yōu)?;C2=2/3,φs變?yōu)?.5。

從圖4中可以看出：賣方Agent s依據(jù)初始策略因子（φs=4）分別向三個(gè)買方提供出價(jià)。在t＜10之前，三個(gè)買方都不接受賣方的價(jià)格。當(dāng)t=10時(shí)，t=Db1，Agent b1退出協(xié)商并把count=count+1。當(dāng)t=11時(shí)，此時(shí)count/(count+precount)=1/(2+1)=1/3，Agent s遇到了第一個(gè)臨界點(diǎn)C1，φs變?yōu)?。此后當(dāng)t=15時(shí)，pb2(t)＞ps(t)，Agent b2接受價(jià)格ps(t)=606.25，并告知Agent s達(dá)成交易。

圖3 無策略變化的賣方與多個(gè)買家協(xié)商過程Fig.3 Seller and multiple buyers negotiation process without strategy change

圖4 φs改變的賣方與多個(gè)買家協(xié)商過程Fig.4 Seller and multiple buyers negotiation process with φs change

2.2結(jié)果分析

2.2.1 協(xié)商達(dá)成時(shí)間對于買賣雙方Agent協(xié)商達(dá)成時(shí)間越短越好，在協(xié)商中，賣方通過改變自己的策略來進(jìn)行價(jià)格階段式的逐步快速降低。圖3中賣方Agent在協(xié)商中始終沒有改變自己的策略，最終只能錯(cuò)過前兩個(gè)買方Agent，與Agent b3達(dá)成交易。對比圖4中改變策略的方式，策略因子的改變使得在錯(cuò)過Agent b1后，加快了價(jià)格的下降幅度，從而縮短了達(dá)成交易的時(shí)間。時(shí)間提升效益E(t)=(34-15)/34=55.88%。

2.2.2 成交價(jià)格成交雙方對于價(jià)格的衡量都是相對于初始價(jià)和保留價(jià)。也就是說，成交價(jià)格越靠近初始價(jià)協(xié)商效果越好。對于買方來說成交價(jià)越低越好，但綜合考慮到貨品質(zhì)量和買家的耐心程度，買家在規(guī)定時(shí)間內(nèi)能夠容忍在[IPb,RPb]中的價(jià)格，而不會感覺到效益的損失。對于賣方Agent來說成交價(jià)格越高越好，算例2的成交價(jià)顯然高于算例1。賣方價(jià)格提升效益E(p)=(606.25-569.50)/569. 50=6.4%。

2.2.3 買方滿意度買方與賣方的協(xié)商交易中對，除了對價(jià)格和時(shí)間的關(guān)注外，也去關(guān)注自我的心理滿足。最基本的滿足就是買方能夠在自己的承受范圍內(nèi)達(dá)成交易。算例2中買方流失數(shù)量（退出協(xié)商）少于算例1，使得更多的買方有機(jī)會體會自己的滿足感。

3 結(jié)語

本文提出了在“單賣方、多買方”的協(xié)商環(huán)境下，參與協(xié)商的買方人數(shù)資源對賣方產(chǎn)生心理上的影響和改變，心理狀態(tài)的改變則相應(yīng)的去促使自己通過修改策略因子來改變讓步策略，使得協(xié)商可以盡早的、多收益、雙方都滿意的情況下達(dá)成一致。將來的工作應(yīng)對時(shí)間約束、資源約束進(jìn)行更詳細(xì)的分類，并對多種約束合作協(xié)商下算法和模型的設(shè)計(jì)進(jìn)行討論。同時(shí)，針對賣方策略受心理狀態(tài)影響的特性，如何設(shè)計(jì)一個(gè)合理有效的學(xué)習(xí)策略來更加準(zhǔn)確、動態(tài)地找到臨界點(diǎn)和設(shè)置策略因子也是需要進(jìn)一步研究。

[1]Aknine S P,Shakun M F.An Extended Multi-agent Negotiation Protocol[J].International Journal on Autono mous Agents and Multi-agent Systems,2004(8):5-45

[2]Liang T P,Huang J S.A framework for applying intelligent agents to support electronic trading[J].Decision Support Systems,2000,28(4):305-317

[3]Osborne M J,RubinsteinA.Acourse in game theory[M].US:MIT press,1994

[4]Bichler M,Kaukal M,Segev A.Multi-attribute auctions for electronic procurement[C]//Proceedings of the first IBM IAC workshop on Internet based negotiation technologies,1999:18-19

[5]Kraus S,Wilkenfeld J,Zlotkin G.Multiagent negotiation under time constraints[J].Artificial intelligence,1995, 75(2):297-345

[6]Faratin P,Sierra C,Jennings N R.Negotiation decision functions for autonomous agents[J].Robotics and Autonomous Systems,1998,24(3):159-182

[7]Kraus S,Sycara K,Evenchik A.Reaching agreements through argumentation:a logical model and implementation[J]. Artificial Intelligence,1998,104(1):1-69

[8]張鴿,蔣國瑞,黃梯云.基于辯論的多Agent商務(wù)談判產(chǎn)生機(jī)制研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(2):594-597

[9]張宏,何華燦.多Agent自動協(xié)商策略和算法[J].計(jì)算機(jī)應(yīng)用,2006,26(8):1935-1937

[10]Kersten G E,Lai H.Satisfiability and completeness of protocols for electronic negotiations[J].European Journal of Operational Research,2007,180(2):922-937

[11]蔣勛,卞藝杰,薛國民.基于時(shí)間約束的雙邊多屬性自動協(xié)商模型研究[J].圖書情報(bào)工作,2011,55(6):86-90

[12]申靜,姚軍財(cái).基于歷史信息和時(shí)間約束的多Agent協(xié)商模型[J].陜西理工學(xué)院學(xué)報(bào):自然科學(xué)版,2009,25(1):51-55

[13]Rahwan I,Kowalczyk R,Pham H H.Intelligent agents for automated one-to-many e-commerce negotiation[C]// Australian Computer Science Communications.Australian Computer Society,Inc.,2002,24(1):197-204

[14]PILLATT FR,DE VIT AR,DA SILVEIRA JC.et al.Automating the Process of Negotiation in B2B Transacti ons through Software Agents[EB/OL].[2014-07-06].http://dinf.unicruz.edu.br/～pillatt/2004_iadis.pdf,2005

ADynamic Bilateral Negotiation Model between Multi-agent under Time and Resource Constraints

WANG Can1,2,LIANG Yong-quan1
1.Shandong University of Science and Technology,Qingdao266590,China
2.Shandong Institute of Commerce and Technology,Jinan250103,China

The bilateral bargaining agents with incomplete information will often fall into failure or cause poor utility of negotiation under time and resource constrains.We present a dynamic negotiation model between multi-agent under time and resource constraints by using offer function and offer curve to design agent's strategy and adopting special protocol to describe the influence of negotiating resource on mental states.As well as we also define three negotiating strategies named compromised、conservative and impatient strategies and rules of the strategy's changes with the transformation of mental states.Experiment shows that the proposed negotiating strategy and algorithm can improve the efficiency of negotiation, reduce the transaction price and enhance the satisfaction between buyers and seller under the“many buyers-to-one seller”model.

Dynamic negotiation;negotiating strategy;negotiating algorithm

TP18

A

1000-2324(2014)04-0605-05

2012-12-22

2013-03-12

山東省自然科學(xué)基金(ZR2012FM003,ZR2013FM023);青島市科技發(fā)展計(jì)劃項(xiàng)目(KJZD-13-29-JCH);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20133718110014)

王燦((1981-),男,博士研究生,主要研究方向:人工智能、Agent技術(shù).