Deals Among Rational Agents

Abstract

A formal framework is presented that models commu­ nication and promises in multi-agent interactions. This f1·amework generalizes previous work on cooperation with­ ont communication, and shows t}u~ ability of communi­ cation to resolve conflicts among agents having disparate goals. Using a deal-making mechanism, agents are able to coordinate and cooperate more easily than in the commu­ nicat.ion-free model. In addition, there are certain types of interactions where communication makes possible mu­ tually bcn~ficial activity that is otherwise impossible to coordinate.

§1. Introduction

1.1 The Multi-Agent Paradigm and AI

Research in artificial intelligence has focused for many years on the problem of a single intelligent agent. This agent, usually operating in a relatively static domain, was designed t.o plan, navigate, or solve problems under certain simplifying assumptions, most notable of which was the absence of other intelligent entities.

The presence of multiple agents, however, is an un­ avoidable condition of the real world. People must plan actions taking into account the potential actions of others, which .might be a help or a hindrance to their own activ­ ities. ln order to reason about others' actions, a person must be ;tble to model thdr beliefs and desires.

The arlilicial intelligence community has only lately come to address the problems inherent in multi-agent ac­ tivity. A community of researchers, worldng on distributed artificial intelligence (DAI), has arisen. Even as they have begun their work, however, these researchers have added on a new set of simplifying assumptions that severely re­ strict the applicability of their results.

1.2 B<~nevolent Agents

Virtually all researchers in DAI have a.ssnmed that the ar;cnts in their domains have comn!on or nun-conflicting goals. Work has thus proceeded on the question of how these agents can best help one another in carrying out their common tasks [3, 4, 6, 7, 21], or how they can avoid

This resca~ch has been supported by DARPA under NAVELEX grant number N0003!.H!3-C-0136.

Deals Among Rational Agents

Jeffrey S. Rosenschein Michael R. Genesereth

Computer Science Department Stanford University Stanford, California 94305

interference while using common resources [10, 11]. Multi­ ple agent interactions a.re studied so as to gain the benefits of increased system efficiency or increased capabilities.

Of course, when there is no conflict, there is no need to study the wide range of interactions that can occur among intelligent agents. All agents are fundamentally assumed to be helping one another, and will trade data and hy­ potheses a.s well as carry out tasks that arc requested of them. We call this aspect of the pa:·adigm the benevolent agent assumption.

1.3 Interactions of a More General Nature

In the real world, agents are not necessarily benevolent in their dealings with one another. Each agent has its own set of desires and goals, and will not necessarily help another agent with information or with actions. Of course, while confLict among agents exists, it is not total. There is often potential for compromise and mutually beneficial activity. Previous work in distributed artificial intelligence, bound to the benevolent agent assumption, has generally been incapable of handling these types of interactions.

