$O$-contract Paths - Monotone Utility Functions

We conclude our results concerning $O$-contracts by presenting a lower bound on $\rho_{{\rm mono}}^{\max}$, i.e. the length of paths when the utility functions are required to be monotone.

In principle one could attempt to construct appropriate monotone utility functions that would have the desired properties with respect to the path used in Theorem 3. It is, however, far from clear whether such a construction is possible. We do not attempt to resolve this question here. Whether an exact translation could be accomplished is, ultimately, a question of purely combinatorial interest: since our aim is to demonstrate that exponential length contract paths are needed with monotone utility functions we are not, primarily, concerned with obtaining an optimal bound.

Theorem 4   With $\Phi(P,Q)$ and $\Psi(P,Q)$ be defined as in Theorem 3 and $m\geq 14$

$$\rho^{\max}_{{\rm mono}}(2,m,\Phi,\Psi) \geq \left\{ { \be... ...-1)/2}-3&\mbox{ if }&\mbox{$m$ is odd} \end{array}} \right.$$

Proof. We describe the details only for the case of $m$ being even: the result when $m$ is odd is obtained by a simple modification which we shall merely provide in outline.

Let $m=2s$ with $s\geq 7$. For any path

$$\Delta_s=\langle\alpha_1,\alpha_2,\ldots,\alpha_t\rangle$$

in ${\mathcal H}_s$ (where $\alpha_i$ describes a subset of ${\mathcal R}_s$ by an $s$-bit label), the path $double(\Delta_s)$ in ${\mathcal H}_{2s}$ is defined by

$$\begin{array}{lcl} double(\Delta_s)&=&\langle \alpha_1\ov... ...eta_{2i-1},\beta_{2i+1},\ldots,\beta_{2t-1}\rangle \end{array}$$

(The reason for successive indices of $\beta$ increasing by $2$ will become clear subsequently)

Of course, $double(\Delta_s)$ does not describe an $O$-contract path⁶: it is, however, not difficult to interpolate appropriate allocations, $\beta_{2i}$, in order to convert it to such a path. Consider the subsets $\beta_{2i}$ (with $1\leq i < t$) defined as follows:

$$\beta_{2i}= \left\{ { \begin{array}{lcl} \alpha_{i+1}\over... ...}&\mbox{ if }&\alpha_i\supset\alpha_{i+1} \end{array}} \right.$$

If we now consider the path, $ext(\Delta_s)$, within ${\mathcal H}_{2s}$ given by

$$ext(\Delta_s)= \langle\beta_1,\beta_2,\beta_3,\ldots,\beta_{2(t-1)},\beta_{2t-1}\rangle$$

then this satisfies,

a.

If $\Delta_s$ has property (SC) of Theorem 3 in ${\mathcal H}_s$ then $ext(\Delta_s)$ has property (SC) in ${\mathcal H}_{2s}$.

b.

If $j$ is odd then $\vert\beta_j\vert=s$.

c.

If $j$ is even then $\vert\beta_j\vert=s+1$.

From (a) and the bounds proved in [Abbott Katchalski, 1991] we deduce that $ext(\Delta_s)$ can be chosen so that with $P^{(i)}$ denoting the allocation $\langle\beta_i,\overline{\beta_i}\rangle$

d.

$ext(\Delta_s)$ describes an $O$-contract path from $P^{(1)}$ to $P^{(2t-1)}$.

e.

For each pair $\langle i,j\rangle$ with $j\geq i+2$, the deal $\langle P^{(i)},P^{(j)}\rangle$ is not an $O$-contract.

f.

If $\Delta_s$ is chosen as in the proof of Theorem 3 then the number of deals in $ext(\Delta_s)$ is as given in the statement of the present theorem.

We therefore fix $\Delta_s$ as the path from Theorem 3 so that in order to complete the proof we need to construct utility functions $\langle u_1,u_2\rangle$ that are monotone and with which $ext(\Delta_s)$ defines the unique IR $O$-contract path realising the reallocation $\langle P^{(1)},P^{(2t-1)}\rangle$.

The choice for $u_2$ is relatively simple. Given $S\subseteq{\mathcal R}_{2s}$,

$$u_2(S)= \left\{ { \begin{array}{lcl} 0&\mbox{ if }&\vert S... ...-1\\ 2t+2&\mbox{ if }&\vert S\vert\geq s \end{array}} \right.$$

In this $t$ is the number of allocations in $\Delta_s$. The behaviour of $u_2$ is clearly monotone.

The construction for $u_1$ is rather more complicated. Its main idea is to make use of the fact that the size of each set $\beta_i$ occurring in $ext(\Delta_s)$ is very tightly constrained: $\vert\beta_i\vert$ is either $s$ or $s+1$ according to whether $i$ is odd or even. We first demonstrate that each set of size $s+1$ can have at most two strict subsets (of size $s$) occurring within $ext(\Delta_s)$: thus, every $S$ of size $s+1$ has exactly $2$ or $1$ or $0$ subsets of size $s$ on $ext(\Delta_s)$. To see this suppose the contrary. Let $\gamma$, $\beta_{2i-1}$, $\beta_{2j-1}$, and $\beta_{2k-1}$ be such that $\vert\gamma\vert=s+1$ with

$$\beta_{2i-1}\subset\gamma;\beta_{2j-1}\subset\gamma;\beta_{2k-1}\subset\gamma$$

Noting that $\beta_{2i-1}=\alpha_i\overline{\alpha_i}$ and that $\Delta_s$ has the property (SC) it must be the case that (at least) two of the $s$-bit labels from $\{\alpha_i,\alpha_j,\alpha_k\}$ differ in at least two positions. Without loss of generality suppose this is true of $\alpha_i$ and $\alpha_k$. As a result we deduce that the sets $\beta_{2i-1}$ and $\beta_{2k-1}$ have at most $s-2$ elements in common, i.e. $\vert\beta_{2i-1}\cap\beta_{2k-1}\vert\leq s-2$: $\beta_{2i-1}=\alpha_i\overline{\alpha_i}$ and $\beta_{2k-1}=\alpha_k\overline{\alpha_k}$ so in any position at which $\alpha_i$ differs from $\alpha_k$, $\overline{\alpha_i}$ differs from $\overline{\alpha_k}$ at exactly the same position. In total $\vert\beta_{2i-1}\setminus\beta_{2k-1}\vert\geq2$, i.e. there are (at least) two elements of $\beta_{2i-1}$ that do not occur in $\beta_{2k-1}$; and in the same way $\vert\beta_{2k-1}\setminus\beta_{2i-1}\vert\geq2$, i.e. there are (at least) two elements of $\beta_{2k-1}$ that do not occur in $\beta_{2i-1}$. The set $\gamma$, however, has only $s+1$ members and so cannot have both $\beta_{2i-1}$ and $\beta_{2k-1}$ as subsets: this would require

$$\beta_{2i-1}\cap\beta_{2k-1}\cup\beta_{2i-1}\setminus\beta_{2k-1}\cup \beta_{2k-1}\setminus\beta_{2i-1}\subseteq\gamma$$

but, as we have just seen,

$$\vert\beta_{2i-1}\cap\beta_{2k-1}\cup\beta_{2i-1}\setminu... ...2k-1}\cup \beta_{2k-1}\setminus\beta_{2i-1}\vert\geqs+2$$

One immediate consequence of the argument just given is that for any set $\gamma$ of size $s+1$ there are exactly two strict subsets of $\gamma$ occurring on $ext(\Delta_s)$ if and only if $\gamma=\beta_{2i-1}\cup\beta_{2i+1}=\beta_{2i}$ for some value of $i$ with $1\leq i < t$. We can now characterise each subset of ${\mathcal R}_{2s}$ of size $s+1$ as falling into one of three categories.

C1.

Good sets, given by $\{\gamma:\gamma=\beta_{2i}\}$.

C2.

Digressions, consisting of

$$\{\gamma:\beta_{2i-1}\subset\gamma\mbox{, }\gamma\not=\beta_{2i}\mbox{ and }i<t\}$$

C3.

Inaccessible sets, consisting of

$$\{\gamma:\mbox{$\gamma$ is neither $Good$ nor a $Digression$}\}$$

$Good$ sets are those describing allocations to $A_1$ within the path defined by $ext(\Delta_s)$; $Digressions$ are the allocations that could be reached using an $O$-contract from a set of size $s$ on $ext(\Delta_s)$, i.e. $\beta_{2i-1}$, but differ from the set that actually occurs in $ext(\Delta_s)$, i.e. $\beta_{2i}$. Finally, $Inaccessible$ sets are those that do not occur on $ext(\Delta_s)$ and cannot be reached via an $O$-contract from any set on $ext(\Delta_s)$. We note that we view any set of size $s+1$ that could be reached by an $O$-contract from $\beta_{2t-1}$ as being inaccessible: in principle it is possible to extend the $O$-contract path beyond $\beta_{2t-1}$, however, we choose not complicate the construction in this way.

