- ... maximal
^{1} - ``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.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... property
^{4} - 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
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... path
^{6} - 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 .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... vertices
^{7} - 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
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
least
^{8} - 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.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
value
^{9} - 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.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .