基于时间和资源约束的多Agent双边动态协商模型

王灿,梁永全

基于时间和资源约束的多Agent双边动态协商模型

王灿1,2,梁永全1

1.山东科技大学,山东青岛266590
2.山东商业职业技术学院,山东济南250103

双边交易Agent协商中因时间、资源的约束和信息的不完整，常会导致协商失败和较差的协商收益。本文提出一种基于时间和资源双重约束下的多Agent动态协商模型，使用出价函数和出价曲线来设定Agent的策略，采用特定协议来描述协商资源对心理状态的影响。同时，定义了折中、保守和急躁三种协商策略以及心理状态对策略的动态改变规则。通过实验模拟发现“多买方、单卖方”条件下，采用提出的协商策略和动态协商算法能够提高协商效率、降低成交价格和提升协商满意度。

动态协商；协商策略；协商算法

Agent技术已被越来越多的应用在工业和经济等领域[1]。协商已成为一种重要Agent之间的交互形式。自动协商则是Mulit-Agent之间就共同关注问题达成一致时所进行的行动过程。Agent所能采取的行动包括：提议、反提议、让步、退出和同意等。通过智能Agent技术能够在买卖双方交易中更好的做出决定和减少资源消耗已经被很多研究证明[2]。然而，由于信息不完整和时间、资源约束会经常导致agent的交易策略很难被设计。同时，交易策略不仅会影响协商的效率，也会影响到买卖双方的收益。

在以前研究中，一些关于协商的理论背景已经广泛被讨论，特别是在博弈论中[3]。一些研究[4]采用效用函数来衡量协商效果，从而达到协商的一致。Kraus在1995年提出时间约束下的Mulit-agent协商，把时间折算因子和延时损耗作为协商策略进行研究[5]。P.Faratin和N.R.Jennings则使用了出价函数结合策略因子来进行价格协商[6]。Kraus在原有研究基础上，把心理模型引入到协商谈判中[7]，认为协商高效的条件是能够理解和影响其他Agent的信念、愿望、目标和意图。蒋国瑞、黄梯云等提出了一个Agent的多目标优化模型谈判过程控制，使用状态机协议以及基于冲突解决策略进行辩论协商[8]。张宏、何华灿把协商策略分为了急躁型、节约型和折中型，并使用可连续变化的曲线簇来描述基于BDI理论的协商策略[9]。

综观上述研究，本文在构建在信息不完整条件下“单卖方、多买方”双边自动协商模型中，考虑时间约束和资源约束的影响，关注买方退出行为对卖方心理状态的改变，使用出价函数来进行决策。重点研究协商策略、算法和协议，从而提高协商效率和协商满意度。

1 多Agent协商策略和算法

1.1出价函数

在自动协商中，Agent一般会有两种出价方式：一种是根据他们的效用函数，另一种是根据带策略因子（Tactic factor）的出价函数。本文我们采用后者，双方Agent按照轮次进行出价来完成协商。引入文献[6]中P.Faratin给出的Time-dependent tactics的指数函数形式，出价函数可定义如下：

并且

IPb，RPb和Db来分别表示买方（Buyer）的初始价、保留价和协商最长忍耐时间。同理，IPs，RPs和Ds分别表示卖方（Seller）的初始价、保留价和最大协商忍耐时间。fb(t)和fs(t)分别表示买卖双方Agent的协商决策函数，其中φb和φs是双方协商时间t与最大协商忍耐时间Di比值的指数，用来决定Agent的类型以及让步的策略，称为策略因子。

1.2协商策略

参与协商的Agent会根据剩余的协商时间[10～12]和协商资源[6]去改变自己的策略。对于不同的Agent协商时间有可能会不同，最大协商忍耐时间（Di）越大，Agent的协商压力越小，价格让步越小；协商时间距离Di越近，协商压力越大，价格让步越快。根据价格随时间变化的趋势，我们对协商所采用的让步策略定义如下。

定义1折中策略：买卖双方在协商过程中随着时间的消耗，价格呈近似线性的增加和减少，期望在中期能够达成一致。策略因子φi∈(0.5,2)。

定义2保守策略：在整个协商过程中，前期价格随时间消耗变化缓慢，后期变化迅速，期望在预定的时间内达成一致。策略因子φi∈[2,∞)。

定义3急躁策略：在整个协商过程中，价格在前期随时间的消耗变化迅速，期望能在最短的时间内达成一致，后期则变化趋于缓慢。策略因子φi∈(0,0.5]。

图1 买方Agent不同策略下的出价曲线Fig.1 Offer curve of buyer Agent under different tactics

