中图法分类号: TP18 文献标识码: A

多 Agent 多问题协商模型🞼

王立春, xxx

(南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093); (南京大学 计算机科学与技术系,江苏 南京 210093)

E-mail: xxxxxx-xxxxxx@000.xxx xxxx://xxx.xxx.xxx.xx

摘要: 在多 agent 环境中,协商是多 agent 系统能够成功运转的关键.根据参与协商 agent 的数目和协商问题的数目,多 agent 环境中的协商可以分为双边-单问题协商、双边-多问题协商、多边-单问题协商、多边-多问题协商.前 3 种协商是多边-多问题协商在不同维上的简化.利用协商-协商过程-协商线程的概念建立了一个多边-多问题协商模型MMN(multi-agent multi-issue negotiation).该模型通过提供一个灵活的协商协议支持多agent 环境中的不同协商形式,并且支持 agent 在协商过程中的学习.

关 键 词: 多 agent 系统;多问题协商;协商协议

中图法分类号: TP18 文献标识码: A

随着 agent 技术的逐渐成熟,其应用领域不断扩展,目前在工业、商业、医疗、娱乐业均有成功范例[1].如何保证 agent 间能够有效、有序地进行交互是多 agent 系统成功运转的关键.Agent 间的交互有 3 种表现形式:合作(cooperation)、协调(coordination)、协商(negotiation).其中协商是最普遍、最主要的表现形式[2],因此协商是多 agent 系统技术的关键问题.

由于协商是个体间交互的表现形式,因此协商的研究内容必然包括对交互规则、决策模型、交互过程的研究,甚至包括对为个体间交互提供低层支持的通信的研究.这些问题并不是独立的,例如一个通用的协商模型需要考虑协商协议对协商策略选择的影响,从而为实际应用提供灵活的选择.目前对协商的研究往往只是单纯地研究协商协议[3~5]或者只重视研究协商策略[6~8],为数不多的对协商模型的研究大部分是在特定的应用系统中针对具体协商背景的研究,因此通用性较差.有关协商模型的理论研究是博弈论领域的主要工作[9],该领域的协商模型有两类:面向结果的协商模型和面向过程的协商模型.

Xxxxxxxx 针对电信服务行业的特点在 ADEPT 系统[10]中定义了一个面向服务的协商模型[11],并在以后的工作中对其进行了改进[12],对 agent 的协商结构增加了相对复杂的思考机制(deliberative mechanism),用于决定 offer 的内容.Zeng[13]等人基于对协商过程中 agent 学习的重要性的认识设计了协商模型 Bazaar,这是一个基于连续决策过程的协商模型,其目的在于支持 agent 在协商过程的学习.Bazaar 支持 Bayesian 学习.在 Bazaar中,agents 之间的协商只是简单地交换 offer 的过程.

本文给出了一个多 agent 多问题协商模型 MMN(multi-agent multi-issue negotiation),该模型包含了一个通用协商协议 GP,且 agent 以 Q-学习及 Bayesian 学习作为在线学习机制参与协商,GP 在不同约束条件下表现为不同的协商协议.MMN 支持多回合协商,且支持协商过程中的学习.其中协商协议 GP 是对经典合同网协议[7]的扩展,可支持多种协商形式.在经典合同网协议中,Contractor 在表达合作意愿后只被允许与Manager 进行一次通

🞼 收稿日期: 2000-11-01; 修改日期: 2001-06-15

基金项目: 国家自然科学基金资助项目(69905001);国家教育部博士点基金资助项目(97028428)

作者简介: 王立春(1975－),女,黑龙江绥化人,博士,讲师,主要研究领域为多 Agent 系统,分布式人工智能;xxx(1938－),男,

安徽合肥人,教授,博士生导师,主要研究领域为分布式人工智能.

信,而 GP 允许双方进行多次通信.另外,GP 支持协商过程中对协商问题的变更.比较而言,我们给出的协商模型

MMN 更具有一般性.

