Next: M(k)-contract paths Up: Lower Bounds on Path Length Previous: O-contract Paths - Unrestricted

## -contract Paths - Monotone Utility Functions

We conclude our results concerning -contracts by presenting a lower bound on , 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 and be defined as in Theorem 3 and

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 path6: 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 .
From (a) and the bounds proved in [Abbott & Katchalski, 1991] we deduce that can be chosen so that with denoting the allocation
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.
We therefore fix as the path from Theorem 3 so that in order to complete the proof we need to construct utility functions that are monotone and with which defines the unique IR -contract path realising the reallocation .

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 both and as subsets: this would require

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

sets are those describing allocations to within the path defined by ; are the allocations that could be reached using an -contract from a set of size on , i.e. , but differ from the set that actually occurs in , i.e. . Finally, sets are those that do not occur on and cannot be reached via an -contract from any set on . We note that we view any set of size that could be reached by an -contract from as being inaccessible: in principle it is possible to extend the -contract path beyond , however, we choose not complicate the construction in this way.

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 deduce that is monotone completing our lower bound proof for for even values of .

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.

Example 2   For , we can choose so that . This gives as

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

The monotone utility functions, , employed in proving Theorem 4 are defined so that the path arising from 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
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).

Example 3   For and using the same -contract path as the previous example, i.e.

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.

Next: M(k)-contract paths Up: Lower Bounds on Path Length Previous: O-contract Paths - Unrestricted
Paul Dunne 2004-11-26