We now define $u_1$ as

$$u_1(\gamma)= \left\{ { \begin{array}{lcl} 2i-1&\mbox{ if }... ...cessible$ or $\vert\gamma\vert\geq s+2$} \end{array}} \right.$$

It remains only to prove for these choices of $\langle u_1,u_2\rangle$ that the $O$-contract path $\langle P^{(1)},\ldots,P^{(2t-1)}\rangle$ defined from $ext(\Delta_s)$ is the unique IR $O$-contract path realising the IR deal $\langle P^{(1)},P^{(2t-1)}\rangle$ and that $u_1$ is monotone.

To show that $\langle P^{(1)},\ldots,P^{(2t-1)}\rangle$ is IR we need to demonstrate

$$\forall1\leq j < 2t-1u_1(\beta_j)+u_2(\overline{\beta_j})< u_1(\beta_{j+1})+u_2(\overline{\beta_{j+1}})$$

We have via the definition of $\langle u_1,u_2\rangle$

$$\begin{array}{lcl} u_1(\beta_{2i-1})+u_2(\overline{\beta_{2i... ...i+1})+u_2(\overline{\beta_{2i+1}})\\ &=&2(t+i)+3 \end{array}$$

Thus, via Definition 4, it follows that $ext(\Delta_s)$ gives rise to an IR $O$-contract path.

To see that this path is the unique IR $O$-contract path implementing $\langle P^{(1)},P^{(2t-1)}\rangle$, consider any position $P^{(j)}=\langle\beta_j,\overline{\beta_j}\rangle$ and allocation $Q$ other than $P^{(j+1)}$ or $P^{(j-1)}$. It may be assumed that the deal $\langle P^{(j)},Q\rangle$ is an $O$-contract. If $j=2i-1$ then $\sigma_u(P^{(2i-1)})=2(t+i)+1$ and $\vert\beta_j\vert=s$. Hence $\vert Q_1\vert\in\{s-1,s+1\}$. In the former case, $u_1(Q_1)=0$ and $u_2(Q_2)=2t+2$ from which $\sigma_u(Q)=2t+2$ and thus $\langle P^{(j)},Q\rangle$ is not IR. In the latter case $u_1(Q_1)=2i$ since $Q_1$ is a $Digression$ from $\beta_{2i-1}$ and $u_2(Q_2)=2t+1$ giving $\sigma_u(Q)=2(t+i)+1$. Again $\langle P^{(j)},Q\rangle$ fails to be IR since $Q$ fails to give any increase in the value of $\sigma_u$. We are left with the case $j=2i$ so that $\sigma_u(P^{(2i)})=2(t+i)+2$ and $\vert\beta_j\vert=s+1$. Since $\langle P^{(j)},Q\rangle$ is assumed to be an $O$-contract this gives $\vert Q_1\vert\in\{s,s+2\}$. For the first possibility $Q_1$ could not be a set on $ext(\Delta_s)$: $\beta_{2i-1}$ and $\beta_{2i+1}$ are both subsets of $\beta_{2i}$ and there can be at most two such subsets occurring on $ext(\Delta_s)$. It follows, therefore, that $u_1(Q_1)=0$ giving $\sigma_u(Q)=2t+2$ so that $\langle P^{(j)},Q\rangle$ is not IR. In the second possibility, $u_1(Q_1)=2t-1$ but $u_2(Q_2)=0$ as $\vert Q_2\vert=s-2$ so the deal would result in an overall loss. We deduce that for each $P^{(j)}$ the only IR $O$-contract consistent with it is the deal $\langle P^{(j)},P^{(j+1)}\rangle$.

The final stage is to prove that the utility function $u_1$ is indeed a monotone function. Suppose $S$ and $T$ are subsets of ${\mathcal R}_{2s}$ with $S\subset T$. We need to show that $u_1(S)\leq u_1(T)$. We may assume that $\vert S\vert= s$, that $S$ occurs as some set within $ext(\Delta_s)$, and that $\vert T\vert=s+1$. If $\vert S\vert<s$ or $\vert S\vert= s$ but does not occur on $ext(\Delta_s)$ we have $u_1(S)=0$ and the required inequality holds; if $\vert S\vert\geq s+1$ then in order for $S\subset T$ to be possible we would need $\vert T\vert\geq s+2$, which would give $u_1(T)=2t-1$ and this is the maximum value that any subset is assigned by $u_1$. We are left with only $\vert S\vert= s$, $\vert T\vert=s+1$ and $S$ on $ext(\Delta_s)$ to consider. It has already been shown that there are at most two subsets of $T$ that can occur on $ext(\Delta_s)$. Consider the different possibilities:

a.

$T=\beta_{2i}$ so that exactly two subsets of $T$ occur in $ext(\Delta_s)$: $\beta_{2i-1}$ and $\beta_{2i+1}$. Since $u_1(\beta_{2i})=2i+1$ and this is at least $\max\{u_1(\beta_{2i-1}),u_1(\beta_{2i+1})\}$, should $S$ be either of $\beta_{2i-1}$ or $\beta_{2i+1}$ then $u_1(S)\leq u_1(T)$ as required.

b.

$T$ is a $Digression$ from $S=\beta_{2i-1}$, so that $u_1(T)=2i$ and $u_1(S)=2i-1$ and, again, $u_1(S)\leq u_1(T)$.

We deduce that $u_1$ is monotone completing our lower bound proof for $\rho^{\max}_{{\rm mono}}$ for even values of $m$.

We conclude by observing that a similar construction can be used if $m=2s+1$ is odd: use the path $ext(\Delta_s)$ described above but modifying it so that one resource ($r_m$) is always held by $A_2$. Only minor modifications to the utility function definitions are needed.$\Box$

Example 2   For $s=3$, we can choose $\Delta_3=\langle 000,001,101,111,110\rangle$ so that $t=5$. This gives $double(\Delta_3)$ as

$$\langle 000111,001110,101010,111000,110001\rangle$$

with the $O$-contract path being defined from $ext(\Delta_3)$ which is

$$\begin{array}{cl} &\langle 000111,001111,001110,101110,10101... ...a_4,\beta_5,\beta_6,\beta_7,\beta_8,\beta_9\rangle \end{array}$$

Considering the 15 subsets of size $s+1=4$, gives

$$\begin{array}{lcl} Good&\mbox{ $=$ }&\{001111,101110,1110... ...=$ }&\{011011,011101,101101,110110,110011,110101\} \end{array}$$

Notice that both of the sets in $\{110011,110101\}$ are $Inaccessible$: in principle we could continue from $\beta_9=110001$ using either, however, in order to simplify the construction the path is halted at $\beta_9$.

Following the construction presented in Theorem 4, gives the following utility function definitions with $S\subseteq{\mathcal R}=\{r_1,r_2,r_3,r_4,r_5,r_6\}$.

$$u_2(S)=\left\{ { \begin{array}{lcl} 0&\mbox{ {\rm if }}&... ... 12&\mbox{ {\rm if }}&\vert S\vert\geq 3 \end{array}} \right.$$

For $u_1$ we obtain

$$u_1(S)= \left\{ { \begin{array}{lcl} 0&\mbox{ {\rm if} }&\... ...1011,011101,101101,110110,110011,110101\} \end{array}} \right.$$

The monotone utility functions, $\langle u_1,u_2\rangle$, employed in proving Theorem 4 are defined so that the path arising from $ext(\Delta_s)$ is IR: in the event of either agent suffering a loss of utility the gain made by the other is sufficient to provide a compensatory payment. A natural question that now arises is whether the bound obtained in Theorem 4 can be shown to apply when the rationality conditions preclude any monetary payment, e.g. for cases where the concept of rationality is one of those given in Definition 7. Our next result shows that if we set the rationality condition to enforce cooperatively rational or equitable deals then the bound of Theorem 4 still holds.

Theorem 5   For each of the cases below and $m\geq 14$

a.

$\Phi(\delta)$ holds if and only if $\delta$ is a cooperatively rational $O$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.

b.

$\Phi(\delta)$ holds if and only if $\delta$ is an equitable $O$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is equitable.

$$\rho^{\max}_{{\rm mono}}(2,m,\Phi,\Psi) \geq \left\{ { \be... ...-1)/2}-3&\mbox{ if }&\mbox{$m$ is odd} \end{array}} \right.$$

Proof. We again illustrate the constructions only for the case of $m$ being even, noting the modification to deal with odd values of $m$ outlined at the end of the proof of Theorem 4. The path $ext(\Delta_s)$ is used for both cases.

For (a), we require $\langle u_1,u_2\rangle$ to be defined as monotone functions with which $ext(\Delta_{s})$ will be the unique cooperatively rational $O$-contract path to realise the cooperatively rational deal $\langle P^{(1)},P^{(2t-1)}\rangle$ where $P^{(j)}=\langle\beta_j,\overline{\beta_j}\rangle$. In this case we set $\langle u_1,u_2\rangle$ to be,

$$\langle u_1(\gamma),u_2(\overline{\gamma})\rangle= \left\... ...cessible$ or $\vert\gamma\vert\geq s+2$} \end{array}} \right.$$

Since,

$$\begin{array}{lcl} \langle u_1(\beta_{2i-1}),u_2(\overline{\... ...+1}})\rangle &\mbox{ $=$ }&\langle i+1,i+1\rangle \end{array}$$

it is certainly the case that $\langle P^{(1)},P^{(2t-1)}\rangle$ and all deals on the $O$-contract path defined by $ext(\Delta_s)$ are cooperatively rational. Furthermore if $Q=\langle\gamma,{\overline{\gamma}}\rangle$ is any allocation other than $P^{(j+1)}$ then the deal $\langle P^{(j)},Q\rangle$ will fail to be a cooperatively rational $O$-contract. For suppose the contrary letting $\langle P^{(j)},Q\rangle$ without loss of generality be an $O$-contract, with $Q\not\in\{P^{(j-1)},P^{(j+1)}\}$ - we can rule out the former case since we have already shown such an deal is not cooperatively rational. If $j=2i-1$ so that $\langle u_1(\beta_j),u_2(\overline{\beta_j})\rangle =\langle i,i\rangle$ then $\vert\gamma\vert\in\{s-1,s+1\}$: the former case leads to a loss in utility for $A_1$; the latter, (since $\gamma$ is a $Digression$ from $\beta_{2i-1}$) a loss in utility for $A_2$. Similarly, if $j=2i$ so that $\langle u_1(\beta_j),u_2(\overline{\beta_j})\rangle =\langle i+1,i\rangle$ then $\vert\gamma\vert\in\{s,s+2\}$: for the first $\gamma\not\in ext(\Delta_s)$ leading to a loss of utility for $A_1$; the second results in a loss of utility for $A_2$. It follows that the path defined by $ext(\Delta_s)$ is the unique cooperatively rational $O$-contract path that realises $\langle P^{(1)},P^{(2t-1)}\rangle$.

