Interactions in Multiagent Systems

The following sections are included:

• Foreword
• About the Editors
• About the Contributors
• Contents

Equilibrium-based multiagent reinforcement learning (MARL) is an important approach when deal with cooperative and competitive problems in multiagent systems. However, most of the equilibrium-based MARL algorithms cannot scale due to the high time complexity which arises for a large number of computationally expensive equilibrium computations. This problem can be solved from two aspects: 1) simplify equilibrium calculation and 2) reduce the number of equilibrium calculations. From these two points, this chapter will introduce three kinds of algorithms which can improve the scalability of MARL significantly.

Coordination of agent behaviors is crucial in multiagent systems (MASs). Social norm has been considered to be an effective tool to achieve coordination in MASs by placing social constraints on agent actions. The two distinct approaches for achieving social norms, i.e., the centralized top-down prescriptive approach and the decentralized bottom-up emerging approach, have their own inevitable advantages and disadvantages. How to make the best of these two approaches and circumvent their drawbacks is a challenging problem in norm research. In this chapter, we propose a hierarchical learning framework that creates a balance between centralized control and distributed interactions during norm emergence by integrating hierarchical supervision into distributed learning interactions. Experiments are carried out to explore the effectiveness of the proposed framework in various situations, and results verify that this compromising solution can be an effective mechanism for achieving coordination in MASs.

Compared to automated entities, human trustees have two distinct characteristics: (1) they are resource constrained (with limited time and effort to serve requests) and (2) their utility is not linearly related to income. Existing research in reputation-aware task delegation did not consider these two issues together. This limits their effectiveness in human–agent collectives such as crowdsourcing systems. In this chapter, we propose a distributed reputation-aware task allocation approach — RATA-NL — to address these issues simultaneously. It is designed to help an individual human trustee determine the optimal number of task requests to accept at each time step based on his situation to maximize his long-term well-being. The resulting task allocation maximizes social welfare through efficient utilization of the collective capacity of the trustees and provides provable performance guarantees. RATA-NL has been compared with five state-of-the-art approaches through extensive simulations based on human task delegation behavior abstracted from a user study involving over 100 trustees for eight weeks. The results demonstrated significant advantages of RATA-NL, especially under high workload conditions.

In environments where the effects of actions are stochastic and observations incomplete, partially observable Markov decision processes (POMDPs) serve as a powerful mathematical model for single-agent sequential decision making. However, solving POMDPs exactly is challenging in practice due to their computational complexity. Over the past 15 years, there have been significant advances in scalable approximate POMDP planning methods in both offline and online settings, allowing for important real-world applications. Finding optimal or near-optimal solutions to POMDPs is often challenging due to two distinct but related reasons: the curse of dimensionality, where the computation is directly related to the number of states, and the curse of history, where the number of distinct histories grows exponentially as the planning horizon increases. On the theoretical front, the covering number, a metric of capturing the curse of history, has been proposed as a complexity measure for approximate POMDP planning. This chapter begins by introducing the POMDP model, offline and online POMDP solution methods, followed by a description of theoretical results based on covering numbers.

In this chapter, we will introduce a class of algorithms which are extended from Q-learning (Watkins, 1989) based on gradient ascent policy. The objective of this chapter is to figure out the advantages, the disadvantages, and the scope of application of these algorithms by analyzing their design objectives and mathematical mechanism. This chapter is organized as follows: Section 5.1 gives a brief summary of gradient ascent based Q-learning algorithms, and classifies each algorithm according to their design purpose. In the rest of each section, we introduce and analyze one or two representative algorithms of each classification, respectively: Section 5.2 for the basic gradient ascent Q-learning algorithm, Infinitesimal Gradient Ascent algorithm (IGA) (Singh et al., 2000); Section 5.3 for WoLF-IGA (Bowling and Veloso, 2002) and WPL (Abdallah and Lesser, 2008); and Section 5.4 for the SA-IGA (Li et al., 2016).

