CASOS Working PAPER

"Multi-Agent Negotiation: Logical Foundations and Computational Complexity"(PDF file)
Authors: Panzarasa, P., Carley, K. M.
Abstract
This paper is concerned with the use of logic-based formalisms for multi-agent negotiation. We begin by introducing a quantified multi-modal language that draws on and extends standard Belief-Desire-Intention (BDI) logics. Using this language, a number of properties concerning the behavior and cognition of negotiating agents will be examined on a proof-theoretic basis. We then concentrate on the computational complexity of a fundamental problem that arises in multiagent negotiations - the problem of determining whether negotiation guarantees coordination among interdependent agents. To this end, we introduce a series of progressively more sophisticated negotiation protocols, and consider how computational complexity varies, depending on the properties of these protocols.