本文将给出协商模型 MMN 的定义,包括协商模型的形式化描述、协商协议的定义、agent 协商结构的定义、协商模型对学习机制的支持.最后给出实验结果.

1 协商模型 MMN

一个好的协商模型应具有如下能力:① 能够有效地描述协商问题;② 能够支持多 agent 学习(因为各种理论研究及对人类实际协商过程的观察表明,学习有利于增加 agent 在协商过程中的收益);③ 能够描述协商的动态特性;④ 能够为 agent 提供灵活的、可选择的协商协议;⑤ 协商过程需要的计算资源是有限的.基于以上设计思想和目标,本文定义了多 agent 多问题协商模型 MMN.该模型是面向多 agent、多问题协商场景的协商模型,支持多种形式的协商并支持协商过程中的学习.

MMN 中的一个协商过程可以看做是由某个 agent 发起的该 agent 与一个或多个 agent 间协商线程的集合.多 agent 系统内的协商则是若干个这样的协商过程的集合.MMN 的协商过程可以定义为一个六元组:〈G,S,O,A,Time,Thread,Protocol〉.

• G:参与协商过程的 agent 集合.包含在一个协商过程中的 agent 有两类:proposer 和 participator,proposer

是发起协商的 agent,participator 是响应 proposer 的有协商意愿的 agent.

• S:协商问题是若干协商主题的集合.单问题协商中只有一个协商主题,而多问题协商中至少有两个协商主题.

• O:协商主题的范畴集合,是参与协商 agent 间的公共知识.协商主题 Si 对应的范畴 Oi 包括对协商主题及允许取值范围的定义,其中取值范围是所有允许取值的集合,记为 Vi.

• A:agent 在 offer 中提供的 agreement 的有效取值集合.协商过程中,agent 关于协商主题的有效取值 agreement∈{(aj)|aj∈Vi,i∈S},即 agreement 的值可以是协商问题中各协商主题允许取值的任意组合.另外还有一类特殊的 agreement 值:accept 表示接受当前 offer 的值;quit 表示退出协商;reject 表示拒绝当前 offer 的取值,这个 offer 可能导致协商线程重新开始;change 表示希望变更协商问题,则集合 A 应该包括以上所有允许取值:A={(aj)|aj∈Vi,i∈S}∪{accept,quit,reject,change}.

• Time:以顺序排列的自然数表示的系统时钟.

d →e

• Thread:Thread(i,j,u)(i∈G,j∈G,uk∈S,k∈N)表示 agent i 和 agent j 间关于问题 u 的协商.用 xt

表示 agent d

d1→e1

在时刻 t 向 agent e 发送的 offer 中 agreement 的值,则 Thread(i,j , u)= {xt1

, x

t2

d2 →e2

,..., xtn |

d →e

n n

dk →ek

dk,ek∈{i,j},tm∈Time, xtm ∈ A(u)}是满足以下条件的 offer 序列:

① 两个 agent 交替向对方发送 offer,即 ei≠di 且 ei=di+1;

② 序列中的元素是按时间顺序排列的,即如果 k≤l 则 tk≤tl.

当 x

tn

dk →ek

并行的.

∉ {accept, quit} 时,我们称协商线程是活动的(active).协商线程间既可以是串行的也可以是

• Protocol:协商协议.我们提出了一个通用的协商协议 GP(如图 1 所示),根据协商协议 GP,agent i 发起的协商过程按照以下步骤进行:

① 在协商开始前,agent i 提出协商问题并向其他 agent 发送有关消息.消息的发送既可以采用广播形式,也可以采用 agent-agent 方式;

② 收到消息的某个agent j 回信表明其协商意愿,如果agent i 在限定时间内没有收到有协商意愿的消息,则可以选择再次发送消息或结束(图 1 中用虚线注明);

③ agent i 与有协商意愿的agent 进入协商状态,双方交换initial offer.Initial offer 的交换根据实际应用的需要,可以是双方同时交换或者只是由其中一方向另一方提供 initial offer;