Intelligent agents capable of interacting even when their goals are not identical would have many uses. For example, autonomous land vehicles (ALV's), operating in a combat environment, can be expected to encounter both friend and foe. In the latter case there need not be total conflict, and in the former there need not be an identity of interests. Other domains in which general interactions are prevalent are resource allocation and management tasks. An automated secretary [12], for example, may be required to coordinate a schedule with ;mother automated (or hu­ man) secretary, while properly representing the desires of its owner. The ability to negotiate, to compromise and promise, would be desirable iu these types of encounters.

Finally, even in situations where all agents in theory have a single goal, the complexity of interaction might be better handled by a framework t.hat recognizes and resolves sub-goal conflict in a general manner. For example, robots involved in the construction of a space station arc fun­ danu~nt.ally 1.11otivated hy the same goal; in the course of construction, however, tlwre may be 111any minor conmcts caused by occurrences that cannot fully be predicted (e.g., fud running low, drifting of objects in space). The build­ ing agents, each with a different task, could then negotiate with one another and resolve conflict.

1.4 Game Theory's Model and Extensions

In modeling the interaction of agents with potentially diverse goals, we borrow the simple construct of game the­ ory, lhc payoff matrix. Consider the following matrix:

The first player is assumed to choose one of the two rows, while the second simultaneously picks one of the two columns. The row- column outcome determines the payoff to each; for example, if the first player picks row b and the second player picks column c, the first player receives a payoff or 2 while the second receives a payoff of 5. If the choice results in an identical payoff for both players, a single number appears in the square (e.g., the a\d payoff above is 2 for both players). Payoffs designate utility to the players of a particular joint niove [18].

Game theory addresses the issues of what moves a rational agent will make, given that other agents are also rational. We wish to remove the a priori assumption that other agents will necessarily be rational, while at the same time formalizing the concept of rationality in various ways.

Our model in lhis paper allows communication among the agents in the interaction, and allows them to make binding promises to one another. The agents arc assumed to be making their decisions based only on the current eJtcotmtcr (e .g., they won't intentionally choose a lower utility in the hope of gaining more utility later on). The formalism handles the case of agents with disparate goals as well as the case of agents with common goals.

§2. Notation

We expand on the notation developed in [8]. For each game there is a set P of players and, for each player i E P, a set M; of possible moves for i . For S C P, we denote P -· 8 by S, and write i instead of { i} {so '! = P - { i} ). We write Ms for fliES M;.

We denote by ms an ele111cnt of Ms; this -is a joint move for the players in S'. '.l'o ms E Ms ami ms E Mg correspond an clement m of Mf' . The payoff function for a game is a function

whose value at (i, iii) is the p<lyoff for player i if move rn is made.

Each agent is able to specify a set of joint moves (i.e., elements of M p) that. specify ou tcomcs the agent is willing to ;u:cept; this set is called an of!er group. If ;uiy move or tnoves offered by one agent arc likewise offered by all other agents, this set of moves constitlttcs the deal (i. o. , the deal is the intersection of all the agents' offer groups). In practice, a single clement of the deal set will be selected by a fai r arbiter , and the result of the select ion communicated to all agents . At that point, the agents arc all compelled to carry out. their part of the move. Of course, if the deal set has on ly one member, no arbiter is needed .

We dcfme a secondary payoff function pa.y(i, mi, D;), the set of possible payofrs to i of making move m; and suggesting offer group P;:

We dcsig11ate by allowed"' ( i, m;) the set of moves that other agents might potcnt.fally make while i makes move m;, and by allowed"( i, D;) the set of offers that other agents mi ,!;ht 1nake while i suggests offer group D; . Our formalism implicitly separates offer groups from moves (in ot.her words, there will be no effect on moves by offer groups or vice versa). Intuitively, this reflects simulta­ neously revealing one's move and offer group, with one's eventual action determined by others' offer groups (that is, only if there is no agreement will you haw~ to carry out your move) . Future work might investigate the situat ion where offers arc made before moves arc chosen, and may thus affect them.

For nonempty sets {a;} and {.BJ}, we write {a;} < {.BJ} if lX; < .81 for all ·i, j (and say that. {fi.d strictly domi­ nates { lx 1 } ). Likewise, we write {a;} -:; {.81} for nonempty sets {a;} and {.Bj} if a; S:: .Bi for all i, j and the inc<lnal­ ity is strict in at least one case. We then say that {.Bj} dominates { aj }.

Finally, we define 1J(S, Ys) as {p( i, 17) : i E S A Ys E M fi } . These arc the possible payon·s to a groupS of players of making move Ys .

2.1 Rational Moves

We will denote by ll,.(p , i ) the ~c t of r;ttional moves for agent i in game p. We u~c the following definition to con~trai n what moves arc clements of R,.(p,i), that is, what moves arc rational (we will follow the convention that free variables arc considered universally quantified):

In other words, if, when no binding agreement will be reached, every possible payoff to i of making move y; is less than every possible pay on· to i of making move x;, then Yi is irrational fori. Of course, this dol'S not imply that X; 13 r;d.ional, since better moves may still he available.

In general, it will not be possible to fully specify the value of pay( i, m;, 0) for all m;, since there is not full in­ formation as to the moves that the other agents will make. Instead, we usc ( 1) to show that some moVl)S arc not ra­ tional. Because the dominance relation is transitive but irrellexive (and there are a finite number of moves), it is impossible to show that all moves are irrational.

2.2 Rational Offer Groups

We define a rational offer group in a way analogous to how we defined a rational move above. We denote by R,(p, i) the set of rational offer groups for agent i in game p, and characterize a rational offer group by the following constraint on Rv(P, i)'s members:

In other words, if for some move m; every possible payoff resulting from offer _group P; is less than every possible payoff resulting from offer group 0;, then P; is not a ra­ tional offer group.

There .is one more constraint on members of Ro(P, i): rational offer groups specify (through the function p) a continuous range of payoffs that are acceptable to an agent. Intuitively, a rational offer group must reflect the notion of "monotonic satisfaction" - if a rational agent is satisfied with a particular payoff, he will be satisfied with one of equal or greater value (this is a fundamental meaning of "utility"). Formally, we write

for all 0; E R.,(p, i) and moves r and ;~. For a particular ganw and player, a rational offer group can thus be unam­ biguously specified by any of its members with the lowest payoff.

In general, there may be more than one rational offer group for an agent in a game. U full information were available to an agent about the offers others were going to make (along with t.hcir "backup lliOVl!s"), it would be trivial t.o det.cnninc H.,(p,i). l11 pract.ice sncl1 inronnation is not. available, but a rational agent i 111ay be able to discover some rational offer group, i.e., some offer group provably in Ro(P, i).

2.3 Rational Moves and Offer Groups for a Set of Players

We also w.ish to define the rational moves and the r;ttional offer groups available to a set or players. For S c P, we denote by Rm(p,S) the rational moves for the group S in the game p. It rollows that the members of Rm(P, S) arc clements of Ms . We assume that

This states that no rational move for a set can requir-e irra­ tionality on the part of a subset. An obvious consequence of this assumption is that

A move that is rational .for a group of players is thus ra­ tional for each player in the group.

Similarly, we denote by R 0 (p, S) the set of rational deals for Sin the game p (that is, the members of Ro(P, S) are sets of elements from Mp). It is the "crossproduct­ intersection" of rational offer groups for the individual agents:

2.4 Rationality Assumptions

The value of pay(i,m;,y;) will depend, of course, on the values of allowedm(i,m;) and allowed0 (i,y;) (i.e., the moves and the deals that other agents can make). In order to constrain the value of pay, we now define each of the allowed functions ( allowedm is defined as in [8]).

1. Minimal move rationality: allowe:dm(i,m;) = M,. Each player assumes that the others may be moving randomly.
2. Separate move rationality: allowed.,.(i,m;) C Rm(p,'i). Each player assumes the others me moving rationally.
3. Unique move rationality: For all m; and m;, allowed,.('i,m;) = allowedm(i,m;) and iallowed.,.(i,m;)i = 1. Each player assumes that the others' moves are fixed in advance. This may be combined with separate rationality.

The assumptions above do not fully specify what is or is not a rational move. Rather, they help constrain the set of rational moves by allowing us to prove that certain moves arc not ratioual. We· now define analogous a.ssump­ tions rcgardin[!; deals other agents lllight be making:

1. Minimal deal rationality: allowedo(i,y;) C P(Mp), where P(Mr) denotes the power set of Mp. Each player assumes that the others may he making random deals.
2. Separate deal rationality: allowed0 ( i, y;) C Ro(p, 7:). Each player assumes that the others are making rational deals.
3. Unique deal rationality: For all D; and E;, allowed 0 (i,D;) = allowed 0 (i,E;) and iallowcd 0 (i,D;)I = 1. Each player assumes that the others' offers arc fixed in advance. This may be combined with separate deal rationality.

We refer to the combination of separate and unique move rationality as individual move rationality, and to the combination of separate and unique deal rationality as in­ dividual deal rationality. As in [8], any move that can be proven irrational under the assumption of minimal move r.-.tionality will he similarly irrational under the other move r<Llionality assumptions. Analogously, any offer group that can uc proven irrational under the assumption of minimal deal rationality will be irrational under the other deal ra­ tionality assumptions.

§3. Rational Deal Characteristics

With our notational conventions defined, we can now prove several characteristics of Ro(P, i). We henceforth use s to denote any move that gives agent i his highest payoff.

Theorem 1 (Existence of a non-null rational offer group). IRo(p,i)l2 1.

Proof. If R 0 (p, i) were empty then i would do best by making no offers and relying on his move to generate his payoff. But pay(i, m;, s) will be greater than or equal to pay(i,m;,0) for all m; (since swill either be matched by other agents, increasing i's payoff, or will not be matched, and will therefore be harmless since it doesn't affect other's moves). Thus the offer group {S} would also be in Rv(p,i), guaranteeing it to have at least one non-null member. a

It foll c>ws directly from the definition of a rational offer group (3) that all non-empty members of i's set of rational offer groups include s. Together with Theorem 1, this implies that it is always rational for an agent to include in his offer 1;roup the move th<\t gives him his highest payoff.

In addition, an agent can often restrict his offers to those whose payoffs arc higher than that which he can get by making the null offer, relying on his move to give him this payo.ff.

Theorem 2 (Lower bound). Assuming unique deal ra­ tionality, if for auy move m; a/ICI joint move if f. s,

Proof. There arc two cases:

1. p(i,y) < pay(i,m;,0): The only way for if to be in some rational on·cr group P; is for the if deal not to be accepted (otherwise pay(i,m;,P;) would .bc dom­ inated by the offer group pay(i,m;,O;) where 0; = {i: p(i, i) > p(i, y)}). But if y is not accepted, then it is equivalent to another offer group that includes only tlwse moves with payoffs higher than if. This smaller on·er group will then also be in R.,(p, i).
2. p(i,y') = pay(i,m;,0): Assume that if is in some rational offer group P; . If y is not accepted, or is ac­ ceptt:rl along with other offers, then puy( i, m;, 0;) > pay('i,m;,P;) where 0; = {X' : p(i,i) > p(i,y)}, so there is an.other rational offer group without if, namely the offer group 0;. If if is the only accepted offer, then pay(i,m;, s) = pay(i,m;,P;) (where s is the move that gives i his highest payoff), since s· will not be accepted anyway and therefore pay(i, m;, S) = pay(i,m;,0). Again, there is a rational offer group that does not include if. a

Note that Theorem 2 will not hold for s (i.e., the joint move that gives i his highest payoff) since that would con­ tradict Theorem 1 (Theorem 2's proof makes implicit use of the fact that if f. s in its construction of the dominating offer group 0;). Note also that Theorem 2 will not hold under minimal deal rationality. Imagine that a perverse opponent chooses his offer group as follows:

1. If you include in your offer group deals with low payoff (for you), he will accept the deal with your best payoff;
2. If you don't offer that low deal he will accept no deals and you will have to rely on your move to get a payoff. Under these circumstances (fully consistent with minimal deal rationality), it might be to your advantage to offer a low-payoff deal, ·since that might be the only way to get your maximal payoff.

3.1 Restricted Case Analysis

The consequences of Theorem 2 will differ, of course, based on assumptions about allowed.,. since these will af­ fect pay(i,m;, 0) for any given m;. Consider the following payoff matrix:

It is shown in [8] that, assuming minimal move ratio­ nality (pot(!ntially random or even malevolent moves by other agents), the row agent can still usc "restricted case analysis" to consl.r<tin his HtoVt! to b. If unique deal ratio­ nality can he assumed then the offer group consisting solely of move b\c (i.e., bottom left corner) is guaranteed hy The­ orems 1 and 2 to he a rational offer group. Of course, there may he other rational offer groups, for example the offer {b\d,b\c}, depending on what deals the other player can offer.

We formalize part of the above discussion:

Corollary 3 (Restricted case analysis). Assuming minimal move ratiorw/il,y and unique deal rationality, if for some x; ami y;, for all x1 aJJd y1,

then there exists an 0; E R 0 (p, i) sucl1 that no ii is in 0;. Proof. Follows from Lemma 3 in [8] and Theorem 2. o

3.2 Case Analysis and Iterated Case Analysis

There are restrictions on rational offer groups anal­ ogous to Corollary 3 that apply for case analysis and it­ crated case analysis under the assumptions of unique and individual move rationality, respectively. The case analy­ sis situation is represented in the following payoff matrix, seen from the row player's perspective:

The row player need only assume that the column player's move will not be affected by its own move (i.e., unique move rationality) to realize that making move a is in all circumstances superior to making move b. As long as unique deal rationality can also be assumed, there is a guarantet:d rational offer group consisting only of move a\c.

Corollary 4 (Case analysis). Assuming unique move rationality and unique deal rationality, if for some x; and y;, for all x, andy, witl1 x, = y,,

Oren there exists an 0; E R"(p, i) such tl~at 110 ii is in 0;.

Proof. Follows from Lemma 4 in [8] and Theorem 2. o

Similarly, if the column player can assume that the row player is rational and making moves independent of the column player's moves (i .e., individual move rationality), then lw can prove that move d is optimal in the above matrix (since the row player will play a). With unique deal rationality, he has a guaranteed rational offer group of { a\ d, b\ c} (the offer group {b\c} is also rational).

The effect of Theorems 1 and 2 is to show us that there is always a r;ttional offer group that includes an agent's highest payoff outcome, and includes no outcomes below or equal to what he could achieve without deals. Below, we consider other constraints on an agent's rational offer groups.

§4. The Group Rationality Theorem

The work in [8] and [9] was concerned with the formal­ ization of cooperative behavior, given certain constraints ahout the agents participating in an interaction. Using our notation, a desirable general result would have been

that is, if any joint move for all players is dominated by any other, then the dominated joint move is not rational for them. This result could not be proven, and the inabil­ ity to do so stemmed directly from the lack of communi­ cation inherent in the model. Without at least minimal communication (e.g., self-identification), there is no way to coordinate on a universally perceived best move when several such moves exist.

We me now able to derive an important result about Ro(P, P) very similar to the elusive non-communication re­ sult in (4).

Theorem 5 (Group offers). Assuming individual deal rat.ionality,

for all i E P .

Proof. There are two possible cases:

1. \f0i[01 E R0 (p,'i) =-=> ii ~ OiJ: Since ii will not be a consummated deal, if P; is any offer group con­ taining ii then pay(i,m; ,O;) ~ pay(i,m;,Pi) where 0; = {x : p(i, x ) > p(i.JT)} . Along with Theorem 1, this shows the existence of a non-null rational offer group without fi.
2. 30 3 [0j E Ra(PJ) A ii E OiJ: All other agents are rational (by assumption), and any rational offer group that includes if also includes x (3); thus, if P; is any offer group containing ii, then pay( i, m;, 0;) > pay(i,m;,P;) where 0; = {x : p(l:, :i:') > p(i,j/')}. This, along with Theorem 1, shows the existence of a rational ofl'cr group without fi. o

Because of Theorem 5, a rational agent interacting with other rational agents knows that he need not offer a move that is dominated for all players- doing so can­ not increase his payoff. If the other rational agents also know that all agents arc rational, they too will realize that they Call refrain from on'ering a IIIOVC that is dominated for a.ll players. Higher level::; of kuowledgc [1:1], such as their knowing that all agents know that all agents arc rational, arc not needed. ln addition, because of the definition of rational oll'er groups (3), the agents can refrain from of­ fering any moves with smaller payoffs, since those groups would necessarily include the dominated move.

§5. Examples

We will now examine the consequences of our rational offer theorems in several additional types of games.

5.1 Best Plan

The best plan scenario 1s renectecl 111 the following matrix:

All agents recognize that there is a single best move; how will their offer groups reflect this? From Theorem 1, a ra­ tional agent knows that he can safely offer the move that gives him his best payoff (i .e., move a\c), even assum­ ing minimal deal rationality on the part of other players (though the theorem is noncommittal as to whether other moves can or should be included with it). All players can also rule out move a\d using Theorem 2 if urJique deal ra­ tionality holds (since a\d yields the lowest payoff) . If there is an assumption of individual deal rationality, Theorem 5 can guarantee each agent that the offer group consisting solely of a\c is rational. Communication thus allows coor­ dination on the best plan under more intuitive assumptions ahout the int<~raction than those used in [8].

5.2 Breaking Symmetries-Multiple Best Plan

Our rational offer group theorems allow us to solve the "Multiple Best Plans" case that could not be solved in [8]. The following matrix illustrates the scenario:

Assuming minimal deal rationality, an agent can rationally offer b\c and a\d. In addition, assuming unique deal ra­ tiouality an agent knows that he can rationally not offer a\c and b\d (since they are lowest yield moves). This anal­ ysis can be done by Loth agents if they are rational and operating under the unique deal assumption. Their o(fer sets will overlap on the multiple best outcomes; selection of a single alternative from the multiple agreements then occurs.

5.3 Prisoner's Dilemma

The prisouer's dilemma is represented by the following matrix (we choose diHerent names for our moves so as to conform to the literature):

Each agent most desires to play d while the opponent plays c, then to play c along with the opponent, then to play d along with the opponent, and least of ;dl to play c while the opponent plays d. The dilemma comes about because case analysis implies that it is always better to play d; both players choosing d, however, is less deHirabl<! for both than if they had chosen c. The dilemma ha~; received much attention within the philosophy and game throry literature [2 , 5, 22, 27]. In the usual presentation of the prisoner's dilemma, playing cis called "cooperating," and playing dis called "defecting." With the presence of binding promises, in fact, there is no dilemma:

Corollary 6 (Prisoner's Dilemma). If all players Jmow tl1al all players are operating under the assumption of in­ dividual deal ratior1ality, agents will cooperate in tlw p.ris­ OIJer's dilemma.

Proof. The first player knows that it is rational to of­ fer d\c (since it is rational even under minim<>.! rational­ ity, Theorem 1); he also knows it is irrational to offer c\d (from Theorem 2, since individua l deal rationality includes unique deal rationality) . By Theorem 5, there is a ratio­ nal offer group without d\d: Now he ]mows that the other agent will not offer d\c (since the other agent is assumed rational and operating under the assumption of unique deal rationality, Theorem 2). Since d\c will certainly not be met, pay(i,d, {d\c}) .::; pay(i,d, {d\c , c\c}). Thus, the of­ fer group {d\c,c\c} is rational. The second agent will, if rational and working under the same assumptions, come to the same conclusion. The deal c\c will be struck, and the agents avoid the d\d trap. o

§6. Extending the Model

For certain types of interactions, the model presented above (.i.e., the various assumptions and theorems about rational moves and deals) docs not specify rational activity in sufficient detail. We can extend t.he model in a variety of ways to handle these cases, and at the same time capture a wider range of assumptions abon t the interaction. In this section, we briefly IH·esent some of the extensions that might be made to our original model.

6.1 Similar bargainers

ConsidN tlH~ following payoff matrix (equival<!nt to game 77 in ltapoport and G uycr's taxonomy . [23])

Assuming separate deal ration;tlity, the firs t player can assume that b\c shmlld be in a rational ofl"er group of his, and that b\ d should not be. What else can be said about what constitutes a rational offer group in this galllc'? Th<!re arc three choices, nauHdy {h\c}, {n\r:,b\c}, and { a\d, a \c, b\c}. In order to decide among !.he choices, we would like to make more assumptions about the "bar­ gaining tendencies" of the other agent (since, in fact, some agents might be tougher deal-makers than others). We will ir,nore what value the agents might place on making a particular move in the absence of a deal, since the payoff is nnderdctcrmined.

Let us define two offer groups 0; and Oi to be similar if and only if they both have the same lower boundary for what deals are included or not included. It is true that similar(O;, OJ) if and only if

for some number n. If we use the similar bargainers defi­ nition, we implicitly assume some meaningful measure for comparing inter-personal utility.

One a:;sumption to use in deciding upon rational offer groups is HOW that the other agent will accept deals that you would accept; that is, OJ E Ro(P, j) {.} 0; E R,(p, i) where similar(O;, OJ)·

Under this assumption, we can decide what deal is ra­ tional in tiH! above game. Player 1 reasons that if he offers {b\c}, player 2 (who is a similar bargainer) will offer only { b\d}. There will be no match. In the same way, if it would be rational for player 1 to offer { a\c, b\c} then player 2 will offer { a\c, b\d}, with an agreement on a\c and a payoff of {3} for beth. If player 1 offers {a\d,a\c,b\c} then player 2 will offer {a\d,a\c,b\d} and there will be agreement on a\d and on a\c, with a payoff of {2, 3} for both. Since {3} dominates {2, 3}, agents who assume common knowledge [13] of the similar bargainer assumption should choose the rational oO'er group that yields agreement on a\c.

6.2 Stochastic Model-The Game of Chicken

Note, however, the following payoff matrix (commonly known as the game of chicken [23]):

Two agents, even if they assume indivillnal deal ratio­ nality and the similar bargainers assumption, will be faced with the following choices: a payoff of {3} or a payoff of {2, 3, 5}. According to our definitions, neither of these sets dominates the other.

If, however, we extend the model to include a prob­ abilistic choice from within the agreement set, it is clear that the latter agreement set dominates the former (with an expected value of 3.33 versus 3). A further stochastic extension to our model would allow moves themselves to be specified probabilistically (e.g., a wit.h probability .5, and b with probability .5). In the ga111c theory literature, this is the distinction between pure strategies and mixed strategies [18]. An <malysis of this model is beyond the scope of the present discussion.

6.3 Conjunctive Offers-Battle of the Sexes

In the game of chicken example presented above, there was an added complexity that was temporarily ignored: the possibility of "defection." If one agent reasons that the other agent will accept all payoffs above 2, it is to the first agent's benefit to only offer moves of payoff 5 (this is analogous to the prisoner's dilemma, with the same potential that both players will usc identical reasoning and no agreement will be reached). A similar problem can be seen in the so-called battle of the sexes matrix, seen below.

One approach to solving this problem is to allow "com­ posite" offers, for example, an offer consistin!~ of a conjunct of several moves (the conjunct must be matched exactly in order for a deal to occur). Thus, the offer consisting of a\dllb\c can consistently be made by both agents without the potential of defection (and with an expected utility of 1.5 for each). This notion can be extended to general log­ ical offers consisting of disjuncts, conjuncts and negations of joint moves. The battle of the sexes can thus be uniquely solved with the assumption of similarity in bargaining, if conjunctive offers are allowed.

§7. Previous Work

The suhjcct of iiltcracting ration.d agents has been addressed within the field of artificial intelligence as well as in the discipline of game theory. Here Wl~ will briefly review relevant contributions from these two areas, and contr;tst our present approach with vrcvious efforts.

7.1 Work in Artificial Intelligence

As mentiotwd ;tbovl!, resea.rchl~rs in dist.ribnt.cd artifi­ cial intelligence have begun to address the issues arising in multi-agent interactions. Lesser and Corkill [1] have per­ formed empirical studies to determine cooperation strate­ gies with positive characteristics (such as, for example, what types of dat<.t should be shared among distributed processors). They arc solely concerned with groups of agc11ts who share a common goal, but have acknowledged the benefit even under this assumption of having agents demonstrate "skepticism" (i.e., not being distracted by others' information).

Ceorgclf [10, ll] has developed a formalmollel to com­ bine separate plans of independent agents . The primary concern is to avoid destructive interference caused by si­ multaneous access to a shared resource . The model used assumes that the agents have separate goals, but that these goals do not directly oppose one another. Cooperative ac­ tion is neither required nor exploited, except insofar as it allows a~jents to keep out of each other's way.

Other notable efforts include Smith's work on the con­ tract net [7], Malone's work extending the contract net model using economic theory [19], and the theoretical work on knowledge and belief of carried out by Appelt, Moore, J{onolige, Halpern and Moses [1, 14, 15, 16, 17, 20, 21] .

The current work extends these previous models of in­ teraction by allowing a fuller range of goal disagreements among agents . By using a framework that captures to­ tal and partial goal conflicts, it allows investigation into compromise, promises and cooperative action.

This paper considers the communication scenario in ways similar to the manner in which previous work [8, 9] investigated cooperation among rational agents when no communication occurs. Below we briefly note the advan­ tages that were gained when communication and promises were added to the interaction model.

The best plan interaction was handled in our frame­ work by assuming individual deal rationality. Because in the no-communication case this scenario could not be solved using .individual move rationality, other assump­ tions were introduced: informed rationality in [8] and com­ mon rationality in [9] . Informed rationality constrained allowedm in a way that assumed each player would re­ spond in a r<ttional way to the others' moves, whatever they might be.

H should be noted in passing that an assumption of common knowledge of rat.ioi)ality will also allow for a solu­ tion to the best plan case, though this has not previously been pursued in the literature.

To solv(! the prisoner's dilemma, even more assump­ tions had to be introduced. The interested reader is re­ ferred to [8] ;u1d [9] for full details; see also [25].

Even using a variety of assumptions, previous work could not. handle t.IH! multiple IH!St plan case, wl)erc there arc several outcomes all equally recognized as best by all players. To break the symmetry, some communication is needed, though this comm1mication can be as simple as self-identification and reliance on a common rule (e.g., agent with lowest name p{!rforms lowest ordered action).

7.2 Game Theory

Game theory has focused on a . variety of interactions, and sought to characterize the types of actions that ratio­ nal agents will take in each. Many of the same questions that come up in our work have been addressed by game theoreticians'. Their approach, however, has left some important issues unexamined. Consider the following -quote from the classic game theory text, [18]:

Though it is not apparent from some writings, the term "rational" is far from precise, and it certainly means different things in the different theories that have been developed. Loosely, it seems to include any assumption one makes about the players maximizing something, and any about complete knowledge on the part of the player in a very complex situation ... [Games and Decisions, p. 5]

As another example, consider the following best plan interaction:

It was demonstrated above that the best plan case can only be solved under particular definitions of rationality. Rapoport and Guyer, however, writing in [23], put for­ ward the following assumption regarding agents' behavior (citing the similarity with [26]):

(A3). If a game has a single Pareto equilibrium, the players will choose the strategy which con­ tains it ...

Our assumption (A3 ) says that A 1A 2 is the natu­ ral outcome, which, of course, is dictated by com­ mon t:ense ... we shall refer to this as a prominent soluti.m. [A Taxonomy of 2 X 2 Games]

In short, game theory has sometimes been willing to take for granted certain types of behavior without carefully formalizing its definitions of rationality, or its assumptions of inter-agent knowledge.

These questions arc particularly important in the field of artificial intelligence. We arc not interested in charac­ terizing game matrices: we want to characterize agent ra­ tionality and explore the consequences of various assump­ tions. The goal is to be able t.o implement intelligent agents whos<! strategies of behavior will be provably rational.

§8. Conclusion

Intelligent agents will inevitably need to interact flexi­ bly in real world domains. Previo11s work has not modeled the full range and complexity of agents' varied goals. The benevolent agent assumption, which assumes that agents have identical or uon-conflicting goals, has permeated pre­ vious approaches to distributed AI.

This paper has presented a framework for interaction that explicitly accounts for conununication and promises, and allows multiple goals among agents. The model pro­ vides a 11nified solution to a wide range of problems, in­ cluding t.he types of int<!racl.ions discussed in [8] and [9].

Through the use of communication and binding promises, agents are able to coordinate their actions more effectively, and handle interactions that were previously problemati­ cal. By extending the communication model even further, a wider variety of interactions can be handled.

Acknowledgement

The anthors wish to thank Matt Ginsberg, who has played an inv<1.luable role in the development of our ideas on cooperation among rational agents.