图2 卖方Agent不同策略下的出价曲线Fig.2 Offer curve of saler Agent under different tactics

依据定义1～3，交易中Agent采用不同策略将会产生相应的三种心理状态：折中心理状态、保守心理状态和急躁心理状态。心理状态的变化很容易影响到Agent的最大协商忍耐时间。例如，急躁心理的变化将会促使Agent想要尽快结束协商，相应的Di将会变小。同时，协商资源的多少也会对价格让步策略产生影响。在多Agent协商中，最重要的协商资源就是参与协商的Agent。也就是说，与一个给定的Agent a进行协商的Agent数目越多，Agent a可以达成交易的协商压力越小。资源的变化将会在交易过程中影响和改变Agent心理状态。

为了证明上面的观点，我们考虑下面的例子。给定一个Agent a处于保守状态，在交易开始阶段有10个Agent试图与a协商并达成交易，a使用保守策略来进行报价。当有1个Agent因为报价或时间原因退出了交易，Agent a会感觉到协商的一点不顺利，但不足以改变自己的策略和状态。当有4个Agent退出交易后，Agent a明显的感到了协商的压力，为了能够与剩余的某一Agent达成最终的交易，它将会改变自己的状态为折中状态，并使用折中策略来进行报价。若7个Agent退出时还未达成协议，Agent a心理状态将会变得急躁，很想早些达成交易，则会采用急躁策略来进行报价。

1.3协商协议

我们借助于基础的回合制轮流出价协议[3]和Rahwan等人采用的一对多协商框架[13]。本文意在研究卖方信息不完全情况下的协商策略，我们假定买方Agent b可以准确得知卖方Agent s每轮出价的信息，而卖方Agent s不能获得Agent b每轮的出价信息。在一对一的协商中，规定买卖双方在t∈T,T={0,1,…,min(Db,Ds)}的时间节点上根据出价函数Offerb(t)和Offers(t)分别给出价格pb(t)和ps(t)，由Agent b来决定是否接受Agent s提出价格。如果pb(t)≥ps(t)，协议达成一致；反之，如果pb(t)＜ps(t)，则没有达成一致，双方进入下一轮。这种只基于时间约束的一对一出价规律相对简单，并有很多相关研究[5,6]，故不在本文讨论。

本文重点研究在卖方无法获得买方价格的情况下，单卖方、多买方依据自己的协商策略在各轮次中进行比价协商。前面一对一协商协议仍然可以应用于一对多的情况。另外，我们还规定买方可以在协商最长忍耐时间Db到达后单方面退出协商。而买方的退出行为被卖方视为资源损失，当达到某一临界点（剩余Agent数量与总数量的比例）时，Agent s会改变自己的心理状态，从而导致出价策略的改变。因此，买方动作Ab(t)被定义为：

我们把剩余的还处于谈判状态的买方Agent数量用|Nb(t)|2表示，那么卖方动作As(t)被定义为：1.4协商算法

根据上面提出的协商策略，给出一种“多买方单卖方”多Agent并发执行的卖方协商算法如下：

Step1:多个买方Agent分别设置自己的初始价IPbi、保留价RPbi、协商策略Sbi以及最大协商忍耐时间Dbi。

Step2:卖方Agent设置自己的初始价IPs、保留价RPs、协商策略Ss[]、最大协商忍耐时间Ds、状态变化临界点Ci。其中卖方最初选择协商策略Ss为保守策略，Ds大于所有的Dbi。然后Agent s最先选择IPs报价，并告知所有的买方Agent，置时间t=1。

Step3:所有买方Agent接收到卖方报价后，根据自己的策略和出价函数选择自己的动作Ab(t)：若t≥Db则退出寄存器中总数（count）加一，然后退出；若pb(t)≥ps(t)则接受报价，把协商次数、初始价、让步过程和最终交易价格存入达成交易队列，并向卖方发送成交消息；要不然，则把协商次数信息存入待协商队列。

Step4:卖方Agent接受所有买方Agent消息，若得到成交消息则选择最终交易价格最高的成交，然后结束谈判。要不然检查待协商队列中是否还存在买方Agent，若存在则计算待协商Agent的总数（precount），并准备与相应的买方Agent进行下一步协商，置时间t=t+1。

Step5:若，检查count/(count+precount)是否达到临界点Ci，来决定是否改变自己的状态，从而改变策略因子的值。若状态改变则把新策略加入Ss[]中，并采用新的出价函数计算报价，若状态没有改变则采用原出价函数计算报价，然后转向Step3。

买方的协商算法简单，只需要根据t时刻卖方的报价来选择退出还是继续谈判。

