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 $\rho^{\max}(n,m,\Phi,\Psi)$.

a.

For the contract-net graph partitioning $m$ resources among $n$ agents, construct a path, $\Delta_m=\langle P^{(1)},P^{(2)},\ldots,P^{(t)}\rangle$ realising a deal $\langle P^{(1)},P^{(t)}\rangle$. For the structural constraint, $\Phi'$ influencing $\Phi$ it is then proved that:

a1.

The contract path $\Delta_m$ is a $\Phi'$-path, i.e. for each $1\leq i < t$, the deal $\langle P^{(i)},P^{(i+1}\rangle$ satisfies the structural constraint $\Phi'$.

a2.

For any pair of allocations $P^{(i)}$ and $P^{(i+j)}$ occurring in $\Delta_m$, if $j\geq 2$ then the deal $\langle P^{(i)},P^{(i+j)}\rangle$ is not a $\Phi'$-deal.

Thus (a1) ensures that $\Delta_m$ is a suitable contract path, while (a2) will guarantee that there is exactly one allocation, $P^{(i+1)}$, that can be reached within $\Delta_m$ from any given allocation $P^{(i)}$ in $\Delta_m$ by means of a $\Phi'$-deal.

b.

Define utility functions ${\mathcal U}_n=\langle u_1,\ldots,u_n\rangle$ with the following properties

b1.

The deal $\langle P^{(1)},P^{(t)}\rangle$ is a $\Psi$-deal.

b2.

For the rationality constraint, $\Phi''$ influencing $\Phi$, every deal $\langle P^{(i)},P^{(i+1)}\rangle$ is a $\Phi''$-deal.

b3.

For every allocation $P^{(i)}$ in the contract path $\Delta$ and every allocation $Q$ other than $P^{(i+1)}$ the deal $\langle P^{(i)},Q\rangle$ is not a $\Phi$-deal, i.e. it violates either the stuctural constraint $\Phi'$ or the rationality constraint $\Phi''$.

Thus, (a1) and (b2) ensure that $\langle P^{(1)},P^{(t)}\rangle$ has a defined value with respect to the function $L^{{\rm opt}}$ for the $\Psi$-deal $\langle P^{(1)},P^{(t)}\rangle$, i.e. a $\Phi$-path realising the deal is possible. The properties given by (a2) and (b3) indicate that (within the constructed resource allocation setting) the path $\Delta_m$ is the unique $\Phi$-path realising $\langle P^{(1)},P^{(t)}\rangle$. It follows that $t-1$, the length of this path, gives a lower bound on the value of $L^{\max}$ and hence a lower bound on $\rho^{\max}(n,m,\Phi,\Psi)$.

Before continuing it will be useful to fix some notational details.

We use ${\mathcal H}_m$ to denote the $m$-dimensional hypercube. Interpreted as a directed graph, ${\mathcal H}_m$ has $2^m$ vertices each of which is identified with a distinct $m$-bit label. Using $\alpha=a_1a_2\ldots a_m$ to denote an arbitrary such label, the edges of ${\mathcal H}_m$ are formed by

$$\{ \langle\alpha,\beta\rangle \mbox{ : $\alpha$ and $\beta$ differ in {\em exactly one} bit position}\}$$

We identify $m$-bit labels $\alpha=a_1a_2\ldots a_m$ with subsets $S^{\alpha}$ of ${\mathcal R}_m$, via $r_i\in S^{\alpha}$ if and only if $a_i=1$. Similarly, any subset $S$ of ${\mathcal R}$ can be described by a binary word, $\beta(S)$, of length $m$, i.e. $\beta(S)=b_1b_2\ldots b_m$ with $b_i=1$ if and only if $r_i\in S$. For a label $\alpha$ we use $\vert\alpha\vert$ to denote the number of bits with value $1$, so that $\vert\alpha\vert$ is the size of the subset $S^{\alpha}$. If $\alpha$ and $\beta$ are $m$-bit labels, then $\alpha\beta$ is a $2m$-bit label, so that if ${\mathcal R}_m$ and ${\mathcal T}_m$ are disjoint sets, then $\alpha\beta$ describes the union of the subset $S^{\alpha}$ of ${\mathcal R}_m$ with the subset $S^{\beta}$ of ${\mathcal T}_m$. Finally if $\alpha=a_1a_2\ldots a_m$ is an $m$-bit label then $\overline{\alpha}$ denotes the label formed by changing all $0$ values in $\alpha$ to $1$ and vice versa. In this way, if $S^{\alpha}$ is the subset of ${\mathcal R}_m$ described by $\alpha$ then $\overline{\alpha}$ describes the set ${\mathcal R}_m\setminus S^{\alpha}$. To avoid an excess of superscripts we will, where no ambiguity arises, use $\alpha$ both to denote the $m$-bit label and the subset of ${\mathcal R}_m$ described by it, e.g. we write $\alpha\subset\beta$ rather than $S^{\alpha}\subset S^{\beta}$.

For $n=2$ the contract-net graph induced by $O$-contracts can be viewed as the $m$-dimensional hypercube ${\mathcal H}_m$: the $m$-bit label, $\alpha$ associated with a vertex of ${\mathcal H}_m$ describing the allocation $\langle\alpha,\overline{\alpha}\rangle$ to $\langle A_1,A_2\rangle$. In this way the set of IR $O$-contracts define a subgraph, ${\mathcal G}_m$ of ${\mathcal H}_m$ with any directed path from $\beta(P)$ to $\beta(Q)$ in ${\mathcal G}_m$ corresponding to a possible IR $O$-contract path from the allocation $\langle P,{\mathcal R}\setminus P\rangle$ to the allocation $\langle Q,{\mathcal R}\setminus Q\rangle$.