摘要
Agent组织是合作求解的Agent集合,它描述了Agent与其承担的角色之间的关系.本文主要讨论Agent组织中的角色分配问题,提出了一种考虑了Role与Agent的偏好因素的扩充的角色分配二部图的概念,并指出Agent的角色分配问题就是在扩充的角色分配二部图上构造一个二部图的完美匹配.在Agent组织中,由于Agent及其组织的管理者都具有智能性,虽然Agent及其角色都可以得到匹配,但有些匹配不具有稳定性,因此自利的组织管理者和Agent都会在利益的驱动下背叛对方,从而导致组织破坏.紧接着本文讨论了稳定的扩充角色分配二部图的完美匹配集合,并在其上构造一个强稳定关系,从而将稳定匹配集和强稳定关系构造成一个代数结构———角色分配格,并在该格上构造了两个运算,并分析了两个运算之间的关系,由此得出角色分配格是一个分配格.最后分析了角色分配格中的几类特殊元———最大元、最小元、补元及交不可约元,并指出任何一个角色分配格都存在最大元和最小元,从而角色分配格是一个有界格,但并不是任何元都存在补元,从而角色分配格不一定是布尔代数,但是在给定特定的偏好下,即在特定的扩充角色分配二部图上,角色分配格可以构成布尔代数.对于交不可约元来说,它的重要意义就在于角色分配格中的任何元都可以表示成一些交不可约元的交,从而所有的交不可约元构成的集合是稳定匹配集的一个完备集.本文的结论是:扩充的角色分配二部图是Agent组织中的角色分配模型,其上所有的稳定匹配在强稳定关系下构成一个角色分配格,该格是一个有界分配格,但不一定是布尔代数,该格中的所有元都可以用其中的交不可约元来构造,从而为快速求解角色分配格做好了理论上的准备.
Agent organization is a set of agents which will solve a problem together. It describes the relation of roles and roles agents play. This paper discusses the role assigning problem, and brings forward the concept of role assigning bipartite graph considering the preference of agents and roles. The problem of role assigning is to construct a bipartite graph perfect matching in an extended role assigning bipartite graph. Because some matching is not stable and the agent and its administrator are intelligent, they can betray their participator to form a new matching out o{ their benefit. Subsequently, discuss stable role assigning set and construct a strong and stable relation on stable role assigning set. All the stable matching of role assigning bipartite graph form an algebra structure-role assigning lattice on condition of strong stable matching relation. Construct two operators on role assigning lattice and analyze their relation, point out that any one of operators is distributive to another, so role assigning lattice is a distributive lattice. Finally we discuss some special elements maximal element, minimal element, complement element and meet irreducible element, and make a conclusion that role assigning lattice is a bounded lattice because any role assigning lattice has a maximal element and minimal element, commonly, role assigning lattice is not a boolean algebra, because some elements of role assigning lattice have not complement element. But on condition of some special agents and role preference, role assigning lattice is also a boolean algebra. Considering meet irreducible element, its significance is any element of role assigning lattice can express by some meet irreducible elements through meet operation. So all the meet irreducible elements can form a set which is a complete group of all the stable matching. The conclusion of this paper is that extend role assigning bipartite graph is a mathematics model of role assigning problem on agent organization. The stable matching set and strong stable relation {orm a role assigning lattice which is bounded distributive lattice, but not boolean algebra. All the elements of role matching lattice can be constructed by meet irreducible elements, which makes the preparation for the constructing of role assigning lattice.
出处
《南京大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第2期179-187,共9页
Journal of Nanjing University（Natural Science）
基金
国家自然科学基金(60496323)
山东省自然科学基金(Y2005G13)
关键词
AGENT组织
角色分配格
有界分配格
特异元
交不可约元
agent organization, role matching lattice, bounded distributive lattice, special elements,meet irreducible elements
