留学生计算机硕士dissertation范文-多议题协商协议框架构建-Artificial Intelligence-An agenda-b

留学生计算机硕士dissertation范文-多议题协商协议框架构建-Artificial Intelligence-An agenda-based framework for multi-issue negotiation由留学生dissertation代写中心提供整理文本资源，帮助写更好的计算机硕士dissertation。Shaheen S. Fatima a,∗, Michael Wooldridge a, Nicholas R. Jennings b
a Department of Computer Science, University of Liverpool, Liverpool L69 7ZF, UK
b Department of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK
Received 28 April 2002; received in revised form 28 March 2003
Abstract
This paper presents a new model for multi-issue negotiation under time constraints in an
incomplete information setting. The issues to be bargained over can be associated with a single
good/service or multiple goods/services. In our agenda-based model, the order in which issues are
bargained over and agreements are reached is determined endogenously, as part of the bargaining
equilibrium. In this context we determine the conditions under which agents have similar preferences
over the implementation scheme and the conditions under which they have conflicting preferences.
Our analysis shows the existence of equilibrium even when both players have uncertain information
about each other, and each agent’s information is its private knowledge. We also study the properties
of the equilibrium solution and determine conditions under which it is unique, symmetric, and Paretooptimal.

2003 Elsevier B.V. All rights reserved.
Keywords: Multi-issue negotiation; Game theory; Agendas; Intelligent agents
1. Introduction
Negotiation is a means for agents to communicate and compromise to reach mutually
beneficial agreements [11,14,18,29,30,40]. In such situations, agents have a common
interest to cooperate, but have conflicting interests over exactly how to cooperate. Put
differently, agents can mutually benefit from reaching agreement on an outcome from a
* Corresponding author.
doi:10.1016/S0004-3702(03)00115-2
2 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
set of possible outcomes, but have conflicting interests over the set of outcomes. In this
context, the main problem that confronts agents is to decide how to cooperate—before
they actually enact the cooperation and obtain the associated benefits. On the one hand,
each agent would like to reach some agreement rather than disagree and not reach any
agreement. But, on the other hand, each agent would like to reach an agreement that is as
favourable to it as possible.
To this end, a number of negotiation models that address this problem have been
developed and applied to data allocation in information servers, resource allocation and
task distribution [18,19,27,31,32]. Apart from these, another application area in which
agent-mediated negotiation has received considerable attention is in the field of electronic#p#分页标题#e#
commerce [22–24,35,36]. In this domain, which is the main focus of this paper, the aim is
to build software agents that will optimally negotiate with other agents on behalf of users
for buying and selling goods/services. Here we look at one-to-one negotiation between
a buyer and a seller. In order to develop software agents for such bilateral encounters,
we first examine the important features of real-life bargaining situations that need to be
incorporated in the software agents. To this end, the three crucial features of most practical
bargaining processes are as follows [28]:
(1) The time constraints of the bargainers.
(2) The information state of the bargainers.
(3) The number of issues to be bargained over.
We first explain the role of time in negotiation. Consider an e-commerce scenario in which
a buyer agent and a seller agent negotiate over the price of a good or service. The buyer
clearly prefers a low price, while the seller prefers a high one (hence the competitive nature
of the encounter). In addition to attempting to obtain the best price, agents also usually need
to ensure that negotiation ends before a certain deadline. However, the end point may not
be the only way in which time influences negotiation behaviour. Consider the case in which
the service is provided immediately after negotiation ends successfully (say at price P and
time T ). In some situations, it is not sufficient merely for an agent to ensure that T is any
time less than its deadline. This may be the case, for instance, because one of the agents,
say the buyer, could be losing utility with time as a result of not getting the service. On
the other hand, the seller may perhaps gain more utility by providing the service as late as
possible. Thus, in this case, the seller tries to maximize T (within the limit of its deadline)
and the buyer tries to minimize T . In short, it is clear that agents can have different attitudes
toward time. Generally speaking, the most common time effects in bargaining situations
are time discounting and deadlines [10,21]. An agent that gains utility with time and has
the incentive to reach a late agreement (within its deadline) is said to be a strong or patient
player. An agent that loses utility with time and tries to reach an early agreement is said
to be a weak or impatient player. As we will show, this disposition and the actual deadline
itself strongly influence the negotiation outcome.
The second crucial feature of a bargaining process is information. During negotiation,
each agent has to make decisions about generating offers and counter-offers in such a
way that its own utility from the final agreement is maximized. An essential input to
this decision making process is information; here defined as knowledge about all factors
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 3#p#分页标题#e#
which affect the ability of an individual to make choices in a given situation. For instance,
in bargaining between a buyer and a seller, information includes not only information
about an agent’s own parameters (such as its reservation price or its preferences over
possible outcomes), but also those of its opponent. In most realistic cases agents have
only incomplete information about their opponent.
To this end, game theoretic models have already been proposed for bargaining with
incomplete information. For instance, Rubinstein [34] developed a model in which agents
have incomplete information about time preferences. Fudenberg et al. [12] analyse buyerseller
negotiation in which reservation prices are uncertain. Sandholm and Vulkan [37]
consider uncertainty over agent deadlines. All these models are built on the assumption that
information about the uncertain parameter (in the form of possible values and a probability
distribution over them) is the agents’ common knowledge.However, in practice, perhaps the
main way of acquiring information about the opponent is through learning from previous
encounters. In such cases, an agent’s beliefs about its opponent will not be known to its
opponent. We therefore study the strategic behaviour of agents by treating each agent’s
information as its private knowledge.
The third key feature is the number of issues that have to be negotiated. In many of
the applications that are conceived in the domain of e-commerce, it is important that the
agents should not only bargain over the price of a product, but also take into account
issues such as the delivery time, quality, payment methods, and other product specific
properties. In such multi-issue negotiations, one approach is to bundle all the issues and
discuss them simultaneously as a complete package. This allows the players to exploit
trade-offs among different issues, but requires complex computations to be carried out
[4,17]. The other approach, which is computationally simpler, is to negotiate the issues
sequentially. A second and more important reason why parties may choose to settle issues
one by one is the strategic implications of the choice of the negotiation procedure (i.e.,
issue-by-issue vs. complete package).When there are two objects to negotiate, the decision
to negotiate them simultaneously or one by one is by no means neutral to the outcome
[2,38]. Although issue-by-issue negotiation minimizes the complexity of the negotiation
procedure, an important question that arises is the order in which the issues are bargained
over. This ordering is called the negotiation agenda and it has been shown to be one of the
factors that determines the outcome of negotiation [9]. For instance, if there are two issues,
X and Y , the two agendas XY and YX can lead to two different outcomes. The agents#p#分页标题#e#
need not have identical preferences over these outcomes and one of them may prefer the
agenda XY to YX, while the other may prefer YX to XY . Given this fact, exploring the
role of the bargaining agenda, and how players might manipulate it, is timely, especially
given that many real-life negotiations involve multiple issues.
There are two ways of incorporating agendas in the negotiation model. One is to fix the
agenda exogenously as part of the negotiation procedure. Considering the above example,
one of the agendas, say XY is imposed exogenously. Then the bargainers have to settle
X first, and will be allowed to negotiate Y only after X is settled. The other way, which
is more flexible, is to allow the bargainers to decide which issue they will negotiate next
during the process of negotiation. This is called an endogenous agenda [16] and is the
approach we explore in this paper.
4 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
Existing game theoretic models for issue-by-issue negotiation [1,9,16], which are
basically extensions of [33,34], have two main shortcomings. Firstly, they study the
strategic behaviour of agents by treating the information they have as common knowledge.
In practice however, the information that a player has about its opponent is mostly acquired
through learning from previous encounters. An agent’s beliefs about its opponent will
therefore not be known to its opponent. Secondly, these models do not consider agent
deadlines.We overcome these problems by considering each agent to have its own deadline
and by treating each agent’s information state as its private knowledge. In this case we
obtain the connection between this private knowledge and the existence of equilibrium for
single issue negotiation. We then extend this model for multi-issue negotiation and study
the properties of the equilibrium solution.
To provide a setting for our negotiationmodel,we consider the case in which negotiation
needs to be completed by a specified time, which may be different for different parties
(since this is the most realistic case). Apart from the agents’ respective deadlines, the
time at which agreement is reached can affect the agents (patient or impatient) in different
ways [7]. To this end, Fatima et al. [7] presented a single-issue model for negotiation
between two agents under time constraints and in an incomplete information setting by
considering the agents’ information as its private knowledge. Within this context, they
determined optimal strategies for agents but did not address the issue of the existence
of equilibrium. Here we adopt this framework and prove that mutual strategic behavior
of agents, where both use their respective optimal strategies, results in equilibrium. We
then extend this framework for multi-issue negotiation. The order in which issues are#p#分页标题#e#
bargained over and agreements are reached is determined by the equilibrium strategies.
The time of equilibrium agreement may not be equal for all the issues. Consequently,
the outcome of multi-issue negotiation can be implemented in two ways: sequentially or
simultaneously.We then determine conditions under which agents have similar, as well as
conflicting, preferences over the implementation scheme. Finally, we study the properties
of the equilibrium solution.
This work extends the state of the art in multi-issue negotiation by presenting a more
realistic negotiation model that captures the three aspects, mentioned above, that are
associated with many real-life bargaining situations. Firstly, it is a model for negotiating
multiple issues. Secondly, it takes the time constraints of bargainers into consideration,
both in the form of agent deadlines and their discounting factors. Thirdly, it allows agents
to have incomplete information about each other, and each agent’s information is treated
as its private knowledge. Although we study bargaining in which agents have one specific
information state and the agenda is endogenous, our negotiation framework is general and
can be used for exploring a wide range of negotiation environments by changing the agents’
information states or the way in which the players manipulate the agenda.
The paper is organised as follows. Section 2 describes the components that make up a
negotiation model. In Section 3, we describe the single issue negotiation model. Section 4
extends this for negotiating multiple issues. Section 5 discusses related work. Finally,
Section 6 gives some conclusions and suggests some topics for future work. Appendix A
provides a summary of notation employed throughout the paper.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 5
2. Components of a negotiation model
The four components of a negotiation model are as follows [31]:
(1) The negotiation protocol.
(2) The negotiation strategies.
(3) The information state of agents.
(4) The negotiation equilibrium.
The protocol specifies the rules of encounter between the negotiation participants. That
is, it defines the circumstances under which the interaction between agents takes place,
what deals can be made and what sequences of offers are allowed. In general, agents
must reach agreement on the negotiation protocol to use before negotiation proper begins.
A negotiation protocol can be designed for handling a single issue or multiple issues.
Within the class of multi-issue negotiations, we can have protocols that negotiate on all
the issues together or one by one.
An agent’s negotiation strategy is a specification of the sequence of actions (usually
offers or responses) the agent plans to make during negotiation. There will usually be#p#分页标题#e#
many strategies that are compatible with a particular protocol, each of which may produce
a different outcome. For example, an agent could concede in the first round or bargain
very hard throughout negotiation until its timeout is reached. It follows that the negotiation
strategy that an agent employs is crucial with respect to the outcome of negotiation. It
should also be clear that the strategies which perform well with certain protocols will not
necessarily do so with others. The choice of a strategy to use is thus a function not just of
the specifics of the negotiation scenario, but also the protocol in use.
An agent’s information state describes the information it has about the negotiation
game. Von Neumann and Morgenstern [26] introduced the fundamental classification of
games into those of complete information and those of incomplete information. The former
category is basic. In these games the players are assumed to know all relevant information
about the rules of the game and players’ preferences that are represented by utility
functions. In the latter category, information may be lacking about a variety of factors
in the bargaining problem. Thus each player may have some private information about
his own situation that is unavailable to the other players, while having only probabilistic
information about the private information of other players. Following Harsanyi [14,15],
models of games of incomplete information proceed from the assumption that all players
start with the same probability distribution on this private information and that these priors
are common knowledge. This is modelled by having the game begin with a probability
distribution, known to all players. Thus players not only have priors over other players’
private information, they also know what priors the other players have over their own
private information. Strategic models of incomplete information thus include an extra level
of detail, since they specify not only the actions and information available to the other
players in the course of the game, but also their probability distributions and information
prior to the start of the game.
A negotiation mechanism consists of a negotiation protocol together with the negotiation
strategies for the agents involved. A negotiation mechanism has to be stable (i.e.,
6 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
a strategy profile must constitute an equilibrium), the earliest concept of which was the
Nash equilibrium for games of simultaneous offers [25]. Two strategies are in Nash equilibrium
if each agent’s strategy is a best response to its opponent’s strategy. This is a necessary
condition for system stability where both agents act strategically. For sequential offer
protocols, the Nash equilibrium concept was strengthened in several ways by requiring#p#分页标题#e#
that the strategies stay in equilibrium at every step of the game [39]. In summary, rationality,
as understood in game theory, requires that each agent will select an equilibrium
strategy when choosing independently. Given this, game theory prescribes the following
main criteria [28] for evaluating the equilibrium outcome:
(1) Uniqueness. If the solution of the negotiation game is unique, then it can be identified
unequivocally.
(2) Efficiency. An agreement is efficient if there is no wasted utility (i.e., the agreement
satisfies Pareto-optimality).An outcome is Pareto-efficient if there is no other outcome
that improves the payoff of one agent without making another agent worse off. All
other things being equal, Pareto-efficient solutions are preferred over those that are
not.
(3) Symmetry. A bargaining mechanism is said to be symmetric if it does not treat the
players differently on the basis of inappropriate criteria. Exactly what constitutes
inappropriate criteria depends on the specific domain. For example, if the bargaining
outcome remains the same irrespective of which player starts the process of bargaining,
then it is said to be symmetric with respect to the identity of the first player.
(4) Distribution. This property relates to the issue of how the gains from trade are split
between the players; does the outcome split the gains equally between the traders or
does it favour one agent more than the other? In this paper, our aim is not to design
a negotiation mechanism that divides the gains fairly among players but to study the
outcome that results when both agents are self-interested.
With these broad guidelines in mind, many different models can be designed. Below, we
report on the development of a new model based on negotiation decision functions (see
Section 3.2) for bargaining over multiple issues. We first describe the single issue model
and study its equilibrium strategies and outcomes. We then extend this model for multiissue
negotiation and study its equilibrium properties.
3. The single-issue negotiation model
We first describe the single issue negotiation protocol and obtain the agents’ optimal
strategies. We then prove that the optimal strategy profiles form sequential equilibrium.
3.1. The negotiation protocol
Here we adopt what is basically an alternating offers protocol [28]. Let b denote the
buyer, s the seller and let [IPa,RPa] denote the range of values for price that are acceptable
to agent a, where a ∈ {b, s}. We let ˆa denote agent a’s opponent. A value for price that is
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 7
acceptable to both b and s (i.e., the zone of agreement) is the interval [RPs ,RPb] and
(RPb − RPs ) is known as the price-surplus. The buyer’s initial price, IPb, has a value less#p#分页标题#e#
than the seller’s reservation price. Similarly, the seller’s initial price has a value greater
than the buyer’s reservation price. In other words, both IPb and IPs lie outside the zone of
agreement.
The agents alternately propose offers at times in T = {0, 1, . . .}. Each agent has a
deadline. T a denotes agent a’s deadline where T a ∈ T . Let pt
b→s denote the price offered
by agent b at time t . Negotiation starts when the first offer is made by an agent. The
agent who makes the initial offer is selected randomly at the beginning of negotiation.
When an agent, say s, receives an offer from agent b at time t , i.e., pt
b→s , it rates the
offer using its utility function Us . If the value of Us for pt
b→s at time t is greater than
the value of the counter-offer agent s is ready to send in the next time period, t ′ , i.e.,
Us(pt
b→s , t)
Us (pt ′
s→b, t ′) for t ′ = t + 1, then agent s accepts the offer at time t and
negotiation ends successfully in an agreement. Otherwise a counter-offer is made in the
next time period, t ′. Thus the action, As , that agent s takes at time t , in response to the
offer pt
b→s , is defined as:
As

