... maximal1
Maximal'' in the sense that if is such a path, then for every allocation, , does not hold.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....2
Sandholm [1998] gives an upper bound on the length of such paths which is also exponential in , but does not explicitly state any lower bound other than that already referred to.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... undefined.3
In recognising the possibility that could be undefined, we are not claiming that such behaviour arises with any of the instantiations of considered subsequently: in fact it will be clear from the constructions that, denoting by the function for a fixed instantiation of , with the restricted deal types and rationality conditions examined, the function is a total function. Whether it is possible to formulate sensible'' choices of with which is undefined for some values of (and, if so, demonstrating examples of such) is, primarily, only a question of combinatorial interest, whose development is not central to the concerns of the current article.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... property4
This defines the so-called snake-in-the-box'' codes introduced in [Kautz, 1958].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....5
In our example with , the sequence , although defining an -contract path gives rise to a deal which is not IR, namely that corresponding to .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... path6
In terms of the classification described in [Sandholm, 1998], it contains only swap deals (-contracts): each deal swaps exactly one item in with an item in in order to give .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... vertices7
This can be shown by an easy inductive argument. For , the sequence defines a Hamiltonian cycle in . Inductively assume that (with ) is such a cycle in then defines a Hamiltonian cycle in .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... least8
We omit the rounding operation in the exponent, which is significant only if is not an exact multiple of , in which event the device described in our overview of the proof is applied.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... value9
It is worth noting that the interpolation'' stage used in Theorem 4 is not needed in forming : the deal is an -contract. We recall that in going from of Theorem 3 to the intermediate stage - - was not an -contract path.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... itself.10
The use of may'' rather than must'' is needed because of the convention for representing utility functions employed in [Dunne et al., 2003].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...11
A very preliminary investigation of complexity-theoretic questions arising in settings with allocative externalities is presented in [Dunne, 2004] where these are referred to as context-dependent'': such utility functions appear to have been neglected in the computational and algorithmic analysis of resource allocation problems, although the idea is well-known to game-theoretic models in economics from which the term allocative externality'' originates.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.