Related Work

The principal focus of this article has considered a property of contract paths realising rational reallocations $\langle P,Q\rangle$ when the constituent deals are required to conform to a structural restriction and satisfy a rationality constraint. In Section 2 the structural restriction limited deals to those involving a single resource, i.e. $O$-contracts. For the rationality constraint forcing deals strictly to improve utilitarian social welfare, i.e. to be individually rational (IR) we have the following properties.

a.

There are resource allocation settings $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ within which there are IR reallocations $\langle P,Q\rangle$ that cannot be realised by a sequence of IR $O$-contracts. [Sandholm, 1998, Proposition 2]

b.

Every IR reallocation, $\langle P,Q\rangle$, that can be realised by an IR $O$-contract path, can be realised by an IR $O$-contract path of length at most $n^m - (n-1)m$. [Sandholm, 1998, Proposition 2]

c.

Given $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ together with an IR reallocation $\langle P,Q\rangle$ the problem of deciding if $\langle P,Q\rangle$ can be implemented by an IR $O$-contract path is NP-hard, even if $\vert{\mathcal A}\vert=2$ and both utility functions are monotone. [Dunne et al., 2003, Theorem 11].

d.

There are resource allocation settings $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ within which there are IR reallocations $\langle P,Q\rangle$ that can be realised by an IR $O$-contract path, but with any such path having length exponential in $m$. This holds even in the case $\vert{\mathcal A}\vert=2$ and both utility functions are monotone. (Theorem 3 and Theorem 4 of Section 2)

In a recent article [Endriss & Maudet, 2004a] analyse contract path length also considering $O$-contracts with various rationality constraints. Although the approach is from a rather different perspective, the central question addressed - ``How many rational deals are required to reach an optimal allocation?'', [Endriss & Maudet, 2004a, Table 1, p. 629] - is closely related to the issues discussed above. One significant difference in the analysis of rational $O$-contracts from Sandholm's[1998] treatment and the results in Section 2 is that in [Endriss & Maudet, 2004a] the utility functions are restricted so that every rational reallocation $\langle P,Q\rangle$ can be realised by a rational $O$-contract path. The two main restrictions examined are requiring utility functions to be additive, i.e. for every $S\subseteq{\mathcal R}$, $u(S)=\sum_{r\in S} u(r)$; and, requiring the value returned to be either $0$ or $1$, so-called $0-1$ utility functions. Additive utility functions are considered in the case of IR $O$-contracts [Theorems 3, 9]Endriss-et-al:2004, whereas $0-1$ utility functions for cooperatively rational $O$-contracts [Endriss & Maudet, 2004a, Theorems 4, 11]. Using $\rho^{\max}_{{\rm add}}(n,m,\Phi,\Psi)$ and $\rho^{\max}_{{\rm0-1}}(n,m,\Phi,\Psi)$ to denote the functions introduced in Definition 6 where all utility functions are additive (respectively $0-1$), cf. the definition of $\rho^{\max}_{{\rm mono}}$, then with $\Phi_1(P,Q)$ holding if $\langle P,Q\rangle$ is an IR $O$-contract; $\Phi_2(P,Q)$ holding if $\langle P,Q\rangle$ is a cooperatively rational $O$-contract and $\Psi(P,Q)$ true when $\langle P,Q\rangle$ is IR, we may formulate Theorems 9 and 11 of [Endriss & Maudet, 2004a] in terms of the framework used in Definition 6, as

$$\begin{array}{lclcr} \rho^{\max}_{{\rm add}}(n,m,\Phi_1,\Psi... ...{ $ $ }&\shortcite[Theorem 11]{Endriss-et-al:2004} \end{array}$$

We can, of course, equally couch Theorems 3 and 4 of Section 2 in terms of the ``shortest-path'' convention adopted in [Endriss & Maudet, 2004a], provided that the domains of utility and reallocation instances are restricted to those for which an appropriate $O$-contract path exists. Thus, we can obtain the following development of [Table 1]Endriss-et-al:2004 in the case of $O$-contracts.

Table 2: How many $O$-contract rational deals are required to reach an allocation?
Extension of Table 1 from [p. 629]Endriss-et-al:2004

Utility Functions	Additive	0-1	Unrestricted	Monotone	Unrestricted	Monotone
Rationality	IR	CR	IR	IR	CR	CR
Shortest Path	$m$	$m$	$\Omega(2^m)$	$\Omega(2^{m/2})$	$\Omega(2^m)$	$\Omega(2^{m/2})$
Complete	Yes	Yes	No	No	No	No