Preliminary Definitions

To begin, we first formalise the concepts of deal and contract path.

Definition 2   Let $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ be a resource allocation setting. A deal is a pair $\langle P,Q\rangle$ where $P=\langle P_1,\ldots,P_n\rangle$ and $Q=\langle Q_1,\ldots,Q_n\rangle$ are distinct partitions of ${\mathcal R}$. The effect of implementing the deal $\langle P,Q\rangle$ is that the allocation of resources specified by $P$ is replaced with that specified by $Q$. Following the notation of [Endriss & Maudet, 2004b] for a deal $\delta=\langle P,Q\rangle$, we use ${\mathcal A}^\delta$ to indicate the subset of ${\mathcal A}$ involved, i.e. $A_k\in{\mathcal A}^\delta$ if and only if $P_k\not=Q_k$.

Let $\delta=\langle P,Q\rangle$ be a deal. A contract path realising $\delta$ is a sequence of allocations

$$\Delta=\langle P^{(1)}, P^{(2)} ,\ldots, P^{(t-1)}, P^{(t)}\rangle$$

in which $P=P^{(1)}$ and $P^{(t)}=Q$. The length of $\Delta$, denoted $\vert\Delta\vert$ is $t-1$, i.e. the number of deals in $\Delta$.

There are two methods which we can use to reduce the number of deals that a single agent may have to consider in seeking to move from some allocation to another, thereby avoiding the need to choose from exponentially many alternatives: structural and rationality constraints. Structural constraints limit the permitted deals to those which bound the number of resources and/or the number of agents involved, but take no consideration of the view any agent may have as to whether its allocation has improved. In contrast, rationality constraints restrict deals $\langle P,Q\rangle$ to those in which $Q$ ``improves'' upon $P$ according to particular criteria. In this article we consider two classes of structural constraint: $O$-contracts, defined and considered in [Sandholm, 1998], and what we shall refer to as $M(k)$-contracts.

Definition 3   Let $\delta=\langle P,Q\rangle$ be a deal involving a reallocation of ${\mathcal R}$ among ${\mathcal A}$.

a.

$\delta$ is a one contract ($O$-contract) if

O1.

${\mathcal A}^\delta=\{i,j\}$.

O2.

There is a unique resource $r\in P_i\cup P_j$ for which $Q_i = P_i\cup \{r\}$ and $Q_j=P_j\setminus\{r\}$ (with $r\in P_j$) or $Q_j = P_j\cup \{r\}$ and $Q_i=P_i\setminus\{r\}$ (with $r\in P_i$)

b.

For a value $k\geq2$, the deal $\delta=\langle P,Q\rangle$ is an $M(k)$-contract if $2\leq\vert{\mathcal A}^\delta\vert\leq k$ and $\cup_{i\in{\mathcal A}^\delta} Q_i = \cup_{i\in{\mathcal A}^\delta} P_i$.

Thus, $O$-contracts involve the transfer of exactly one resource from a particular agent to another, resulting in the number of deals compatible with any given allocation being exactly $(n-1)m$: each of the $m$ resources can be reassigned from its current owner to any of the other $n-1$ agents.

Rationality constraints arise in a number of different ways. For example, from the standpoint of an individual agent $A_i$ a given deal $\langle P,Q\rangle$ may have three different outcomes: $u_i(P_i)<u_i(Q_i)$, i.e. $A_i$ values the allocation $Q_i$ as superior to $P_i$; $u_i(P_i)=u_i(Q_i)$, i.e. $A_i$ is indifferent between $P_i$ and $Q_i$; and $u_i(P_i)>u_i(Q_i)$, i.e. $A_i$ is worse off after the deal. When global optima such as utilitarian social welfare are to be maximised, there is the question of what incentive there is for any agent to accept a deal $\langle P,Q\rangle$ under which it is left with a less valuable resource holding. The standard approach to this latter question is to introduce the notion of a pay-off function, i.e. in order for $A_i$ to accept a deal under which it suffers a reduction in utility, $A_i$ receives some payment sufficient to compensate for its loss. Of course such compensation must be made by other agents in the system who in providing it do not wish to pay in excess of any gain. In defining notions of pay-off the interpretation is that in any transaction each agent $A_i$ makes a payment, $\pi_i$: if $\pi_i<0$ then $A_i$ is given $-\pi_i$ in return for accepting a deal; if $\pi_i>0$ then $A_i$ contributes $\pi_i$ to the amount to be distributed among those agents whose pay-off is negative.

This notion of ``sensible transfer'' is captured by the concept of individual rationality, and is often defined in terms of an appropriate pay-off vector existing. It is not difficult, however, to show that such definitions are equivalent to the following.

Definition 4   A deal $\langle P,Q\rangle$ is individually rational (IR) if and only if $\sigma_u(Q)>\sigma_u(P)$.

We shall consider alternative bases for rationality constraints later: these are primarily of interest within so-called money free settings (so that compensatory payment for a loss in utility is not an option).

