$M(k)$-contract paths

 We now turn to similar issues with respect to $M(k)$-contracts, recalling that in one respect these offer a form of deal that does not fit into the classification of [Sandholm, 1998]. This classification defines four forms of contract type: $O$-contracts, as considered in the previous section; $S$-contracts, that involve exactly 2 agents swapping single resources; $C$-contracts, in which one agent tranfers at least two of its resources to another; and $M$-contracts in which three or more agents reallocate their resource holding amongst themselves. Our definition of $M(k)$-contracts permits two agents to exchange resources (thus are not $M$-contracts in Sandholm's[1998] scheme) and the deals permitted are not restricted to $O$, $S$, and $C$-contracts. In one regard, however, $M(k)$-contracts are not as general as $M$-contracts since a preset bound ($k$) is specified for the number of agents involved.

Our main result on $M(k)$-contract paths is the following development of Theorem 3.

Theorem 6   Let $\Phi_k(P,Q)$ be the predicate which holds whenever $\langle P,Q\rangle$ is an IR $M(k)$-contract. For all $k\geq 3$, $n\geq k$ and $m\geq\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}$, there is a resource allocation setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ and an IR deal $\delta=\langle P,Q\rangle$ for which,

$$\begin{array}{lcclr} L^{{\rm opt}}(\delta,\langle{\mathcal A... ...hi_{k-2})&&\mbox{ {\rm is undefined}}& \mbox{ }&(c) \end{array}$$

Before presenting the proof, we comment about the formulation of the theorem statement and give an overview of the proof structure.

We first note that the lower bounds (where defined) have been phrased in terms of the function $L^{{\rm opt}}$ as opposed to $\rho^{\max}$ used in the various results on $O$-contract paths in Section 2.2. It is, of course, the case that the bound claimed for $L^{{\rm opt}}(\delta,\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi_{k-1})$ will also be a lower bound on $\rho^{\max}(n,m,\Phi_{k-1},\Psi)$ when $n\geq k$ and $\Psi(P,Q)$ holds whenever the deal $\langle P,Q\rangle$ is IR. The statement of Theorem 6, however, claims rather more than this, namely that a specific resource allocation setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ can be defined for each $n\geq k$ and each $m$, together with an IR deal $\langle P,Q\rangle$ in such a way that: $\langle P,Q\rangle$ can be achieved by a single $M(k)$-contract and cannot be realised by an IR $M(k-2)$-contract path. Recalling that $L^{{\rm opt}}$ is a partial function, the latter property is equivalent to the claim made in part (c) for the deal $\langle P,Q\rangle$ of the theorem statement. Furthermore, this same deal although achievable by an IR $M(k-1)$-contract path can be so realised only by one whose length is as given in part (b) of the theorem statement.

Regarding the proof itself, there are a number of notational complexities which we have attempted to ameliorate by making some simplifying assumptions concerning the relationship between $m$ - the size of the resource set ${\mathcal R}$ - and $k$ - the number of agents which are needed to realise $\langle P,Q\rangle$ in a single IR deal. In particular, we shall assume that $m$ is an exact multiple of $\left({\begin{array}{c}k\ 2\end{array}}\right)$. We observe that by employing a similar device to that used in the proof of Theorem 4 we can deal with cases for which $m$ does not have this property: if $m = s\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}+q$ for integer values $s\geq 1$ and $1\leq q<\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}$, we simply employ exactly the same construction using $m-q$ resources with the ``missing'' $q$ resources from ${\mathcal R}_m$ being allocated to $A_1$ and never being reallocated within the $M(k-1)$-contract path. This approach accounts for the rounding operation ( $\lfloor{\ldots}\rfloor$) in the exponent term of the lower bound. We shall also assume that the number of agents in ${\mathcal A}$ is exactly $k$. Within the proof we use a running example for which $k=4$ and $m=18=3\times6$ to illustrate specific features.

We first give an outline of its structure.

Given $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ a resource allocation setting involving $k$ agents and $m$ resources, our aim is to define an IR $M(k-1)$-contract path

$$\Delta = \langle P^{(1)},P^{(2)},\ldots,P^{(t)}\rangle$$

that realises the IR $M(k)$ deal $\langle P^{(1)},P^{(t)}\rangle$. We will use $d$ to index particular allocations within $\Delta$, so that $1\leq d\leq t$.

