Next: O-contract Paths - Unrestricted Up: Lower Bounds on Path Length Previous: Lower Bounds on Path Length

## Overview

The strategy employed in proving our results involves two parts: for a given class of restricted contract paths we proceed as follows in obtaining lower bounds on .
a.
For the contract-net graph partitioning resources among agents, construct a path, realising a deal . For the structural constraint, influencing it is then proved that:
a1.
The contract path is a -path, i.e. for each , the deal satisfies the structural constraint .
a2.
For any pair of allocations and occurring in , if then the deal is not a -deal.
Thus (a1) ensures that is a suitable contract path, while (a2) will guarantee that there is exactly one allocation, , that can be reached within from any given allocation in by means of a -deal.
b.
Define utility functions with the following properties
b1.
The deal is a -deal.
b2.
For the rationality constraint, influencing , every deal is a -deal.
b3.
For every allocation in the contract path and every allocation other than the deal is not a -deal, i.e. it violates either the stuctural constraint or the rationality constraint .
Thus, (a1) and (b2) ensure that has a defined value with respect to the function for the -deal , i.e. a -path realising the deal is possible. The properties given by (a2) and (b3) indicate that (within the constructed resource allocation setting) the path is the unique -path realising . It follows that , the length of this path, gives a lower bound on the value of and hence a lower bound on .
Before continuing it will be useful to fix some notational details.

We use to denote the -dimensional hypercube. Interpreted as a directed graph, has vertices each of which is identified with a distinct -bit label. Using to denote an arbitrary such label, the edges of are formed by

We identify -bit labels with subsets of , via if and only if . Similarly, any subset of can be described by a binary word, , of length , i.e. with if and only if . For a label we use to denote the number of bits with value , so that is the size of the subset . If and are -bit labels, then is a -bit label, so that if and are disjoint sets, then describes the union of the subset of with the subset of . Finally if is an -bit label then denotes the label formed by changing all values in to and vice versa. In this way, if is the subset of described by then describes the set . To avoid an excess of superscripts we will, where no ambiguity arises, use both to denote the -bit label and the subset of described by it, e.g. we write rather than .

For the contract-net graph induced by -contracts can be viewed as the -dimensional hypercube : the -bit label, associated with a vertex of describing the allocation to . In this way the set of IR -contracts define a subgraph, of with any directed path from to in corresponding to a possible IR -contract path from the allocation to the allocation .

Next: O-contract Paths - Unrestricted Up: Lower Bounds on Path Length Previous: Lower Bounds on Path Length
Paul Dunne 2004-11-26