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.

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

Let with . For any path

in (where describes a subset of by an -bit label), the path in is defined by

(The reason for successive indices of increasing by will become clear subsequently)

Of course,
does not describe an -contract path^{6}: it is, however, not difficult to interpolate appropriate allocations, , in
order to convert it to such a path. Consider the subsets (with ) defined
as follows:

If we now consider the path, , within given by

then this satisfies,

- a.
- If has property (SC) of Theorem 3 in then has property (SC) in .
- b.
- If is odd then .
- c.
- If is even then .

- d.
- describes an -contract path from to .
- e.
- For each pair
with , the deal
is
*not*an -contract. - f.
- If is chosen as in the proof of Theorem 3 then the number of deals in is as given in the statement of the present theorem.

The choice for is relatively simple. Given
,

In this is the number of allocations in . The behaviour of is clearly monotone.

The construction for is rather more complicated. Its main idea is to make use of the fact
that the size of each set occurring in is very tightly
constrained: is either or according to whether is odd or even.
We first demonstrate that
each set of size can have at most two strict subsets (of size ) occurring within :
thus, every of size has exactly or or subsets of size on .
To see this suppose the contrary.
Let , , , and be such that with

Noting that and that has the property (SC) it must be the case that (at least) two of the -bit labels from differ in at least two positions. Without loss of generality suppose this is true of and . As a result we deduce that the sets and have at most elements in common, i.e. : and so in any position at which differs from , differs from at exactly the same position. In total , i.e. there are (at least) two elements of that do not occur in ; and in the same way , i.e. there are (at least) two elements of that do not occur in . The set , however, has only members and so cannot have

but, as we have just seen,

One immediate consequence of the argument just given is that for any set of size there are exactly two strict subsets of occurring on if and only if for some value of with . We can now characterise each subset of of size as falling into one of three categories.

- C1.
*Good*sets, given by .- C2.
*Digressions*, consisting of

- C3.
*Inaccessible*sets, consisting of

We now define as

It remains only to prove for these choices of that the -contract path defined from is the unique IR -contract path realising the IR deal and that is monotone.

To show that
is IR we need to demonstrate

We have via the definition of

Thus, via Definition 4, it follows that gives rise to an IR -contract path.

To see that this path is the unique IR -contract path implementing , consider any position and allocation other than or . It may be assumed that the deal is an -contract. If then and . Hence . In the former case, and from which and thus is not IR. In the latter case since is a from and giving . Again fails to be IR since fails to give any increase in the value of . We are left with the case so that and . Since is assumed to be an -contract this gives . For the first possibility could not be a set on : and are both subsets of and there can be at most two such subsets occurring on . It follows, therefore, that giving so that is not IR. In the second possibility, but as so the deal would result in an overall loss. We deduce that for each the only IR -contract consistent with it is the deal .

The final stage is to prove that the utility function is indeed a *monotone*
function. Suppose and are subsets of
with . We need to show
that
. We may assume that , that occurs as some
set within , and that . If or but does not occur on we
have and the required inequality holds; if then in order for
to be possible we would need , which would give
and this is the maximum value that any subset is assigned by . We are left with
only , and on to consider.
It has already been shown that there are at most two subsets of that can occur on .
Consider the different possibilities:

- a.
- so that exactly two subsets of occur in : and . Since and this is at least , should be either of or then as required.
- b.
- is a from , so that and and, again, .

We conclude by observing that a similar construction can be used if is odd: use the path described above but modifying it so that one resource () is always held by . Only minor modifications to the utility function definitions are needed.

with the -contract path being defined from which is

Considering the 15 subsets of size , gives

Notice that both of the sets in are : in principle we could continue from using either, however, in order to simplify the construction the path is halted at .

Following the construction presented in Theorem 4, gives the following
utility function definitions with
.

For we obtain

- a.
- holds if and only if is a cooperatively rational -contract.

holds if and only if is cooperatively rational. - b.
- holds if and only if is an equitable -contract.

holds if and only if is equitable.

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

For (a), we require
to be defined as monotone functions with which
will be the unique cooperatively rational -contract path to realise the cooperatively rational deal
where
. In this
case we set
to be,

Since,

it is certainly the case that and all deals on the -contract path defined by are cooperatively rational. Furthermore if is any allocation other than then the deal will fail to be a cooperatively rational -contract. For suppose the contrary letting without loss of generality be an -contract, with - we can rule out the former case since we have already shown such an deal is not cooperatively rational. If so that then : the former case leads to a loss in utility for ; the latter, (since is a from ) a loss in utility for . Similarly, if so that then : for the first leading to a loss of utility for ; the second results in a loss of utility for . It follows that the path defined by is the unique cooperatively rational -contract path that realises .

It remains only to show that these choices for define monotone utility functions.

Consider and suppose and are subsets of with . If , or does not occur on then . If or is then which is the maximum value attainable by . So we may assume that , occurs on , i.e. for some , and that and is either a set or a . From the definition of , : if then ; if is a from then . We deduce that if then , i.e. the utility function is monotone.

Now consider with and subsets of having . If or does not occur in then its maximal value. If or is then . Thus we may assume that giving and , so that is either a or one of the sets . If is a then ; if it is the set then ; if it is the set then . It follows that is monotone completing the proof of part (a).

For (b) we use,

These choices give as the unique equitable -contract path to realise the equitable deal , since

each deal is equitable. If is any allocation other than then the deal is not an equitable -contract. Assume that is an -contract, and that . If , so that and then . In the first of these ; in the second since must be a . This leaves only with and . For this, : if then (with equality when ); if then . In total these establish that is the unique equitable -contract path realising the equitable deal .

That the choices for describe monotone utility functions can be shown by a similar argument to that of part (a).

For in (a) we obtain

Similarly, in (b)

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 , or if an IR -contract path exists - requiring utility functions to be monotone does not result in a setting which is computationally more tractable.