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.10We 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 .