t ,pt
b→s

=


Quit if t > T s ,
Accept if Us (pt
b→s )
Us(pt ′
s→b),
Offerpt ′
s→b at t ′ otherwise.
Agents’ utilities are defined with the following two von Neumann–Morgenstern utility
functions [17] that incorporate the effect of time discounting
Ua(p, t) = Ua
p(p)Ua
t (t). (1)
Ua
p and Ua
t are unidimensional utility functions. Here, preferences for attribute p, given
the other attribute t , do not depend on the level of t . Ua
p is defined as:
Ua(p) =

RPb − p for the buyer,
p − RPs for the seller.
Ua
t is defined as Ua
t (t) = (a)t , where a is the discounting factor. Thus when (a > 1) the
agent is patient and gains utility with time and when (a < 1) the agent is impatient and
loses utility with time. The utility from conflict is lower than the utility from any of the
possible agreements for both agents. Each agent prefers to reach an agreement, rather than
disagree and not reach any agreement at all, since the utility from an agreement is always
higher than conflict utility. Consequently, it is optimal for agent a to offer RPa at the latest
by its deadline, if it has not done so earlier, and avoid a conflict (see Section 3.5 for details
on an agent’s optimal strategy). Agents are said to have similar time preferences if both
gain on time or both lose on time. Otherwise they have conflicting time preferences.#p#分页标题#e#
3.2. Counter-offer generation
The tactics for generating offers and counter-offers are defined as follows. Since both
agents have a deadline, we assume that they use a time-dependent tactic (e.g., linear (L),
Boulware (B) or Conceder (C) [3]) for generating offers. In these tactics, the predominant
factor used to decide which value to offer next is time t . These tactics vary the value of
8 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
price depending on t and T a. The initial offer is a point in the interval [IPa, RPa]. The
constant ka multiplied by the size of interval determines the price to be offered in the
first proposal by agent a. The offer made by agent a to agent ˆa at time t (0  t  T a) is
modelled as a function a depending on time as follows:
pt
a→ˆa =

IPa + a(t)(RPa − IPa) for a = b,
RPa + (1− a(t))(IPa − RPa) for a = s.
A wide range of time-dependent functions can be defined by varying the way in which
a(t) is computed (see [3] for more details). However, functions must ensure that 0 
a(t)  1, a(0) = ka (where ka lies in the interval [0, 1]), and a(T a) = 1. That is, the
offer will always be between the range [IPa,RPa], at the beginning it will give the initial
constant and when the deadline is reached it will offer the reservation value. The initial
offer is IPa if ka = 0, lies between IPa and RPa for 0 < ka < 1, and is RPa for ka = 1.
Thus by varying ka between 0 and 1, the initial price that is offered can be varied between
IPa and RPa . Since we want IPa to be the initial offer, we set ka to 0. Function a(t) is
called the negotiation decision function (NDF) and is defined as follows:
a(t) = ka +


1 − ka
t
T a
1/
. (2)
These NDFs represent an infinite number of possible tactics, one for each value of  (see
[3] for more details). However, depending on the value of , three extreme sets show
clearly different patterns of behaviour (see Fig. 1).
(1) Boulware (B) [30]. For this tactic,  < 1 and close to zero. The initial offer is
maintained till time is almost exhausted, when the agent concedes up to its reservation
value. Fig. 1 shows the Boulware function for  = 0.02.
Fig. 1. Negotiation decision functions for the buyer.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 9
(2) Conceder (C) [29]. For this tactic,  > 1. The agent goes to its reservation value very
quickly1 and maintains the same offer till the deadline. Fig. 1 shows the Conceder
function for  = 50.
(3) Linear (L) Finally, when  = 1, price is increased linearly.
The value of a counter offer depends on the initial price (IP) at which the agent starts
negotiation, the final price (FP) beyond which the agent does not concede, the time t at#p#分页标题#e#
which it offers the final price, and . These four variables form an agent’s strategy.
Definition 1. An agent’s strategy Sa is defined as a quadruple whose elements are the
initial price (IPa) at which the agent starts negotiation, the final price (FPa) beyond which
the agent does not concede, time (ta ) at which the final price is offered, and a . Thus
Sa =
 
IPa,FPa, ta,a

.
Agent a uses its strategy, Sa , to generate an offer, pt
a→ˆa, for t  ta . Different strategies
can be defined for different values of these four elements. For example, when b starts
making offers at s’s reservation price, and offers its own reservation price at a time, say
T , and uses an extreme Boulware NDF, then Sb is defined as Sb =
RPs ,RPb, T ,B. Note
that the B in Sb is a value for  that gives the Boulware function. In general, we use B,
C, and L to indicate a value for  that gives the Boulware, Conceder, and Linear NDFs
respectively. When both agents use strategies of this form, negotiation can end either in
an agreement or a conflict, depending on the four elements that constitute each agent’s
strategy.
Definition 2. The negotiation outcome (O) is an element of
(p, t), C. The pair (p, t)
denotes the price and time of agreement where p ∈ [RPs ,RPb] and t ∈ [0,min(T b, T s )].
C denotes the conflict outcome.
As an illustration, when agent b’s strategy is defined as Sb
1 =
IPb,RPb, T s ,B and
agent s’s strategy is defined as Ss1
=
IPs ,RPs , T s ,B, the outcome (O1) that results is
shown in Fig. 2(a) (i.e., the point where Sb
1 and Ss1
converge). As shown in the figure,
agreement is reached at a price RPs +(price-surplus/2) and at a time close to T s . Similarly
when the NDF in both strategies is replaced with C, then agreement (O2) is reached at
the same price but towards the beginning of negotiation. If the agents’ strategies do not
converge before the deadline, then negotiation results in a conflict. This is illustrated in
Fig. 2(b), where both agents use the extreme Boulware NDF, but offer the final price at
different times, thereby resulting in conflict.
Since agents are assumed to be Von Neumann and Morgenstern [26] expected utility
maximizers, we need to determine the four elements of each agent’s strategy that will give
1 As  increases (decreases)  becomes more Conceder (Boulware). At very high (low) values of ,  is an
extreme Boulware (Conceder). In our discussion, Boulware always refers to the extreme Boulware for which the
function generates the initial price from the beginning until the time point just prior to T , and the final price at
time T . Similarly Conceder always refers to the extreme Conceder.#p#分页标题#e#
10 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
Fig. 2. Negotiation outcome for Boulware and Conceder functions. (a) Agreement. (b) Conflict.
it maximum possible utility. An agent’s optimal strategy depends on the information it has
about the negotiation parameters. We therefore define the information state for each agent
and then show how the optimal strategies are determined.
3.3. Agents’ information states
Each agent has a reservation limit, a deadline, a utility function and a strategy.
Thus the buyer and seller each have four parameters denoted
RPb, T b,Ub, Sb and

