Negotiations Over Time in a Multi-Agent Environment: Preliminary Report

1 Introduction

One of the major foci of research in distributed artifi­ cial intelligence (DAI) is the design of automated agents which can interact effectively in order to cooperate in problem-solving. Negotiation is recognized as an impor­ tant means by which inter-agent cooperation is achieved. That is, DAI is concerned with the design of agents which are able to communicate in such a way as to enhance the possibility of reaching mutually beneficial agreements concerning problems such as a division of labor or re­ sources among the agents.

Negotiation has always been a central theme in DAI research [Davis and Smith, 1983; Georgeff, 1983; Mal­ one et al., 1988; Durfee, 1988; Durfee and Lesser, 1989; Rosenschein and Genesereth, 1985; Sathi and Fox, 1989; Conry et al., 1988; Zlotkin and Rosenschein, 1990]. This research has focused on strategies for designing agents capable of reaching mutually beneficial agree­ ments. Sycara ([Sycara, 1987]), using case-based rea­ soning, and Kraus et al. ([Kraus et al. , 1991]) modeled negotiations from a cognitive standpoint .

·This work was partially completed while the first au­ thor was at the Institute for Advanced Computer Studies and Dept. of Computer Science, University of Maryland, College Park.

Jonathan Wilkenfeld

Dept. of Government and Politics University of Maryland College Park, MD 20742 wilkenfeld @umd2. umd.edu

Yet it is also recognized that although negotiations are necessary for reaching such agreements, the negotiation process is both costly and time-consuming, and thus may increase the overhead of the operation in question (see [Bond and Gasser, 1988]). In negotiations on such issues as job-sharing or resource allocation, it is important to minimize the amount of time spent on negotiating mu­ tually beneficial agreements so as not to detract from time spent on the task itself. Thus, in the presence of time constraints, negotiation time should be taken into consideration.

In [Kraus and Wilkenfeld, 1991a] we propose a strate­ gic model of negotiation that takes the passage of time during the negotiation process itself into consideration. That study focused exclusively on a two-agent model. The present study generalizes this process by consider­ ing the N-agent environment .

Following [Rosenschein and Genesereth, 1985; Zlotkin and Rosenschein, 1990; Kraus and Wilkenfeld, 1990; Kraus and Wilkenfeld, 1991a] we examine negotiation using game theory techniques with appropriate modifica­ tions to fit artificial intelligence situations. We will focus primarily on works in game theory and economics that have studied the effect of time preferences on the negoti­ ation process, following the classic paper by Rubinstein ([Rubinstein, 1982]). Unlike the work of Zlotkin and Rosenchein, [Zlotkin and Rosenschein, 1990] we investi­ gate multi-agent environments (more than two agents) and our approach makes no assumptions about the pro­ tocol for negotiations. Also, our model takes the pas­ sage of time during the negotiation process itself into consideration. Furthermore, by taking the passage of time during the negotiation process into consideration, our approach is able to influence the outcome of the ne­ gotiation so as to avoid delays in reaching agreements.

2 Initial Setting

N autonomous agents A1 , A2, ... ,AN have a common goal they want to satisfy as soon as possible. In order to sat­ isfy a goal, costly actions must be taken and an agent cannot satisfy the goal without reaching an agreement with one of the other agents . Each of the agents wants to minimize its costs, i.e., prefers to do as little as possi­ ble, if it can assume that the goal will be fulfilled prop­ erly without additional effort on its part. We note that even though the agents have the same goal (under our simplified assumptions), there is actually a conflict of in­ terests. The agents have different preferences concerning goal satisfaction and for the different possible agreements which can be reached.

We make the following assumptions:

1. Full information - each agent knows all relevant information including the other agents' preferences for the different outcomes over time.
2. The agents are rational- they will behave according to their preferences.
3. Commitments are enforced - if an agreement IS reached both sides are forced to follow it.
4. Assumptions (1)-(3) are common knowledge.
5. We demonstrate the cases we are interested in with the following example.

Example 2.1 Three robots, A, B and C, stationed on a satellite, are instructed to move an expensive telescope from one location to another 'as soon as possible. Delay in moving the telescope will reduce the number of pictures sent back to scientists on earth. Any two of the robots can move the telescope, but the tools essential to perform the task are distributed among the three agents. Any of the agents can opt out of the negotiation, choosing not to satisfy the goal. If that occurs, the remaining two cannot achieve the goal (since critical tools will be missing).

3 The Structure of Negotiations

