A decision-theoretic approach to coordinating multiagent int

We describe a decision-theoretic method that an autonomous agent can use to model multiagent situations and behave rationally based on its model. Our approach, which we call the Recursive Modeling Method, explicitly accounts for the recursive nature of mul

A Decision-Theoretic Approach to Coordinating Multiagent Interactions

Piotr J. Gmytrasiewicz*, Edmund H. Durfee*, and David K. Wehe

*Department of Nuclear Engineering

tD epartment of Electrical Engineering and Computer Science

University of Michigan Ann Arbor, Michigan 48109 Abstract

We describe a decision-theoretic method that an au-tonomous agent can use to model multiagent situ-ations and behave rationally based on its model. Our approach, which we call the Recursive Modeling Method, explicitly accounts for the recursive nature of multiagent reasoning. Our method lets an agent recursively model another agent's decisions based on probabilistic views of how that agent perceives the multiagent situation, which in turn are derived from hypothesizing how that other agent perceives the initial agent's possible decisions, and so on. Fur-ther, we show how the possibility of multiple inter-actions can affect the decisions of agents, allowing cooperative behavior to emerge as a rational choice of selfish agents that otherwise might behave unco-operatively.

Introduction

A central issue in distributed artificial intelligence (DAI) is how to get autonomous intelligent agents, each of whom has its own goals and preferences, to model each other and coordinate their activities for their mutual benefit. This paper describes a recursive method that agents can use to model each other in order to estimate expected utilities more completely in multiagent situa-tions, and thus to make rational and coordinated de-cisions. Our method works by letting agents explicitly reason about how the collective actions of agents can af-fect the utilities of individual actions. Thus, to choose an action that maximizes its individual utility, an agent should predict the actions of others. The fact that other agents are likely to take the same approach gives rise to the recursive nesting of models.

Our Recursive Modeling Method (RMM) represents this recursion explicitly to allow an agent to arrive, within the bounds of its processing, on the most rational decision in the multiagent environment. RMM consid-ers all of the available information an agent might have about others and summarizes the possible uncertainties °This research was supported, in part, by the Department of Energy under contract DG-FG-86NE37969, and by the NSF under Coordination Theory and Collaboration Technol-ogy Initiative grant IRI-9015423.

62

Architectures and Languages

as a set of probability distributions. This representa-tion can reflect the uncertainty as to the other agents' intentions, abilities, long-term goals, and sensing capa-bilities. Furthermore, on a deeper level of the recursion, the agents may have information on how other agents are likely to view them, how they themselves think they are viewed, and so on.

Our work, thus, extends other work [Rosenschein and Breese, 1989] that uses a game theoretic approach to co-ordinating interactions without communication. That work unrealistically assumes that agents have full in-formation about each other's choices, preferences, and perceptions. Other research efforts in DAI use similar formalisms to our work, but avoid the recursive issues that we are studying by allowing agents to communicate about their beliefs, goals, and preferences, in order to make explicit deals [Werner, 1989; Zlotkin and Rosen-schein, 1989; Zlotkin and Rosenschein, 1990].

Research in cooperation indicates that agents can con-verge on cooperative strategies during repeated interac-tions without ever explicitly communicating [Axelrod, 1984]. The most well-known example is the Prisoner's Dilemma game, where a rational "one-shot" strategy is to defect, but where a "Tit-for-Tat" strategy is best for repeated interactions. Following the methodology of metagames [Howard, 1966; Reagade, 1987], the goal of our work is to develop a formal, algorithmic model that captures how cooperative strategies can be derived by self-interested, rational agents.

In the remainder of this paper, we begin by outlining the basic concept of a payoff matrix from decision and game theories, and then we define the RMM and illus-trate it with an example. Subsequently, we show how the possibility of multiple interactions changes the char-acter of games, and illustrate this using the Prisoner's Dilemma problem. We revisit the earlier example and apply the multiple interactions concept within RMM. We conclude by summarizing our results and current re-search directions.

Establishing Payoffs

A decision-theoretic approach to multiagent interaction requires that an agent view its encounters with other agents in terms of possible joint actions and their util-ities, usually assembled in the form of a payoff matrix. We have developed a system, called the Rational Rea-

We describe a decision-theoretic method that an autonomous agent can use to model multiagent situations and behave rationally based on its model. Our approach, which we call the Recursive Modeling Method, explicitly accounts for the recursive nature of mul

soning System (RRS) [Gmytrasiewicz et al., 1991a] that determines plans' utilities [Jackobs and Kiefer, 1973] to automatically generate the information for a payoff mar trix. For brevity, we will not describe the details of RRS, beyond saying that it combines decision-theoretic tech-niques with hierarchical planning to generate alterna-tive decisions (plans of action), and uses time-dependent calculations of utility to generate the expected payoffs. These calculations involve formal notions of agents' pref-erences and the ways specific tasks …… 此处隐藏：20096字，全部文档内容请下载后查看。喜欢就下载吧 ……