The central issue of interest in this paper concerns the properties of the contract-net graph when the allowed deals must satisfy both a structural and a rationality constraint. Thus, if we consider arbitrary predicates $\Phi$ on deals $\langle P,Q\rangle$ - where the cases of interest are $\Phi$ combining a structural and rationality condition - we have,

Definition 5   For $\Phi$ a predicate over distinct pairs of allocations, a contract path

$$\langle P^{(1)}, P^{(2)} ,\ldots, P^{(t-1)}, P^{(t)}\rangle$$

realising $\langle P,Q\rangle$ is a $\Phi$-path if for each $1\leq i < t$, $\langle P^{(i)},P^{(i+1)}\rangle$ is a $\Phi$-deal, that is $\Phi(P^{(i)},P^{(i+1)})$ holds. We say that $\Phi$ is complete if any deal $\delta$ may be realised by a $\Phi$-path. We, further, say that $\Phi$ is complete with respect to $\Psi$-deals (where $\Psi$ is a predicate over distinct pairs of allocations) if any deal $\delta$ for which $\Psi(\delta)$ holds may be realised by a $\Phi$-path.

The main interest in earlier studies of these ideas has been in areas such as identifying necessary and/or sufficient conditions on deals to be complete with respect to particular criteria, e.g. [Sandholm, 1998]; and in establishing ``convergence'' and termination properties, e.g. [Endriss et al., 2003; Endriss & Maudet, 2004b] consider deal types, $\Phi$, such that every maximal¹ $\Phi$-path ends in a Pareto optimal allocation, i.e. one in which any reallocation under which some agent improves its utility will lead to another agent suffering a loss. Sandholm [1998] examines how restrictions e.g. with $\Phi(P,Q)=\top$ if and only if $\langle P,Q\rangle$ is an $O$-contract, may affect the existence of contract paths to realise deals. Of particular interest, from the viewpoint of heuristics for exploring the contract-net graph, are cases where $\Phi(P,Q)=\top$ if and only if the deal $\langle P,Q\rangle$ is individually rational. For the case of $O$-contracts the following are known:

Theorem 1   $$

a.

$O$-contracts are complete.

b.

IR $O$-contracts are not complete with respect to IR deals.

In the consideration of algorithmic and complexity issues presented in [Dunne et al., 2003] one difficulty with attempting to formulate reallocation plans by rational $O$-contracts is already apparent, that is:

Theorem 2   Even in the case $n=2$ and with monotone utility functions the problem of deciding if an IR $O$-contract path exists to realise the IR deal $\langle P,Q\rangle$ is NP-hard.

Thus deciding if any rational plan is possible is already computationally hard. In this article we demonstrate that, even if an appropriate rational plan exists, in extreme cases, there may be significant problems: the number of deals required could be exponential in the number of resources, so affecting both the time it will take for the schema outlined to conclude and the space that an agent will have to dedicate to storing it. Thus in his proof of Theorem 1 (b), Sandholm observes that when an IR $O$-contract path exists for a given IR deal, it may be the case that its length exceeds $m$, i.e. some agent passes a resource to another and then accepts the same resource at a later stage.

The typical form of the results that we derive can be summarised as:

For $\Phi$ a structural constraint ($O$-contract or $M(k)$-contract) and $\Psi$ a rationality constraint, e.g. $\Psi(P,Q)$ holds if $\langle P,Q\rangle$ is individually rational, there are resource allocation settings $\langle{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}\rangle$ in which there is a deal $\langle P,Q\rangle$ satisfying all of the following.

a.

$\langle P,Q\rangle$ is a $\Psi$-deal.

b.

$\langle P,Q\rangle$ can be realised by a contract path on which every deal satisfies the structural constraint $\Phi$ and the rationality constraint $\Psi$.

c.

Every such contract path has length at least $g(m)$.

For example, we show that there are instances for which the shortest IR $O$-contract path has length exponential in $m$.²In the next section we will be interested in lower bounds on the values of the following functions: we introduce these in general terms to avoid unnecessary subsequent repetition.

Definition 6   Let $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ be a resource allocation setting. Additionally let $\Phi$ and $\Psi$ be two predicates on deals. For a deal $\delta=\langle P,Q\rangle$ the partial function $L^{{\rm opt}}(\delta,\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi)$ is the length of the shortest $\Phi$-contract path realising $\langle P,Q\rangle$ if such a path exists (and is undefined if no such path is possible). The partial function $L^{\max}(\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi,\Psi)$ is

$$L^{\max}(\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangl... ...ta,\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi)$$

Finally, the partial function $\rho^{\max}(n,m,\Phi,\Psi)$ is

$$\rho^{\max}(n,m,\Phi,\Psi) =\ \max_{{\mathcal U}=\langle u_... ...e{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}\rangle ,\Phi,\Psi)$$

