Extremal Behaviour in Multiagent Contract Negotiation
Paul E. Dunne
Department of Computer Science
The University of Liverpool, Liverpool, UK
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
may result in some reallocations of the resource set becoming unrealisable,
in this paper we address the issue
of the number of restricted rational deals 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
), even when
all of the agent utility functions are monotonic. We further
agents may achieve in a single deal a reallocation
requiring exponentially many rational deals if at most
agents can participate, this
same reallocation being unrealisable by any sequences of rational deals in which at most
agents are involved.