  This paper studies bilateral multi-issue negotiation between self-interested
autonomous agents. Now, there are a number of different procedures that can be
used for this process; the three main ones being the package deal procedure in
which all the issues are bundled and discussed together, the simultaneous
procedure in which the issues are discussed simultaneously but independently of
each other, and the sequential procedure in which the issues are discussed one
after another. Since each of them yields a different outcome, a key problem is
to decide which one to use in which circumstances. Specifically, we consider
this question for a model in which the agents have time constraints (in the
form of both deadlines and discount factors) and information uncertainty (in
that the agents do not know the opponents utility function). For this model, we
consider issues that are both independent and those that are interdependent and
determine equilibria for each case for each procedure. In so doing, we show
that the package deal is in fact the optimal procedure for each party. We then
go on to show that, although the package deal may be computationally more
complex than the other two procedures, it generates Pareto optimal outcomes
(unlike the other two), it has similar earliest and latest possible times of
agreement to the simultaneous procedure (which is better than the sequential
procedure), and that it (like the other two procedures) generates a unique
outcome only under certain conditions (which we define).