where consideration is restricted to those $\Psi$-deals $\delta=\langle P,Q\rangle$ for which a realising $\Phi$-path exists.

The three measures, $L^{{\rm opt}}$, $L^{\max}$ and $\rho^{\max}$ distinguish different aspects regarding the length of contract-paths. The function $L^{{\rm opt}}$ is concerned with $\Phi$-paths realising a single deal $\langle P,Q\rangle$ in a given resource allocation setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$: the property of interest being the number of deals in the shortest, i.e. optimal length, $\Phi$-path. We stress that $L^{{\rm opt}}$ is a partial function whose value is undefined in the event that $\langle P,Q\rangle$ cannot be realised by a $\Phi$-path in the setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$. The function $L^{\max}$ is defined in terms of $L^{{\rm opt}}$, again in the context of a specific resource allocation setting. The behaviour of interest for $L^{\max}$, however, is not simply the length of $\Phi$-paths realising a specific $\langle P,Q\rangle$ but the ``worst-case'' value of $L^{{\rm opt}}$ for deals which are $\Psi$-deals. We note the qualification that $L^{\max}$ is defined only for $\Psi$-deals that are capable of being realised by $\Phi$-paths, and thus do not consider cases for which no appropriate contract path exists. Thus, if it should be the case that no $\Psi$-deal in the setting $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ can be realised by a $\Phi$-path then the value $L^{\max}(\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi,\Psi)$ is undefined, i.e. $L^{\max}$ is also a partial function. We may interpret any upper bound on $L^{\max}$ in the following terms: if $L^{\max}(\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle ,\Phi,\Psi)\leq K$ then any $\Psi$-deal for which a $\Phi$-path exists can be realised by a $\Phi$-path of length at most $K$.

Our main interest will centre on $\rho^{\max}$ which is concerned with the behaviour of $L^{\max}$ as a function of $n$ and $m$ and ranges over all $n$-tuples of utility functions $\langle u\mbox{ : }2^{\mathcal R} \rightarrow {\bf Q}\rangle ^n$. Our approach to obtaining lower bounds for this function is constructive, i.e. for each $\langle\Phi,\Psi\rangle$ that is considered, we show how the utility functions ${\mathcal U}$ may be defined in a setting with $m$ resources so as to yield a lower bound on $\rho^{\max}(n,m,\Phi,\Psi)$. In contrast to the measures $L^{{\rm opt}}$ and $L^{\max}$, the function $\rho^{\max}$ is not described in terms of a single fixed resource allocation setting. It is, however, still a partial function: depending on $\langle n,m,\Phi,\Psi\rangle$ it may be the case that in every $n$ agent, $m$ resource allocation setting, regardless of which choice of utility functions is made, there is no $\Psi$-deal, $\langle P,Q\rangle$ capable of being realised by $\Phi$-path, and for such cases the value of $\rho^{\max}(n,m,\Phi,\Psi)$ will be undefined.³

It is noted, at this point, that the definition of $\rho^{\max}$ allows arbitrary utility functions to be employed in constructing ``worst-case'' instances. While this is reasonable in terms of general lower bound results, as will be apparent from the given constructions the utility functions actually employed are highly artificial (and unlikely to feature in ``real'' application settings). We shall attempt to address this objection by further considering bounds on the following variant of $\rho^{\max}$:

$$\rho^{\max}_{{\rm mono}}(n,m,\Phi,\Psi) =\ \max_{{\mathcal ... ...e{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}\rangle ,\Phi,\Psi)$$

Thus, $\rho^{\max}_{{\rm mono}}$ deals with resource allocation settings within which all of the utility functions must satisfy a monotonicity constraint.

The main results of this article are presented in the next sections. We consider two general classes of contract path: $O$-contract paths under various rationality conditions in Section 2; and, similarly, $M(k)$-contract paths for arbitrary values of $k\geq2$ in Section 3. Our results are concerned with the construction of resource allocation settings $\langle{\mathcal A},{\mathcal R}_m,{\mathcal U}\rangle$ for which given some rationality requirement, e.g. that deals be individually rational, there is some deal $\langle P,Q\rangle$ that satisfies the rationality condition, can be realised by a rational $O$-contract path (respectively, $M(k)$-contract path), but with the number of deals required by such paths being exponential in $m$. We additionally obtain slightly weaker (but still exponential) lower bounds for rational $O$-contract paths within settings of monotone utility functions, i.e. for the measure $\rho^{\max}_{{\rm mono}}$, outlining how similar results may be derived for $M(k)$-contract paths.

In the resource allocation settings constructed for demonstrating these properties with $M(k)$-contract paths, the constructed deal $\langle P,Q\rangle$ is realisable with a single $M(k+1)$-contract but unrealisable by any rational $M(k-1)$-contract path. We discuss related work, in particular the recent study of Endriss-et-al:2004 that addresses similar issues to those considered in the present article, in Section 4. Conclusions and some directions for further work are presented in the final section.