分布式语义自动协商与博弈机制研究

何雨青 朱俊武 李开荣

摘   要：文章在语义集成中引入了协商—博弈机制。各个Agents由于对领域的认知程度不同，因此，他们构建本体的“可信度”也是不同的。本体“可信度”越高，基于本体语义进行的检索准确率就越高。注意到每个Agent构建的本体与最终本体之间相似度可以看作Agent的收益，Agents之间如果通过协商与博弈来形成均衡，那么这个均衡就是所有Agents最能接受的结果，即“可信度”最高的本体。因此，模拟Agents之间的协商与博弈，构建更“可信”的本体，是完全可行的。

关键词：机制设计;协商—博弈;本体论

当两个本体之间存在语义关联时，就可以通过本体映射来将源本体的实例映射到目标本体，从而解决异构本体的共享和重用问题[1]。现有的本体映射工作并不能适用于那些规模较大的本体通信与共享的情况。本文拟设计一种新颖的本体合并方法，即把多个同主题领域的本体相结合，从而构建一个规模更大的语义共享空间。那就是本体构建者对领域知识的认知程度不同。由于认知程度较低的Agent所构建出的本体可信度不高，基于该现状，在设计的本体合并方法基础上增加“可信度”这样一个概念是必要的。

1    Agent协商系统

在Agent协商与博弈的情形下，大多数学者没有考虑到一个事实，那就是Agent之间的知识共享[2]。知识共享在协商—博弈系统中是非常有必要的，在协商阶段进行知识共享，可以更有效地达成一致，从而进行下一个阶段，即博弈阶段。在博弈阶段，知识共享能帮助博弈双方根据对方的知识对自己的策略进行改良，从而使得自己的收益尽可能大。

现有的Agent协商系统中，协商环境复杂、动态，Agent存在异构的可能。Agent对于特定的协议和领域具有依赖性，因此，没有办法让协议与领域无关[3]。选择适当的形式化工具描述协商Agent的交互和规则问题，使得协商Agent不依赖于特定的协商和博弈机制，如何做到领域无关是极具研究价值的问题[4]。

2    协商—博弈本体定义

协商和博弈本体（Negotiation/Game Ontology，NO/GO）分别对协商领域和博弈领域进行建模，提供了Agent互相之间可以进行共享的协商或博弈知识库，使得Agent与领域知识、协商/博弈协议相分离，能够在加入协商或博弈时自动获取该领域的知识本体并通过自身的推理机制解析协商/博弈对象、协商/博弈规则等通信信息从而更适用于语义Web的环境，能够参与任何领域的协商/博弈活动。

描述逻辑（Description Logic）是基于对象的知识表示的形式化，建立在概念和关系之上，具有很强的表达能力与可判定性。基于描述逻辑，将本体定义为一个二元组，即O=（Tbox，Abox），其中，Tbox=（C，R，P）包含内涵知识用于描述概念的一般性质，（C，R，P）分别表示概念（concept）、角色（role）和属性（property）;Abox包含外延知识（又称断言知识）用于某个特定个体。

构建了如下的协商本体和博弈本体，如图1—2所示。

协商Agent根据分工的不同可分为negotiation participant和negotiation host，两者分别表示协商的参与者以及对协商过程进行监督的主持者。其中，对协商过程进行监督的主持者又可根据职责分为3种类型：validator用于判定各个规则是否合理、updater用于更新反饋结果、agreement make根据终态时得到最终的协商结果。协商中有3种状态，即初始状态、中间状态和最终状态;当到达最终状态时，Agent达成一致（agreement）或矛盾（conflict），协商结束。这样一个由多种协商Agent进行的，从初始状态到最终状态的过程，就是一个完整的协商过程。

与协商本体类似，博弈的参与者有两类，分别是game host和game participant;策略是博弈参与者在进行博弈时可选择的行动集合，而策略的选择又依赖于外界环境和参与者所掌握的信息的影响。博弈规则是指博弈的约束，博弈规则指导着博弈的进行。收益是指参与者在采取策略后所得到的利益。

3    本体语义支撑的协商-博弈机制

自动协商的静态成分可以用一组协议来表示〈Pad，Pal，Pag〉，其中，Pad是规范如何进入（admission）协商的协议，Pal是协商进行时参与者如何交互（alternate）的协议，Pag是交互完成时，协商一致（agreement）如何生成的协议。