Our strategic model of negotiations is a model of Alter­ native Offers. 1

For reasons of simplification and clarity, we will con­ centrate on the case of three agents, but our results can be easily extended to N agents where an agent can sat­ isfy a goal by reaching an. agreement with another agent 2 · So, in our case, three agents, A, B and C have a com­ mon goal they want to satisfy as soon as possible. Each of them has a set of capabilities, PA, PB and Pc and a set of tools TA,TB and Tc respectively. The agents' capabilities influence their ability and their ways of satis­ fying the goal, and all the tools are needed to satisfy the goal. We now present formal definitions of agreements and strategies.

3.1 Agreements and Strategies

We first define the set of possible agreements. We assume that there exists a set of possible agreements between any two agents. We denote by A the set of agents.

Definition 3.1 Agreement:

Let Act be the set of actions required to satisfy a goal. An agreement is a pair (si,Sj), where i,j E A, i # j;

1 See [Osborne a.nd Rubinstein, 1990] for a. detailed review of the bargaining ga.me of Alternating Offers.

2 In the ca.se in which the agents ma.y divide the labor be­ tween a.ll of them, i.e., agreement ma.y be reached only among a.ll the agents, the model of Alternative Offers is usually dis­ appointing (see [Osborne a.nd Rubinstein, 1990]}. It is still useful when the agents ha.ve specific types of utility functions (see [Stahl, 1977]).

Si U Sj = Act. Si is agent i 's portion of the worfJ. We assume that the set Sij i, j E A, i # j includes all the possible agreements between agents i and j. We also assume that Sii = Sii. Let S ~r Uij Sii i, j E A i # j, i.e., S is the set of all possible agreements.

The negotiation procedure is as follows. The agents can take actions only at certain times in the set T = {0, 1, 2 ... }. In each period t E Tone of the agents, say i, proposes an agreement to one of the other agents. The other agent (j) either accepts the offer (chooses Y) or rejects it (chooses N), or opts out of the negotiation (chooses 0). Also, the third agent may opt out of the negotiation (chooses 0), or it can choose not to do any­ thing (chooses N op). If the offer is accepted, without the third agent opting out, then the negotiation ends and the agreement is implemented (i.e., each of the agents that reached the agreement, does its part of the job and the other agent is obliged to contribute its tools). Also, opt­ ing out by one of the agents ends the negotiations since all the tools are required to satisfy the goal. After a re­ jection, another agent must make a counter offer, and so on.

There are no rules which bind the agents to any previ­ ous offers and there is no limit on the number of periods. The only requirement we make is that the length of a sin­ gle period be fixed and the agents always make offers in the same order, i.e., agent i makes offers in time periods t, t + 3, t + 6 ... , agent j makes offers on periods t + 1, t + 4 ... , and similarly to the last agent. If an agreement is never reached, and none of the agents opts out, we assume the outcome to be D (Disagreement) . We do not make any assumption about who begins the nego­ tiations, i.e., who makes the first offer and who is the second agent to make an offer. So, without loss of gen­ erality we assume that i, j, IE A, i # j # I are the first, the second and the third agents, respectively.

Definition 3.2 Negotiation Strategies:

A strategy is a sequence of functions. The domain of the ith element of a strategy is a sequence of agreements of length i and its range is the set {Y, N, 0, N op} US. We first define a strategy f for an agent i who is the first agent to give an offer.

