We note that our analyses have primarily been focused on worst-case lower bounds on path length when appropriate paths exist, and as such there are several questions of practical interest that merit further discussion. It may be noted that the path structures and associated utility functions are rather artificial, being directed to attaining a path of a specific length meeting a given rationality criterion. We have seen, however, in Theorems 4 and 5 as outlined in our discussion concluding Section 3 that the issue of exponential length contract paths continues to arise even when we require the utility functions to satisfy a monotonicity condition. We can identify two classes of open question that arise from these results.

Firstly, focusing on IR -contract paths, it would be of interest to identify ``natural'' restrictions
on utility functions which would ensure that, *if* a deal
can be implemented
by an IR -contract path, then it can be realised by one whose length is polynomially bounded in , e.g. such as additivity mentioned in the preceding section.
We can interpret Theorem 4, as indicating that monotonicity does *not* guarantee ``short''
IR contract paths. We note, however, that there *are*
some restrictions that suffice. To use a rather trivial example, if the number of *distinct* values that
can assume is at most for some *constant* then no IR -contract path can
have length exceeding : successive deals must strictly increase and if this can
take at most different values then no IR contract path can have length exceeding . As well as being
of practical interest, classes of utility function with the property being considered would also
be of some interest regarding one complexity issue. The result proved in
[Dunne et al., 2003] establishing
that deciding if an IR -contract path exists is NP-hard, gives a *lower bound* on the
computational complexity of this problem. At present, no (non-trivial) *upper bound* on
this problem's complexity has been demonstrated. Our results in
Theorems 3 and 4 indicate that *if* this decision problem
is in NP (thus its complexity would be NP-complete rather than NP-hard) then the
required polynomial length existence certificate *may* have to be something other than the
path itself.^{10}We note that
the proof of NP-hardness in [Dunne et al., 2003]
constructs an instance in which
can take at most distinct values: thus, from our example of a restriction
ensuring that if such are present then IR -contract paths are ``short'', this result
of [Dunne et al., 2003]
indicates that the question of *deciding* their existence might remain
computationally hard.

Considering restrictions on the form of utility functions is one approach that could be taken regarding
finding ``tractable'' cases. An alternative,
would be
to gain some insight into what the ``average'' path length is likely to be. In attempting to
address this question, however, a number of challenging issues arise. The most immediate of these concerns,
of course, the notion of modeling a distribution on utility function given our
definitions of rationality in terms of the value agents attach to their resource holdings. In principle
an average-case analysis of scenarios involving exactly *two* agents could be carried out
in purely graph-theoretic terms, i.e. without the complication of considering utility functions directly.
It is unclear, however, whether such a graph-theoretic analysis
obviating the need for consideration of literal utility functions, can be extended beyond settings
involving exactly two agents. One difficulty arising with three or more agents is that
our utility functions have no allocative externalities, i.e. given an allocation
to
three agents, is unchanged should be redistributed among
and .^{11}

As one final set of issues that may merit further study we raise the following. In our constructions,
the individual deals on a contract path must satisfy both a *structural* condition (be an -contract
or involve at most agents), and a *rationality* constraint. Focusing on -contracts we
have the following extremes: from [Sandholm, 1998],
at most -contracts suffice to realise any rational deal; from our results above,
*rational* -contracts are needed to realise some rational deals. There are
a number of mechanisms we can employ to relax
the condition that every single deal be an -contract and be rational. For example, allow
a path to contain some number of deals which are not -contracts (but must still be IR)
or insist that all deals are -contracts but allow some to be irrational. Thus, in the latter
case, if we go to
the extent of allowing up to irrational -contracts, then any rational deal can be
realised efficiently. It would be of some interest to examine issues such as the effect of allowing
a *constant* number, , of irrational deals and questions such as whether there are situations
in which irrational contracts yield a `short' contract path but force one of
exponential length. Of particular interest, from an application viewpoint, is the following:
define a -path as
an -contract path containing at most -contracts which are
not individually rational. We know that if then individually rational
-paths are not complete with respect to individually rational deals; similarly if
then -paths *are* complete with respect to individually rational deals. A question
of some interest would be to establish if there is some
for which
-paths are complete with respect to individually rational deals *and*
with the maximum length of such a contract path bounded by a polynomial function of .