④ 收到对方的 offer 后,agent 需要做出应答.如果 agent 以 accept 或 quit 作为应答,则协商结束;如果

agent 希望变更(增加或减少)协商问题,则以change 作为应答;如果agent 希望重新开始协商,则以

reject 作为应答;agent 也可以选择以协商问题的值作为应答.如果 agent 选择以协商问题的值作为应答,则交换 offer 的过程一直持续到 agreement∈{accept,quit,reject,change}或协商过程结束.

d →e

在协商限定时间内,如果 xtm

k k

∉ {accept, reject, change, quit}则 xtm

一定属于 A(u).如果到达协

dk →ek

商限定时间,则无论 offer 的取值如何,协商均自动结束.

协商协议 GP 是对经典合同网协议[7]xxx.XX 通过定义消息“change”支持协商过程中协商问题的变更;通过定义消息“reject”支持多回合协商.协商协议 GP 对 agent 在协商过程中学习的支持将结合下一节定义的协商结构给予说明.

Subject change⑦

Offer

⑤

counter-offer

Subject

②

①

④

⑧

Start

Willing

Initial offer

Accept quit

  S1 (proposer)

propose

(participator)

S2

   S3

time is out

End

Reject⑥

No willing③

No willing

①发起协商 agent 提出协商主题,②接到协商主题的 agent 表明自己有参加协商的意愿,③接到协商主题的 agent 表明自己没有参加协商的意愿,④参与协商 agents 间交换初始 offer,⑤参与协商 agents 间交换 offer,⑥参与协商的一方拒绝对方的 offer,

⑦参与协商的一方提出变更协商主题,⑧参与协商的一方接受对方的 offer,或参与协商的一方退出,或到达协商限定时间.

Fig.1 Negotiation protocol GP

图 1 协商协议 GP

2 Agent 协商结构

在协商协议GP 的约束下,agent i 通过与其他agent 交换offer 进行协商,agent i 的协商结构可以用四元组〈H,

Ω,P,Strategy-model〉加以描述:

H:协商历史集合,

i

H = {(hm ( j, u))

m=1,2,...,M

| ∀i, j ∈ A,uk ∈ S, m ∈ N , 且存在Thread(i, j, u)}.

i

历史 hM ( j, u) 是长度为 M 的 offer 序列,该序列的元素是 agent i 收到的 agent j 向其发送的关于协商问题 u

的 offer,即 hm ( j, u) = xtk (u), t

∈ Time, m ≤ M .历史集合 H 具有以下特性:

i j→i k

i

∅∈H,即空序列也是历史;

i

如果(hm ( j, u))

m=1,2,...,M

∈ H ,且 L≤M,则(hm ( j, u))

m =1,2,..., L

∈ H ;

如果(hm ( j, u)) ∈ H ,且 hM ( j, u) ∈{accept, quit} ,则当 m<M 时 hm ( j, u) ∉{accept, quit} ;

i

i

历史(hm ( j, u))

m =1,2,..., M

m =1,2,..., M

i

i

∈ Z 当且仅当不存在 M+1 满足(hm ( j, u))

i

m =1,2,..., M +1

∈ Z ,其中 Z 是终止历史集合,Z 的

元素称为终止历史.

Ω:agent 关于环境或其他 agent 的知识.例如关于环境参数的知识;关于其他 agent 决策模型、协商类型等的信念.

P:agent 在每个协商决策点拥有的知识.定义在Ω上的主观概率分布 Ph,i(Ω)用于表示 agent i 在协商历史为

h 的协商决策点拥有的知识.

Strategy-model:协商策略模型.agent i 的协商策略是指 agent i 在协商过程中提供的 offer 序列,从对手的角度观察就是 agent i 的协商历史,且该历史属于集合 Z.协商策略模型的主要任务就是决定如何根据协商环境及协商对手制定 offer.实际应用中用户可以选择为 agent 配置不同的协商策略模型.

