Tech Reports

ULCS-03-002

The Complexity of Contract Negotiation

Paul E. Dunne, Michael Wooldridge and Michael Laurence


Abstract

The use of agent systems as a means of implementing contract negotiation in e-commerce and e-trading environments has been the focus of considerable recent interest. A widely studied abstract model considers the setting in which a set of agents have some collection of resources shared out between them and attempt to construct a mutually beneficial optimal reallocation of these by trading resources. The simplest such trades are those in which a single agent transfers exactly one resource to another -- so-called 'one-resource-at-a-time' or 'O-contracts'. In this research note we consider the computational complexity of a number of natural decision problems in this setting.

[Full Paper]