It remains only to show that these choices for $\langle u_1,u_2\rangle$ define monotone utility functions.

Consider $u_1$ and suppose $S$ and $T$ are subsets of ${\mathcal R}_{2s}$ with $S\subset T$. If $\vert S\vert\leq s-1$, or $S$ does not occur on $ext(\Delta_s)$ then $u_1(S)=0$. If $\vert T\vert\geq s+2$ or is $Inaccessible$ then $u_1(T)=2t-1$ which is the maximum value attainable by $u_1$. So we may assume that $\vert S\vert= s$, occurs on $ext(\Delta_s)$, i.e. $S=\beta_{2i-1},$ for some $i$, and that $\vert T\vert=s+1$ and is either a $Good$ set or a $Digression$. From the definition of $u_1$, $u_1(S)=i$: if $T\in\{\beta_{2i},\beta_{2i-2}\}$ then $u_1(T)\geq i = u_1(S)$; if $T$ is a $Digression$ from $\beta_{2i-1}$ then $u_1(T)=i=u_1(S)$. We deduce that if $S\subseteq T$ then $u_1(S)\leq u_1(T)$, i.e. the utility function is monotone.

Now consider $u_2$ with $S$ and $T$ subsets of ${\mathcal R}_{2s}$ having $S\subset T$. If $\vert T\vert\geq s+1$ or ${\mathcal R}_{2s}\setminus T$ does not occur in $ext(\Delta_s)$ then $u_2(T)=2t-1$ its maximal value. If $\vert S\vert\leq s-2$ or ${\mathcal R}_{2s}\setminus S$ is $Inaccessible$ then $u_2(S)=0$. Thus we may assume that $T=\overline{\beta_{2i-1}}$ giving $u_2(T)=i$ and $\vert S\vert=s-1$, so that ${\mathcal R}_{2s}\setminus S$ is either a $Digression$ or one of the $Good$ sets $\{\beta_{2i},\beta_{2i-2}\}$. If ${\mathcal R}_{2s}\setminus S$ is a $Digression$ then $u_2(S)=i-1$; if it is the $Good$ set $\beta_{2i-2}$ then $u_2(S)=i-1<u_2(T)$; if it is the $Good$ set $\beta_{2i}$ then $u_2(S)=i=u_2(T)$. It follows that $u_2$ is monotone completing the proof of part (a).

