Signaling game based strategy of intrusion detection in wireless sensor networks

As Wireless Sensor Networks (WSNs) become increasingly popular, it is necessary to require Intrusion Detection System (IDS) available to detect internal malicious sensor nodes. Because sensor nodes have limited capabilities in terms of their computation, communication, and energy, selecting the profitable detection strategy for lowering resources consumption determines whether the IDS can be used practically. In this paper, we adopt the distributed-centralized network in which each sensor node has equipped an IDS agent, but only the IDS agent resided in the Cluster Head (CH) with sufficient energy will launch. Then, we apply the signaling game to construct an Intrusion Detection Game modeling the interactions between a malicious sensor node and a CH-IDS agent, and seek its equilibriums for the optimal detection strategy. We illustrate the stage Intrusion Detection Game at an individual time slot in aspects of its player’s utilities, pure-strategy Bayesian–Nash equilibrium (BNE) and mixed-strategy BNE. Under these BNEs the CH-IDS agent is not always on the Defend strategy, as a result, the power of CH can be saved. As the game evolves, we develop the stage Intrusion Detection Game into a multi-stage dynamic Intrusion Detection Game in which, based on Bayesian rules, the beliefs on the malicious sensor node can be updated. Upon the current belief and the Perfect Bayesian equilibrium (PBE), the best response strategy for the CH-IDS agent can be gained. Afterward, we propose an intrusion detection mechanism and corresponding algorithm. We also study the properties of the multi-stage dynamic Intrusion Detection Game by simulations. The simulation results have shown the effectiveness of the proposed game, thus, the CH-IDS agents are able to select their optimal strategies to defend the malicious sensor nodes’ Attack action.     

Dynamics in network interaction games

We study the convergence times of dynamics in games involving graphical relationships of players. Our model of interaction games generalizes a variety of recently studied games in game theory and distributed computing. In a local interaction games each agent is a node embedded in a graph and plays the same 2-player game with each neighbor. He can choose his strategy only once and must apply his choice in each 2-player game he is involved in. This represents a fundamental model of decision making with local interaction and distributed control. Furthermore, we introduce a generalization called 2-type interaction games, in which one 2-player game is played on edges and possibly another game is played on non-edges. For the popular case with symmetric 2 ×?2 games, we show that several dynamics converge to a pure Nash equilibrium in polynomial time. This includes arbitrary sequential better-response dynamics, as well as concurrent dynamics resulting from a distributed protocol that does not rely on global knowledge. We supplement these results with an experimental comparison of sequential and concurrent dynamics.     

Design of a class of nonlinear consensus protocols for multi‐agent systems

This paper investigates the consensus problem for multi‐agent systems and presents a class of nonlinear consensus protocols. First, we reveal some structure property of the corresponding Laplacian matrix by decomposing the interaction graph into strongly connected components. Then, by means of the input‐to‐state stability and algebraic graph theory, we propose a framework to prove consensus for multi‐agent systems with nonlinear protocols. In particular, we prove that consensus can be always reached in systems of single‐integrator agents with a directed communication topology containing a spanning tree, provided the nonlinear protocol is an odd and increasing function. The nonlinear consensus protocols proposed in this paper include the classical linear consensus protocol as a special case, and may have a wide range of applications, including consensus with faster convergence rates and with bounded control inputs. Copyright © 2012 John Wiley & Sons, Ltd.     

COMPLIANCE VERIFICATION OF AGENT INTERACTION: A LOGIC-BASED SOFTWARE TOOL

In open societies of agents, where agents are autonomous and heterogeneous, it is not realistic to assume that agents will always act so as to comply with interaction protocols. Thus, the need arises for a formalism to specify constraints on agent interaction, and for a tool able to observe and check for agent compliance with interaction protocols. In this paper we present a JAVA-PROLOG software component built on logic programming technology, which can be used to verify compliance of agent interaction to protocols, and that has been integrated with the PROSOCS platform.     

A two-layered multi-agent reinforcement learning model and algorithm

Multi-agent reinforcement learning technologies are mainly investigated from two perspectives of the concurrence and the game theory. The former chiefly applies to cooperative multi-agent systems, while the latter usually applies to coordinated multi-agent systems. However, there exist such problems as the credit assignment and the multiple Nash equilibriums for agents with them. In this paper, we propose a new multi-agent reinforcement learning model and algorithm LMRL from a layer perspective. LMRL model is composed of an off-line training layer that employs a single agent reinforcement learning technology to acquire stationary strategy knowledge and an online interaction layer that employs a multi-agent reinforcement learning technology and the strategy knowledge that can be revised dynamically to interact with the environment. An agent with LMRL can improve its generalization capability, adaptability and coordination ability. Experiments show that the performance of LMRL can be better than those of a single agent reinforcement learning and Nash-Q.     