根据协商协议 GP 的定义 agent 在协商过程中交替交换 offer,在这个过程中 agent 在每次收到协商对手的 offer 后按照一定的策略决定 offer 值作为应答,因此 agent 参与协商的过程也可以看做是一个连续决策的过程.协商结构定义了协商历史 H、agent 关于环境和其他 agent 知识Ω、每个决策点的知识 P 用于支持协商过程中的学习.在每个协商线程,agent 根据 initial offer 形成初始知识,初始知识是定义在Ω上的概率分布,在后续协商中 agent 根据对方的 offer 值对其进行更新得到每个决策点的知识.

前面我们分别给出了协商模型MMN 及协商结构的形式化描述,其中协商模型MMN 采用“协商-协商过程-协商线程”的层次概念描述多 agent 间的协商.在与 Xxxxxxxx 的协商模型比较时,我们指出 MMN 是支持多回合协商的多agent 多问题协商模型.MMN 对多回合协商的支持体现在agent 间可以通过发送消息“reject”开始新一轮的协商(如图 1 所示).多问题协商体现在这样几个方面:① 协商问题 S 满足|S|>1;② agent 间交换的agreement相应地包括多个协商主题的有效取值,至于这些有效值的交换形式,例如是一次交换还是分多次交换,取决于低一层的通信机制的定义;③ agent 的协商策略模型因为需要权衡不同协商主题间的优先关系而不同于单问题协商情况.解决多问题协商的关键在于如何xx各协商主题间的收益,从而使得协商问题的收益满足设计的要求,经济学领域用来解决这类问题的理论称为多属性效应理论 MAUT(multi-attribute utility theory)[14].对 MMN来说,多问题协商意味着配置适当的协商策略模型及下层通信机制的支持.

3 多 agent 系统中的协商

根据本文协商模型 MM N 的定义,agent i 发起的关于问题 u 的协商过程 Proc e ss( i , u )=

∪

x∈participator (i,u )

Thread(i, x, u) ,多 agent 系统 E 中的协商 Negotiation(E) = ∪ Pr ocess(i, u) .下面给出关于协商、协商

i∈E u⊆S

过程、协商线程的伪码描述,其中将要用到的符号标记的含义如下:Negotiation(E)表示多 agent 系统 E 中的协商,其中 E 既表示多agent 系统又表示系统内agent 集合;Process(i,u)表示agent i 发起的关于问题 u 的协商过程;u(i)表示 u 是由 agent i 提出的协商问题;Thread(i,x,u)表示 agent i 和 agent x 间关于问题 u 的协商,u=u(i);Proposer 是发起协商的 agent 集合;propose(u)表示提出问题 u 的 agent;Participator(i,u)是响应 agent i 提出的协商问题 u 的 agent 的集合;opponent(i)表示 agent i 的协商对手;KE 表示关于环境的知识,KA 表示关于其他 agent 的知识, KE ⊆ Ω , KA ⊆ Ω .下面给出协商、协商过程、协商线程的伪码描述.

Negotiation(E)

{Proposer=∅; S=∅;

While |E|>1 //当系统中只有一个 agent 时,系统中不存在 agent 间的协商

If i=propose(u) //系统中任一 agent 提出协商问题

{Proposer=Proposer∪{i};

S=S∪{u};

Process(i,u);

}}

Process(i,u)