RPs , T s ,Us , Ss  respectively. The outcome of negotiation depends on all these eight
parameters. The information state, I a , of an agent a is the information it has about the
negotiation parameters. An agent’s own parameters are known to it, but the information it
has about the opponent is not complete.We define I b and I s as:
I b =
 
RPb, T b,Ub, Sb,Ls
p,Lst

and
I s =
 
RPs , T s ,Us , Ss ,Lb
p,Lb
t

,
where RPb, T b, Ub and Sb are the information about the buyer’s own parameters and Ls
p
and Lst
are its beliefs about the seller. Similarly, RPs , T s , Us and Ss are the seller’s own
parameters and Lb
p and Lbtare its beliefs about the buyer. Lst
and Ls
p are two probability
distributions2 that denote agent b’s beliefs about agent s’s deadline and reservation price.
Lst
is an n-tuple of ordered pairs of the form
T s
i ,s
i , where 1  i  n. The first element in
a pair, T s
i , (where T s
i ∈ T for 1  i  n) denotes a possible value for the seller’s deadline
and the second element, s
i , denotes the probability with which the seller’s deadline is T s
i .
2 The difference between this model and [6,7] is that in the latter, agents have a binary probability distribution
over their opponent’s reservation value and deadline whereas here we consider the more general case by taking a
probability distribution over n values.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 11
In other words, the pairs are possible time values for agent s’s deadline and the associated
probabilities. One of the n possible values is agent s’s actual deadline. The pairs are
assumed to be arranged in ascending order of time values, i.e., T s
i < T s
i+1 for 1  i  n−1.
Ls
p is analogous to Lst
and denotes the buyer’s beliefs about the seller’s reservation price.
The elements of Ls
p are pairs are denoted
RPs
i , s
i  where 1  i  m. The first element#p#分页标题#e#
is a possible value for the seller’s reservation price and  s
i is the associated probability.
Similarly Lbt
and Lb
p are two probability distributions that denote the seller’s beliefs about
the buyer’s deadline and reservation price. The elements of Lbt
are of the form
T b
i ,b
i 
(where T b
i ∈ T for 1  i  n) and the elements of Lb
p are of the form
RPb
i , b
i . For our
present analysis we consider the case where RPs
1 < RPb
m, i.e., the highest possible value for
the seller’s reservation price is less than the lowest possible value for the buyer’s reservation
price.3 We treat the agents’ beliefs as being static4 and not changing during negotiation.
Thus agents have uncertain information about each other’s deadline and reservation
value. Moreover, agents do not know their opponent’s utility function or strategy. In
other words, an agent’s information state models two5 parameters of the opponent: the
opponent’s reservation price and its deadline. Each agent’s information state is its private
information that is not known to its opponent.
3.4. Negotiation scenarios
On the basis of the relationship between agent deadlines and their discounting factors,
we define six negotiation scenarios. An agent negotiates in one of these six scenarios. The
buyer believes that with probability s
i , the seller’s deadline is T s
i . This gives rise to three
relations between agent deadlines. All the n possible seller deadlines could be less than
the buyer’s deadline, some of them could be less and the others greater, and finally all of
them could be greater than the buyer’s deadline. For each of the two possible realizations
of the buyer’s discounting factor, these three relations can hold between agent deadlines. In
other words, negotiation can take place in any one of the six scenarios, N1, . . . ,N6, listed
in Table 1. The set of negotiation scenarios for the seller can be defined in the same way.
The scenario combinations that are possible for the two agents to interact are listed in
Table 2. For instance, when agent b is in scenario N1, T s is less than T b. In such a situation,
agent s can only be in one of the four scenarios N2, N3, N5 or N6, since T s can be less
then T b in only these four scenarios. Recall that one of the possible values is the opponent’s
actual deadline. This implies that when agent b is in scenario N1, agent s can neither be in
scenario N1 nor in N4. Thus in general when agent a is in scenario N1, agent ˆa may be in
any one of the four scenarios—N2, N3, N5, or N6. The remaining scenario combinations,
listed in Table 2 can be obtained using similar reasoning. Note that it is possible for the#p#分页标题#e#
agents to have equal deadlines in the following cases: when both agents are in scenario N2,
3 Future work will deal with the situation where RPs
1 > RPb
m.
4 Future work will deal with the situation where an agent learns and changes its beliefs during negotiation.
5 An agent’s information state may be different for different negotiations. Also, as shown in [5], the
information states of agents strongly influence the negotiation outcome. It would therefore be interesting to study
the negotiation process by modelling other parameters of the opponent. Future work will deal with such a study.
12 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
Table 1
Possible negotiation scenarios for agent b
Negotiation scenario Relationship between agent deadlines Discounting factor
N1 T s
n < T b b > 1
N2 T s
k < T b  T s
k+1 for k + 1 < n b > 1
N3 T b < T s
1 b > 1
N4 T s
n < T b b < 1
N5 T s
k < T b  T s
k+1 for k + 1 < n b < 1
N6 T b < T s
1 b < 1
Table 2
Possible negotiation scenarios for buyer-seller interactions
Agent a Agent ˆa
N1 N2, N3, N5, N6
N2 N1, N2, N3, N4, N5, N6
N3 N1, N2, N4, N5
N4 N2, N3, N5, N6
N5 N1, N2, N3, N4, N5, N6
N6 N1, N2, N4, N5
or when both agents are in scenario N5, or when agent a is in scenario N2 and agent ˆa is
in scenario N5. For all the other combinations, the agents have different deadlines.
3.5. Optimal strategies
We describe how optimal strategies are obtained for players that are von Neumann–
Morgenstern expected utility maximizers. The discussion is from the perspective of the
buyer (although the same analysis can be taken from the perspective of the seller). In order
to simplify the discussion we first assume that Ls
p contains a single element, which is the
seller’s reservation price, and obtain the optimal strategy. We then extend the analysis to
the more general case where Ls
p contains m elements.
Each agent’s optimal strategy is determined on the basis of its own information state,
i.e., the buyer’s optimal strategy is determined on the basis of I b and the seller’s optimal
strategy is determined on the basis of I s . We then determine if this mutual strategic
behavior of agents results in equilibrium.
3.5.1. Optimal strategies for the buyer when Ls
p contains a single element
In all the six scenarios, the strategies should ensure agreement by the earlier deadline
(i.e., T s if T s < T b and T b if T b < T s ). Otherwise the agent with the earlier deadline quits
and negotiation ends in a conflict, a situation which both agents prefer to avoid. We begin#p#分页标题#e#
with scenario N1 where all the n possible values for the seller’s deadline are less than T b.
Since b > 1 in scenario N1, the buyer prefers to reach agreement at the latest possible
time and at the lowest possible price. As T s < T b in scenario N1, the latest possible time
for reaching an agreement is T s
n .
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 13
Fig. 3. Buyer strategies in different scenarios when Ls
p contains a single element.
The outcome of negotiation depends on both agents’ strategies. Since both agents use
a time-dependent strategy, an agent always plays a strategy that offers its own reservation
price at its deadline. The buyer does not know the seller’s deadline, but it has a lottery
(Lst
) over n possible values for the seller’s deadline. So the buyer knows that if the seller’s
deadline is T s
i , then the seller will play a strategy, Ss
i , that offers RPs at T s
i . The probability
that the seller’s deadline is T s
i is s
i , i.e., the seller will play strategy Ss
i with probability
s
i . From its lottery (Lst
) the buyer knows that the seller can play n different strategies,
and will play strategy Ss
i with probability s
i . In other words, although the buyer does not
know the seller’s actual strategy, it knows6 the possible strategies the seller can play and
the associated probabilities.
Since the maximum possible value for the seller’s deadline is less than T b, the buyer
can minimize the price of agreement by waiting for the seller to offer RPs . Thus the
6 Note that the buyer does not know the seller’s complete strategy. It only knows the seller’s final price and
the time at which the price is offered.
14 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
optimal price of agreement, denoted Pb
o , is RPs . As an agent’s utility also depends on
time, and b > 1, the buyer tries to maximize the time of agreement. Since the buyer has n
possible values for the seller’s deadline, it has n strategies to choose from. At time t during
negotiation, strategy Sb
j is defined as
IPb,RPs , T s
j ,B for all t  T s
j . At all later times,
(i.e., between T s
j and T s
n ) the strategy offers the price RPs . Thus the earliest time at which
agreement can be reached using strategy Sb
j is T s
j and the latest time is T s
n . If the seller’s
actual deadline is less than T s
j , then Sb
j results in conflict. These strategies are depicted in
Fig. 3(a). Out of these n strategies, the one that gives the buyer the maximum expected
utility (EUbo
) is its optimal strategy (Sb#p#分页标题#e#
o ). Agent b’s expected utility from strategy Sb
j , is:
EUb
j =
j−1
x=1
sx
Ub( C)+ s
jUb

RPs , T s
j

+
n
y=j+1
sy
Ub

RPs , t

