Next: Related Work Up: M(k)-contract paths Previous: M(k)-contract paths

## Monotone Utility Functions and -contract paths

The device used to develop Theorem 3 to obtain the path of Theorem 4 can be applied to the rather more intricate construction of Theorem 6, thereby allowing exponential lower bounds on to be derived. We will merely outline the approach rather than present a detailed technical exposition. We recall that it became relatively straightforward to define suitable monotone utility functions once it was ensured that the subset sizes of interest - i.e. those for allocations arising in the -contract path - were forced to fall into a quite restricted range. The main difficulty that arises in applying similar methods to the path of Theorem 6 is the following: in the proof of Theorem 4 we consider two agents so that converting from a setting with resources in Theorem 3 to with resources in Theorem 4 is achieved by combining complementary'' allocations, i.e. with . We can exploit two facts, however, to develop a path for which monotone utility functions could be defined: the resource set in Theorem 6 consists of disjoint sets of size ; and any deal on the path involves a reallocation of between and when . Thus letting be formed by disjoint sets, each of size , suppose that is described by

with the -bit label corresponding to the subset of that is held by in . Consider the sequence of allocations,

in a resource allocation setting have agents and resources - for which is characterised by

In this, , indicates the subset of described by the -bit label,

i.e. selects a subset of while a subset of .

It is immediate from this construction that for each allocation in and each , it is always the case that . It follows, therefore, that the only subsets that are relevant to the definition of monotone utility functions with which an analogous result to Theorem 6 for the path could be derived, are those of size : if has , we can fix as a small enough negative value; similarly if then can be set to a large enough positive value.9

Our description in the preceding paragraphs, can be summarised in the following result, whose proof is omitted: extending the outline given above to a formal lower bound proof, is largely a technical exercise employing much of the analysis already introduced, and since nothing signifcantly new is required for such an analysis we shall not give a detailed presentation of it.

Theorem 7   Let be the predicate which holds whenever is an IR -contract. For all , and , there is a resource allocation setting in which every is monotone, and an IR deal for which,

Next: Related Work Up: M(k)-contract paths Previous: M(k)-contract paths
Paul Dunne 2004-11-26