A protocol for multi-agent negotiation in a group-choice decision making process

Negotiation is one of the most important features of agent interactions found in multi-agent systems, because it provides the basis for managing the expectations of the individual negotiating agents, and it enables selecting solutions that satisfy all the agents as much as possible. In order for negotiation to take place between two or more agents there is need for a negotiation protocol that defines the rules of the game; consequently, a variety of agent negotiation protocols have been proposed in literature. However, most of them are inappropriate for Group-Choice Decision Making (GCDM) because they do not explicitly exploit tradeoff to achieve social optimality, and their main focus is solving two-agent negotiation problems such as buyer–seller negotiation. In this paper we present an agent negotiation protocol that facilitates the solving of GCDM problems. The protocol is based on a hybrid of analytic and artificial intelligence techniques. The analytic component of the protocol utilizes a Game Theory model of an n-person general-sum game with complete information to determine the agreement options, while the knowledge-based (artificial intelligence) component of the protocol is similar to the strategic negotiation protocol. Moreover, this paper presents a tradeoff algorithm based on Qualitative Reasoning, which the agents employ to determine the ‘amount’ of tradeoff associated with various agreement options. Finally, the paper presents simulation results that illustrate the operational effectiveness of our agent negotiation protocol.     

Specification and Verification of Agent Interaction using Social Integrity Constraints

In this paper we propose a logic-based social approach to the specification and verification of agent interaction. We firstly introduce integrity constraints about social acts (called Social Integrity Constraints) as a formalism to express interaction protocols and to give a social semantics to the behavior of agents, focusing on communicative acts. Then, we discuss several possible kinds of verification of agent interaction, and we show how social integrity constraints can be used to verify some properties in this respect. We focus our attention on static verification of compliance of agent specifications to interaction protocols, and on run-time verification, based on agents' observable behavior. We adopt as a running example the NetBill security transaction protocol for the selling and delivery of information goods.     

一个基于“恶意对抗”的公平交互机制的研究

由于多代理交互环境中检测机制、仲裁机制的有限性,合法代理将注定要遭受损失。针对上述现象,该文提出了一个恶意对抗机制（Malice-Antagonized Interaction Mechanism,MAIM),即在该机制下,交互代理双方都允许表现出恶意行为,以期实现交互的公平性,为了分析MAIM机制的可行性,文中应用游戏理论对MAIM在几种典型的游戏中实现交互公平性的情况进行了分析和证明。最终得出结论：在完善信息的纯策略游戏中,MAIM无法实现交互的公平性,而在完美信息的混合策略游戏、不完美信息的顺序游戏和同时决策游戏中,能实现交互的公平性。从而从理论上证明了恶意对抗机制的可行性。     

Multi-agent graphical games with input constraints: an online learning solution

This paper studies an online iterative algorithm for solving discrete-time multi-agent dynamic graphical games with input constraints. In order to obtain the optimal strategy of each agent, it is necessary to solve a set of coupled Hamilton-Jacobi-Bellman (HJB) equations. It is very difficult to solve HJB equations by the traditional method. The relevant game problem will become more complex if the control input of each agent in the dynamic graphical game is constrained. In this paper, an online iterative algorithm is proposed to find the online solution to dynamic graphical game without the need for drift dynamics of agents. Actually, this algorithm is to find the optimal solution of Bellman equations online. This solution employs a distributed policy iteration process, using only the local information available to each agent. It can be proved that under certain conditions, when each agent updates its own strategy simultaneously, the whole multi-agent system will reach Nash equilibrium. In the process of algorithm implementation, for each agent, two layers of neural networks are used to fit the value function and control strategy, respectively. Finally, a simulation example is given to show the effectiveness of our method.     

基于极大熵原理的理性公平交换协议

鉴于理性交换协议是一个动态博弈模型, 在完全不完美动态博弈中, 力图用极大熵原理来解决理性参与者的策略行为推断问题。扩展了一个基于信息熵的理性交换协议模型, 通过引入期望收益函数和期望均衡的方法, 给出理性交换协议的公平性描述; 基于最大熵原理构造了一种新的理性交换协议; 证明该协议的安全性, 利用博弈树的方法对整个交换过程进行分析并给出了理性公平性证明, 结果表明该协议能达到期望均衡。协议交换过程中无须可信第三方的参与, 该协议实现了理性公平性且具有更好的适应性。     

