... maximal¹

``Maximal'' in the sense that if $\langle P^{(1)},\ldots,P^{(t)}\rangle$ is such a path, then for every allocation, $Q$, $\Phi(P^{(t)},Q)$ does not hold.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....²

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... undefined.³

In recognising the possibility that $\rho^{\max}(n,m,\Phi,\Psi)$ could be undefined, we are not claiming that such behaviour arises with any of the instantiations of $\langle\Phi,\Psi\rangle$ considered subsequently: in fact it will be clear from the constructions that, denoting by $\rho_{\Phi,\Psi}^{\max}(n,m)$ the function $\rho^{\max}(n,m,\Phi,\Psi)$ for a fixed instantiation of $\langle\Phi,\Psi\rangle$, with the restricted deal types and rationality conditions examined, the function $\rho_{\Phi,\Psi}^{\max}(n,m)$ is a total function. Whether it is possible to formulate ``sensible'' choices of $\langle\Phi,\Psi\rangle$ with which $\rho_{\Phi,\Psi}^{\max}(n,m)$ is undefined for some values of $\langle n,m\rangle$ (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⁴

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....⁵

In our example with $m=4$, the sequence $\langle 0000,1000,1001,1101\rangle$, although defining an $O$-contract path gives rise to a deal which is not IR, namely that corresponding to $\langle 1000,1001\rangle$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... path⁶

In terms of the classification described in [Sandholm, 1998], it contains only swap deals ($S$-contracts): each deal swaps exactly one item in $\beta_{2i-1}$ with an item in $\overline{\beta_{2i-1}}$ in order to give $\beta_{2i+1}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... vertices⁷

This can be shown by an easy inductive argument. For $s=2$, the sequence $\langle 00,01,11,10,00\rangle$ defines a Hamiltonian cycle in ${\mathcal H}_2$. Inductively assume that $\langle\alpha_1,\alpha_2,\ldots,\alpha_p,\alpha_1\rangle$ (with $p=2^s$) is such a cycle in ${\mathcal H}_s$ then $\langle 0\alpha_1,1\alpha_1,1\alpha_p,1\alpha_{p-1},\ldots,1\alpha_2,0\alpha_2\ldots,0\alpha_p,0\alpha_1\rangle$ defines a Hamiltonian cycle in ${\mathcal H}_{s+1}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... least⁸

We omit the rounding operation $\lfloor{\ldots}\rfloor$ in the exponent, which is significant only if $m$ is not an exact multiple of $\left({\begin{array}{c}k\ 2\end{array}}\right)$, in which event the device described in our overview of the proof is applied.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... value⁹

It is worth noting that the ``interpolation'' stage used in Theorem 4 is not needed in forming $multi(\Delta)$: the deal $\langle C^{(d)},C^{(d+1)}\rangle$ is an $M(k-1)$-contract. We recall that in going from $\Delta_s$ of Theorem 3 to $ext(\Delta_s)$ the intermediate stage - $double(\Delta_s)$ - was not an $O$-contract path.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... itself.¹⁰

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$A_3$¹¹

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.