(3)
where T s
j  t  T s
n .
This is the general expression for the buyer’s EU from different strategies. Here, the value
of t depends on the opponent’s strategy. In Section 3.5.2 we will explain how to obtain
the value of t . For the present assume that this value is known to us. For this given value
of t , the expected utility depends on the probability distribution (s ), the utility function
(Ub), and j . For example, the EU for different values of j between 1 and 15 is illustrated
in Fig. 4. In this example, s was defined as a Poisson distribution and b was 1.6 (a value
greater than 1). As seen in the figure, EUb
j is maximum at j = 7, indicating that the
optimal time for entering the zone of agreement, denoted T s
J , is T s
7 . The optimal strategy
is therefore Sb
7 . In this figure, the time points are at uniform discrete intervals. However,
this is not necessary as long as the conditions for convergence of agents’ strategies (listed
Fig. 4. Buyer’s EU for the possible strategies in scenario N1.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 15
Table 3
Optimal buyer strategies in different negotiation scenarios when Ls
p contains a single element. T ′ denotes the
second time period, i.e., if negotiation begins at time t , T ′ = t +1
Negotiation scenario Time t during negotiation Optimal strategy
N1 t  T s
J
IPb,RPs , T s
J ,B
t > T s
J
RPs ,RPs , T s
n ,L
N2 t  T s
J
IPb,RPs , T s
J ,B
T s
J < t  T s
k
RPs ,RPs , T s
k ,L
t > T s
k
RPs ,RPb, T b,B
N3 t  T b
IPb,RPb, T b,B
N4 t  T ′
IPb,RPs , T ′,C
t > T ′
RPs ,RPs , T s
n ,L
N5 t  T ′
IPb,RPs , T ′,C
T ′ < t  T s
k
RPs ,RPs , T s
k ,L
t > T s
k
RPs ,RPb, T b,B
N6 t  T ′
IPb,RPb, T ′,C
t > T ′
RPb,RPb, T b,L
in Section 3.5.3) are satisfied. For a higher value of b, EUb
j is maximum at a higher value
of j . Lowering the value of b causes the peak of the curve to shift left. In other words
T s
J increases as b increases and T s
J decreases as b decreases. For b = 1, EUb is at a
maximum for j = 1. This happens because the agent is indifferent to time. Higher values#p#分页标题#e#
of j result in some conflict situations and thus give a lower utility. But when b > 1, the
agent gains utility with time and the maximum utility is obtained for j > 1.
The buyer’s optimal strategy for scenario N1 is listed in Table 3. Let Sb
o (t) denote the
price generated by the buyer’s optimal strategy at time t . The buyer’s action function for
scenario N1 is defined as follows:
o (t),
Offer Sb
o (t ′) in the next time period t ′ otherwise.
In the definition of an agent’s action given in Section 3.1, the opponent’s offer is accepted
if the utility from the opponent’s offer at time t is greater than or equal to the utility of the
offer the agent is willing to generate at time t ′. But here, in order to decide when to accept
the seller’s offer, the price offered by the seller at time t (pt
s→b) is compared with the price
generated by the buyer’s optimal strategy (Sb
o ) at time t . This is because the seller’s actual
deadline is not known to the buyer, and t could be the seller’s deadline, in which case the
seller quits and negotiation ends in a conflict if the buyer does not accept the offer at time
t . So even though the buyer’s utility increases with time, it has to accept the seller’s offer
o (t) and thereby avoid the chance of a conflict.
In scenario N2, the seller’s deadline can be either less than or greater than T b. Since
some of the possible values for the seller’s deadline are less than T b, the buyer’s optimal
strategy would be to wait for the opponent to offer RPs . If T s < T b, the latest time by
which the seller will offer RPs is T s
k . Thus until T s
k , the buyer need not offer a price greater
16 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
than RPs . If an agreement is not reached by T s
k , it implies that the seller’s deadline is
greater than T b and to avoid conflict, the buyer needs to offer its reservation price RPb
at T b. Thus agent b should enter the zone of agreement at the latest possible time (to
ensure that agreement is not reached earlier than that), remain at RPs until T s
k and then
offer/accept its own reservation price, RPb, at T b. The possible times for entering the zone
of agreement are T s
1 , . . . , T s
k . These strategies are depicted in Fig. 3(b), where strategy Sb
j
enters the zone of agreement at T s
j . The expected utility for strategy Sb
jy and T s
j  t2  T b.
As for scenario N1, assume that the values of p, t1, and t2, are known. In Section 3.5.2 we
will explain how to obtain these values. For the given values of p, t1, and t2, the values
of EUb
j for different values of j between 1 and 15 and b = 1.6 (where s is a Poisson#p#分页标题#e#
distribution) are depicted in Fig. 5. As seen in the figure, the value of j for which EUb
j is
maximum depends on the value of k. For higher values of b, we get the same pattern as in
Fig. 5 but the peak of the curve shifts to the right. Lowering the value of b shifts the peak to
the left. In other words, the optimal time (T s
J ) for entering the zone of agreement increases
as b increases and decreases as b decreases. Fig. 6 shows EUb for b = 1. As seen from
the figure, EUb is maximum at j = 1. This happens because, for b = 1, the agent is
Fig. 5. Buyer’s EU for different strategies in scenario N2 when b > 1.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 17
Fig. 6. Buyer’s EU for different strategies in scenario N2 when b = 1.
indifferent to time. Higher values of j result in some conflict situations and thus give a
lower utility. But when b > 1, the agent gains utility with time and the maximum utility is
obtained for j > 1. The buyer’s optimal strategy for scenario N2 is listed in Table 3. The
buyer’s action function for scenario N2 is the same as that for scenario N1.
In scenario N3, the buyer gains utility with time (i.e., b > 1) and T b < T s
1 . The buyer’s
optimal strategy here is Sb
o =
IPb,RPb, T b,B. This strategy (shown in Fig. 3(c)) enters
the zone of agreement at the latest possible time, which is close to the earlier deadline T b,
and thereby maximizes the time of agreement. It also optimizes the price of agreement by
offering RPb only at T b.
In the remaining three scenarios, N4 to N6, b < 1 and the buyer loses utility with time.
In scenario N4 (shown in Fig. 3(d)), it is clear that the buyer can optimize both the price
and the time of agreement by offering RPs right from the beginning of negotiation, until
T s
n (see Table 3). Contrast this with Sb
o of scenario N1, in which the zone of agreement is
entered at T s
J , whereas here it is entered at the beginning of negotiation using the Conceder
function (since b < 1).
In scenario N5, the buyer’s optimal strategy is to offer RPs from the beginning of
negotiation until T s
k . If T s  T s
k , then negotiation ends at the latest by T s
k . Otherwise
it continues beyond T s
k . The buyer then has to concede up to RPb in order to ensure
agreement (see Fig. 3(e)). This strategy is listed in Table 3.
Finally, in scenario N6, the buyer’s optimal strategy is to offer RPb right from the
beginning of negotiation until T b (see Fig. 3(f)). This is because when the buyer is
in scenario N6, the possible scenarios for the opponent are N1, N2, N4 or N5. Since
the seller also behaves strategically, in none of these scenarios will agent s concede#p#分页标题#e#
beyond RPb, until time T b, using its optimal strategy. Thus for the price RPb, the time
of agreement is optimized in strategy Sb
o using the Conceder function. Table 3 lists the
18 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
buyer’s optimal strategies in all the six negotiation scenarios. The buyer’s action function
in all the scenarios is the same as that for scenario N1.
3.5.2. Optimal strategies for the buyer when Ls
p contains more than one element
Optimal strategies for the buyer when Ls
p contains more than one element remain the
same as those obtained in Section 3.5.1 in some, but not all, negotiation scenarios. Only
those optimal strategies (listed in Table 3) that depend on the opponent’s reservation price
change, while the others remain the same. More specifically, the optimal strategies in
scenarios N3 and N6 remain the same, while those in scenarios N1, N2, N4, and N5 change
when Ls
p contains more than one element.We analyze each of these four scenarios below.
The buyer’s action function, Ab, does not depend on the number of elements in Ls
p and
therefore remains the same as defined in Section 3.5.1 for all the scenarios.
As mentioned in Section 3.3, the information state of the buyer, I b, has n possible
values for the seller’s deadline and m possible values for its reservation price. Also, recall
that agent b believes that  s
i is the probability that the opponent’s reservation price is RPs
i
and that s
j is the probability that the opponent’s deadline is T s
j . The probability that the
seller has the reservation price RPs
i and deadline T s
j is thus the product of  s
i and s
j , and
is denoted ) s
i,j .
Consider scenario N1 first. The possible buyer strategies for this scenario are depicted in
Fig. 7. The number of possible strategies here is m×n. We use Sb
i,j to denote the strategy
that starts making offers at IPb, offers RPs
i at T s
j using the Boulware function, and does not
change the price thereafter. The strategy that yields the highest EU is the buyer’s optimal
strategy. Let I and J denote the values of i and j that give agent b the highest utility. Here
we need to find these two values. Contrast this with the case where Ls
p had a single element
which required finding only the optimal value of j , i.e., J .
Fig. 7. Possible buyer strategies in scenario N1 when Ls
p contains more than one element.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 19
The outcome of negotiation depends on both the buyer’s and the seller’s strategy. The
buyer does not know the seller’s strategy, but it has two lotteries, Ls#p#分页标题#e#
p and Lst
, over the
seller’s reservation price and deadline. So if the seller’s reservation price and deadline are
RPs
i and T s
j , then it plays strategy Ss
i,j that offers RPs
i at T s
j . The probability with which the
seller plays strategy Ss
i,j is ) s
i,j . Thus although the buyer does not know the seller’s actual
strategy, it knows that the seller can play m × n different strategies and the associated
probabilities.
Consider the strategy Sb m,n. This strategy results in an agreement only if the seller’s
actual reservation price is RPs
m and its deadline is T s
n . All the other values for the seller’s
reservation price or deadline result in a conflict. Thus the EU from strategy Sb m,n is:

In general, strategy Sb
i,j results in conflict if either the seller’s reservation price is higher
than RPs
i , or its deadline is less than T s
j . The utility from Sb
i,j is therefore:

In the above expression, the values of p1 and p2 depend on two factors: the opponent’s
strategy and the identity of the player that makes a move at the earlier deadline. The values
of t1 and t2 depend only on the opponent’s strategy. Although the buyer does not know the
opponent’s actual strategy, it does know that the opponent will also behave strategically.
This strategic behavior depends on the opponent’s scenario. Recall that when the buyer’s
scenario is N1, the seller can be in any of the four scenarios: N2, N3, N5, or N6. We know
from Section 3.5.1 that in scenario N6, an agent’s optimal strategy is to offer its reservation
price using the Conceder function. Thus if agent s is in scenario N6, its optimal strategy is
to offer RPs using the Conceder function. In addition to the seller’s strategy, the values of
p1 and p2 also depend on who makes an offer at the earlier deadline. The player that makes
an offer at the earlier deadline could be the buyer or the seller, depending on who made
the initial offer. Consider the case where it is the seller’s turn to make a move at the earlier
deadline. The seller’s optimal strategy in scenario N6 is to offer RPs using the Conceder
function. As per the buyer’s action function, the buyer accepts the seller’s offer at T s
j . We
therefore get p1 = p2 = RPs
y and t1 = t2 = T s
j . On the other hand, if it is the buyer’s turn
to make a move at the earlier deadline, it offers RPs
i . For z
j , RPs
i

RPs , and the seller
20 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
accepts the buyer’s offer at time T s
j . This makes p1 = p2 = RPs
i and t1 = t2 = T s
j . Using#p#分页标题#e#
similar analysis, it can be seen that when agent s is in any of the remaining three scenarios
(N2, N3, or N5), we get p1 = p2 = RPs
y , t1 = T s
x , and t2 = T s
z if the seller makes an offer at
the earlier deadline; and p1 = p2 = RPs
i , t1 = T s
x , and t2 = T s
z if the buyer makes an offer
at the earlier deadline. The buyer knows who will make an offer at the earlier deadline,
since the decision about which player will make the initial offer is made at the beginning
of negotiation and thereafter players take turns alternately at each successive time period.
Since the buyer does not know the seller’s scenario, we associate equal probabilities with
each of the four possible seller’s scenarios, N1, N3, N5, and N6. Let eub1
denote the value
of Eq. (6) when the seller’s scenario is N2, N3, or N5. Also, let eub2
denote the value of
Eq. (6) when the seller’s scenario is N6. The buyer’s EU therefore becomes:
EUb
i,j = 3
4 eub1
+ 1
4 eub2
. (7)
The values of i and j for which Eq. (7) is at a maximum are denoted I and J . The buyer’s
optimal strategy for scenario N1, in terms of I and J , is listed in Table 4.
In scenario N2, the buyer uses a strategy Sb
i,j of the form depicted in Fig. 8. This strategy
starts at IPb, offers RPs
i at T s
j using the Boulware function, keeps the price constant at RPs
i
until T s
k , and thereafter uses the Boulware function again to offer RPb at T b. It is clear from
Fig. 8 that i can vary between 1 and m and j can vary between 1 and k. Thus there are
m × k possible strategies and the one that yields the maximum EU is the buyer’s optimal
strategy. Let I and J denote the values of i and j respectively that give the highest utility.
Here we need to find these two values. Contrast this with the case where Ls
p had a single
element, which required finding only J . The buyer’s EU from strategy Sb
iRPb,RPb, T b,L
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 21
Fig. 8. The buyer’s strategy Sb
i,j in scenario N2 where Ls
p contains more than one element.
Here, the term EUb1
denotes agent b’s EU if the seller’s actual reservation price is higher
than RPs
i , EUb2
denotes its EU if the seller’s actual reservation price is equal to RPs
i , and
EUb3
denotes its EU if the seller’s actual reservation price is lower than RPs
i . We obtain
each of these three terms below.
For EUb1
(i.e., for RPs > RPs
i ), the seller’s deadline can be either less than or equal to
T s
k , or it can be greater than or equal to T s
k+1 (see Fig. 8). If T s  T s#p#分页标题#e#
k , then negotiation ends
in a conflict. EUb1
is therefore given by:
EUb1
=
i−1
x=1

