Next: Conclusions and Further Work Up: Extremal Behaviour in Multiagent Contract Negotiation Previous: Monotone Utility Functions and M(k)-contract paths

# Related Work

The principal focus of this article has considered a property of contract paths realising rational reallocations 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. -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 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)
In a recent article [Endriss & Maudet, 2004a] analyse contract path length also considering -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 -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 can be realised by a rational -contract path. The two main restrictions examined are requiring utility functions to be additive, i.e. for every , ; and, requiring the value returned to be either or , so-called utility functions. Additive utility functions are considered in the case of IR -contracts [Theorems 3, 9]Endriss-et-al:2004, whereas utility functions for cooperatively rational -contracts [Endriss & Maudet, 2004a, Theorems 4, 11]. Using and to denote the functions introduced in Definition 6 where all utility functions are additive (respectively ), cf. the definition of , then with holding if is an IR -contract; holding if is a cooperatively rational -contract and true when is IR, we may formulate Theorems 9 and 11 of [Endriss & Maudet, 2004a] in terms of the framework used in Definition 6, as

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.

Table 2: How many -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 Complete Yes Yes No No No No

Next: Conclusions and Further Work Up: Extremal Behaviour in Multiagent Contract Negotiation Previous: Monotone Utility Functions and M(k)-contract paths
Paul Dunne 2004-11-26