... maximal1
``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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....2
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.3
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... property4
This defines the so-called ``snake-in-the-box'' codes introduced in [Kautz, 1958].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....5
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 $.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... path6
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}$.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... vertices7
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}$.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... least8
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... value9
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.10
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$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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.