2 算例分析

2.1参数设定与计算

在单卖方、多买方协商环境中，为了便于讨论，我们假设买方对协商达成一致的积极性不高，因此心理状态在协商过程中不改变；卖方在信息不完全情况下，有义务和耐心对买方进行全程的服务，因此Ds不随心理状态改变而改变。这种假设也符合现实交易中买卖双方所处的服务和被服务地位。算例数据是对Pillatt[14]中四个Agent参与协商（单买家，多卖家）的数据分析变换后得到的。

设定多个买方采用相同的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=保守。

为了分析卖方心理状态改变对协商的影响效果，我们使用下面2个算例进行比较：

算例1:设定卖方的IPs=700，RPs=450，Ds=40，初始策略Ss=保守策略,φs=4，无临界点和策略的改变。

从图3中可以看出：卖方Agent s以φs=4的出价函数分别向三个买方提供出价。协商过程简单，最终Agent b1和Agent b2没有能与Agent s达成交易，纷纷退出，Agent b3在t=34时接受ps(t)=569.50，达成交易。

算例2:设定卖方的IPs=700，RPs=450，Ds=40，初始策略Ss[0]=保守策略，φs=4，临界点Ci有两个：C1=1/3,φs变为1;C2=2/3,φs变为0.5。

从图4中可以看出：卖方Agent s依据初始策略因子（φs=4）分别向三个买方提供出价。在t＜10之前，三个买方都不接受卖方的价格。当t=10时，t=Db1，Agent b1退出协商并把count=count+1。当t=11时，此时count/(count+precount)=1/(2+1)=1/3，Agent s遇到了第一个临界点C1，φs变为1。此后当t=15时，pb2(t)＞ps(t)，Agent b2接受价格ps(t)=606.25，并告知Agent s达成交易。

图3 无策略变化的卖方与多个买家协商过程Fig.3 Seller and multiple buyers negotiation process without strategy change

图4 φs改变的卖方与多个买家协商过程Fig.4 Seller and multiple buyers negotiation process with φs change

2.2结果分析

2.2.1 协商达成时间对于买卖双方Agent协商达成时间越短越好，在协商中，卖方通过改变自己的策略来进行价格阶段式的逐步快速降低。图3中卖方Agent在协商中始终没有改变自己的策略，最终只能错过前两个买方Agent，与Agent b3达成交易。对比图4中改变策略的方式，策略因子的改变使得在错过Agent b1后，加快了价格的下降幅度，从而缩短了达成交易的时间。时间提升效益E(t)=(34-15)/34=55.88%。

2.2.2 成交价格成交双方对于价格的衡量都是相对于初始价和保留价。也就是说，成交价格越靠近初始价协商效果越好。对于买方来说成交价越低越好，但综合考虑到货品质量和买家的耐心程度，买家在规定时间内能够容忍在[IPb,RPb]中的价格，而不会感觉到效益的损失。对于卖方Agent来说成交价格越高越好，算例2的成交价显然高于算例1。卖方价格提升效益E(p)=(606.25-569.50)/569. 50=6.4%。

2.2.3 买方满意度买方与卖方的协商交易中对，除了对价格和时间的关注外，也去关注自我的心理满足。最基本的满足就是买方能够在自己的承受范围内达成交易。算例2中买方流失数量（退出协商）少于算例1，使得更多的买方有机会体会自己的满足感。

3 结语

本文提出了在“单卖方、多买方”的协商环境下，参与协商的买方人数资源对卖方产生心理上的影响和改变，心理状态的改变则相应的去促使自己通过修改策略因子来改变让步策略，使得协商可以尽早的、多收益、双方都满意的情况下达成一致。将来的工作应对时间约束、资源约束进行更详细的分类，并对多种约束合作协商下算法和模型的设计进行讨论。同时，针对卖方策略受心理状态影响的特性，如何设计一个合理有效的学习策略来更加准确、动态地找到临界点和设置策略因子也是需要进一步研究。

[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商务谈判产生机制研究[J].计算机应用研究,2011,28(2):594-597

[9]张宏,何华灿.多Agent自动协商策略和算法[J].计算机应用,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]蒋勋,卞艺杰,薛国民.基于时间约束的双边多属性自动协商模型研究[J].图书情报工作,2011,55(6):86-90

[12]申静,姚军财.基于历史信息和时间约束的多Agent协商模型[J].陕西理工学院学报:自然科学版,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

山东省自然科学基金(ZR2012FM003,ZR2013FM023);青岛市科技发展计划项目(KJZD-13-29-JCH);高等学校博士学科点专项科研基金(20133718110014)

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