In order to simplify the presentation we employ a setting in which the $k$ agents are ${\mathcal A}=\{A_0,A_1,\ldots,A_{k-1}\}$. Recalling that $m=s\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}$, the resource set ${\mathcal R}_m$ is formed by the union of $\left({\begin{array}{c}k\ 2\end{array}}\right)$ pairwise disjoint sets of size $s$. Given distinct values $i$ and $j$ with $0\leq i<j\leq k-1$, we use ${\mathcal R}^{i,j}$ to denote one of these subsets with $\{r_{1}^{\{i,j\}}, r_{2}^{\{i,j\}} ,\ldots, r_{s}^{\{i,j\}}\}$ the $s$ resources that form ${\mathcal R}^{\{i,j\}}$.

There are two main ideas underpinning the structure of each $M(k-1)$-contract in $\Delta$.

Firstly, in the initial and subsequent allocations, the resource set ${\mathcal R}^{\{i,j\}}$ is partitioned between $A_i$ and $A_j$ and any reallocation of resources between $A_i$ and $A_j$ that takes place within the deal $\langle P^{(d)},P^{(d+1)}\rangle$ will involve only resources in this set. Thus, for every allocation $P^{(d)}$ and each pair $\{i,j\}$, if $h\not\in\{i,j\}$ then $P_{h}^{(d)}\cap{\mathcal R}^{\{i,j\}}=\emptyset$. Furthermore, for $\delta=\langle P^{(d)},P^{(d+1)}\rangle$ should both $A_i$ and $A_j$ be involved, i.e. $\{A_i,A_j\}\subseteq{\mathcal A}^\delta$, then this reallocation of ${\mathcal R}^{\{i,j\}}$ between $A_i$ and $A_j$ will be an $O$-contract. That is, either exactly one element of ${\mathcal R}^{\{i,j\}}$ will be moved from $P^{(d)}_{i}$ to become a member of the allocation $P^{(d+1)}_{j}$ or exactly one element of ${\mathcal R}^{\{i,j\}}$ will be moved from $P^{(d)}_{j}$ to become a member of the allocation $P^{(d+1)}_{i}$. In total, every $M(k-1)$-contract $\delta$ in $\Delta$ consists of a simultaneous implementation of $\left({\begin{array}{c}k-1\ 2\end{array}}\right)$ $O$-contracts: a single $O$-contract for each of the distinct pairs $\{A_i,A_j\}$ of agents from the $k-1$ agents in ${\mathcal A}^{\delta}$.

The second key idea is to exploit one well-known property of the $s$-dimensional hypercube network: for every $s\geq 2$, ${\mathcal H}_s$ contains a Hamiltonian cycle, i.e. a simple directed cycle formed using only the edges of ${\mathcal H}_s$ and containing all $2^s$ vertices.⁷ Now, suppose

$${\mathcal S}^{(v)}=\underline{v}^{(0)},\underline{v}^{(1)},\... ...e{v}^{(i)},\ldots,\underline{v}^{(2^s-1)}, \underline{v}^{(0)}$$

is a Hamiltonian cycle in the hypercube ${\mathcal H}_s$ and

$${\mathcal S}^{(w)}=\underline{w}^{(0)},\underline{w}^{(1)},\... ...w}^{(i)},\ldots, \underline{w}^{(2^s-1)}, \underline{w}^{(0)}$$

