Tech Reports

ULCS-04-001

Extremal Behaviour in Multiagent Contract Negotiation

Paul E. Dunne


Abstract

We consider models of contract negotiation for settings in which a set of agents exchange resources in order to optimise their individual holdings. The schemes discussed relate to well-known negotiation protocols proposed in earlier work and we consider a number of alternative notions of 'contract rationality' covering both quantitative measures, e.g. cooperative and individual rationality and more qualitative forms, e.g. Pigou-Dalton transfers. While it is known that imposing particular rationality and structural restrictions on the form of contracts may render these unable to realise every rational deal, in this paper we address the issue of how many deals may be involved in restricted rational contracts to implement a particular deal when it is possible to do so. We construct examples showing the optimal path length may be exponential (in the number of resources $m$). We further show that $k$ agent rational negotiations may achieve in a single deal, exchanges that require exponentially many $k-1$ agent rational negotiations.

[Full Paper]