Feasible Formation of Coalitions Among Autonomous Agents in Nonsuperadditive Environments

Cooperating and sharing resources by creating coalitions of agents are important ways for autonomous agents to execute tasks and to maximize payoff. Such coalitions will form only if each member of a coalition gains more by joining the coalition than it could gain otherwise. There are several ways of creating such coalitions and dividing the joint payoff among the members. In this paper we present algorithms for coalition formation and payoff distribution in nonsuperadditive environments. We focus on a low-complexity kernel-oriented coalition formation algorithm. The properties of this algorithm were examined via simulations. These have shown that the model increases the benefits of the agents within a reasonable time period, and more coalition formations provide more benefits to the agents.
     

Allocating the fixed cost based on data envelopment analysis in view of the Shapley value

This paper considers fixed cost allocation in view of cooperative game theory and proposes an approach based on data envelopment analysis while incorporating the perspectives of coalition efficiency and the Shapley value. To do this, we first build two models to evaluate coalition efficiencies before and after cost allocation, and we prove that all coalitions can be efficient after fixed cost allocation. Then, following the premise that each coalition makes itself efficient without reducing the efficiencies of other decision-making units' preallocation efficiency, we propose a model that determines the acceptable range of each coalition's allocated fixed cost. Furthermore, a model is constructed to determine the final cost allocation based on three principles: efficiency, monotonicity, and similarity. Moreover, the Shapley value is employed to obtain the cost allocated to each decision-making unit (DMU). The proposed approach considers the relationships among DMUs across their forming coalitions to determine their interaction types and then generates a fixed cost allocation result that possesses the features of the Shapley value. This process makes the fixed cost allocation more acceptable. Finally, a simple numerical example and an empirical case are provided to illustrate the calculation process of the proposed approach and compare our approach with the traditional methods.     

Agent long-term coalition credit

Agent trust researches become more and more important because they will ensure good interactions among the software agents in large-scale open systems. Moreover, individual agents often interact with long-term coalitions such as some E-commerce web sites. So the agents should choose a coalition based on utility and trust. Unfortunately, few studies have been done on agent coalition credit and there is a need to do it in detail. To this end, a long-term coalition credit model (LCCM) is presented. Furthermore, the relationship between coalition credit and coalition payoff is also attended. LCCM consists of internal trust based on agent direct interactions and external reputation based on agent direct observation. Generalization of LCCM can be demonstrated through experiments applied in both cooperative and competitive domain environment. Experimental results show that LCCM is capable of coalition credit computation efficiently and can properly reflect various factors effect on coalition credit. Another important advantage that is a useful and basic property of credit is that LCCM can effectively filter inaccurate or lying information among interactions.     

一种多agent网络中的分布式联盟形成算法

针对多agent系统的具体网络结构,提出一种分布式联盟形成算法。首先,每个agent向自己邻居任务中“信价比”最高的任务提出加入申请,形成潜在联盟;当联盟资源大于对应任务的资源需求时,使相应agent退出当前联盟,转而选择“信价比”次高的任务,从而提高联盟形成的可能性。仿真实验结果表明,与其他方法相比,所提出的算法能大幅提高系统效率和收益。     

基于模糊盟友关系的多主体系统长期联盟

多Agent系统形成长期联盟有利于降低计算复杂度、改善盟友关系．Breban和Griffiths等人研究了Agent之间的信任关系，但计算复杂度高、可行性差．长期联盟形成的模糊盟友关系的提出，可以合理地描述长期联盟Agent之间的盟友关系．通过监控Agent之间的交互更新盟友关系，降低盟友关系的计算复杂度，提高盟友关系计算的实时性，深化了Breban和Griffiths的工作，仿真结果验证了该方法的可靠性和实用性．该方法是长期联盟和组织的形成、演化研究基础．     

基于熟人的Agent联盟策略

在多ａｇｅｎｔ系统中,ａｇｅｎｔ可以通过协商形成联盟来完成任务求解。本文基于ａｇｅｎｔ联盟的统计规律提出了ａｇｅｎｔ熟人的概念,以熟人为基础的联盟策略可以有效减少联盟形成过程中的通讯开销和计算量。随后给出了一种基于该策略的联盟竞争任务的算法,该算法适用于动态,开放的环境、无中心控制,不存在通讯和计算瓶颈。     

基于直觉模糊关系的多主体联盟机制

提出一种新的联盟形成机制,以模糊数学为理论基础,着重研究个体间"满意度"和任务问"相似性"对联盟形成的影响,并将其表示为直觉模糊关系,通过模糊关系合成运算,得到新任务条件下agent间的"满意度".在此基础上,按不同阶段在不同范围内进行协商,从而有效降低了联盟形成的复杂性,并对其基本性质进行了分析.仿真实验表明了该机制的有效性.     

An Agent Based Framework for Internetware Computing

Internetware intends to be a paradigm of Web-based software development. At present, researches on Internetware have gained daily expanding attentions and interests. This paper proposes an agent based framework for Internetware computing. Four principles are presented that are followed by this framework. They are the autonomy principle, the abstract principle, the explicitness principle and the competence principle. Three types of agents with di?erent responsibilities are designed and specified. They are the capability providing agents, the capability planning agents and the capability consuming agents. In this sense, capability decomposition and satisfaction turns to be a key issue for this framework and becomes a communication protocol among these distributed and heterogenous agents. A capability conceptualization is proposed and based on the conceptualization, an agent coalition formation mechanism has been developed. This mechanism features that (1) all the participants make their one decisions on whether or not joining the coalition based on the capability realization pattern generated by the capability planning agents as well as the benefits they can obtain; and (2) the coalition selection is conducted by a negotiation process for satisfying the expectations of all the participants as the complexity of this problem has been proven to be NP-complete.     

一种基于理性Agent的任务求解联盟形成策略

联盟形成是多 agent 系统中的一个关键问题, 主要着眼于如何在联盟内 agent 间划分联盟的效用. 但已有策略无法摆脱搭便车问题, 尤其是额外效用的分配没有确切反映出各 agent 对于联盟贡献的差异性, 导致联盟潜在的不稳定. 本文给出了一种新的联盟形成的行为策略, 在公平分配原则和无妒忌原则的基础上, 提高了对额外效用分配的合理性, 在具有超加性的面向任务的领域中可以形成全局最优联盟, 并具有 Nash 均衡意义下的稳定性.     

Soft cooperation systems and games

A cooperative game for a set of agents establishes a fair allocation of the profit obtained for their cooperation. In order to obtain this allocation, a characteristic function is known. It establishes the profit of each coalition of agents if this coalition decides to act alone. Originally players are considered symmetric and then the allocation only depends on the characteristic function; this paper is about cooperative games with an asymmetric set of agents. We introduced cooperative games with a soft set of agents which explains those parameters determining the asymmetry among them in the cooperation. Now the characteristic function is defined not over the coalitions but over the soft coalitions, namely the profit depends not only on the formed coalition but also on the attributes considered for the players in the coalition. The best known of the allocation rules for cooperative games is the Shapley value. We propose a Shapley kind solution for soft games.