k
y=1
) s
x,yUb( C)+
n
y=k+1
) s
x,yUb

p1, T b

(9)
where (RPs
x  p1  RPb).
Note that the value of p1 depends on the opponent’s strategy and the identity of the
player that makes an offer at the earlier deadline. The four possible seller scenarios for
the second term of Eq. (9) (i.e., T s > T b) are N1, N2, N4, or N5. For each of these
scenarios, the seller’s strategic behavior gives p1 = RPb if the buyer makes a move at
the earlier deadline, and p1 = RPb
I if the seller makes a move at the earlier deadline. Note
that in order to get these values for p1, the buyer and seller strategies need to converge
before the earlier deadline. The conditions for convergence of agents’ strategies are listed
in Section 3.5.3. Also note that the value of RPb
I is present in the seller’s information state
and is not known to the buyer. The buyer can therefore only take p1 = RPb as the closest
approximation.
The next term, EUb2
, is the buyers EU when RPs is equal to RPs
i and is:
22 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
the same way it can be seen that for all the circles shown in Fig. 10, an agreement occurs
at (RPs , T s) if it is the seller’s turn to make an offer at T s . Thus when the buyer’s scenario
is N1 and the seller’s scenario is N2, the outcome is (RPs
I , T s) if the buyer has to make
a move at T s and the outcome is (RPs , T s) if the seller has to make a move at T s . The
remaining entries in Table 6 can be obtained using similar analysis.
The similarity between these results and those of Sandholm and Vulkan [37] on
bargaining with deadlines is that, in both cases, the price-surplus always goes to the
agent with the longer deadline. However, the key difference is that in [37] the deadline
effect overrides time discounting, whereas here the deadline effect does not override time
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 27
Fig. 10. Possible values for the seller’s reservation price and deadline when the buyer’s scenario is N1. Strategy
Sb
I,J is the buyer’s optimal strategy for scenario N1.
discounting. This happens because in [37] the agents always make offers that lie within the
zone of agreement. In our model, agents initially make offers that lie outside this zone, and
thereby delay the time of agreement. Thus when agents have conflicting time preferences,
in our case, agreement is reached near the earlier deadline, but in [37] agreement is reached
towards the beginning of negotiation.#p#分页标题#e#
The outcomes listed Table 6 are possible only if this mutual strategic behavior of agents
leads to equilibrium (i.e., neither agent has the motivation to deviate from its optimal
strategy). In the following subsection we prove this with respect to the standard game
theoretic solution concept of sequential equilibrium [20,28].
3.6. Equilibrium agreements
Recall that an agent’s information state does not contain the opponent’s strategy
or its utility function. This makes negotiation a game, G, of incomplete information.
Furthermore, agents have uncertain information about each other’s reservation price and
deadline. The extensive game, G, is formally defined as a 5-tuple
N,H,P, Ib, Is . The set
N = {b, s} denotes the set of players, each member of the set H is a history, P is the player
function that assigns a member of N to each history. The player that initiates negotiation
is chosen randomly, the players then take turns as defined in the negotiation protocol. The
set Ia denotes the set of agent a’s information sets. Let Ia
i denote the i th element of Ia.
The first three levels of the extensive form of game, G, are shown in Fig. 11. One of the
players, say agent a, starts negotiation. The EUs that agents get from the terminal histories
depend on their negotiation scenarios, and are as determined in Section 3.5.2. For instance,
if agent a’s scenario is N1, then its utility from the terminal histories would be one of m×n
possible values.
We first introduce the notion of information set. In this game G, an agent may not know
which of the nodes it is actually at. Agent a’s information set [20,28], Ia
i , is defined as
28 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
Fig. 11. Extensive form of the negotiation game.
a subset of its decision nodes such that when play reaches one of the decision nodes in
the information set, and it is the agent’s turn to make a move, it does not know which of
these nodes it is actually at. This is because although an agent knows the offer made by the
opponent, it does not know the actual strategy that was used to make the offer. For instance,
in Fig. 11, when it is agent ˆa’s turn to make a move (at level 2), it does not know agent
a’s actual strategy. The nodes labelled 2, . . . , 3, . . . , 4 thus form agent ˆa’s information
set, I ˆa
1 .
Since agents have uncertain information about the opponent, we use the solution
concept of sequential equilibrium for the game G. There are three key notions related to
sequential equilibrium [20,28] of an extensive game: assessment, sequential rationality,
and consistency. An assessment in an extensive game is a pair (,,μ), where , is a
strategy profile and μ is a function that assigns to every information set a probability#p#分页标题#e#
measure on the set of histories in the information set: μ is referred to as the belief
system. In Fig. 11, agent ˆa believes that agent a plays strategy Sa
ij with probability ) a
ij ,
i.e., μ({Sa
11, Sa
12, . . . , Sa mn})(Sa
ij ) = ) a
ij . Recall that ) a
ij is obtained from agent ˆa’s lotteries,
La
p and Lat
, and is equal to a
i ×  a
j . An assessment is sequentially rational if for each
information set of each player a ∈N, the strategy of player a is a best response to the other
player’s strategies, given a’s beliefs at that information set. An assessment is consistent if
there is a sequence ((,n,μn))∞
n=1 of assessments that converges to (,,μ) and has the
properties that each strategy profile ,n is completely mixed and that each belief system
μn is derived from ,n using Bayes’ rule. An assessment is a sequential equilibrium of an
extensive game if it is sequentially rational and consistent [20,28].
Theorem 1. The assessment (,,μ)x,y in which ,a = Sa
o for scenario x, ,ˆa = S ˆa
o for
scenario y, and μ({Sa
11, Sa
12, . . . , Sa mn})(Sa
ij ) = ) a
ij for 1  i  m and 1  j  n forms
a sequential equilibrium of the game G, for 1  x  6 and 1  y  6.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 29
Proof. Let the negotiation scenario for one of the agents, say agent a, be Na
1 and let the
opponent’s scenario be N ˆ a
2 , i.e., x = 1 and y = 2. The first three levels of the extensive
form of this game are shown in Fig. 11. At node 1, one of the players, say agent a, starts
negotiation. Agent a has m×n possible strategies, and it selects a strategy at node 1. Once
it selects a strategy at node 1, it generates offers using that strategy every time it has to
make a move. Agent a’s strategy Sa
i,j is as defined in Section 3.5.2. Agent a’s utility from
any of these m × n strategies depends on the opponent’s strategy. Although agent a does
not know the opponent’s strategy, it has beliefs about the opponent’s reservation price and
deadline. Agent a believes that there are m×n different (reservation price, deadline) pairs
and also has the associated probabilities in the two lotteries Lˆa
p and Lˆat
. Recall that an agent
always plays a strategy that offers its own reservation price at its deadline. Thus agent a
believes (on the basis of its lotteries Lˆa
p and Lˆat
) that ) ˆa
i,j is the probability with which the
opponent will play the strategy S ˆa
i,j that offers RPˆ a
i at time T ˆ a#p#分页标题#e#
i . The different strategies that
agent a can play and the expressions for computing agent a’s utility for different strategies
are as given in Section 3.5.2. Agent a gets maximum EU from strategy Sa
o defined in terms
of RPˆa
I and T ˆ a
J . Thus as per agent a’s beliefs about the opponent, strategy Sa
o is agent a’s
optimal strategy. Once this strategy is selected, agent a uses it, from the beginning to the
end of negotiation, to generate an offer whenever it is its turn.
At level 2 of the tree, it is agent ˆa’s turn. From agent ˆa’s perspective of the game tree,
I ˆa
1 forms its information set since it does not know the strategy used by agent a. However,
agent ˆa too has beliefs about agent a’s strategy in the form of lotteries La
p and Lat
. Agent
ˆa believes that agent a will play strategy Sa
i,j with probability ) a
i,j where strategy Sa
i,j is a
strategy that offers the final price RPa
i at time T a
j . Agent ˆa’s EU if it plays strategy S ˆap
,q
for 1  p  m and 1  q  n depends on agent a’s strategy and is given by the expression:
EUˆ a
p,q =
m
i=1
n
j=1
) a
i,jEUˆ a

S ˆa
p,q , Sa
i,j

. (17)
The values of p and q that give agent ˆa the maximum EU form its optimal strategy. We
know from Section 3.5.2 that agent ˆa’s optimal strategy is S ˆa
o for p = I and q = J . No
matter which node in the information set (I ˆa
1 ) agent ˆa is at, strategy S ˆa
o is better than all
the other strategies. The strategy S ˆa
o is agent ˆa’s optimal strategy which agent ˆa uses, from
the beginning to the end of negotiation, to make an offer whenever it is its turn.
Thus strategy Sa
o is agent a’s optimal strategy whenever it is agent a’s turn to make
an offer, for a = b and a = s. The assessment (,,μ)x,y is therefore sequentially rational.
This holds good for all other scenario combinations.We know from Section 3.5.2 that the
number of possible strategies may be different for different scenarios but the condition
for sequential rationality holds good for all possible scenario combinations. Thus the
assessment (,,μ)x,y is sequentially rational for 1  x  6 and 1  y  6.
The second condition for sequential equilibrium is consistency of the strategy profile
and the beliefs. The assessment (,,μ)x,y in which ,a = Sa
o for scenario x, ,ˆa = S ˆa
o
for scenario y, and μ({Sa
11, Sa
12, . . . , Sa mn})(Sa
ij ) = ) a
ij for 1  i  m and 1  j  n is#p#分页标题#e#
consistent since it is the limit as /→0 of assessments (,/,μ/) where
,/
a =


/) a
11, /) a
12, . . . , (1− /)) a
I,J , . . . , /) a
mn

, (18)
30 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
,/
ˆa =


/, /, . . . , (1 − /), . . . , /

, and (19)
μ/

Sa
11, Sa
12, . . . , Sa
mn


Sa
ij

= ) a
ij (20)
for 1  i  m, 1  j  n, and for every /.
The entry (1 −/) in ,/
ˆa is for agent ˆa’s optimal strategy.
The assessment (,,μ)x,y in which ,a = Sa
o for scenario x, ,ˆa = S ˆa
o for scenario y, and
μ({Sa
11, Sa
12, . . . , Sa mn})(Sa
ij ) = ) a
ij for 1  i  m and 1  j  n is therefore a sequential
equilibrium of the game G, for 1  x  6 and 1  y  6.

Theorem 2. If the conditions for convergence of optimal strategies are true, the time of
agreement is unique for each possible scenario combination. The price of equilibrium
agreement is unique if the agents have different deadlines, and RPa
I = RPa for T a < T ˆ a .
Proof. It is straightforward to verify the uniqueness of the time of equilibrium agreement
from Table 6. In Table 6, the price of agreement is either RPs or RPs
I for T s < T b, i.e.,
in rows 1, 2, 3, 4, 6, 7, 9, and 10. On the other hand the price of agreement is either
RPb or RPb
I for T s > T b, i.e., rows 5, 6, 8, 9, 11, 12, 13, and 14. Thus for each scenario
combination, there are two possible values for the price of agreement. When the agents
have different deadlines, the price of agreement is either RPa or RPa
I for T a < T ˆa. Recall
from Section 3.3 that RPb
m > RPs
1. The price of agreement for T s = T b is either RPs or
RPb. This means that the equilibrium solution cannot be unique when T s = T b. But when
the agents have different deadlines, the equilibrium solution is unique if RPa
I = RPa.

