Tuomas Sandholm and Victor Lesser
In this paper we discuss a number of previously unaddressed issues that arise in automated negotiation among self-interested agents whose rationality is bounded by computational complexity. These issues are presented in the context of iterative task allocation negotiations. First, the reasons why such agents need to be able to choose the stage and level of commitment dynamically are identified. A protocol that allows such choices through conditional commitment breaking penalties is pre-sented. Next, the implications of bounded rationality are analysed. Several tradeoffs between allocated computation and negotiation benefits and risk are enumerated, and the necessity of explicit local deliberation control is substantiated. Techniques for linking negotiation items and multiagent contracts are presented as methods for escaping local optima in the task allocation process. Implementing both methods among self-interested bounded rational agents is discussed. Finally, the problem of message congestion among self-interested agents is described, and alternative remedies are presented.