Analysis of Authentication Protocols in Agent-Based Systems Using Labeled Tableaux

The study of multiagent systems (MASs) focuses on systems in which many intelligent agents interact with each other using communication protocols. For example, an authentication protocol is used to verify and authorize agents acting on behalf of users to protect restricted data and information. After authentication, two agents should be entitled to believe that they are communicating with each other and not with intruders. For specifying and reasoning about the security properties of authentication protocols, many researchers have proposed the use of belief logics. Since authentication protocols are designed to operate in dynamic environments, it is important to model the evolution of authentication systems through time in a systematic way. We advocate the systematic combinations of logics of beliefs and time for modeling and reasoning about evolving agent beliefs in MASs. In particular, we use a temporal belief logic called TML$^{+}$ for establishing trust theories for authentication systems and also propose a labeled tableau system for this logic. To illustrate the capabilities of TML$^{+}$, we present trust theories for several well-known authentication protocols, namely, the Lowe modified wide-mouthed frog protocol, the amended Needham–Schroeder symmetric key protocol, and Kerberos. We also show how to verify certain security properties of those protocols. With the logic TML$^{+}$ and its associated modal tableaux, we are able to reason about and verify authentication systems operating in dynamic environments.      

Automated contracting in distributed manufacturing among independent companies

So far, most distributed scheduling systems have been designed for cooperative agents, and are inappropriate for self-interested agents, as for example in inter-firm interactions such as virtual enterprises. This paper discusses issues that arise in extending automated contracting to operate among such self-interested agents. We construct a leveled commitment contracting protocol that allows self-interested agents to efficiently accommodate future events by having the possibility of unilaterally decommitting from a contract based on local reasoning. A decommitment penalty is assigned to both agents in a contract to be freed from the contract, an agent only pays this penalty to the other party. It is formally shown that this leveled commitment feature in a contracting protocol increases Pareto efficiency of deals and can enable contracts by making them individually rational when no full commitment contract can. The analysis is nontrivial because self-interested agents decommit manipulatively a Nash equilibrium analysis of the decommitting game is necessary.     

Evolutionary asymmetric games for modeling systems of partially cooperative agents

Based on the tenet of Darwinism, we propose a general mechanism that guides agents (which can be partially cooperative) in selecting appropriate strategies in situations of complex interactions, in which agents do not have complete information about other agents. In the mechanism, each participating agent generates many instances of itself to help it find an appropriate strategy. The generated instances adopt alternative strategies from the agent's strategy set. While all instances generated by different agents meet randomly to complete a task, every instance adapts its strategy according to the difference between the average utilities of its current strategy and all its strategies. We give a complete analysis of the mechanism for the case with two agents when each agent has two strategies, and show that by the tenet of Darwinism, agents can find their appropriate strategies through evolution and adaptation: 1) if dominant strategies exist, then the proposed mechanism is guaranteed to find them; 2) if there are two or more strict Nash equilibrium strategies, the proposed mechanism is guaranteed to find them by using different initial strategy distributions; and 3) if there is no dominant strategy and no strict Nash equilibrium, then agents will oscillate periodically. Nevertheless, the mechanism allows agent designers to derive the appropriate strategies from the oscillation by integration. For cases with two agents when each agent has two or more strategies, it is shown that agents can reach a steady state where social welfare is optimum.     

DECLARATIVE SPECIFICATION OF FAULT TOLERANT AUCTION PROTOCOLS: THE ENGLISH AUCTION CASE STUDY