For (b) we use,

$$\begin{array}{lcl} \langle u_1(\gamma),u_2(\overline{\gamma}... ...or $\vert\gamma\vert\geq s+2$} \end{array}} \right. \end{array}$$

These choices give $ext(\Delta_s)$ as the unique equitable $O$-contract path to realise the equitable deal $\langle P^{(1)},P^{(2t-1)}\rangle$, since

$$\begin{array}{lcl} \min\{u_1(\beta_{2i-1}),u_2(\overline{\be... ...),u_2(\overline{\beta_{2i+1}})\}&\mbox{ $=$ }&2i+1 \end{array}$$

each deal $\langle P^{(j)},P^{(j+1)}\rangle$ is equitable. If $Q=\langle\gamma,\overline{\gamma}\rangle$ is any allocation other than $P^{(j+1)}$ then the deal $\langle P^{(j)},Q\rangle$ is not an equitable $O$-contract. Assume that $\langle P^{(j)},Q\rangle$ is an $O$-contract, and that $Q\not\in\{P^{(j-1)},P^{(j+1)}\}$. If $j=2i-1$, so that $P^{(j)}=\langle\beta_{2i-1},\overline{\beta_{2i-1}}\rangle$ and $\min\{u_1(\beta_{2i-1}),u_2(\overline{\beta_{2i-1}})\}=2i-1$ then $\vert\gamma\vert\in\{s-1,s+1\}$. In the first of these $\min\{u_1(\gamma),u_2(\overline{\gamma})\}=0$; in the second $\min\{u_1(\gamma),u_2(\overline{\gamma})\}=2i-1$ since $\gamma$ must be a $Digression$. This leaves only $j=2i$ with $P^{(j)}=\langle\beta_{2i},\overline{\beta_{2i}}\rangle$ and $\min\{u_1(\beta_{2i}),u_2(\overline{\beta_{2i}})\}=2i$. For this, $\vert\gamma\vert\in\{s,s+2\}$: if $\vert\gamma\vert=s$ then $\min\{u_1(\gamma),u_2(\overline{\gamma})\}\leq 2i-1$ (with equality when $\gamma=\beta_{2i-1}$); if $\vert\gamma\vert=s+2$ then $\min\{u_1(\gamma),u_2(\overline{\gamma})\}=0$. In total these establish that $ext(\Delta_s)$ is the unique equitable $O$-contract path realising the equitable deal $\langle P^{(1)},P^{(2t-1)}\rangle$.

That the choices for $\langle u_1,u_2\rangle$ describe monotone utility functions can be shown by a similar argument to that of part (a).$\Box$

Example 3   For $s=3$ and using the same $O$-contract path $ext(\Delta_3)$ as the previous example, i.e.

$$\begin{array}{cl} &\langle 000111,001111,001110,101110,10101... ...a_4,\beta_5,\beta_6,\beta_7,\beta_8,\beta_9\rangle \end{array}$$

For $\langle u_1,u_2\rangle$ in (a) we obtain

$$\langle u_1(S),u_2({\mathcal R}\setminus S)\rangle= \left... ...1011,011101,101101,110110,110011,110101\} \end{array}} \right.$$

Similarly, in (b)

$$\langle u_1(S),u_2({\mathcal R}\setminus S)\rangle= \left... ...1011,011101,101101,110110,110011,110101\} \end{array}} \right.$$

That we can demonstrate similar extremal behaviours for contract path length with rationality constraints in both money-based (individual rationality) and money-free (cooperative rationality, equitable) settings irrespective of whether monotonicity properties are assumed, has some interesting parallels with other contexts in which monotonicity is relevant. In particular we can observe that in common with the complexity results already noted from dunne:2003 - deciding if an allocation is Pareto optimal, if an allocation maximises $\sigma_u$, or if an IR $O$-contract path exists - requiring utility functions to be monotone does not result in a setting which is computationally more tractable.