Theorem 3. The equilibrium agreement is Pareto-optimal if
(1) both agents gain utility with time, or
(2) both agents lose utility with time and one of them is in scenario N6.
Proof. Consider the case where both agents gain utility with time. This happens in rows 1,
2, 5, 6, 7, 11, and 12 of Table 6. The equilibrium outcome in these cases is either (RPs , T s )
or (RPs
I , T s) if T s < T b, either (RPb, T b) or (RPb
I , T b) if T b < T s , and either (RPs , T b) or
(RPb, T b) if T b = T s . In other words, the time of agreement is always the earlier deadline.
The utility of an agent can be changed by changing the price, or the time of agreement, or#p#分页标题#e#
both.When both agents gain utility with time, the time of agreement can only be decreased,
since the agent with the earlier deadline quits if agreement is not reached by its deadline.
Consider the case where T s < T b. Since the time of agreement can only be decreased and
both agents gain utility with time, a change in time decreases the utility of both agents.
The price of agreement here is either RPs or RPs
I . If the price of agreement is RPs , it
can only be increased, since a price below RPs will never be acceptable to the seller. So
there are three possible changes to the equilibrium agreement (RPs , T s): a decrease in
time, a decrease in price, or both. The first change decreases the utility of both agents. The
second change increases the seller’s utility but decreases the buyer’s utility. Finally, the
third change decreases the buyer’s utility and can either increase or decrease the seller’s
utility. In other words, in none of the three possible changes to the equilibrium agreement
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 31
is it possible to improve the utility of both agents. Likewise, it is not possible to increase
the utility of both agents when the outcome is (RPs
I , T s ). The equilibrium agreements
(RPs , T s ) and (RPs
I , T s) for T s < T b are thus Pareto-optimal. In the same way it can
be seen that the equilibrium agreements (RPb, T b) and (RPb
I , T b) for T s > T b are Paretooptimal;
and the agreements (RPs , T b) and (RPb, T b) for T s = T b are also Pareto-optimal.
When both agents lose utility with time and one of them is in scenario N6, the
equilibrium agreement is either (RPs , T ′) or (RPs
I , T ′) for T s < T b, and either (RPb, T ′)
or (RPb
I , T ′) for T b < T s . This corresponds to rows 4, 10, 13, and 14 of Table 6. Here,
the time of agreement can only be increased and since both agents lose utility with time, a
change in time decreases the utility of both agents. If the price of agreement is RPs , then
price can only be increased. This decreases the buyer’s utility and increases the seller’s
utility. If the price of agreement is RPs
I , then price can either be increased or decreased.
An increase in price decreases the buyer’s utility and increases the seller’s utility, while
a decrease in price increases the buyer’s utility and decreases the seller’s utility. In other
words, it is not possible to improve the utility of both agents simultaneously when both
agents lose utility with time and one of them is in scenario N6.

