** 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