{Participator(i,u)=∅;

S(i)=u(i);

time=0, time∈Time;

protocol=GP; // 协商协议是由发起协商的 agent 指定的

send(i,u,message-deadline); // agent i 发送关于问题 u 的消息,并指定有效响应时间

While time<message-deadline

If receive(x,u,willingness) //agent x 表明了对问题 u 的协商意愿

{Participator(i,u)=Participator(i,u)∪{x}; Thread(i,x,u);

}

If agent i receive nothing about u

Agent i has to decide send message again or quit

//在有效响应时间内没有收到其他 agent 的表明协商意愿的消息,提出协商问题的 agent 需要选择重发消息或放弃协商意图} Thread(i,x,u)

{k,opponent(k)∈{i,x} and k≠opponent(k); t=0, t∈Time;

deadline∈Time; //为了避免无休止协商定义协商的期限时间,t=deadline 时协商无条件终止

k

ht = ∅ ; //协商开始前 agent k 的历史为空 create(k,initial-offer); // agent k 的协商策略模型生成 initial-offer send(k,opponent(k),initial-offer); //向协商对手发送 initial-offer

While t<deadline

While k receive offer f

Case f:

{content(f)=accept: negotiation is end; content(f)=quit: negotiation is end;

content(f)=reject: Thread(i,x,u); //开始新一轮的协商 content(f)=change(u,u′): Process(opponent(k),u′);

//对方希望变更协商问题 u,在协商协议 GP 的定义中协商线程被终止并开始新的协商过程.实际上也可以考虑在不终止当前协商的情况下考虑新的协商问题.

default:

{if f is initial-offer

then P∅(KX)=estimation(f);

h

//agent 根据接收到的 initial-offer 形成关于对手协商类型的先验知识,在这一步 agent 可以通过 Q-学习以协商的收益作为激励学习如何根据 initial-offer 猜测对手的协商类型.

else

P

t

h ,k

(K X ) = update(P t −1 ,k

(K X ), f ) ; //根据协商历史更新知识

//这里的关于对手协商类型的知识用定义在 KX 上的概率表示, KX ⊆ KA create(k,offer); // agent k 的协商策略模型生成 offer send(k,opponent(k),offer); //向协商对手发送 offer

}}}

在协商过程中,agent 用信念描述关于对手协商类型的知识,并用 Bayesian 信念网表达 agent 的信念,使用 Bayesian 更新规则进行知识的更新.Zeng[13]等人的实验表明,Bayesian 学习可以解决这个问题.在以前的研究工作中,我们[15]曾经研究过在由于环境参数的改变导致的动态协商环境中agent 的学习(即对 KE 的学习).在MMN模型中存在协商过程的另外一种动态特性,由于协商对手的变化导致的协商过程的动态变化.另外在协商线程中使用的 Bayesian 学习的学习效率是与 P∅有关的,在 Zeng[13]的实验中,P∅是随机分布的.而实际上对应不同的协商对手即使其initial offer 相同,相应的 P∅也有可能不同.我们在模型应用过程中使用强化学习[16]解决这个问题,即agent 通过强化学习机制来学习如何根据对手initial offer 形成 P∅,这样形成的 P∅更接近实际情况,并将提高 Bayesian 学习的学习效率.

4 相关工作比较

Xxxxxxxx[5]的协商模型也将协商看做是 agents 间交换 offer 的过程,但该模型并不支持协商过程中问题的变更.Agents 在协商之初确定了协商问题 J,并将问题 J 分为两个部分 Jcore 和 J ┐core.Agent 在时刻 t 的协商问题是 Jt=Jcore∪Jc,其中 Jc⊆J ┐core,且在 offer 中只对属于 Jt 的问题给出有效值,而对属于 J−Jt 的问题并不提供 offer 值.策略机制中的add 和remove 是针对 Jt−Jcore 的,add 将属于 J ┐core 而不属于 Jt 的问题加入 Jt,remove 将属于 Jt−Jcore

的问题从 Jt 中删除.因此 add 和 remove 策略机制并不改变协商问题 J,只是对将要提供 offer 值的问题的选择.另外,Jennings[5]的协商模型不是严格意义上的多回合协商模型,多回合协商应该是两个 agents 间协商线程的反复.

本文的协商协议通过定义 change 为有效 offer 值支持协商过程中协商问题的变更.协商结构中对协商策略只是抽象地给出了一个strategy-model,主要是考虑到协商模型MMN 是用于面向agent 开发环境AODE 的协商问题,而开发环境侧重解决领域级问题求解能力.协商策略留待应用系统开发人员根据实际问题配置.考虑到人类社会的协商过程中协商问题变更及协商反复的情况,协商协议定义了 change 消息和 reject 消息.协商问题的变更将导致agent 重新发布消息,因为变更问题后可能有比当前参与协商的agent 更为合适的其他agent,因此协议 GP 定义change 消息是协商从状态 S3 迁移到状态 start.协议 GP 的reject 消息支持协商线程的重新开始,也是对多回合协商的支持.

Zeng[13]的协商模型支持协商过程中的学习,但在该模型中,agent 之间只是简单地交换 offer,由于协商协议过于简单而无法完成复杂的协商任务.

5 实验与结论

本文给出的协商模型MMN 利用“协商-协商过程-协商线程”的概念描述多agent 多问题协商,并且通过提供一个灵活的协商协议支持多 agent 环境中的多种协商形式.另外,该模型还支持 agent 在协商过程中的学习.

我们已经在 AODE 系统中应用了协商模型 MMN,AODE 系统是我们研制的一个面向 agent 的智能系统开发环境,我们使用 AODE 生成多个 agent 构造试验环境,并在该环境中模拟 agent 之间的买/卖行为.协商协议如图 1 所示,agent 采用第 2 节的协商结构,agent 的知识定义为关于对手保留价的知识,agent 间的交易过程实际上就是协商的过程.

在试验过程中,agent 既可以扮演 proposer 的角色发起协商,也可以充当 participator 参与其他 agent 发起的协商.任意两个 agent 之间的协商构成一个协商线程;任一agent 发起的协商是一个协商过程,该协商过程可以包含若干线程;整个系统中的协商问题是该系统内所有协商过程的集合.Agent 在协商过程中的学习任务包括根据对手的初始报价猜测对手的保留价即 KX,agent 根据协商线程的结果利用Q-学习的奖惩机制学习对手的初始报价与其保留价的关系;agent 在每次收到对手新的报价之后,更新关于对手保留价的知识.试验表明,模型MMN能够较好地解决试验环境中的协商问题.与只使用Bayesian 学习的agent[13]相比,Q-学习与Bayesian 学习的联合使用可以提高 agent 的协商性能.对初始报价-保留价关系的学习可以提高 agent 的协商效率,这意味着 MMN 在电子市场的应用将改进市场的收益.

今后,我们将继续研究学习机制对 agent 协商效率的影响,例如研究在 agent 提出 initial-offer 阶段学习机制对 agent 策略选择的影响.

References:

[1] Xxxxxxxx, X., Xxxxxxx, X., Xxxxxxxxxx, X. Multi-Agent system: which research for which applications. Robotics and Autonomous Systems, 1999,27(1,2):91~106.

[2] Xxxxxxxx, N.R., Xxxxxxx, S., Xxxxxx, C., et al. Automated negotiation. In: Proceedings of the 5th International Conference on the Practical Application of Intelligent Agents and Multi-Agent Systems (PAAM-2000). 2000. 23~30. xxxx://xxx.xxx.xxxxx.xx. uk/~nrj/download-files/xxxx0000-xxx.xx.

[3] Xxxxx, X.X. The contract net protocol: high-level communication and control in a distributed problem solver. IEEE Transactions on Computers, 1980,C29(12):1104~1113.

[4] Xxxxx, X., Xxxxxx, N., Xxxxxx, K.P. Reaching agreements through argumentation: a logical model and implementation. Artificial Intelligence, 1998,104(1,2):1~69.

[5] Xxxxxx, N., Xxxxxxxx, N.R. Efficient mechanisms for the supply of services in multi-agent environments. International Journal of Decision Support Systems, 2000,28(1,2):5~19.

[6] Xxxxxxx, X., Xxxxxxxxxxx, J.S. A domain theory for task-oriented negotiation. In: Proceedings of the 13th International Joint Conference of Artificial Intelligence. 1993. 416~422. xxx://xxx.xxxx.xx.xx/xxxxx/xxxx/xxxxx00xxxxx.xx.xx.

[7] Xxxxxxxx, X.X. Negotiation among self-interested computationally limited agents [Ph.D. Thesis]. Amherst, MA: University of Massachusetts, 1996.

[8] Xxxxx, N., Xxxxxx, C., Xxxxxxxx, N.R. Determining successful negotiation strategies: an evolutionary approach. In: Proceedings of the 3rd International Conference on Multi-Agent Systems (ICMAS’98). 1998. 182~189. xxxx://xxx.xxx.xxxxx.xx.xx/

~nrj/download-files/xxxxx.xx.

[9] Xxxxxxx, M.J., Xxxxxxxxxx, X. A Course in Game Theory. MIT Press, 1994.

[10] Xxxxxxxx, N.R., Xxxxxxx, X., Xxxxxxx, X.X., et al. Agent-Based business process management. Journal of Cooperative Information Systems, 1996,5(2,3):105~130.

[11] Xxxxxx, C., Xxxxxxx, D., Xxxxxxxx, N.R. A service-oriented negotiation model between autonomous agents. In: Proceedings of the 8th European Workshop on Modeling Autonomous Agents in a Multi-agent World (MAAMAW’97). 1997. 17~35. xxxx://xxx.xxx. xxxxx.xx.xx/xxxx/xxxxxxxx-xxxxx/XxxxxxXxxxxxxXxxxxxxx.xx.

[12] Xxxxxxx, P., Xxxxxx, C., Xxxxxxxx, N.R., et al. Designing responsive and deliberative automated agents. In: Proceedings of the AAAI Workshop on Negotiation: Settling Conflicts and Identifying Opportunities. 1999. 12~18. xxxx://xxx.xxx.xxxxx.xx.xx/xxxx/ download-files/xxxx-xx-xxxxxx.xx.

[13] Xxxxxx, K., Xxxx, Da-jun. Bayesian learning in negotiation. In: Working Notes of the AAAI 1996 Stanford Spring Symposium Series on Adaptation, Co-Evolution and Learning in Multi-Agent Systems. 1996. xxxx://xxx.xx.xxx.xxx/xxxx/xxx_0000.xxxx.

[14] Xxxxxx, X., Xxxxxx, X. Decisions with Multiple Objectives: Preferences and Value Trade Offs. Xxxx Wiley & Sons, 1976.

[15] Xxxx, Xx-xxxx, Xxx, Xxxx, Xxxx, Xxx-xx. Reinforcement learning based negotiation model in AODE. Journal of Nanjing University, 2001,37(2):135~141 (in Chinese).

[16] Xxxxxxxxx, L.P. Reinforcement learning: a survey. Journal of Artificial Intelligence Research, 1996,4:237~285.

附中文参考文献:

[15] 王立春,xx,xxx.AODE 中基于强化学习的 Agent 协商模型.南京大学学报,2001,37(2):135~141.

A Multi-Agent Multi-Issue Negotiation Model🞼

XXXX Xx-xxxx, CHEN Shi-xx

(Xxxxx Xxx Xxxxxxxxxx xxx Xxxxx Xxxxxxxx Xxxxxxxxxx, Xxxxxxx Xxxxxxxxxx, Xxxxxxx 000000, Xxxxx); (Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)

E-mail: xxxxxx-xxxxxx@000.xxx xxxx://xxx.xxx.xxx.xx

Abstract: Negotiation is a key issue for success application of multi-agent technology. According to the number of agents and the number of issues, negotiation in multi-agent environment can be classified as bilateral-single issue negotiation, bilateral-multi-issue negotiation, multi-lateral-single issue negotiation, and multi-lateral-multi-issue negotiation. The previous three scenarios are the simple forms of the multi-lateral-multi-issue negotiation. A multi-lateral-multi-issue negotiation model is provided to divide negotiation into processes, which are further divided into threads. The model defines a flexible negotiation protocol, which makes it easy to support different negotiation scenarios. And the model also supports the learning capability of participating agents.

Key words: multi-agent system; multi-issue negotiation; negotiation protocol

🞼 Received November 1, 2000; accepted June 15, 2001

Supported by the National Natural Science Foundation of China under Grant No.69905001; the National Research Foundation for the Doctoral Program of Higher Education of China under Grand No.97028428