the Hamiltonian cycle in which $\underline{w}^{(i)}$ is obtained by complementing each bit in $\underline{v}^{(i)}$. As we have described in the overview of Section 2.1 we can interpret the $s$-bit label $\underline{v}=v_1v_2\ldots v_s$ as describing a particular subset of ${\mathcal R}^{\{i,j\}}$, i.e. that subset in which $r_{k}^{\{i,j\}}$ occurs if and only if $v_k=1$. Similarly from any subset of ${\mathcal R}^{\{i,j\}}$ we may define a unique $s$-bit word. Now suppose that $P_{i}^{(d)}$ is the allocation held by $A_i$ in the allocation $P^{(d)}$ of $\Delta$. The deal $\delta=\langle P^{(d)},P^{(d+1)}\rangle$ will affect $P_{i}^{(d)}\cap{\mathcal R}^{\{i,j\}}$ in the following way: if $i\not\in{\mathcal A}^{\delta}$ or $j\not\in{\mathcal A}^{\delta}$ then $P_{i}^{(d+1)}\cap{\mathcal R}^{\{i,j\}}=P_{i}^{(d)}\cap{\mathcal R}^{\{i,j\}}$ and $P_{j}^{(d+1)}\cap{\mathcal R}^{\{i,j\}}=P_{j}^{(d)}\cap{\mathcal R}^{\{i,j\}}$. Otherwise we have $\{i,j\}\subseteq{\mathcal A}^{\delta}$ and the (complementary) holdings $P_{i}^{(d)}\cap{\mathcal R}^{\{i,j\}}$ and $P_{j}^{(d)}\cap{\mathcal R}^{\{i,j\}}$ define (complementary) $s$-bit labels of vertices in ${\mathcal H}_s$: if these correspond to places $\langle\underline{v}^{(h)},\underline{w}^{(h)}\rangle$ in the Hamiltonian cycles, then in $P_{i}^{(d+1)}$ and $P_{j}^{(d+1)}$ the $s$-bit labels defined from $P_{i}^{(d+1)}\cap{\mathcal R}^{\{i,j\}}$ and $P_{j}^{(d+1)}\cap{\mathcal R}^{\{i,j\}}$ produce the $s$-bit labels $\underline{v}^{(h+1)}$ and $\underline{w}^{(h+1)}$, i.e. the vertices that succeed $\underline{v}^{(h)}$ and $\underline{w}^{(h)}$ in the Hamiltonian cycles. In total, for each $j$, $A_i$ initially holds either the subset of ${\mathcal R}^{\{i,j\}}$ that maps to $\underline{v}^{(0)}$ or that maps to $\underline{w}^{(0)}$ and, at the conclusion of the $M(k-1)$-path, holds the subset that maps to $\underline{v}^{(2^s-1)}$ (or $\underline{w}^{(2^s-1)}$). The final detail is that the progression through the Hamiltonian cycles is conducted over a series of rounds each round comprising $k$ $M(k-1)$-deals.

We have noted that each $M(k-1)$-contract, $\langle P^{(d)},P^{(d+1)}\rangle$ that occurs in this path $\Delta$ can be interpreted as a set of $\left({\begin{array}{c}k-1\ 2\end{array}}\right)$ distinct $O$-contracts. An important property of the utility functions employed is that unless $p\geq k-1$ there will be no individually rational $M(p)$-contract path that realises the deal $\langle P^{(d)},P^{(d+1)}\rangle$, i.e. the $\left({\begin{array}{c}k-1\ 2\end{array}}\right)$ $O$-contract deals must occur simultaneously in order for the progression from $P^{(d)}$ to $P^{(d+1)}$ to be IR. Although the required deal could be realised by a sequence of $O$-contracts (or, more generally, any suitable $M(k-2)$-contract path), such realisations will not describe an IR contract path. The construction of utility functions to guarantee such behaviour provides the principal component in showing that the IR deal $\langle P^{(1)},P^{(t)}\rangle$ cannot be realised with an IR $M(k-2)$-contract path: if $Q$ is any allocation for which $\langle P^{(1)},Q\rangle$ is an $M(k-2)$-contract then $\langle P^{(1)},Q\rangle$ is not IR.

We now proceed with the proof of Theorem 6.

Proof. (of Theorem 6) Fix ${\mathcal A}=\{A_0,A_1,\ldots,A_{k-1}\}$. ${\mathcal R}$ consists of $\left({\begin{array}{c}k\ 2\end{array}}\right)$ pairwise disjoint sets of $s$ resources

$${\mathcal R}^{\{i,j\}}=\{r_{1}^{\{i,j\}},r_{2}^{\{i,j\}},\ldots,r_{s}^{\{i,j\}}\}$$

For $k=4$ and $s=3$ these yield ${\mathcal A}=\{A_0,A_1,A_2,A_3\}$ and

$$\begin{array}{lcl} {\mathcal R}^{\{0,1\}}&=&\{r_{1}^{\{0,1\}... ...\{r_{1}^{\{2,3\}},r_{2}^{\{2,3\}},r_{3}^{\{2,3\}}\} \end{array}$$

We use two ordering structures in defining the $M(k-1)$-contract path.

a.

$${\mathcal S}^{(v)}=\underline{v}^{(0)},\underline{v}^{(1)},\... ...e{v}^{(i)},\ldots,\underline{v}^{(2^s-1)}, \underline{v}^{(0)}$$

a Hamiltonian cycle in ${\mathcal H}_s$, where without loss of generality, $\underline{v}^{(0)}=111\ldots11$.

b.

$${\mathcal S}^{(w)}=\underline{w}^{(0)},\underline{w}^{(1)},\... ...w}^{(i)},\ldots, \underline{w}^{(2^s-1)}, \underline{w}^{(0)}$$

the complementary Hamiltonian cycle to this, so that $\underline{w}^{(0)}=000\ldots00$.

Thus for $k=4$ and $s=3$ we obtain

$$\begin{array}{llcl} \mbox{a. }&{\mathcal S}^{(v)}&=&\langle ... ...}&=&\langle 000,001,101,100,110,111,011,010\rangle \end{array}$$

