Conclusions and Further Work

Our aim in this article has been to develop the earlier studies of Sandholm[1998] concerning the scope and limits of particular ``practical'' contract forms. While [Sandholm, 1998] has established that insisting on individual rationality in addition to the structural restriction prescribed by $O$-contracts leads to scenarios which are incomplete (in the sense that there are individually rational deals that cannot be realised by individually rational $O$-contracts) our focus has been with respect to deals which can be realised by restricted contract paths, with the intention of determining to what extent the combination of structural and rationality conditions increases the number of deals required. We have shown that, using a number of natural definitions of rationality, for settings involving $m$ resources, rational $O$-contract paths of length $\Omega(2^m)$ are needed, whereas without the rationality restriction on individual deals, at most $m$ $O$-contracts suffice to realise any deal. We have also considered a class of deals - $M(k)$-contracts - that were not examined in [Sandholm, 1998], establishing for these cases that, when particular rationality conditions are imposed, $M(k-1)$-contract paths of length $\Omega(2^{2m/k^2})$ are needed to realise a deal that can be achieved by a single $M(k)$-contract.

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 $O$-contract paths, it would be of interest to identify ``natural'' restrictions on utility functions which would ensure that, if a deal $\langle P,Q\rangle$ can be implemented by an IR $O$-contract path, then it can be realised by one whose length is polynomially bounded in $m$, 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 $\sigma_u$ can assume is at most $m^p$ for some constant $p$ then no IR $O$-contract path can have length exceeding $m^p$: successive deals must strictly increase $\sigma_u$ and if this can take at most $K$ different values then no IR contract path can have length exceeding $K$. 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 $O$-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.¹⁰We note that the proof of NP-hardness in [Dunne et al., 2003] constructs an instance in which $\sigma_u$ can take at most $O(m)$ distinct values: thus, from our example of a restriction ensuring that if such are present then IR $O$-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 $\langle X,Y,Z\rangle$ to three agents, $u_1(X)$ is unchanged should $Y\cup Z$ be redistributed among $A_2$ and $A_3$.¹¹

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 $O$-contract or involve at most $k$ agents), and a rationality constraint. Focusing on $O$-contracts we have the following extremes: from [Sandholm, 1998], at most $m$ $O$-contracts suffice to realise any rational deal; from our results above, $\Omega(2^m)$ rational $O$-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 $O$-contract and be rational. For example, allow a path to contain some number of deals which are not $O$-contracts (but must still be IR) or insist that all deals are $O$-contracts but allow some to be irrational. Thus, in the latter case, if we go to the extent of allowing up to $m$ irrational $O$-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, $t$, of irrational deals and questions such as whether there are situations in which $t$ irrational contracts yield a `short' contract path but $t-1$ force one of exponential length. Of particular interest, from an application viewpoint, is the following: define a $(\gamma(m),O)$-path as an $O$-contract path containing at most $\gamma(m)$ $O$-contracts which are not individually rational. We know that if $\gamma(m)=0$ then individually rational $(0,O)$-paths are not complete with respect to individually rational deals; similarly if $\gamma(m)=m$ then $(m,O)$-paths are complete with respect to individually rational deals. A question of some interest would be to establish if there is some $\gamma(m)=o(m)$ for which $(\gamma(m),O)$-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 $m$.