Related Work

- a.
- There are resource allocation settings
within which
there are IR reallocations
that
*cannot*be realised by a sequence of IR -contracts. [Sandholm, 1998, Proposition 2] - b.
- Every IR reallocation,
, that
*can*be realised by an IR -contract path, can be realised by an IR -contract path of length at most . [Sandholm, 1998, Proposition 2] - c.
- Given together with an IR reallocation the problem of deciding if can be implemented by an IR -contract path is NP-hard, even if and both utility functions are monotone. [Dunne et al., 2003, Theorem 11].
- d.
- There are resource allocation settings
within which
there are IR reallocations
that
*can*be realised by an IR -contract path, but with any such path having length exponential in . This holds even in the case and both utility functions are monotone. (Theorem 3 and Theorem 4 of Section 2)

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 -contract path exists. Thus, we can obtain the following development of [Table 1]Endriss-et-al:2004 in the case of -contracts.