Our analysis therefore shows that even when players have incomplete and uncertain
information about each other, and each agent’s information is its private knowledge, a#p#分页标题#e#
unique equilibriumagreement exists for T s = T b under the conditions listed in Theorem2.
When these conditions are not satisfied, there are two possible equilibrium solutions for
each possible scenario combination.
4. The multi-issue negotiation model
We extend the above model for multi-issue bargaining. The buyer, b, and the seller,
s, that each have deadlines, bargain over the price of two distinct goods/services, X
and Y . Here, T a denotes agent a’s deadline for reaching agreement on both the issues.
Negotiation on all the issues must end by the earlier of the two deadlines. We consider
two goods/services in order to simplify the discussion but this is a general framework that
works for more than two goods/services. As we will show in Section 4.6, this framework
can in fact be used for negotiating multiple issues associated with a single good/service
and multiple goods/services.
4.1. Agents’ information states
Note that the discounting factors are different for different issues. This allows an agent to
have a different attitude towards time for different issues.
4.3. Negotiation agenda
A negotiation agenda defines the order in which the issues are negotiated. If agents
define this order before negotiating the issues, then the agenda is said to be exogenous.
On the other hand, if the agents are allowed to decide what issue they will negotiate
next during the process of negotiation, then the agenda is said to be endogenous. In the
proposed negotiation model, although agents initially make offers on both issues, there is
no restriction on the price they offer. Thus by initially offering a price that lies outside the
zone of agreement, an agent can effectively delay the time of agreement for that issue. For
example, the buyer can offer a very low price which will not be acceptable to the seller
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 33
and the seller can offer a price which will not be acceptable to the buyer. In this way, the
order in which the issues are bargained over and agreements are reached is determined
endogenously as part of the bargaining equilibrium rather than imposed exogenously as
part of the game tree.
Two implementation rules are possible for this protocol. One is sequential implementation
in which agreement on an issue is implemented as soon as it is settled; and the other is
simultaneous implementation in which agreement is implemented only after all the issues
are settled. We first show how to obtain equilibrium outcomes for multi-issue negotiation
and then compare the outcome that results from the sequential implementation with that of
the simultaneous implementation.
4.4. Equilibrium outcomes
As agents negotiate over the price of two distinct goods/services, the equilibrium#p#分页标题#e#
strategies for the single issue model can be applied to X and Y independently of each
other. Since T a denotes agent a’s deadline for reaching agreement on both issues, the
relationship between agent deadlines is the same for both issues. However, as mentioned
in Section 4.2, an agent can have different discounting factors for the two issues. Thus if
agent a’s negotiation scenario for issue X is N1, its scenario for issue Y can be either N1
or N4. Likewise, if agent a’s scenario for issue X is N2, its scenario for issue Y can be
either N2 or N5. Agent a’s possible scenarios for two issues are listed in Table 7. For the
scenarios listed in Table 7, the equilibrium price and time of agreement for each of the two
issues can be obtained from Table 6. For instance, if the buyer’s scenario for issues X and
Y are N1 and N4, and the seller’s scenarios for issues X and Y are N2 and N5, the price
and time of equilibrium agreement for issue X is either (RPs
and the buyer loses utility with time, it prefers sequential implementation for issue Y ,
while the seller prefers simultaneous implementation because it gains utility with time
on issue Y . The buyer’s combined utility for the two issues is therefore higher for
sequential implementationwhile the seller’s combined utility is higher for the simultaneous
implementation scheme. The same result holds good when a represents the seller. Thus
when t = T a and 0 = T a
J , agents have conflicting preferences over the implementation
scheme.
The entries marked “×” in Table 8 indicate that agreement cannot be reached at the
corresponding times for the two issues. For instance, it is not possible for agreement on
issue X to be reached at T b and issue Y to be reached at T s
J . This is explained as follows.
From Table 6 we know that the time of agreement on an issue is T s
J when the buyerseller
scenario combination for the issue is (N1,N6) or (N2,N6) (see rows 4 and 10 of
Table 6). Consider the buyer-seller scenario combination (N1,N6) for issue Y . Here the
36 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
buyer-seller scenario combinations that are possible for issue X are (N1,N6), (N1,N3),
(N4,N6), or (N4,N3). We know from Table 6 that in none of these four combinations the
time of agreement is T b. The same result holds good for the other scenario combination
for issue Y , i.e., (N2,N6). In other words, when the time of agreement for an issue is T s
J ,
the time of agreement for the other issue cannot be T b. Using similar analysis, it can be
seen that the time of agreement on the two issues cannot be T s and T b
J . Thus the agents
are indifferent to the implementation scheme when t = 0 , both agents prefer the sequential#p#分页标题#e#
scheme when t = T ′ and 0 = T ′, and have conflicting preferences over the implementation
scheme when t = T a and 0 = T a
J .

4.6. Multi-issue negotiation for a single good/service
The previous subsection described bargaining over the price of more than one
good/service. But since this is a general framework it can also be used for negotiating
multiple issues associated with a single good/service. Let issue X be the price of a service
and issue Y be the quality of service. The utility functions for the buyer and seller are:
Ub(pX,pY , t) =

Since both issues are associated with a single good/service, only simultaneous implementation
applies in this case. The optimal and equilibrium strategies for X and Y still remain
the same. Thus the framework can be used for negotiating multiple issues associated with
a single good/service and multiple goods/services.
4.7. Properties of the equilibrium solution
The main focus in the design of a negotiationmodel is on the properties of the outcome,
since the choice of a model depends on the attributes of the solution it generates. We
therefore study some important properties [28] of the equilibrium agreement.
(1) Uniqueness. If the solution of the negotiation game is unique, then it can be identified
unequivocally.
Theorem 5. The proposed negotiation model has a unique equilibrium agreement if agents
have different deadlines and RPa
I = RPa for T a < T ˆa, for each issue.
Proof. Consider a single issue. When agents have different deadlines, i.e., T a < T ˆa, we
know from Theorem 2 that if RPa
I = RPa then the equilibrium solution for the issue is
unique. In general, if there are 1 different issues to be negotiated, there is a unique solution
for all 1 issues only if there is a unique solution for each individual issue, i.e., when
RPa
I = RPa for each issue.

S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 37
(2) Symmetry. A bargaining mechanism is said to be symmetric if it does not treat the
players differently on the basis of inappropriate criteria. Exactly what constitutes
inappropriate criteria depends on the specific domain.
Theorem 6. The equilibrium agreement for multiple issues is independent of the identity
of the first player if agents have different deadlines, and RPa
I = RPa for T a < T ˆa, for each
issue.
Proof. The equilibrium price of agreement for a single issue depends on the identity of
the player that makes a move at time T a. If it is agent a’s turn to make an offer at T a,
the equilibrium price is RPa . On the other hand if it is agent ˆa’s turn, then the equilibrium
price is RPa
I . But if RPa
I = RPa, the equilibrium solution is unique and does not depend#p#分页标题#e#
on the identity of the agent that makes an offer at time T a. When there are 1 issues to be
negotiated, the equilibriumoutcome for all the 1 issues is independent of the identity of the
agent that makes an offer at time T a, if the equilibrium outcome for each of the 1 issues is
unique, i.e., if RPa
I = RPa for T a < T ˆa, for each issue.

(3) Efficiency. An agreement is efficient if there is no wasted utility, i.e., the agreement
satisfies Pareto-optimality. The equilibrium solution in the proposed model is Paretooptimal
under the conditions given in Theorem 7.
Theorem 7. The equilibrium agreement for 1 issues is Pareto-optimal if the agreement on
each individual issue is Pareto-optimal and each agent has the same discounting factor for
all 1 issues.
Proof. From Table 7, we know an agent’s possible scenario combinations for multiple
issues. Since each agent has the same discounting factor for all the 1 issues, each agent
is in the same scenario for all 1 issues. We also know from Theorem 3 that the outcome
for a single issue is Pareto-optimal either when both agents gain utility with time, or when
both lose utility with time and one of them is in scenario N6. If both agents gain utility
with time, we know from Table 6 that for T a < T ˆa, the equilibrium agreement is either
(RPa, T a) or (RPa
I , T a). Since both agents gain utility with time, a change in the time of
agreement lowers the utility of both agents. A change in the price of agreement has the
following effect on agents’ utilities. Let agent a be the seller. If Pi
e denotes the equilibrium
price on issue i and a denotes agent a’s discounting factor for all the issues, the agents’
utilities from all 1 issues are:
Ua

P1
e , . . . ,P1
e , T s
=

(b)T s 1
i=1(RPb
i − Pi
e ) for b,
(s)T s 1
i=1(Pi
e − RPs
i ) for s.
Let 3i denote the change in price of issue i . Also let 3Ua denote the overall change in
agent a’s utility from a change in price of all the 1 issues. The difference in utilities, 3Ua,
is:
3Ua =

−(b)T s 1
i=1 3i for b,
(s)T s 1
i=1 3i for s.
38 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
Since b > 0 and s > 0, 3Us > 0 if 3Ub < 0 and 3Us < 0 if 3Ub > 0. In other words,
it is not possible to increase the utility of both agents when both gain utility with time.
The same result holds good if a represents the buyer. Likewise, the equilibrium solutions
(RPb, T b) and (RPs , T b), for T s = T b, are Pareto-optimal. In the same way it can be seen
that it is not possible to increase the utility of both agents when both lose utility with time#p#分页标题#e#
and one of them is in scenario N6.

(4) Distribution. The distribution property of negotiation outcome relates to the issue
of how the gains from trade are divided between agents. The equilibrium price
(Pi
e for issue i) and the equilibrium time (T i
e for issue i) of agreement reflect the
relationship between the agents’ bargaining powers. We say that an agent has more
(less) bargaining power over Pi
e , if Pi
e is more (less) favourable to it than its opponent.
Similarly, an agent has more (less) bargaining power over T i
e , if T i
e is more (less)
favourable to it than its opponent.
Theorem 8. For the equilibrium agreement, the relation between the agents’ bargaining
powers over price is as follows. If agents have equal deadlines, agent ˆa has more
bargaining power than agent a on all the issues if agent a makes an offer at T a. For
T a < T ˆa, ˆa has more bargaining power than agent a on all the issues if agent a makes
an offer at T a . For T s < T b, the price-surplus is split between b and s in the ratio
(RPb − RPs
I ):(RPs
I − RPs) if b makes an offer at T s . For T b < T s , the price-surplus is
split between b and s in the ratio (RPb − RPb
I ):(RPb
I − RPs) if s makes an offer at T b.
Proof. We know from rows 6 and 9 of Table 6 that there are four buyer-seller scenario
combinations in which agents can have equal deadlines: (N2,N2), (N2,N5), (N5,N2),
or (N5,N5). Consider the case where the buyer-seller scenario for one of the issues is
(N2,N2). From Table 7, we know that the four possible buyer-seller scenario combinations
for each of the remaining issues are (N2,N2), (N2,N5), (N5,N2), or (N5,N5). The offer
generated by an agent’s optimal strategy in scenarios N2 and N5 is RPˆ a
I in the time interval
[T ˆa
J , T ˆ a
k ], and it is RPa at time T a . Consider the case where the buyer makes an offer (i.e.,
its reservation price) at its deadline. This is a combined offer since we know from Table 6
that in all the possible scenarios for each issue, the time of agreement for each issue is
the earlier deadline. Thus at time T b the buyer makes a combined offer that includes its
reservation price for each of the 1 issues. Since the conditions for convergence of optimal
strategies are satisfied, we know that RPb > RPb
I for each issue. The seller’s action for
each issue at T s , which is equal to T b, is to accept an offer greater than or equal to RPs .
Since RPb > RPs for each of the 1 issues, the seller accepts the price of every issue in the
buyer’s combined offer. Agreement on all the issues therefore takes place at T b. The price
of agreement is the buyer’s reservation price for each issue.#p#分页标题#e#
On the other hand, if it is the seller’s turn to make an offer at time T b, for each issue
it offers its reservation price, which the buyer accepts. Thus if the buyer makes an offer
at T b, the seller has more bargaining power because it gets the entire price-surplus on all
the issues and if the seller makes an offer at T b, the buyer has more bargaining power
because it gets the entire price-surplus on all the issues. In the same way the relationship
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 39
between agents’ bargaining power can be verified for the remaining three scenarios for
equal deadlines, (N2,N5), (N5,N2), or (N5,N5).
For T a < T ˆa, the equilibrium outcome for each issue is (RPa, T a) if agent a makes an
offer at time T a and the outcome is (RPa
I , T a) if agent ˆa makes an offer at time T a. Thus
agent ˆa gets the entire price-surplus on all the issues and has more bargaining power if
agent a makes an offer at time T a . The distribution of price-surplus, if agent ˆa makes an
offer at T a, can be verified in the same way.

Theorem 9. Agents have equal bargaining power over time on an issue if both gain utility
with time on the issue, or if both lose utility with time on the issue and one of them is in
scenario N6.
Proof. We know from Table 6 that when both agents gain utility with time on an issue, the
time of equilibrium agreement is the earlier deadline. Since the time of agreement cannot
be greater than T a for T a < T ˆ a , both agents get the maximum possible utility from time
on the issue and thus have equal bargaining power.
Likewise, when both agents lose utility with time on an issue and one of them is in
scenario N6, the time of agreement is T ′. This gives the agents equal bargaining power
since both of them get the maximum possible utility from time on the issue.

Theorem 10. If agents have conflicting time preferences on an issue, and neither agent
is in scenario N6 for the issue, the agent that gains utility with time has more bargaining
power over time on that issue.
Proof. We know from Table 6 (see rows 1, 2, 3, 5, 6, 7, 8, 9, 13, and 14) that when agents
have conflicting time preferences on an issue and neither agent is in scenario N6 for the
issue, the time of equilibrium agreement is the earlier deadline. In other words, although
the agent that loses utility with time prefers an early agreement, an agreement only takes
place at the latest possible time. This gives the stronger agent the maximum possible utility
from time and it therefore has more bargaining power than the opponent.

5. Related work
Game theoretic models can be divided into two types; those that deal with complete
information and those that deal with incomplete information. In the former setting, agents#p#分页标题#e#
know each other’s characteristics as well as their own. In the latter setting, agents lack
information about some specific parameters. For instance there could be uncertainty over
player’s discounting factors, their reservation values, or their deadlines. These models
study the strategic behavior of agents when there is information uncertainty.
Initial game theoretic research typically dealt with coordination and negotiation issues
by assuming that agents have complete information about each other and then giving precomputed
solutions to specific problems [25,26]. However this complete information assumption
is limiting because uncertainty is endemic in most realistic applications. For this
reason, Harsanyi [14,15] originated research in bargaining with incomplete information.
40 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
He gave a generalized solution for two person bargaining games with incomplete information.
However, there was no notion of timing issues in this model. Another important
model of strategic bargaining is Rubenstein’s infinite horizon alternating offer game [33].
This model takes the time preferences of bargainers into consideration in the form of their
discounting factors but again assumes complete information. It was later extended in [34]
for bargaining with incomplete information about time preferences. However, this is an
infinite horizon model that considers uncertainty over player’s discounting factors. One of
the players, say player 2, may be one of two types: weak (for high discounting factor) and
strong (for low discounting factor). Player 1 adopts an initial belief about the identity of
player 2. Player 1’s preference is known to player 2. Agreement is reached in the first or
second time period. Its main result is the existence of a unique sequential equilibriumwhen
player 1’s belief that player 2 is of type weak, is higher than a certain threshold and another
unique equilibrium when this belief is lower than the threshold.
Other models of incomplete information have also been formulated for different
environments and the strategic behavior of agents is studied. Fudenberg and Tirole
[13] analyse an infinite horizon bargaining game by taking the players’ valuations,
and a probability distribution over them, as common knowledge. Fudenberg et al. [12]
subsequently analysed buyer-seller infinite horizon bargaining games in which reservation
prices are uncertain, but time preferences are known. Sandholm and Vulkan [37] consider
uncertainty over agent deadlines. However, a common feature of all these models is that
they treat the information state of agents as common knowledge.
All the above models deal with single issue negotiation. However, in many real-life
bargaining situations, there is more than one issue over which players want to negotiate.#p#分页标题#e#
As mentioned in the introduction, multiple issues can be negotiated using the bundled
approach or the issue-by-issue approach. Although the fact that the negotiation outcome
depends on the choice of the negotiation approach7 was first noted by Schelling [38] in
1956, the literature on issue-by-issue negotiation is small (albeit growing). This includes
the work of Fershtman [9] who extends Rubinstein’s complete information model [33] for
splitting a single pie to multiple pies. This model imposes an agenda exogenously, and
studies the relation between the agenda and the outcome of the bargaining game. However,
this work is based on the assumption that both players have identical discounting factors
and does not consider agent deadlines. Similar work in a complete information setting
includes [16], but it considers an endogenous agenda.
Closer to our work is that of Bac and Raff [1] who developed a model that has an endogenous
agenda. They extended Rubinstein’s model [34] for single pie bargaining with
incomplete information by adding a second pie. In this model the price-surplus is known
to both agents. For both agents, the discounting factor is assumed to be equal over all the
issues. One of the players knows its own discounting factor and that of its opponent. The
other player knows its own discounting factor, but is uncertain of the opponent’s. This factor
can take one of two values, H with probability5, and L with probability 1−5. However,
these probabilities are again common knowledge. Thus agents have asymmetric information
about discounting factors. However, they do not associate deadlines with players.
7 As Theorem 4 shows, issue-by-issue negotiation again is not neutral to the implementation scheme.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 41
In summary, existing models for multi-issue negotiation [1,9,16] are typically extensions
of single issue models [33,34] and they tend not consider agent deadlines. In addition,
they treat the information state of agents as common knowledge. The main difference
between these models and ours is that firstly, our model considers both agent deadlines and
discounting factors and uses negotiation decision functions for counter offer generation.
Secondly, in our case the players are uncertain about the opponent’s reservation value and
deadline. Each agent knows its own reservation value and deadline but has a probability
distribution over its opponent’s reservation value and deadline. Moreover, the discounting
factor can be different for different issues and the players have no information about the opponent’s
discounting factors. Our analysis is thus more comprehensive, since we consider
all possible negotiation scenarios (i.e., a > 1 and a < 1). Thirdly, we treat each agent’s#p#分页标题#e#
information state as its private knowledge which is not known to its opponent. This is in
contrast to the above mentioned models, where the information state of agents is treated as
common knowledge. In most realistic cases, an agent’s information state is not known to its
opponent.We therefore treat each players’ beliefs about its opponent as private knowledge
and obtain the connection between this private knowledge and the existence of equilibrium.
Our model is therefore closer to most real-life bargaining situations than the existing
models. The fourth point of difference lies in the attributes of the solution. Comparing
the solution properties of multi-issue models, we see that the existing models do not have a
unique equilibriumsolution. The equilibriumsolution in ourmodel depends on the identity
of the player that makes a move at T ′ or the earlier deadline, but is unique and symmetric
under certain conditions. Finally, as is the case with our model, the equilibrium solution is
not always Pareto-optimal in the other models.
6. Conclusions and future work
This paper presented a new model for multi-issue negotiation under time constraints in
an incomplete information setting. The issues to be bargained over can be associated with
a single good/service or multiple goods/services. The order in which issues are bargained
over and agreements are reached is determined endogenously, as part of the bargaining
equilibrium, rather than imposed exogenously, as part of the game tree. Our analysis
shows that even when each agent’s information is private knowledge, a unique equilibrium
exists under certain conditions. Furthermore, we determine conditions under which agents
have similar as well as conflicting preferences over the implementation scheme. Finally,
we studied the properties of the equilibrium solution and determined conditions under
which the equilibrium solution is unique, symmetric, and Pareto-optimal. As highlighted
in Section 5, we believe this model is closer to most real-life bargaining situations than
others that exist in the literature.
In practice, there is a wide range of environments in which negotiation can take place.
For instance, in some applications the buyermay know the seller’s reservation price but the
seller may not know the buyer’s reservation price. Or the seller may know the buyer’s deadline,
but the buyer may not know the seller’s deadline. The information state of agents thus
varies from application to application (the influence of the agents’ information states on
the equilibrium outcome has been explored in [5]). Apart from this, each application will
42 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
require the players to manipulate the agenda in a different way. For instance, some applications#p#分页标题#e#
may require bargaining over all the issues to occur simultaneously, while others may
be more suited to issue-by-issue negotiation. Within the issue-by-issue negotiation, there
can be different agendas. Yet another possibility is for agents to bargain over the agenda
prior to the bargaining over the issues. Although we studied bargaining in which agents
had one specific information state and the agenda was endogenous, our negotiation framework
is general and can be used for exploring a wide range of negotiation environments
by changing the agents’ information states or the way in which the players manipulate the
agenda. In [8], for example, the strategic behavior of agents was studied by allowing the
agents to negotiate the agenda before they negotiate the prices of individual issues. The
key result of this study is that in some scenarios agents have conflicting preferences over
the agenda, while in others they have similar preferences. However, since agents have incomplete
information about each other, they do not have the ability to identify scenarios
in which they have similar preferences. We therefore presented an extended negotiation
protocol that allows agents to identify such scenarios through a mediator.
As it currently stands, our framework treats the agents’ beliefs about their opponent as
being static. In future, we will introduce learning into the model to allow agents to learn
these parameters dynamically during negotiation, and reach a stage where the conditions
for convergence are satisfied. Secondly, we studied the process of negotiation for the case
where agents’ beliefs about each others reservation price do not overlap (i.e., the highest
possible value for the seller’s reservation price in the buyer’s information state was lower
than the lowest possible value for the buyer’s reservation price in the seller’s information
state). The model can be made more general by allowing these beliefs to have overlapping
values. Thirdly, in our present work we studied the strategic behavior of self-interested
agents that use time-dependent strategies to maximize their own benefit. In future, it would
be interesting to study the bargaining process by combining time-dependent tactics with tit
for tat tactics in order to obtain a fair distribution of gains from trade.
Acknowledgements
This research was supported by the EPSRC under grant GR/M07052. We are grateful
to the reviewers of this paper. Their detailed comments helped us to substantially improve
the accuracy and readability of the paper.
Appendix A. A summary of notation
b Buyer
s Seller
a An element of the set {b, s}
ˆa Agent a’s opponent
IPb Buyer’s initial price
IPs Seller’s initial price
RPb Buyer’s reservation price#p#分页标题#e#
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 43
RPs Seller’s reservation price
pt
b→s Price offered by b to s at time t
Aa Action taken by agent a
B Boulware negotiation decision function
C Conceder negotiation decision function
L Linear negotiation decision function
I a Information state of agent a
Ia Information set of agent a
T a Agent a’s deadline
a Agent a’s discounting factor
Ua Agent a’s utility
Sa Agent a’s strategy
Sa
o Agent a’s optimal strategy
Lat
A lottery over agent a’s deadline
La
p A lottery over agent a’s reservation price
 a
i Probability that agent a’s reservation price is RPa
i
a
j Probability that agent a’s deadline is T a
j
) a
ij Probability that agent a’s reservation price is RPa
i and deadline is T a
j
Ni Negotiation scenario i
, Strategy profile
μ Belief system
O Negotiation outcome
EUa Agent a’s expected utility
EUao
Agent a’s maximum expected utility
RPa
X Agent a’s reservation price for issue X
RPa
Y Agent a’s reservation price for issue Y
La
X Agent ˆa’s beliefs about a’s reservation price for issue X
La
Y Agent ˆa’s beliefs about a’s reservation price for issue Y
a
X Agent a’s discount factor for issue X
a
X Agent a’s discount factor for issue Y
Ua
seq Agent a’s utility for the sequential implementation scheme
Ua
sim Agent a’s utility for the simultaneous implementation scheme
T ′ Time at which the second offer is made, i.e., if negotiation starts at time t ,
T ′ = t + 1
Pi
e Equilibrium price for issue i
T i
e Time of equilibrium agreement for issue i
References留学生计算机硕士dissertation范文-多议题协商协议框架构建-Artificial Intelligence-An agenda-based framework for multi-issue negotiation由留学生dissertation代写中心提供整理文本资源，帮助写更好的计算机硕士dissertation。
[1] M. Bac, H. Raff, Issue-by-issue negotiations: the role of information and time preference, Games and
Economic Behavior 13 (1996) 125–134.
[2] L.A. Busch, I.J. Horstman, A comment on issue-by-issue negotiations, Games and Economic Behavior 19
(1997) 144–148.
[3] P. Faratin, C. Sierra, N.R. Jennings, Negotiation decision functions for autonomous agents, Internat. J.
Robotics Autonomous Systems 24 (3-4) (1998) 159–182.
44 S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45
[4] P. Faratin, C. Sierra, N.R. Jennings, Using similarity criteria to make trade-offs in automated negotiations,#p#分页标题#e#
Artificial Intelligence 142 (2) (2002) 205–237.
[5] S.S. Fatima, M. Wooldridge, N.R. Jennings, The influence of information on negotiation equilibrium,
in: Agent Mediated Electronic Commerce IV, Designing Mechanisms and Systems, in: Lecture Notes in
Computer Science, Vol. 2531, Springer, Berlin, 2002, pp. 180–193.
[6] S.S. Fatima, M. Wooldridge, N.R. Jennings, Multi-issue negotiation under time constraints, in: Proceedings
of the First International Conference on Autonomous Agents and Multi-Agent Systems, Bologna, Italy,
2002, pp. 143–150.
[7] S.S. Fatima, M. Wooldridge, N.R. Jennings, Optimal negotiation strategies for agents with incomplete
information, in: J.J. Meyer, M. Tambe (Eds.), Intelligent Agents VIII. Agent Theories, Architectures and
Languages, in: Lecture Notes in Artificial Intelligence, Vol. 2333, Springer, Berlin, 2002, pp. 377–392.
[8] S.S. Fatima, M. Wooldridge, N.R. Jennings, Optimal agendas for multi-issue negotiation, in: Proceedings
of the Second International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-03)
Melbourne, Australia, 2003.
[9] C. Fershtman, The importance of the agenda in bargaining, Games and Economic Behavior 2 (1990) 224–
238.
[10] P.C. Fishburn, A. Rubinstein, Time preference, Internat. Econom. Rev. 23 (1982) 677–694.
[11] R. Fisher, W. Ury, Getting to Yes: Negotiating Agreement without Giving in, Houghton Mifflin, Boston,
MA, 1981.
[12] D. Fudenberg, D. Levine, J. Tirole, Infinite horizon models of bargaining with one sided incomplete
information, in: A. Roth (Ed.), Game Theoretic Models of Bargaining, University of Cambridge Press,
Cambridge, 1985.
[13] D. Fudenberg, J. Tirole, Sequential bargaining with incomplete information, Rev. Econom. Stud. 50 (1983)
221–247.
[14] J.C. Harsanyi, Approaches to the bargaining problem before and after the theory of games, Econometrica 24
(1956) 144–157.
[15] J.C. Harsanyi, R. Selten, A generalized Nash solution for two-person bargaining games with incomplete
information, Management Sci. 18 (5) (1972) 80–106.
[16] R. Inderst, Multi-issue bargaining with endogenous agenda, Games and Economic Behavior 30 (2000) 64–
82.
[17] R. Keeney, H. Raiffa, Decisions with Multiple Objectives: Preferences and Value Trade-offs, Wiley, New
York, 1976.
[18] S. Kraus, Strategic Negotiation in Multi-Agent Environments, MIT Press, Cambridge, MA, 2001.
[19] S. Kraus, J. Wilkenfeld, G. Zlotkin, Negotiation under time constraints, Artificial Intelligence 75 (2) (1995)
297–345.
[20] D.M. Kreps, R. Wilson, Sequential equilibrium, Econometrica 50 (1982) 863–894.
[21] Z.A. Livne, The role of time in negotiation, PhD Thesis, MIT, Cambridge, MA, 1979.
[22] A. Lomuscio, M. Wooldridge, N.R. Jennings, A classification scheme for negotiation in electronic#p#分页标题#e#
commerce, Internat. J. Group Decision and Negotiation 12 (1) (2003) 31–56.
[23] X. Luo, N.R. Jennings, N. Shadbolt, H. Leung, J.H. Lee, A fuzzy constraint based model for bilateral multiissue
negotiations in semi-competitive environments, Artificial Intelligence 148 (2003) 53–102.
[24] P. Maes, R.H. Guttman, A.G. Moukas, Agents that buy and sell, Comm. ACM 42 (3) (1999) 81–91.
[25] J.F. Nash, The bargaining problem, Econometrica 18 (1950) 155–162.
[26] J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press,
Princeton, NJ, 1947.
[27] M.J. Osborne, A. Rubinstein, Bargaining and Markets, Academic Press, San Diego, CA, 1990.
[28] M.J. Osborne, A. Rubinstein, A Course in Game Theory, MIT Press, Cambridge, MA, 1994.
[29] D.G. Pruitt, Negotiation Behavior, Academic Press, New York, 1981.
[30] H. Raiffa, The Art and Science of Negotiation, Harvard University Press, Cambridge, MA, 1982.
[31] J.S. Rosenschein, G. Zlotkin, Rules of Encounter, MIT Press, Cambridge, MA, 1994.
[32] A. Roth, Axiomatic Models of Bargaining, Springer, Berlin, 1979.
[33] A. Rubinstein, Perfect equilibrium in a bargaining model, Econometrica 50 (1) (1982) 97–109.
[34] A. Rubinstein, A bargaining model with incomplete information about time preferences, Econometrica 53
(1985) 1151–1172.
S.S. Fatima et al. / Artificial Intelligence 152 (2004) 1–45 45
[35] T. Sandholm, Agents in electronic commerce: Component technologies for automated negotiation and
coalition formation, Autonomous Agents and Multi-Agent Systems 3 (1) (2000) 73–96.
[36] T. Sandholm, N. Vulkan, Algorithms for optimizing leveled commitment contracts, in: Proc. IJCAI-99,
Stockholm, Sweden, 1999, pp. 535–540.
[37] T. Sandholm, N. Vulkan, Bargaining with deadlines, in: Proc. AAAI-99, Orlando, FL, 1999, pp. 44–51.
[38] T. Schelling, An essay on bargaining, Amer. Econom. Rev. 46 (1956) 281–306.
[39] E. van Damme, Refinements of the Nash Equilibrium Concept, Springer, Berlin, 1983.
[40] O.R. Young, Bargaining: Formal Theories of Negotiation, University of Illinois Press, Urbana, IL, 1975.