其中，对于任何的协议，都可以用元组〈Ag，Ac，W， w0，T，L，u〉进行刻画。其中，Ag={α1，…αn}是协议的使用者（Agent）的集合;Ac={Ac1，…Acn}是使用者的行动（Action）的集合，其中Aci是αi的行动结合;W是使用本协议交互过程中，可能达到的状态的集合;w0是初始的状态，T是结束时可能的终态集合;L是一组函数，其中，函数Li：W+＼T→2Aci被称为αi在特定状态下的合法行动集合，规定了αi在某一非终状态下能采取的交互行动。函数u：W×A1×…×An→W被称为状态更新函数，决定了在某个状态下，Agent采取一定的行动，状态将如何迁移。至此，本文定义了协商协议的统一理论数学模型。

但是此模型应用在开放市场协商环境下却有相当大的局限性，比如协议中的行动集合、状态集合可能非常庞大甚至是无限集。因此，状态迁移函数也有可能难以表示。这意味着很难对协商的领域知识进行扩充，使得协商协议的应用场景受限，可重用性下降。而且在现实的协商环境中，存在多个协议负责约束不同的交互，遵守协议存在时序关系，而此数学模型难以表达协议之间的层级、执行顺序关系，这对自动协商程序的编写造成了极大的困难。

而使用共享协商本体则可以很好地解决上述问题，对开放环境下的自动协商过程进行抽象分析，一般而言，自动协商可以被抽象成如下3个阶段：（1）协商申请阶段。（2）协商交互阶段。（3）协商一致生成阶段。

本体语义支撑的协商机制可用上述定义的协商本体进行描述，具体如下。

3.1  协商申请阶段

协商申请阶段可以被认为是有意愿参加本次协商的Agent和协商的主持者Host之间的沟通，具体体现为以下几点。

（1）Agent向协商主持者Host提交参加本次协商的申请。（2）Host收到申请后，向该Agent发送共享协商本体（包括：角色、协商协议等）。（3）Agent收到贡献给协商本体，对本体进行解析，向Host发送信任状，表明自己是否可以理解遵循协商本体所描述的协商规则。（4）Host收到Agent的信任状，根据信任状的结果判断是否允许该Agent参加本次协商，并将判决结果发送给Agent。（5）Agent收到Host的判决结果，如不同意，则离开本次协商;如同意，则进入本次协商，等待协商进入下一阶段。

具体的交互流程如图3所示。

3.2  协商交互阶段

在参与者通过协商申请阶段后，Host会根据start_rule判定协商何时进入协商交互阶段。协商交互阶段本质上是参与者之间、参与者与Host之间，Host内部各功能Agent之间，根据协商协议进行交互的过程。这样的过程可以抽象成如下6个基本步骤。

（1）Host的子Agent—terminal_checker会根据terminal_rule判断当前状态下协商是否达到了最终状态，如果是，则进入协商过程的第3阶段（协商一致生成状态），否则进入步骤2。

（2）Host根据voice_rule判定此时哪些协商参与者可以发言，协商参与者根据proposal_rule计算自己此时可以提出proposal。

（3）协商参与者向Host提交自己的proposal，Host只会接受在步骤2中判定的可以发言的协商者的消息。

（4）Host将接收到的proposal提交给子功能Agent—validator，validator根据proposal_rule判定各个参与者提交的proposal是否合理，如果不合理，则validator根据规则随机生成一个proposal并发送给Host，并重复步骤4。如果合理，则把proposal提交给Host的子功能Agent—updater，进入步骤5。

（5）updater收到validator发送的proposal，根据proposal对本次协商的各元素进行信息更新，并将更新结果反馈给Host。

（6）Host收到来自updater的更新反馈结果，Host根据inform_rule判断更新结果的哪些部分应该告诉哪些协商参与者，并告知相应的参与者，进入步骤1。

具体协商流程如图4所示。

3.3   协商一致生成阶段

当Host的子功能Agent—terminal_checker监测到协商当前达到了终态时，协商从交互阶段进入到协商一致生成阶段。在此阶段，Host的子功能Agent—agreement_maker根据终态时的proposal情况得到最终的协商结果（包括一致agreement和不一致confict两方面）。并将信息反馈给Host，由Host根据inform_rule告知协商的参与者。

4    结语

本文设计了分布式语义自动协商与博弈机制，能有效提高效率。但是，这仍是非常复杂的问题，仅设计出机制是不够的。后续还将对该机制进行求解。

[參考文献]

[1]KALFOGLOU Y，SCHORLEMMER M.Ontology mapping：the state of the art[J].Knowledge Engineering Review，2003（1）：1-31.

[2]NOY N.Semantic integration：a survey of ontology-based approaches[J].Sigmod Record，2004（4）：65-70.

[3]唐杰，梁邦勇，李涓子，等.语义Web中的本体自动映射[J].计算机学报，2006（11）：1956-1976.

[4]FRIDMAN N，MUSEN M A.Prompt：algorithm and tool for automated ontology merging and alignment[C].Austin：Proceedings of Seventeenth National Conference on Artificial Intelligence（AAAI—2000），2000.