The Double Knapsack Negotiation Problem: Modeling Cooperative Agents and Experimenting Negotiation Strategies

Abstract

This paper presents a novel approach to the well-known Knapsack problem, extending it as a bilateral negotiating problem with default information where each of the two agents has a knapsack and there is a set of items distributed between them. The agents can exchange items in order to reach their goal: fill their knapsacks with items without exceeding their capacity with the aim of maximizing their utility function. Initially the agents do not have any information about their counterpart, e.g. the exact weight of their items and their associated values, so that they consider default assignments for them. This default information can change as the negotiation progresses. A sequential negotiation protocol is proposed, along with different strategies of information exchange and the results obtained when the agents negotiate using them. Information transfer efficiency is assessed in terms of the overall usefulness, quantity of information disclosed and negotiation duration.