Tech Reports

ULCS-04-012

Extremal Behaviour in Multiagent Contract Negotiation

Paul E. Dunne

Abstract

We examine properties of a model of resource allocation in which several 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 "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 exchanges may render these unable to realise every reallocation of the resource set, in this paper we address the issue of the number of restricted rational exchanges that may be required to implement a particular reallocation when it is possible to do so. We construct examples showing that this number may be exponential (in the number of resources m), even when all of the agent utility functions are monotonic. We further show that k agents may achieve in a single exchange a reallocation requiring exponentially many rational exchanges if at most k-1 agents can participate, this same reallocation being unrealisable by any sequences of rational exchanges in which at most k-2 agents are involved.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.