We can now describe the $M(k-1)$-contract path.

$$\Delta = \langle P^{(1)},P^{(2)},\ldots,P^{(t)}\rangle$$

$$
Initial Allocation: $P^{(1)}$.
Define the $k\times k$ Boolean matrix, $B=[b_{i,j}]$ (with $0\leq i,j\leq k-1$) by

$$b_{i,j} = \left\{ { \begin{array}{lcl} \bot&\mbox{ if }&i=... ...f }&i>j\\ \neg b_{i,j-1}&\mbox{ if }&i<j \end{array}} \right.$$

We then have for each $1\leq i\leq k$,

$$P_{i}^{(1)} = \bigcup_{j=0}^{i-1}\{ R^{\{j,i\}}\mbox{ : }... ... \bigcup_{j=i+1}^{k-1}\{ R^{\{i,j\}}\mbox{ : }b_{i,j}=\top\}$$

Thus, in our example,

$$B =\ \left[ { \begin{array}{cccc} \bot&\top&\bot&\top\\ \... ...top&\bot&\bot&\top\\ \bot&\top&\bot&\bot \end{array}} \right]$$

Yielding the starting allocation

$$\begin{array}{lclclcl} P_0^{(1)}&=&{\mathcal R}^{\{0,1\}}\cu... ...cup{\mathcal R}^{\{1,3\}}\cup{\mathcal R}^{\{2,3\}} \end{array}$$

The third column in $P_{i}^{(1)}$ indicating the $3$-bit labels characterising each of the subsets of ${\mathcal R}^{\{i,j\}}$ for the three values that $j$ can assume.
$$
Rounds: The initial allocation is changed over a series of rounds

$$Q^1,Q^2,\ldots,Q^z$$

each of which involves exactly $k$ distinct $M(k-1)$-contracts. We use $Q^{x,p}$ to indicate the allocation resulting after stage $p$ in round $x$ where $0\leq p\leq k-1$. We note the following:

a.

The initial allocation, $P^{(1)}$ will be denoted by $Q^{0,k-1}$.

b.

$Q^{x,0}$ is obtained using a single $M(k-1)$-contract from $Q^{x-1,k-1}$ (when $x\geq1$).

c.

$Q^{x,p}$ is obtained using a single $M(k-1)$-contract from $Q^{x,p-1}$ (when $0<p\leq k-1$).

Our final item of notation is that of the cube position of $i$ with respect to $j$ in an allocation $P$, denoted $\chi(i,j,P)$. Letting $\underline{u}$ be the $s$-bit string describing $P_i\cap{\mathcal R}^{\{i,j\}}$ in some allocation $P$, $\chi(i,j,P)$ is the index of $\underline{u}$ in the Hamiltonian cycle $S^{(v)}$ (when ${\mathcal R}^{\{i,j\}}\subseteq P_{i}^{(1)}$) or the Hamiltonian cycle $S^{(w)}$ (when ${\mathcal R}^{\{i,j\}}\subseteq P_{j}^{(1)}$). When $P=Q^{x,p}$ for some allocation in the sequence under construction we employ the notation $\chi(i,j,x,p)$, noting that one invariant of our path will be $\chi(i,j,x,p)=\chi(j,i,x,p)$, a property that certainly holds true of $P^{(1)}=Q^{0,k-1}$ since $\chi(i,j,0,k-1)=\chi(j,i,0,k-1)=0$.

The sequence of allocations in $\Delta$ is built as follows. Since $Q^{1,0}$ is the immediate successor of the initial allocation $Q^{0,k-1}$, it suffices to describe how $Q^{x,p}$ is formed from $Q^{x,p-1}$ (when $p>0$) and $Q^{x+1,0}$ from $Q^{x,k-1}$. Let $Q^{y,q}$ be the allocation to be formed from $Q^{x,p}$. The deal $\delta=\langle Q^{x,p},Q^{y,q}\rangle$ will be an $M(k-1)$ contract in which ${\mathcal A}^{\delta}={\mathcal A}\setminus \{A_q\}$. For each pair $\{i,j\}\subseteq{\mathcal A}^{\delta}$ we have $\chi(i,j,x,p)=\chi(j,i,x,p)$ in the allocation $Q^{x,p}$. In moving to $Q^{y,q}$ exactly one element of ${\mathcal R}^{\{i,j\}}$ is reallocated between $A_i$ and $A_j$ in such a way that in $Q^{y,q}$, $\chi(i,j,y,q)=\chi(i,j,x,p)+1$, since $A_i$ and $A_j$ are tracing complementary Hamiltonian cycles with respect to ${\mathcal R}^{\{i,j\}}$ this ensures that $\chi(j,i,y,q)=\chi(j,i,x,p)+1$, thereby maintaining the invariant property.

Noting that for each distinct pair $\langle i,j\rangle$, we either have ${\mathcal R}^{\{i,j\}}$ allocated to $A_i$ in $P^{(1)}$ or ${\mathcal R}^{\{i,j\}}$ allocated to $A_j$ in $P^{(1)}$, the description just outlined indicates that the allocation $P^{(d)}=Q^{x,p}$ is completely specified as follows.

The cube position, $\chi(i,j,x,p)$, satisfies,

$$\chi(i,j,x,p) =  \left\{ { \begin{array}{lcl} 0&\mbox{ if }&... ...box{$1\leq p\leq k-1$, and $p\in\{i,j\}$} \end{array}} \right.$$

For each $i$, the subset of ${\mathcal R}^{\{i,j\}}$ that is held by $A_i$ in the allocation $Q^{x,p}$ is,

$$\begin{array}{lcl} \mbox{{ \large$\underline{v}^{(\chi(i,j,x... ...m if} }&{\mathcal R}^{\{i,j\}}\subseteq P_{j}^{(1)} \end{array}$$

(where we recall that $s$-bit labels in the hypercube ${\mathcal H}_s$ are identified with subsets of ${\mathcal R}^{\{i,j\}}$.)

The tables below illustrates this process for our example.

$$\begin{array}{c} \begin{array}{c\vert ll\vert ccc\vert ccc\v... ...\}}$ held by $A_i$ in $Q^{x,p}$ ($k=4$, $s=3$)}} \end{array}$$

$$\begin{array}{c} \begin{array}{c\vert ll\vert ccc\vert ccc\v... ...bf Cube Positions $\chi(i,j,x,p)$ ($k=4$, $s=3$)}} \end{array}$$

It is certainly the case that this process of applying successive rounds of $k$ deals could be continued, however, we wish to do this only so long as it is not possible to go from some allocation $P^{(d)}$ in the sequence to another $P^{(d+r)}$ for some $r\geq 2$ via an $M(k-1)$-contract.

Now if $Q^{x,p}$ and $Q^{y,q}$ are distinct allocations generated by the process above then the deal $\delta=\langle Q^{x,p},Q^{y,q}\rangle$ is an $M(k-1)$-contract if and only if for some $A_i$, $Q^{x,p}_i=Q^{y,q}_i$. It follows that if $\langle P^{(d)},P^{(d+r)}\rangle$ is an $M(k-1)$-contract for some $r>1$, then for some $i$ and all $j\not=i$, $P_{i}^{(d+r)}\cap{\mathcal R}^{\{i,j\}}=P_{i}^{(d)}\cap{\mathcal R}^{\{i,j\}}$.

To determine the minimum value of $r>1$ with which $P_{i}^{(d+r)}=P_{i}^{(d)}$, we observe that without loss of generality we need consider only the case $d=i=0$, i.e. we determine the minimum number of deals before $P_{0}^{(1)}$ reappears. First note that in each round, $Q^{x}$, if $\chi(0,j,x-1,k-1)=p$ then $\chi(0,j,x,k-1)=p+k-2$, i.e. each round advances the cube position $k-2$ places: $\chi(0,j,x-1,k-1)=\chi(0,j,x,0)$ and $\chi(0,j,x,j)=\chi(0,j,x,j-1)$. We can also observe that $P_{0}^{(1)}=Q_{0}^{0,k-1}\not=Q_{0}^{x,p}$ for any $p$ with $0<p<k-1$, since

$$\chi(0,1,x,p)=\chi(0,2,x,p)=\ldots=\chi(0,k-1,x,p)$$

only in the cases $p=0$ and $p=k-1$. It follows that our value $r>1$ must be of the form $qk$ where $q$ must be such that $q(k-2)$ is an exact multiple of $2^s$. From this observation we see that,

$$\min\{\mbox{ $r>1$ : $P_{0}^{(1)}=P_{0}^{(1+r)}$ }\} =\ \min\{\mbox{ $qk$ : $q(k-2)$ is a multiple of $2^s$}\}$$

Now, if $k$ is odd then $q=2^s$ is the minimal such value, so that $r=k2^s$. If $k$ is even then it may be uniquely written in the form $z2^l+2$ where $z$ is odd so giving $q$ as $1$ (if $l\geq s$) or $2^{s-l}$ (if $l\leq s$), so that these give $r=k$ and $r=z2^s+2^{s-l+1}$, e.g. for $k=4$ and $s=3$, we get $k=1\times2^1+2$ so that $r=2^3+2^{3-1+1}=16$ and in our example $P_{0}^{(1)}=P_{0}^{(17)}$ may be easily verified. In total,

$$r\geq\left\{ { \begin{array}{lcl} k2^s&\mbox{ if }&\mbox{$k$... ...ox{$k=z2^l+2$, $z$ is odd and $l\leq s$} \end{array}} \right.$$

All of which immediately give $r\geq 2^s$ (in the second case $k\geq2^s$, so the inequality holds trivially), and thus we can continue the chain of $M(k-1)$ contracts for at least $2^s$ moves. Recalling that $m=s\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}$, this gives the length of the $M(k-1)$-contract path

$$\Delta = \langle P^{(1)},P^{(2)},\ldots,P^{(t)}\rangle$$

written in terms of $m$ and $k$ as at least⁸

$$2^{m/\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}} -1 =\ 2^{\frac{2m}{k(k-1)}} - 1$$

It remains to define appropriate utility functions ${\mathcal U}=\langle u_0,\ldots,u_{k-1}\rangle$ in order to ensure that $\Delta$ is the unique IR $M(k-1)$-contract path realising the IR $M(k)$-deal $\langle P^{(1)},P^{(t)}\rangle$. In defining ${\mathcal U}$ it will be convenient to denote $\Delta$ as the path

$$\Delta=\langle Q^{0,k-1},Q^{1,0},Q^{1,1},\ldots,Q^{1,k-1},\ldots,Q^{x,p},\ldots,Q^{r,k-1}\rangle$$

and, since $rk\geq2^s$, we may without loss of generality, focus on the first $2^s$ allocations in this contract path.

Recalling that $\chi(i,j,x,p)$ is the index of the $s$-bit label $\underline{u}$ corresponding to $Q_{i}^{x,p}\cap{\mathcal R}^{\{i,j\}}$ in the relevant Hamiltonian cycle - i.e. ${\mathcal S}^{(v)}$ if ${\mathcal R}^{\{i,j\}}\subseteq Q_{i}^{0,k}$, ${\mathcal S}^{(w)}$ if ${\mathcal R}^{\{i,j\}}\subseteq Q_{j}^{0,k-1}$ - we note the following properties of the sequence of allocations defined by $\Delta$ that hold for each distinct $i$ and $j$.

P1.

$\forall x,p \chi(i,j,x,p)=\chi(j,i,x,p)$

P2.

If $Q^{y,q}$ is the immediate successor of $Q^{x,p}$ in $\Delta$ then $\chi(i,j,y,q)\leq \chi(i,j,x,p)+1$ with equality if and only if $q\not\in\{i,j\}$.

P3.

$\forall i',j'$ with $0\leq i',j'\leq k-1$, $\chi(i,j,x,k-1)=\chi(i',j',x,k-1)$.

The first two properties have already been established in our description of $\Delta$. The third follows from the observation that within each round $Q^{x}$, each cube position is advanced by exactly $k-2$ in progressing from $Q^{x-1,0}$ to $Q^{x,k-1}$.

The utility function $u_i$ is now given, for $S\subseteq{\mathcal R}_m$, by

$$u_i(S)= \left\{ { \begin{array}{ll} \sum_{j\not=i} \chi(i,j,... ... p\leq k-1$}\\ -2^{km}&\mbox{ otherwise} \end{array}} \right.$$

We claim that, with these choices,

$$\Delta=\langle Q^{0,k-1},Q^{1,0},Q^{1,1},\ldots,Q^{1,k-1},\ldots,Q^{x,p},\ldots,Q^{r,k-1}\rangle$$

is the unique IR $M(k-1)$-contract path realising the IR $M(k)$-deal $\langle Q^{0,k-1},Q^{r,k-1}\rangle$. Certainly, $\Delta$ is an IR $M(k-1)$-contract path: each deal $\delta=\langle Q^{x,p},Q^{y,q}\rangle$ on this path has $\vert{\mathcal A}^\delta\vert=k-1$ and since for each agent $A_i$ in ${\mathcal A}^\delta={\mathcal A}\setminus \{A_q\}$ the utility of $Q_{i}^{y,q}$ has increased by exactly $k-2$, i.e. each cube position of $i$ with respect to $j$ whenever $q\not\in\{i,j\}$ has increased, it follows that $\sigma_u(Q^{y,q})>\sigma_u(Q^{x,p})$ and hence $\langle Q^{x,p},Q^{y,q}\rangle$ is IR.

We now show that $\Delta$ is the unique IR $M(k-1)$-contract path continuation of $Q^{0,k-1}$ Suppose $\delta=\langle Q^{x,p},P\rangle$ is a deal that deviates from the contract path $\Delta$ (having followed it through to the allocation $Q^{x,p}$). Certainly both of the following must hold of $P$: for each $i$, $P_i\subseteq\cup_{j\not=i}{\mathcal R}^{\{i,j\}}$; and there is a $k$-tuple of pairs $\langle(x_0,p_0),\ldots,(x_{k-1},p_{k-1})\rangle$ with which $P_i=Q_{i}^{x_{i},p_{i}}$, for if either fail to be the case for some $i$, then $u_i(P_i)=-2^{km}$ with the consequent effect that $\sigma_u(P)<0$ and thence not IR. Now, if $Q^{y,q}$ is the allocation that would succeed $Q^{x,p}$ in $\Delta$ then $P\not=Q^{y,q}$, and thus for at least one agent, $Q_{i}^{{x_i},p_{i}}\not=Q_{i}^{y,q}$. It cannot be the case that $Q_{i}^{{x_i},p_{i}}$ corresponds to an allocation occurring strictly later than $Q_{i}^{y,q}$ in $\Delta$ since such allocations could not be realised by an $M(k-1)$-contract. In addition, since $P_i=Q_{i}^{{x_i},p_{i}}$ it must be the case that $\vert{\mathcal A}^\delta\vert=k-1$ since exactly $k-1$ cube positions in the holding of $A_i$ must change. It follows that there are only two possibilities for $(y_i,p_i)$: $P_i$ reverts to the allocation immediately preceding $Q_{i}^{x,p}$ or advances to the holding $Q_{i}^{y,q}$. It now suffices to observe that a deal in which some agents satisfy the first of these while the remainder proceed in accordance with the second either does not give rise to a valid allocation or cannot be realised by an $M(k-1)$-contract. On the other hand if $P$ corresponds to the allocation preceding $Q^{x,p}$ then $\delta$ is not IR. We deduce, therefore, that the only IR $M(k-1)$ deal that is consistent with $Q^{x,p}$ is that prescribed by $Q^{y,q}$.

This completes the analysis needed for the proof of part (b) of the theorem. It is clear that since the system contains only $k$ agents, any deal $\langle P,Q\rangle$ can be effected with a single $M(k)$-contract, thereby establishing part (a). For part (c) - that the IR deal $\langle P^{(1)},P^{(t)}\rangle$ cannot be realised using an individually rational $M(k-2)$-contract path, it suffices to observe that since the class of IR $M(k-2)$-contracts are a subset of the class of IR $M(k-1)$-contracts, were it the case that an IR $M(k-2)$-contract path existed to implement $\langle P^{(1)},P^{(t)}\rangle$, this would imply that $\Delta$ was not the unique IR $M(k-1)$-contract path. We have, however, proved that $\Delta$ is unique, and part (c) of the theorem follows.$\Box$

We obtain a similar development of Corollary 1 in

Corollary 3   For all $k\geq 3$, $n\geq k$, $m\geq\mbox{{\scriptsize$\left({\begin{array}{c}k\ 2\end{array}}\right)$}}$ and each of the cases below,

a.

$\Phi_k(\delta)$ holds if and only if $\delta$ is a cooperatively rational $M(k)$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.

b.

$\Phi_k(\delta)$ holds if and only if $\delta$ is $\delta$ is an equitable $M(k)$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is is equitable.

there is a resource allocation setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ and a $\Psi$-deal $\delta=\langle P,Q\rangle$ for which

$$\begin{array}{lcclr} L^{{\rm opt}}(\delta,\langle{\mathcal A... ...hi_{k-2})&&\mbox{ {\rm is undefined}}& \mbox{ }&(c) \end{array}$$

Proof. As with the proof of Corollary 1 in relation to Theorem 3, in each case we employ the contract path from the proof of Theorem 6, varying the definition of ${\mathcal U}=\langle u_1,u_2,\ldots,u_k\rangle$ in order to establish each result. Thus let

$$\begin{array}{lcl} \Delta_m&\mbox{ $=$ }&\langle P^{(1)},P^... ...,k-1},Q^{1,0},\ldots,Q^{x,p},\ldots,Q^{z,r}\rangle \end{array}$$

be the $M(k-1)$-contract path realising the $M(k)$-deal $\langle P^{(1)},P^{(t)}\rangle$ described in the proof of Theorem 6, this path having length $t\geq 2^{\mbox{{\scriptsize$\lfloor{2m/k(k-1)}$}}}-1$.

a.

The utility functions ${\mathcal U}=\langle u_0,\ldots,u_{k-1}\rangle$ of Theorem 6 ensure that $\langle P^{(1)},P^{(t)}\rangle$ is cooperatively rational and that $\Delta_m$ is a cooperatively rational $M(k-1)$-contract path realising $\langle P^{(1)},P^{(t)}\rangle$: the utility held by $A_i$ never decreases in value and there is at least one agent (in fact exactly $k-1$) whose utility increases in value. Furthermore $\Delta_m$ is the unique cooperatively rational $M(k-1)$-contract path realising $\langle P^{(1)},P^{(t)}\rangle$ since, by the same argument used in Theorem 6, any deviation will result in some agent suffering a loss of utility.

b.

Set the utility functions ${\mathcal U}=\langle u_0,\ldots,u_{k-1}\rangle$ as,

$$u_i(S)=\left\{ { \begin{array}{lcl} -1&\mbox{ if }&S\not=Q_{... ...ox{$S=Q_{i}^{x,p}$, $p>i$ and $i\not=0$} \end{array}} \right.$$

To see that these choices admit $\Delta_m$ as an equitable $M(k-1)$-contract path realising the equitable deal $\langle Q^{0,k-1},Q^{z,r}\rangle$, we first note that

$$\min_{0\leq i\leq k-1}  \{u_i(Q_{i}^{z,r})\} > 1 = \min_{0\leq i\leq k-1}  \{u_{i}(Q_{i}^{0,k-1})\}$$

thus, $\langle Q^{0,k-1},Q^{z,r}\rangle$ is indeed equitable. Consider any deal $\delta=\langle Q^{x,p},Q^{y,q}\rangle$ occurring within $\Delta_m$. It suffices to show that

$$\min_{0\leq i\leq k-1}  \{u_i(Q_{i}^{x,p})\} \not= u_q(Q_{q}^{x,p})$$

since $A_q\not\in{\mathcal A}^\delta$, and for all other agents $u_i(Q_{i}^{y,q})>u_i(Q_{i}^{x,p})$. We have two possibilities: $q=0$ (in which case $p=k-1$ and $y=x+1$); $q>0$ (in which case $p=q-1$). Consider the first of these: $u_0(Q_{0}^{x,k-1})=xk^2+k$, however,

$$\min\{u_i(Q_{i}^{x,k-1})\}=xk^2+1=u_{k-1}(Q_{k-1}^{x,k-1})$$

and hence every deal $\langle Q^{x,k-1},Q^{x+1,0}\rangle$ forming part of $\Delta_m$ is equitable.

In the remaining case, $u_q(Q_{q}^{x,q-1})=xk^2+1$ and

$$\begin{array}{lcl} \min\{u_i(Q_{i}^{x,q-1})\}&\mbox{ $\leq$\... ...<$ }&xk^2+1\\ &\mbox{ $=$ }&u_{q}(Q_{q}^{x,q-1}) \end{array}$$

and thus the remaining deals $\langle Q^{x,q-1},Q^{x,q}\rangle$ within $\Delta_m$ are equitable. By a similar argument to that employed in Theorem 6 it follows that $\Delta_m$ is the unique equitable $M(k-1)$-contract path realising $\langle Q^{0,k-1},Q^{z,r}\rangle$.

$\Box$