Multi-issue negotiation under time constraints.
This paper presents a new model for multi-issue negotiation under time constraints in an incomplete information setting. In this model the order in which issues are bargained over and agreements are reached is determined endogenously as part of the bargaining equilibrium. We show that the sequential implementation of the equilibrium agreement gives a better outcome than a simultaneous implementation when agents have like, as well as conflicting, time preferences. We also show that the equilibrium solution possesses the properties of uniqueness and symmetry, although it is not always Pareto-optimal.
INTRODUCTION
Agent mediated negotiation has received considerable attention in
the field of electronic commerce [14, 9, 7]. In many of the applications
that are conceived in this domain it is important that the
agents should not only bargain over the price of a product, but also
take into account aspects like the delivery time, quality, payment
methods, and other product specific properties. In such multi-issue
negotiations, the agents should be able to negotiate outcomes that
are mutually beneficial for both parties [11]. However the complexity
of the bargaining problem increases rapidly as the number
of issues increases. Given this increase in complexity, there is a
need to develop software agents that can operate effectively in such
circumstances. To this end, this paper reports on the development
of a new model for multi-issue negotiation between two agents.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
AAMAS '02, July 15-19, Bologna, Italy
In such bilateral multi-issue negotiations, one approach is to bundle
all the issues and discuss them simultaneously. This allows the
players to exploit trade-offs among different issues, but requires
complex computations to be performed [11]. The other approach
- which is computationally simpler - is to negotiate the issues
sequentially. 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. This ordering
is called the negotiation agenda. Moreover, one of the factors that
determines the outcome of negotiation is this agenda [4]. To this
end, there are two ways of incorporating agendas in the negotiation
model. One is to fix the agenda exogenously as part of the
negotiation procedure [4]. 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 [5]. Against this background, this paper presents a
multi-issue negotiation model with an endogenous agenda.
To provide a setting for our negotiation model, we consider the
case in which negotiation needs to be completed by a specified
time (which may be different for the different parties). Apart from
the agents' respective deadlines, the time at which agreement is
reached can effect the agents in different ways. An agent can gain
utility with time, and have the incentive to reach a late agreement
(within the bounds of its deadline). In such a case it is said to be a
strong (patient) player. The other possibility is that it can lose utility
with time and have the incentive to reach an early agreement.
It is then said to be a weak (impatient) player. As we will show,
this disposition and the actual deadline itself strongly influence the
negotiation outcome. Other parameters that effect the outcome include
the agents'strategies, their utilities and their reservation lim-
its. However, in most practical cases agents do not have complete
information on all of these parameters. Thus in this work we focus
on bilateral negotiation between agents with time constraints and
incomplete information.
To this end, Fatima et al presented a single-issue model for negotiation
between two agents under time constraints and in an incomplete
information setting [3]. 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 between a buyer
and a seller for the price of more than one good/service. Specifi-
cally, each agent has a deadline before which agreement must end
on all the issues. However, the order in which issues are bargained
over and agreements are reached is determined by the equilibrium
strategies. These strategies optimize the time at which an issue is
settled and are therefore appropriate for the sequential implementation
scheme. Moreover, we show that the sequential implementation
of the equilibrium agreement results in an outcome that is
no worse than the outcome for the simultaneous implementation,
both when agents have like as well as conflicting time preferences.
Finally, we study the properties of the equilibrium solution.
This work extends the state of the art by presenting a more realistic
negotiation model that captures the following three aspects
of many real life bargaining situations. Firstly, it is a model for
negotiating multiple issues. Secondly, it takes the time constraints
of bargainers into consideration. Thirdly it allows agents to have
incomplete information about each other.
In section 2 we first give an overview of the single-issue negotiation
model of [3] and then prove that the mutual strategic behavior
of agents where both use their respective optimal strategies results
in equilibrium. In section 3 we extend this model to allow multi-issue
negotiation and study the properties of the equilibrium solu-
tion. Section 4 discusses related work. Finally section 5 gives the
conclusions.
2. SINGLE-ISSUENEGOTIATIONMODEL
In this section we first provide an overview of the single issue negotiation
model and a brief description of the optimal strategies as
determined in [3]. Due to lack of space, we describe the optimal
strategy determination for one specific negotiation scenario. We
then prove that the optimal strategy profiles form sequential equilibrium
points.
2.1 The Negotiation Protocol
This is basically an alternating offers protocol. Let b denote the
buyer, s the seller and let [P a
denote the range of values
for price that are acceptable to agent a, where a 2 fb; sg. A
value for price that is acceptable to both b and s, i.e., the zone of
agreement, is the interval [P s
min ) is the
price-surplus. T a denotes agent a's deadline. Let p t
b!s denote the
price offered by agent b at time t. Negotiation starts when the first
offer is made by an agent. When an agent, say s, receives an offer
from agent b at time t, i.e., p t b!s , it rates the offer using its utility
function U s . If the value of U s for p t
b!s at time t is greater than
the value of the counter-offer agent s is ready to send at time t 0 , i.e.,
s!b with t 0 > t then agent s accepts. Otherwise a counter-offer is
made. Thus the action A that agent s takes at time t is defined as:
Accept if U s (p t
s!b otherwise
2.2 Counter-offer generation
Since both agents have a deadline, we assume that they use a time
dependent tactic (e.g. linear (L), Boulware (B) or Conceder (C)) [2]
for generating the offers. In these tactics, the predominant factor
used to decide which value to offer next is time t. The tactics vary
the value of price depending on the remaining negotiation time,
modeled as the above defined constant T a . The initial offer is a
point in the interval [P a
]. The constant k a multiplied
by the size of interval determines the price to be offered in the first
proposal by agent a (as per [2]). The offer made by agent a to agent
b at time t (0 < t  T a ) is modeled as a function  a depending on
time as follows:
P a
min
P a
min
Price
Time
min
O

Figure

1: Negotiation outcome for Boulware and Conceder
functions
A wide range of time dependent functions can be defined by varying
the way in which  a (t) is computed (see [2] for more details).
However, functions must ensure that 0   a (t)  1,  a
and  a (T a That is, the offer will always be between the
range [P a
max ], at the beginning it will give the initial constant
and when the deadline is reached it will offer the reservation
value. Function  a (t) is defined as follows:
a
T a

These families of negotiation decision functions (NDF) represent
an infinite number of possible tactics, one for each value of .
However, depending on the value of , two extreme sets show
clearly different patterns of behaviour.
1. Boulware [11]. 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 reservtion value.
2. Conceder [10]. For this tactic is high. The agent goes
to its reservation value very quickly and maintains the same
offer till the deadline. Finally 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, and T a . A vector V of these four
forms the agent's strategy. Let
min The negotiation outcome O
is an element of f(p; t); Cg, where the pair (p; t) denotes the price
and time at which agreement is reached and C denotes the conflict
outcome.
For example, when b's strategy is defined as [P s
and s's strategy is defined as [P b
the outcome
(O1 ) that results is shown in figure 1. As shown in the figure,
agreement is reached at a price P s
at a time close to T. 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.
2.3 Agents' information state
Each agent has a reservation limit, a deadline, a utility function and
a strategy. Thus the buyer and seller each have four parameters
denoted hP b
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. I b and I s are taken as:
I
and
I
are the information about b's own parameters
and L s
p and L s
t are its beliefs about s. Similarly, P s
min ,
are s's own parameters and L b p and L b t are its beliefs
about b. L s
p and L s
t are two lotteries that denote b's beliefs
about s's deadline and reservation price, where
minh ] such that (P s
minh ) and
h ] such that (T s
l < T s
Similarly L b
p and L b
t are two lotteries that denote s's beliefs about
b's deadline and reservation price, where
maxh ] such that (P b
and
h ] such that (T b
l < T b
Thus agents have uncertain information about each other's deadline
and reservation price. However, the agents do not know their
opponent's utility function or strategy.
Agents' utilities are defined with the following two von Neumann-Morgenstern
utility functions [6] that incorporate the effect of time
discounting. U a (p;
(p)U a
and U a
are uni-dimensional
utility functions. Here, preferences for attribute p,
given the other attribute t, do not depend on the level of t. U a
is defined as:
U a
for the buyer
min for the seller
U a
t is defined as U 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. Note that the agents may have different discounting factors.
Agents are said to have similar time preferences if both gain on
time or both lose on time. Otherwise they have conflicting time
preferences. Each agent's information is its private information
that is not known to the opponent.
2.4 Optimal strategies
We describe how optimal strategies are obtained for players that
are von Neumann-Morgenstern expected utility maximizers. Since
utility is a function of price and time, these strategies optimize both.
The discussion is from the perspective of the buyer (although the
same analysis can be taken from the perspective of the seller). b
believes that with probability
b , s's deadline is T s
l and with probabilityb it is T s
h . Let T b denote b's own deadline. This
gives rise to three relations between agent deadlines; (T b > T s
l < T b < T s
l ). For each of the two possible
realizations of b's discounting factor, these three relations can hold
between agent deadlines. In other words, there are six possible scenarios
(N1::N6 ) under which negotiation can take place. Due to
lack of space we describe here how the optimal strategies are obtained
for one specific scenario - N1 , i.e, when b gains on time (i.e.,
h .
prefers to reach agreement at the latest possible
time and at the lowest possible price. The optimal strategy for b is
determined using backward induction. The optimal price (P s
the optimal time (T s
are determined first, and then a strategy that
ensures agreement at P s
s
Time
Price
s
minh
min

Figure

2: Possible buyer strategies in a particular negotiation
scenario
No matter which strategy (B, C or L) s uses, it is bound to reach
its reservation price by its deadline. Since both possible values of
s's deadline are less than T b , b's optimal strategy would be never
to offer a price more than s's reservation price (P s
minl or P s
Moreover, it should offer this price at the latest possible time, which
is s's deadline (T s
l or T s
h ). This is because s quits if agreement is
not reached by then.
From its beliefs, it is known to b that s's reservation price, deadline
pair could be one of (P s
l
h
l
or (P s
One of these four pairs is (P s
). The possible
strategies that b can use are S bif s's reservation price deadline pair
is
l
if it is (P s
h
3 if it is (P s
l ) or S bif it is (P s
h ). These strategies are depicted in figure 2. Out
of these four possible strategies, the one that results in maximum
expected utility (EU) is b's optimal strategy (note that b's optimal
strategy does not depend on s's strategy). The EUs from these four
strategies depend on  b and
b .
An agent's utility from price is independent of its utility from
time, i.e, the buyer always prefers a low price to a high price, and
for a given price it always prefers a late agreement to an early one.
In order to simplify the process of finding the optimal strategy, we
assume  there is only one possible value, P s
minl , for
s's reservation price. This leaves us with only two strategies, S band S b(see figure 2). The EUs 1 from these strategies are:
l < t  T s
h and
Out of these two, the one that gives a higher utility is optimal. EU1
and EU2 depend on the value of
b . So
b is varied between 0 and
1 and EU1 and EU2 are computed for different values of
b . A
comparison of these two utilities shows that for a particular value
of
b , say
c , . For (
b <
for (
c is crucial in determining the
optimal strategy. This computation gives the optimal time (T s
reaching agreement. T s
l if (
c ) or T s
b <
The next step is to find the optimal price. Assume that (
which means that S bis better than S b. This implies that the optimal
time for reaching agreement is T s
l and not T s
h . Strategies S band
bcan result in an agreement only after T s
l , since the price offered
prior to T s
l is unacceptable to the seller. Thus neither S bnor S bcan be optimal. The optimal strategy is S bor S bdepending on the
1 Utility from conflict to both agents is less than zero.
Negotiation Optimal
Scenario Strategy
all values of t
l
l
l
all values of t
l ; C] for all values of t
l
l
l
all values of t

Table

1: Optimal strategies for the buyer
value of  b . The expressions for EU1 and EU3 are:
and
l
l ). Here T denotes
the time at which b offers P s
minl .  b is varied between 0 and 1 and
EU1 and EU3 are computed. For
c )EU1 > EU3 . This
gives the optimal price P s
reaching agreement. P s
minl if
c ) or P s
c ). Assume that ( b <  b
c ). This
means that the optimal price is P s
minh and the optimal strategy is
l ; B]. Thus S bresults in an outcome that is
optimal in both the price (P s
l ).
Assume that the seller also gains on time and T
l and
minh . Let the values of T b
l and T b
h in s's lottery be T b
and some value greater than T b respectively. Since both possible
values of the buyer's deadline are greater than its own, irrespective
of its value for
s , it has to concede up to P s
min by T s . Thus from
the seller's perspective, the optimal price P b
min and the optimal
In such a scenario, the optimal strategy for s
is to start at some high price, make small concessions till its deadline
is almost reached and then offer the reservation price P s
min at
using the Boulware NDF, i.e., S
In
order for the b and s strategies to converge, the values of  b and
b in b's lotteries should be such that ( b <  b
c ) and (
When these conditions are satisfied P s
. The optimal strategies S b
3  S s then converge and result in an
agreement at price P s
minh and time T s
l (see figure 2). b gets the
price-surplus.
When both buyer and seller lose utility on time, the optimal strategy
for them is to offer P s
minh at the earliest opportunity. This can
be done using a Conceder NDF that results in agreement at the
same price P s
minh but towards the beginning of negotiation. In the
same way, optimal strategies are obtained for the remaining negotiation
scenarios. These are summarised in table 1. T 0 denotes the
beginning of negotiation. A similar kind of analysis is made from
the seller's perspective to obtain P b
in the six possible sce-
narios. In each of these scenarios, the agents' optimal strategies do
not depend on their opponent's strategy. Again see [3] for details.
There are many scenarios in which negotiation can take place.
These depend on the agents' attitude towards time and the relationship
between their deadlines. As stated earlier in this section,
there are six possible scenarios from the buyer's perspective, on the
basis of which it selects its strategy. Similarly from the seller's perspective
there are also six possible scenarios. But the negotiation
outcome depends on all possible ways in which interaction between
Case 1, 2 and 3 Case 4
Deadline Seller's Outcome Outcome
Ordering Deadline b's deadline b's deadline
l (P s
l
l
l T b
l T b
l T b
l T b
l (P b
l
l T b
l T b
l
l T b
l T b
l (P s
l
l
l T b
l T b
l
l T b
l T b
l (P s
l
l
l T b
l T b
l
l T b
l T b
l (P b
l
l
l T b
l T b
l
l T b
l T b
l (P b
l
l
l T b
l T b
l
l T b
l T b

Table

2: Outcome of negotiation when both agents use their
respective optimal strategies
b and s can take place. There can be six possible orderings on the
agent deadlines:
1. T s
l < T s
l < T b
2. T b
l < T b
l < T s
3. T s
l < T b
l < T s
4. T s
l < T b
l < T b
5. T b
l < T s
l < T s
l < T s
l < T b
For each of these orderings, the agents' attitudes towards time could
be one of the following:
1. Both buyer and seller gain utility with time (Case 1).
2. Buyer gains and seller loses utility with time (Case 2).
3. Buyer loses and seller gains utility with time (Case 3).
4. Both buyer and seller lose utility with time (Case 4).
Thus in total there are 24 possible negotiation scenarios and the
outcome of negotiation depends on the exact scenario. A summary
of these is given in table 2. P s
indicates that the price-surplus goes
to b and P b
indicates that the price-surplus goes to s. As seen
in this table, the price-surplus always goes to the agent with the
longer deadline. The time of agreement is T 0 (which denotes the
beginning of negotiation) if both agents lose on time, and the earlier
Buyer
Seller
Buyer
I
I I I
43

Figure

3: Extensive form of the negotiation game
deadline if at least one agent gains on time. Note that these are
the outcomes that will result if the agents' beliefs about each other
satisfy the following conditions for convergence of strategies.
1. (
b <
l ) for b.
2.
minl ) for b.
3. (
s <
s
s >
s
l ) for s.
4. ( s <  s
maxl
The similarity between these results and those of Sandholm and
Vulkan [15] on bargaining with deadlines is that, in both cases,
the price-surplus always goes to the agent with the longer dead-
line. However, the difference is that in [15] the deadline effect
overrides time discounting, whereas here the deadline effect does
not override time discounting. This happens because in [15] the
agents always make offers that lie within the zone of agreeement.
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 [15] agreement is reached towards the
beginning of negotiation.
The single issue negotiation model of [3] only determines optimal
strategies for agents on the basis of available information and
shows the resulting outcome. However such an outcome is only
possible if this mutual strategic behavior of agents leads to equi-
librium. In the following subsection we prove this by using the
standard game theoretic solution concept of sequential equilibrium.
2.5 Equilibrium agreements
Since agents do not have information about their opponent's strategy
or utility, negotiation can be considered as a game G of incomplete
information. A strategy profile and belief system pair is a
sequential equilibrium of an extensive game if it is sequential rational
and consistent [8]. A system of beliefs  in an extensive form
game G is a specification of a probability x 2 [0; 1] for each decision
node x in G such that
information sets
I . In other words,  represents the agent's beliefs about the history
of negotiation. The player's strategies satisfy sequential rationality
if for each information set of each player a, the strategy of player a
is a best response to the other player's strategies, given a's beliefs
at that information set. The requirement for  to be consistent with
the strategy profile is as follows. Even at an infromation set that
is not reached if all players adhere to their strategies, it is required
that a player's belief be derived from some strategy profile using
Bayes' rule.
THEOREM 1. There exists sequential equilibrium of G at the
point [P b
for the negotiation
scenario corresponding to case 1 and deadline ordering D1, where
minl if (P s
minl
minh
l if (T
l ) or T s
PROOF. The first three levels of the extensive form of this game
are shown in figure 3. At node 1 one of the players, say b, starts
negotiation by using its optimal strategy [P b
reaches node 2. At this level it is player s's turn to make a de-
cision. I 1 becomes the information set for s since it is unaware
of the strategy used by b and hence does not know which of the
three nodes 2, 3 or 4 play has reached. However, irrespective of
which node play reaches at this level (i.e., irrespective of s's belief
about the history of negotiation), the dominant strategy for s
is [P s
Play now reaches node 5 (since both agents
use B) at which b makes a move. At this point b does not know
exactly which node the play is at, but it knows with certainty that
its information set I 2 is reached (the probability of reaching other
decision nodes at this level is 0). The dominant strategy for b at
this information set (and at all others) is [P b
at every information set at which it is b's turn to make a move,
its optimal strategy is [P b
B], and at every information
set at which it is s's turn to make a move, its optimal strategy
is [P s
B]. The strategy profile [P b
therefore satisfies the requirements for sequential
rationality. Furthermore, at every information set, the optimal
strategies are also dominant strategies. This makes the strategy
profile [P b
point irrespective of the agents' beliefs about the history of
negotiation.
COROLLARY 1. The optimal strategy profile constitutes a unique
equilibrium.
PROOF. This is a direct consequence of the above proof. As the
optimal strategies for both agents are dominant strategies at each
of their information sets, there does not exist any other equilibrium
(neither a pure nor a mixed strategy) where an agent uses a strategy
other than its optimal strategy.
In the same way, sequential equilibrium can be shown to exist
when agents use their optimal strategies in all the remaining negotiation
scenarios.
3. MULTI-ISSUE NEGOTIATION
We now extend the above model for multi-issue bargaining where
the issues are independent 2 of each other. Assume that buyer, b,
and seller, s, that have unequal deadlines, bargain over the price of
two distinct goods/services, X and Y. Negotiation on all the issues
must end before the deadline. 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.
3.1 Agents' information state
Let the buyer's reservation prices for X and Y be P b
x and P b
y and the
seller's reservation prices be P s
x and P s
y respectively. The buyer's
information state is:
I
2 Independence is a common and reasonable assumption to make in
this context. Future work will deal with the dependent case.
are the information about its own
parameters and L s
y and L s
are three lotteries that denote its beliefs
about the opponent's parameters.
xH ] is the lottery on the seller's reservation
price for X such that P s
yH ] is the lottery on the seller's reservation
price for Y such that P s
yH and
h ] is the lottery on the seller's deadline
such that T s
l < T s
h .
Similarly, the seller's information state is defined as:
I
An agent's information state is its private knowledge. The agents'
utility functions are defined as:
U a (px
Note that the discounting factors are different for different issues.
This allows agents' attitudes toward time to be different for different
issues.
3.2 Negotiation protocol
Again we use an alternating offers negotiation protocol. There are
two types of offers. An offer on just one good is referred to as
a single offer and an offer on two goods is referred to as a combined
offer. One of the agents starts by making a combined offer.
The other agent can accept/reject part of the offer (single issue) or
the complete offer. If it rejects the complete offer, then it sends a
combined counter-offer. This process of making combined offers
continues till agreement is reached on one of the issues. Thereafter
agents make offers only on the remaining issue (i.e., once agreement
is reached on an issue, it cannot be renegotiated). Negotiation
ends when agreement is reached on both the issues or a deadline is
reached. Thus the action A that agent s takes at time t on a single
offer is as defined in section 2.1 . Its action on a combined offer,
b!s ), is defined as:
1. Quit if t > T s
2. Accept X t
b!s if U s (X t
3. Accept Y t
b!s if U s (Y t
4. Offer X t 0
b!s not accepted
5. Offer Y t 0
b!s not accepted.
A counter-offer for an issue is generated using the method described
in section 2.2. 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, b can offer a very low price which will not be acceptable
to s and s can offer a price which will not be acceptable to b.
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 [4]. 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 list the equilibrium agreements in
different negotiation scenarios and then compare the outcome that
results from the sequential implementation with that of the simultaneous
implementation.
Negotiation Scenario Time of agreement
9 LG GG T T

Table

3: Equilibrium agreements for two issues X and Y
3.3 Equilibrium strategies
We assume that the conditions for convergence (as listed in section
are satisfied for both X and Y. As agents negotiate over
the price of two distinct goods/services, the equilibrium strategies
for the single issue model can be applied to X and Y independently
of each other. The equilibrium agreements in different negotiation
scenarios are listed in table 3. T equals T b if (T b < T s ) and T s if
denotes the beginning of negotiation. G indicates
that the agent gains utility on time and L indicates that it loses on
time. The price-surplus on both issues always goes to the agent
with the longer deadline (see section 2.4).
Consider a situation where both b and s lose on time on X and
gain on time on Y (row 11 of table 3). Let T b > T s . Assuming the
conditions for convergence are satisfied, b's equilibrium strategies
for X and Y are
and those for s are
(see table 1). During the process of negotiation, agents generate
offers using these strategies. This results in an agreement on X
towards the beginning of negotiation, and on Y at time T s (which
is the earlier deadline). The price-surplus for X and Y goes to the
agent with the longer deadline, i.e., b.
3.4 Implementation schemes
Any two strategies (S b ; S s ) lead to an outcome of the game. If
S b and S s are the equilibrium strategies, then the outcome is an
agreement on X at time t and price px and an agreement on Y at
time  and price py . Payoffs for this outcome depend on the rules
by which agreements are implemented.
Sequential implementation. Exchange of a given good/service
takes place at the time of agreement on a price for that good/service.
The agents' utilities from the strategy pair (S b ; S s ) leading
to agreements (px ; t) and (py ;  ) are:
y py )(- b
U s
Simultaneous implementation. Exchange of goods/services
takes place only after agreement is reached on prices of all
the goods. The agents'utilities for this rule are:
y py )(- b
U s
(py P s
Since the equilibrium strategies optimize the time (and price) of
agreement on an issue, it seems obvious that the agents will be better
off if exchange takes place sequentially rather than simultane-
ously. However, since agents can have like, as well as, conflicting
time preferences, it is important to determine if sequential implementation
proves better than simultaneous implementation for both
agents under all negotiation scenarios. We show below that sequential
implementation of the equilibrium agreement always gives a
better outcome than simultaneous implementation.
THEOREM 2. The outcome generated by sequential implementation
is no worse than the outcome for simultaneous implementation
for both agents.
PROOF. When at least one of the agents gains on time on an
issue, say X, then the equilibrium strategies result in an agreement
at the earlier of the two deadlines. If T b > T s , then
x and if T s > T b then
x . When both
agents lose on time on X, then agreement is reached towards the
beginning of negotiation. Thus
and
As shown in table 3, the agents have like
time preferences in the first and last rows. In all other cases they
have conflicting preferences on at least one issue. There are three
possible ways in which agreement can be reached between agents.
We analyze each of these cases below.
1. Both issues are agreed upon near the earlier deadline. Here
Such an agreement is possible only if, for every issue,
at least one agent gains on time. If px and py are the prices
that are agreed for X and Y, the expressions below yield equal
utility from both implementation schemes to both b and s.
y py )(- b
U s
2. Both issues are agreed upon towards the beginning of ne-
gotiation. This happens when both agents lose on time on
both the issues. As in case 1, the expressions for utility from
sequential and simultaneous schemes yield the same values
since
3. One issue is agreed towards the beginning of negotiation and
the other near the earlier deadline. This occurs when both
agents lose on time on one of the issues, say X, and at least
one agent gains on time on the other issue, say Y. Here
and the buyer's utilities from sequential and simultaneous
implementations are:
y py )(- b
and
y py )(- b
The utility from X is greater for sequential implementation
since T 0 <  and both agents lose on time. The utility from Y
is equal for both schemes. As a result, sequential implementation
gives a total utility that is higher than simultaneous
implementation. The utility that the seller gets is:
U s
and
U s
As s also loses on time on X, its utility from X is higher for
sequential implementation giving a higher cumulative utility
than simultaneous implementation. Thus sequential implementation
always gives a better outcome than simultaneous
implementation.
The same argument holds good when b and s negotiate over more
than two issues. Thus from the perspective of both agents, sequential
implementation proves to be a better implementation scheme
than simultaneous implementation.
3.5 Properties of equilibrium solution
The main focus in the design of a negotiation model 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 [8] of the equilibrium agreement.
1. Uniqueness. If the solution of the negotiation game is unique,
then it can be identified unequivocally.
THEOREM 3. For each negotiation scenario, the proposed
negotiation model has a unique equilibrium agreement.
PROOF. There are n independent negotiation issues each
of which has a single equilibrium agreement (see section 2.5
for proof). This gives a unique equilibrium agreement for all
issues.
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. The proposed
negotiation mechanism possesses the property of symmetry
since the outcome does not depend on which player starts the
process of negotiation.
THEOREM 4. In all negotiation scenarios, the bargaining
outcome is independent of the identity of the first player.
PROOF. As shown in table 3, there are two time points
at which agreements can be reached; T 0 which denotes the
beginning of negotiation or T which is the earlier deadline.
At these time points one of the agents (either b or s depending
on whose turn it is) offers the equilibrium solution which the
other agent accepts.
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 Pareto-optimal
in some, but not all, negotiation scenarios.
THEOREM 5. When players have opposite time preferences
on an issue and the agent with the longer deadline
loses on time on that issue, the equilibrium solution is not
necessarily Pareto-optimal.
PROOF. Consider row 5 of table 3. Assume that T s < T b .
On issue Y, the agents have conflicting time preferences. As
and the price-surplus in the equilibrium
solution goes to b
y ). The utility to an agent can
be increased by changing price or time or both. Price (py )
can only be increased and  can only be decreased, since a
decrease in price or an increase in  will be unacceptable
to s. An increase in py decreases U b and increases U s . A
decrease in  increases U b and decreases U s . But a change
in both py and  can improve both U b and U s . The same
argument holds for the other cases.
In all the remanining scenarios it can be seen that the solution
is Pareto-efficient; an increase in one agent's uitlity lowers its
opponent's utility.
4. RELATED WORK
Fershtman [4] extends Rubinstein's complete information model
[12] 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. It 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 [5] but it endogenizes the agenda.
Bac and Raff [1] developed a model that has an endogenous
agenda. They extend Rubinstein's model [13] 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 discounting factor. This can take
one of two values, -H with probability  and -L with probability
1 . These probabilities are common knowledge. Thus agents
have asymmetric information about discounting factors. They however
do not associate deadlines with players.
The difference between these models and ours is that firstly, our
model considers both agent deadlines and discounting factors. Sec-
ondly, in our case the players are uncertain about the opponent's
reservation price and deadline. Each agent knows its own reservation
price and deadline but has a binary probability distribution over
its opponent's reservation price and deadline. Moreover, the discounting
factor is different for different issues and the players have
no information about the opponent's discounting factors. Thirdly,
each agent's information state is its private knowledge which is not
known to its opponent. Our model is therefore closer to most real
life bargaining situations than the other models. The fourth point of
difference lies in the attributes of the solution. Comparing the solution
properties of these models, we see that the existing models do
not have a unique equilibrium solution. The equilibrium solution
depends on the identity of the first player. In our model, the equilibrium
solution is unique and is independent of the identity of the
first player. However, as is the case with our model, the equilibrium
solution is not always Pareto-optimal in the other models.
5. CONCLUSIONS
This paper presented a model for multi-issue negotiation under time
constraints in an incomplete information setting. 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. An important property
of this model is the existence of a unique equilibrium. For any is-
sue, this equilibrium results in agreement at the earlier deadline if
at least one agent has the incentive to reach a late agreement and
at the beginning of negotiation if both agents have the incentive to
reach an early agreement. The price-surplus on all issues goes to
the agent with the longer deadline.
The sequential implementation of the equilibrium agreement was
shown to result in an outcome that is no worse than the outcome for
simultaneous implementation when agents have similar, as well as
conflicting, time preferences. The equilibrium agreement possesses
the properties of being unique and symmetric, although it is not
always Pareto-optimal.
As it currently stands, our model considered the negotiation issues
to be independent of each other. In future we intend to study
bargaining over interdependent issues. Apart from this, our model
considered the case where agents had uncertain information about
each other's deadline and reservation price. In future we will introduce
learning into the model that will allow the agents to learn
these parameters during negotiation. These extensions will take the
model further towards real life bargaining situations.
6.



--R


Negotiation decision functions for autonomous agents.
Optimal negotiation strategies for agents with incomplete information.
The importance of the agenda in bargaining.

Decisions with Multiple Objectives: Preferences and Value Tradeoffs.
A classification scheme for negotiation in electronic commerce.
A Course in Game Theory.
Agents that buy and sell.
Negotiation Behavior.
The Art and Science of Negotiation.
Perfect equilibrium in a bargaining model.
A bargaining model with incomplete information about time preferences.
Agents in electronic commerce: component technologies for automated negotiation and coalition formation.
Bargianing with deadlines.
--TR
Agents that buy and sell
Bargaining with deadlines
Agents in Electronic Commerce
A Classification Scheme for Negotiation in Electronic Commerce
Optimal Negotiation Strategies for Agents with Incomplete Information

--CTR
Leen-Kiat Soh , Xin Li, Adaptive, Confidence-Based Multiagent Negotiation Strategy, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1048-1055, July 19-23, 2004, New York, New York
Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, Bargaining with incomplete information, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.207-232, July      2005
Shohei Yoshikawa , Takahiko Kamiryo , Yoshiaki Yasumura , Kuniaki Uehara, Strategy Acquisition of Agents in Multi-Issue Negotiation, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.933-939, December 18-22, 2006
Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, An agenda-based framework for multi-issue negotiation, Artificial Intelligence, v.152 n.1, p.1-45, January 2004
Robert M. Coehoorn , Nicholas R. Jennings, Learning on opponent's preferences to make effective multi-issue negotiation trade-offs, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands
Shaheen Fatima , Michael Wooldridge , Nicholas R. Jennings, Optimal agendas for multi-issue negotiation, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
Janice W. Y. Hui , Toby H. W. Lam , Raymond S. T. Lee, The design and implementation of an intelligent agent-based negotiation shopping system, Multiagent and Grid Systems, v.1 n.3, p.131-146, August 2005
Xin Li , Leen-Kiat Soh, Hybrid negotiation for resource coordination in multiagent systems, Web Intelligence and Agent System, v.3 n.4, p.231-259, January 2005
Xin Li , Leen-Kiat Soh, Hybrid negotiation for resource coordination in multiagent systems, Web Intelligence and Agent System, v.3 n.4, p.231-259, October 2005
Karl Kurbel , Iouri Loutchko, Towards multi-agent electronic marketplaces: what is there and what is missing?, The Knowledge Engineering Review, v.18 n.1, p.33-46, January
Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, A Comparative Study of Game Theoretic and Evolutionary Models of Bargaining for Software Agents, Artificial Intelligence Review, v.23 n.2, p.187-205, April     2005
Negotiation Framework for Automatic Collision Avoidance between Vessels, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.595-601, December 18-22, 2006
Iyad Rahwan , Sarvapali D. Ramchurn , Nicholas R. Jennings , Peter Mcburney , Simon Parsons , Liz Sonenberg, Argumentation-based negotiation, The Knowledge Engineering Review, v.18 n.4, p.343-375, December
Ricardo Buttner, A Classification Structure for Automated Negotiations, Proceedings of the 2006 IEEE/WIC/ACM international conference on Web Intelligence and Intelligent Agent Technology, p.523-530, December 18-22, 2006
game theory;agendas;negotiation