Let f = {Pn~o· where f 0 E {Sii u Sil}, for t = 3n, n E T p : S' - {Sii u Sil}, and fort = 3n + 1 , n E T ft : S' x {Sii U Sit} - {Y, N, 0, Nop} where if st+ 1 E Sji, ft(s 0 ,s 1 , ... ,st+l) E {Y,N,O}, and if st+ 1 E Sjt, ft(s 0 ,s 1 , ... ,st+ 1 ) E {O,Nop}, (St is the set of all sequences of length t of elements in S). For t = 3n+2, nET f': St x {Su UStj}- {Y,N,O,Nop} where ifst+ 1 E Su, f'(s 0 ,s 1 , ... ,st+l) E {Y,N,O}, and ifst+ 1 E Stj, f'(s 0 ,s 1 , ... ,st+l) E {O,Nop}. We denote by F the set of all strategies of the agent who starts the bargaining.

Similarly, we denote by G the set of all strategies of the agent j who is the second to make offers and we denote by H the set of all strategies of agent I who is the third to make offers 4 .

3 A similar definition ca.n be given concerning a. division of resources.

Let u(f, g, h) be a sequence of offers possibly ending with 0 in which agent i (who can be either A, B or C) starts the bargaining and adopts f E F, agent j adopts g E G and agent I adopts h E H. Let T(J, g, h) be the length of u(J,g,h) (may be oo) . Let La(J,g,h) be the last element of u(f, g, h) (if there is such an element). La(!, g, h) may be either in S or 0 which denotes that one of the agents opted out without the agents reaching an agreement.

Definition 3.3 Outcome of the negotiation: The outcome function of the game is defined by

Thus, the outcome (s, t) where s E Sis interpreted as the reaching of an agreement s in period t. The agreement can be between any two agents. (0, t) is interpreted as one of the agents opting out of the negotiations, and the symbol D indicates a perpetual disagreement without any agent opting out.

3.2 Agents' Preferences Over Possible Outcomes

The last component of the model is the preferences of the agents on the set of outcomes. Each agent has pref­ erences for agreements reached at various points in time, and for opting out at various points in time. The time preferences and the preferences between agreements and opting out are the driving force of the model.

Formally, we assume that any agent i E A has a pref­ erence relation !::::ion the set {S x T}U{ {0} x T}U{D}, where T is the set of time periods.

We note here that by defining an outcome to be either a pair (s, t) or (0, t) or D, we have made a restrictive assumption about the agent's preferences. We assume that agents care only about the nature of the agreement or opting out, and the time at which the outcome is reached, and not about the sequence of offers and coun­ teroffers that leads to the agreement. In particular, no agent regrets either having made an offer that was re­ jected or rejecting an offer (see, for example, the discus­ sion of "decision-regret" in {Raiffa, 1982]).

We make some assumptions about the agents prefer­ ences. First we assume that the least-preferred outcome is disagreement (D).

(AO) For every s E S and t E T, (s, t) >-; D and (0, t) >-; D (Disagreement is the worst outcome) .

The next two conditions (A1), (A2) concern the be­ havior of >-; on S;j x T, i.e., concerning agreements reached with another agent in different time periods. We will assume that the agents have no preference among the actions in Act , i.e., all actions are equally difficult . Condition (A1) requires that among agreements reached in the same period with the same agent, agent i prefers fewer numbers of actions s;.

(A1) ForiE A, t E T and s , r E S;j, j E A,j f; i, if hi< ls;l, then (r,t) >-i (s,t) .

4 The full definitions of the j and l's strategies can be found in [Kraus and Wilkenfeld, 199lb].

We note that this condition does not hold for compar­ isons among agreements between different agents, i.e., beside the amount of work the agents should do it has other considerations that depend on the other agent's capacity to do its part of the job (Pi) .

The next assumption greatly simplifies the structure of preferences among the agreements between any two agents. It requires that preferences between ( s1 , tl) and ( s2, t2) where Si E S;j, depend only on s1, s2 and the differences between t1 and t2.

(A2) For all r,s E Sij, t1,t2,6 E T and i E A, (r, t1) !::::; (s, t1 + 6) iff (r, t2) !::::i (s, t2 + 6) (Stationar­ ity).

We note that assumption (A2) does not hold for 0 and for comparisons among agreements between different agents 5 .

Example 3.1 In the situation from Example 2.1, agents B and C believe that the safest way to move the telescope is by joint action of A and C. In such a case the only possible agreement is one in which agent A will do most of the work. On the other hand agent A prefers to reach an agreement with agent B. In such a case it will need to take fewer actions, and it prefers this despite the cost in safety of the move. It is not safe at all for agents B and C to move the telescope and none of the agents prefers such an agreement.

When analyzing the model, the main question is whether a possibility exists that the agents will reach an agree­ ment. An important feature of the model that strongly influences the outcome of the game is the preference of a player between an agreement and opting out. We need the following definition in order to compare between agreements and opting out.

Definition 3.4 For every t E T and i E A we define §i;, = {sis E Sj,{s, t) >-; (0, t), i,j, IE A,j f; /} . Let -.t -.c -.c -. c S' = S'ii U S';1 U S'i1 where i,j,/ E A,i f; j f; I. If §it f; 0, we denote si ,t = min-<; §it, i.e., s;,c is the worst agreement that can be reached in period t which is still better to agent i than opting out. In case such an agreement does not exist, we define si,t = -1.

We would like now to introduce an additional assump­ tion that will ensure that if all agents prefer some agree­ ments over opting out, an agreement can be reached.

(A3) For any t E T, iffor every i E A, s;,c f; -1, then §it n §it n §It f; 0, where i, j, IE A, if; j f; I.

3.3 Perfect Equilibrium

The main question is how a rational agent chooses his strategy for the negotiation. A useful notion is the Nash Equlibrium ([Nash, 1950; Luce and Raiffa, 1957]) . A triplets of strategies ( u, r, <P) is a Nash Equilibrium if, given T and </>, no strategy of agent A can result in an outcome that agent A prefers to the outcome generated by ( u, r, <P) and, similarly, to agent B given u and <P and to agent C given u and T (assuming that A, B and C

5 An example of a utility function which satisfies the above assumptions concerning agreements is the following: U;(s, t) = Cj +!Act- s;i + t * c; where s E S;j .

are the first, second and third agents to make an offer, respectively). If there is a unique equilibrium, and if it is known that an agent is designed to use this strategy, no agent will prefer to use a strategy other than these. However, the use of Nash Equilibrium is not an effective way of analyzing the outcomes of the models of Alternat­ ing Offers since it puts few restrictions on the outcome and yields too. many equilibria points (see the proof in [Rubinstein, 1982]). Therefore, we will use the stronger notion of {subgame) perfect equilibrium (P.E.) (see [Selten, 1975]) which requires that the agents' strategies induce an equilibrium in any stage of the negotiation, i.e., in each stage of the negotiation, assuming that an agent follows the P.E. strategy, the other agent does not have a better strategy then to follow its own P.E. strat­ egy. So, if there is a unique perfect equilibrium, and if it is known that an agent is designed to use this strategy, no agent will prefer to use a strategy other than this one in each stage of the negotiation.

4 All Agents Lose Over Time

Suppose all agents are losing over time. We assume that all agents prefer to reach a given agreement sooner rather than later, and that all agents prefer to opt out sooner rather than later. We also assume that if a player prefers an agreement over opting out in some period t, then it prefers the same agreement in time period t' prior to t over opting out in t'. Formally:

(A4) For any i E A and t,t1,t2 E T, ift1 < t2 then (O,tt) >-i {O,t2), and for any s E S, (s,tt) >-i (s,t2). If (s, t) >-i (0, t), then for any t' E T such that t' < t, (s, t') >-i (0, t'). If (s, t) >-i (0, t+1), then for any t' E T such that t' < t, (s, t') >-i (0, t' + 1).

We also assume that all agents prefer to take part in satisfying the goal. Formally:

(A5) For any agent i E A, t E T and for agreements s E {S;j U Sil} and s' E Sj,, j, IE A,j f: If: i, (s, t) >-i (s',t).