Auction mechanisms are nowadays widely used in electronic commerce Web sites for buying and selling items among different users. The increasing importance of auction protocols in the negotiation phase is not limited to online marketplaces. In fact, the wide applicability of auctions as resource‐allocation and negotiation mechanisms have also led to a great deal of interest in auctions within the agent community. A challenging issue for agents operating in open Multiagent Systems (such as the emerging semantic Web infrastructure) concerns the specification of declarative communication rules which could be published and shared allowing agents to dynamically engage well‐known and trusted negotiation protocols. To cope with real‐world applications, these rules should also specify fault tolerant patterns of interaction, enabling negotiating agents to interact with each other tolerating failures, for instance terminating an auction process even if some bidding agents dynamically crash. In this paper, we propose an approach to specify fault tolerant auction protocols in open and dynamic environments by means of communication rules dealing with crash failures of agents. We illustrate these concepts considering a case study about the specification of an English Auction protocol which tolerate crashes of bidding agents and we discuss its properties.     

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study concurrent dynamics that emerge when each agent samples another agent and possibly imitates this agent’s strategy if the anticipated latency gain is sufficiently large. Our focus is on convergence properties. We show convergence in a monotonic fashion to stable states, in which none of the agents can improve their latency by imitating others. As our main result, we show rapid convergence to approximate equilibria, in which only a small fraction of agents sustains a latency significantly above or below average. Imitation dynamics behave like an FPTAS, and the convergence time depends only logarithmically on the number of agents. Imitation processes cannot discover unused strategies, and strategies may become extinct with non-zero probability. For singleton games we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton games with linear latency functions. We concentrate on the case of symmetric network congestion games, but our results do not use the network structure and continue to hold accordingly for general symmetric games. They even apply to asymmetric games when agents sample within the set of agents with the same strategy space. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a pure Nash equilibrium.     

基于本体和会话策略的多主体交互协议描述方法

提出一种基于会话策略的多主体交互协议描述方法。交互协议中的消息用言语动作来表示,这些言语动作被描述为WS-Agreement的schema;会话策略则描述了消息传递的流程以及交互过程中的上下文信息,如参与者属性、时间阈值等等,所有这些会话策略组成了一个多主体交互协议;采用本体描述语言OWL作为会话策略的表示语言。这种方法使得主体在一个开放、动态的环境中可以灵活地选择交互协议。     

一种基于社会承诺的Agent组织模型OMSC

多Agent领域所面临的一个重大的挑战是解决开放异质的多Agent系统中自治Agent间的协调问题。多Agent为了协调它们之间的活动,需要进行交互。社会承诺作为一种通信和交互机制,为自治的多Agent提供了一种协调的途径。然而,仅靠交互难以实现多Agent间的协调。Agent组织作为一种协调模型可以有效地控制多Agent间的交互与合作。论文将社会承诺和Agent组织两种协调机制相结合,提出一种基于社会承诺的Agent组织模型OMSC,分析了Agent如何用社会承诺进行推理以及基于社会承诺的多Agent系统并给出了一个实例,为多Agent间的协调提供了一种新的方法。     

Attribute-based authentication for multi-agent systems with dynamic groups

In a multi-agent system, agents are required to interact in order to exchange information. To achieve a reliable information exchange, a sound security protection must be in place. Unfortunately, security and privacy in multi-agent systems have not drawn adequate attention. They have been actually ignored or mistreated in most proposed multi-agent protocols. We observe that security and privacy issues are indeed not trivial and cannot be resolved with traditional security mechanisms, if agents are not trusted each other and their privacy must be protected. In this paper, we propose a secure multi-agent protocol that captures several most important security properties including agent privacy, data confidentiality, and agent authenticity. Intuitionally, we allow each agent in a group to hold a set of policy attributes. To access a protected data set, an agent must hold a correct policy attribute. In other words, the private information between two agents can be exchanged, if and only if the policy attribute embedded in the transmitted message matches that held by the receiver. In case of mismatching attributes, the private information of the corresponding agent will not be revealed to their counterpart. The proposed scheme is formalized with a sound cryptographic algorithm with a rigorous security proof.     

Robust artificial life via artificial programmed death

We propose a novel approach to self-regenerating continuously-operating systems. Such systems provide best-case solutions in security surveillance or decision making centers. We introduce HADES, a self-regenerating system whose agents acknowledge their “citizenship” or faithfulness to the good of the system and are able to monitor their environment. When agents of HADES find irregularity in themselves they first try to repair, and will self-kill if repair fails. When an agent senses that there are persistent malfunctioning agents in its environment, it sends messages to entice them to self-kill. The neighbors then proceed to generate new healthy agents to replace the killed agent. We experiment with HADES on various impairments including the most difficult one of excessive regeneration of irregular aggressive agents. These agents may use all of the system's resources and thus take over the system, reminiscent of biologically grown tumors. We study how irregular growth may occur and then develop protocols of killing these agents to optimize the system's longevity. While some of the inspiration is from the immune system and tumor therapy, we contribute to the field of AI by introducing protocols for system robustness via the notion of active citizenship and the fundamental property of programmed death.