ECAI 2004 Conference Paper

[full paper]

Tractability Results for Automatic Contracting

Paul E. Dunne, Michael Laurence, Michael Wooldridge

Automated negotiation techniques have received considerable attention over the past decade, and much progress has been made in developing negotiation protocols and strategies for software agents. However, comparatively little effort has been devoted to understanding the computational complexity of such protocols and strategies. Building on the work of Rosenschein, Zlotkin, and Sandholm, we consider the complexity of negotiation in a particular class of task-oriented domains. Specifically, we consider scenarios in which agents negotiate to achieve a redistribution of tasks amongst themselves, where the tasks involve visiting nodes in a graph. Focussing on a particular representaion of the domain (as a spanning tree), we establish a number of complexity results pertaining to the complexity of negotiation in this scenario, with our main result to the effect that the problem of deciding whether a given deal could be reached by a chain of rational proposals is tractable.

Keywords: negotiation, multiagent systems, computational complexity

Citation: Paul E. Dunne, Michael Laurence, Michael Wooldridge: Tractability Results for Automatic Contracting. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1003-1004.