The first case we consider is that there is a period in which one of the agents prefers opting out of the negoti­ ation over any agreement. We also assume that in such a case the other agents still prefer at least one agreement over opting out in this period. We will now prove that in such a case if the game has not ended in prior periods, then an agreement will be reached in the prior period, or two periods prior, to the period in which one of the agents prefers opting out over any agreement. We will use additional notation. S{ = {sis E Si, U Sj;, (s, t) >-i (0, t + 1)} where t E T, i,j, IE A, i :/: j :/:I. Sf includes the offers agent j can make on time period t which are better than opting out in the next time period.

Lemma 1 Let (!, g, h) be a Perfect Equilibrium (P.E.) of a model satisfying AO-A5. Suppose there exists T E T such that T > 1 and for any t E T, and for any i E A if t < T then si,t f: -1 and there exists i E A such that si,T+ 1 = -1. Suppose it is j 's turn, j E A, to make an " ' -T -T offer in time period T. If S~ n S 1 n Si f: 0, where · "' -T -T i , IEA,if:jf:l,thenlets1=max-<;{S~nS 1 nSi }. Let si E Sj", k = i or k = I, then using its perfect equilibrium strategy, j will offer k si and k will accept the offer.

". -T -.T If S~ n S 1 n S· = 0 then suppose, without loss of generality, that it is i 's turn to give an offer in time . "· -T-1 - T-1 period T- 1 then let s' = max-<,S'T-1 n S 1 n Si . Let s' E S,~~:, k = j or k = 1, then using its perfect e9uilibrium strategy, i will offer k, in time period T- 1, s' and k will accept the offer.

In the first case we denote si by s and T by 'i' and in the second case we denote s' by s and T- 1 by 'i'.

Proof: The proof of this lemma and the following lem­ mas and theorems can be found in [Kraus and Wilken­ feld, 1991b].

We will show that under certain conditions, in any period there will be an agreement that will be accepted.

Lemma 2 Let (!, g, h) be a Perfect Equilibrium (P.E.) of a model satisfying AO-A5 and let s and 'i' be defined as in Lemma 1. Suppose T < 'i' such that it is i 's turn to make an offer. If for j E A, j f: i there exists x~ E Ssj satisfies the following conditions:

1. (x~, T) >-~~: (0, T) where k E A and i f: k, and (x~, T) >-i (0, T + 1).
2. (x~, T) >-11: (s, T), where k = i or k = j.
3. If exist t E T, T < t < 'i' and s E S, such that (s,t) >-i (x~,T) then (O,T+ 1) >-A: (s,t) where kEA, kf:J.

then if agent i offers agent j x~ in period T, then j using its P.E. strategy, will accept the offer. We denote the set of all the x~ 's satisfying the above conditions by X~.

We will show now that in some cases, the negotiations are concluded in the first period. In other cases, some delay in reaching an agreement may occur. In the worst case, agreement will be reached only in period 'i'.

Theorem 1 Let (!, g, h) be a Perfect Equilibrium (P.E.) of a model satisfying AO-A5 and let X~ be de­ fined as in Lemma 2. Suppose for any i, j E A, i f: j, x'f;- 1 :/: 0. If for all Xfi such that i,j E A, i f: j, t E T and t < T, if x E Xfi then if there is s E S, such that (s,t) >-i (x,t -1) then (O,t) >-A: (s,t), for any k E A, k f: j, then when the agents use their P.E. strategies, agreement will be reached in the first, second or the third periods.

5 Time is Valuable Only to Some Agents

Suppose one of the agents does not lose over time and even gains at least in the early stages of the negotiation. For example, in the robots in Example 2.1, suppose agent A controls the telescope and uses it for his purposes until an agreement is reached. In this case we will assume that agent A prefers any agreement over opting out. As in example 3.1 we will assume that the set of agreements between B and C is empty and that there is only one possible agreement between C and A. Furthermore, we assume that both B and C prefer the agreement between A and C over any agreement between A and B 6 . In this case we show that even when one of the agents gains over time but prefers not to opt out, if the other two agents, which lose over time, have the same preferences they can force the first agent to meet their conditions.

Formally we will make the following assumptions.

(A6) ScB = {0f, and SAc= {sAc}. (The size of the set of possible agreements is limited).

(A7) For every t E T and for every s E SAB, (sAc,t) >-i (s,t), i E {B,C} and (s,t) >-A (sAc,t). (Agents Band C have contradictory preferences to agent A).

(AS) For any t 11 t2 E T such that t1 < t2 and for any s E S, (s,t2) >-A (s,t1), (O,t2) >-A (O,ti) and for i E {B, C}, (s, ti) >-i (s, t2), (0, t1) >-i (0, t2). (Agent A gains over time and agents B and Close over time).

(A9) For any t E T and for any s E S, (s , t) >-A (0, t). (Agent A prefers agreements over opting out).

(A10) Iffor any t,t' E T and for any s E SAc USAB, if (s, t) >-B (0, t') then (s , t) >-c (0, t') and if (s, ~) >-i (0, t), where i E B, C and t' < t then (s , t') >-i (0, t').

We will show now that if there is a period where agent B prefer opting out over any agreement then negotia­ tions will be concluded before that period even though agent A gains over time.

Lemma 3 Let (j, g, h) be a Perfect Equilibrium {P.E.) of a model satisfying AO-A2 and A6-A10. If there exist t1, t2 E T such that t1 < t2, for any s E SAB, (0, t1) >-B (s, ti), (sAc, t2 - 1) >-B (0, t2 - 1) and (0, t2) >-B (sAc, t2), then P(i' 1 , g' 1 , h' 1 ) =(sAc, i) 8 i E T where i is the maximal t such that it is either A or C 's turn to make an offer, t1 ~ i < t2 and (sAc,i) >-B (O,tl) .

The next theorem describes the behavior of the agents.

Theorem 2 Let (j, g, h) be a Perfect, Equilibrium {P.E.) of a model satisfying AO-A2 and A6-A10. If there exist t1, t2 E T such that t1 < t2, for any s E SAB, (O,t1) >-B (s, ti), (sAc, t2- 1) >-B (0, t2- 1) and (O,t2) >-B (sAc,t2), then if there is not< i (i is de­ fined in lemma 3} such that (O,t) >-B (sAc,i) and there is not< i and s E SAB such that (s,t) >-B (sAc,i) and (s,t) >-A (sAc,i) then P(j,g,h) = (sAc,i).

We will demonstrate the above results with the robots from Examples 2.1 and 3.1.

Example 5.1 In the situation in examples 2.1 and 3.1, suppose the robots satisfy AO-A2 and A6-A10 and sup­ pose Vs E SAB, (0, 2) >-B (s, 2) and Vt E T, t < 2 there exists s' E SAB such that (s' , t) >-B (0, t), and (0, 10) >-B (sAc, 10) and (sAc, 9) >-B (0, 9) . Sup­ pose also that (sAc, 3) >-B (0, 0) and for any s E SAB,(sAc,3) >-B (s,O) but Vt E T,t > 3,(0,2) >-B

6 0ther examples where such situations occurred can be found in [Kraus and Wilkenfeld, 1991a; Kraus and Wilken­ feld, 1990].

7 0 denotes the empty agreement.

8 Let s 0 ··· sT E S define /ls 0 ··. sT to be the strategy dervied from f after the offers s 0 , ··· , sT have been announced and already rejected. If fT(s0, ... ,ST-t} does not depend on so , ... ST-1 we denote the result by fT . Similarly for g and h.

(sAc, t). Suppose, A, B and C are the first, second and third agents to make an offer, respectively. In period 3 A will offer C to move the telescope together and C will agree.

We will examine now the case where . there is a time period smaller than i and an agreement between A and B that both agents prefer to reach in this time period over SAC in period i. We will need some additional notations for dealing with this case.

Definition5.1 Let f< ~r {(s,t)ls E SAB , (s,t) >-i (sAc, i), where i E {A, B} , t E T and t < i} (i is defined in lemma 3). Let x' ~r max>-of<, i E {A, B}.

Theorem 3 Let (j, g, h) be a Perfect Equilibrium (P.E.) of a model satisfying AO-A2 and A6-A10. If there exist t1, t2 E T such that t1 < t2, for any s E SAB, (0, t1) >-B (s, t1), (sAc, t2- 1) >-B (0, t2- 1) and (0, t2) >-B (sAc, t2), then if there is not < i (i is de­ fined in lemma 3}, such that (O,t) >-B (sAc,i) and if xA = (s',t') = x 8 then P(j,g,h) = (s',t').

6 The Application of the Theory in Building Autonomous Agents

One of the main questions is how one can use the above theoretical results in building agents capable of acting and negotiating under time constraints.

We note that in each, of the cases we have investigated, either in this paper or in [Kraus and Wilkenfeld, 1991a], where we presented a strategic model of negotiations for only two agents, the perfect-equilibrium strategies are determined by parameters of the situation.

So, one can supply agents with the appropriate strate­ gies for each of the cases we have dealt with. When an agent participates in one of those situations, it will need to recognize which type of situation it is in. Assum­ ing the agent is given the appropriate arguments about the situation it is involved in it can construct the exact strategy for its specific case and use it in the negotia­ tions. Since we provide the agents with unique perfect equilibrium strategies, if we announce it to the other agents in the environment, the other agents can not do better than to use their similar strategies.

7 Conclusion and Future Work

In this paper we demonstrate how the incorporation of time into the negotiation procedure contributes to a more efficient negotiation process where there are at least three agents in the environment. We show that in differ­ ent cases this model, together with the assumption that the agents' strategies induce an equilibrium in any stage of the negotiation, may result in the agent being able to use negotiation strategies that will end the negotiation with only a small delay. We suggest that these results are useful in particular in situations with time constraints. We are in the process of using this model in develop­ ing agents that will participate in crisis situations where time is an important issue.

The most obvious outstanding question concerns the relaxation of the assumption of complete information.

In many situations the agents do not have full infor­ mation concerning the other agents. Several works in game theory and economics have considered different versions of the model of Alternative Offers ,with incom­ plete information (see for example, [Rubinstein, 1985; Osborne and Rubinstein, 1990; Chatterjee and Samuel­ son, 1987]). We are in the process of modifying those results for use in DAI environments.

8 Acknowledgement

We would like to thank K. Arrow, R. Aumann, B. Bueno de Mesquita, J. Oppenheimer, A. Rubinstein and P. Young for helpful suggestions about game theory and negotiation. We would also like to thank J . Hendler and D. Perlis for helpful discussions.