Task allocation is an approach for coordination and cooperation in multiagent systems (MAS). It is an important problem in MAS research and is widely applied in fields such as multirobot systems, crowdsourcing, wireless sensor networks, web services, cloud computing, distributed intrusion detection, and so on. Intrinsically, task allocation is a class of optimization problems, that is, how to allocate a set of tasks to a MAS, in order to achieve a certain objective subject to some constraints. In different applications, the above problem can be formalized as different forms and requires different techniques for designing algorithms. The problem space of task allocation is rather large. However, due to the fact that task allocation is more or less independently studied in several subdomains of computer science and artificial intelligence, a global view on the problem space of task allocation is still missing. In this chapter, we briefly summarize several important directions of task allocation research, including taxonomy study; allocating tasks that are constrained, complex, or dynamic; allocating tasks to agents that are rational, dynamic, or connected by network; and control models which are currently a spectrum between centralized and distributed models. By the above work, we aim to correlate current task allocation research, preliminarily depict the problem space of task allocation, and locate problems that are well-studied or potentially interesting for future study.

Negotiation is any process through which the players on their own try to reach an agreement. It is a task that has a broad spectrum of practical applications to a variety of social, economic, and politic phenomena. When it comes to complicated problems such as negotiations with a large number of issues, finding good agreements is however a tough challenge for human beings, especially in the case that they lack negotiation experience, opponent information, and the available negotiation time is limited. In order to overcome these limitations, there exists considerable interest in automating their negotiation process by means of software agents to assist humans in the decision-making process. Automated negotiation therefore provides people with a realistic alternative solution. This chapter first overviews forms, protocols, and three main approaches of automated negotiation, namely, heuristic, game theoretic, and argumentation approaches. Then, the focus is on the study of complex practical negotiation — multiissue negotiation that runs under real-time constraints and in which the negotiating agents have no prior knowledge about their opponents’ preferences and strategies. Finally, two classes of state-of-the-art negotiation agents for complex negotiation are presented, namely, the agents based on regression techniques and the agents based on transfer learning to support its decision-making process during negotiation.

In multiagent systems, social norms play an important role in regulating agents’ behaviors and facilitating coordination among them and the functioning of agent societies. However, multiple computational agents usually need to coordinate their behaviors to emerge a norm that all agents follow during interactions where multiple norms coexist [Genesereth et al. (1988); Young (1996)]. Therefore, how to evolve one of the multiple norms efficiently and consistently in MAS is the key issue. Furthermore, agents may be faced with the high stochasticity of the environment. Agents need to effectively distinguish between the stochasticity of the environment and the exploration of other agents. Moreover, the possible large norm spaces also add an additional dimension of challenge for norm emergence. With the increase of action spaces, most of the existing approaches usually result in very slow norm emergence or even failure to converge. Hence, the emergence of norms in MASs promises to be a productive and challenging research area. In this chapter, we review a certain number of approaches aiming at addressing norm emergence which can be classified into three categories, i.e., top-down approaches, bottom-up approaches and hierarchical approaches. We also review the studies of fixed-strategy agents and discuss the influence of fixed-strategy agents in details.

Collective behaviors and phenomena can be often observed in complex systems of nature and human society. How to model and analyze the underlying mechanisms of collective behaviors is a crucial problem for the research of complex systems. The multiagent system (MAS) can be employed as an efficient tool to solve the problem. By designing appropriate large-scale MAS consisting of autonomous agents, the emergence of collective behaviors can be analyzed through the strategy diffusion convergence among the agents having simple interaction rules. In this chapter, we firstly introduce the diffusion convergence of collective behaviors and briefly describe typical diffusion convergence mechanisms in MAS, and then review the researches of diffusion convergence from the following perspectives: (a) the structured and non-structured diffusion convergence according to different organization forms of the systems; (b) the homogeneous and heterogeneous diffusion convergence according to the homogeneity or heterogeneity of influence; and (c) the neighboring and global diffusion convergence according to the difference of sensing scopes of agents.

In non-cooperative multiagent settings, methods for planning require modeling other agents’ possible behaviors. However, the space of these models — whether these are policy trees, finite-state controllers, or intentional models — is very large and thus arbitrarily bounded. This may exclude the true model or the optimal model. In this chapter, we present a novel iterative algorithm for online planning that considers a limited model space, updates it dynamically using data from interactions, and provides a provable and probabilistic bound on the approximation error. We ground this approach in the context of graphical models for planning in partially observable multiagent settings — interactive dynamic influence diagrams. We empirically demonstrate that the limited model space facilitates fast solutions and that the true model often enters the limited model space.

The following sections are included:

• Bibliography
• Index