Formal Analysis of Negotiation Protocols for Task Allocation

To formally understand the complex behaviors of negotiating agents so as to design appropriate mechanisms to approximate optimal performance, we have constructed a unified framework to model and analyze the task allocation problem in agent societies with different objectives. This OAR framework includes three aspects: agent’s objective (O), its negotiation attitude (A) and the reward splitting (R) among agents who cooperate to accomplish tasks. An agent’s objective can span the spectrum from totally self-interested to completely cooperative, and there can be a mixture of agents with varying objectives in one agent society. This work focuses on understanding how these different aspects interact in order to achieve individual agent’s objective and to produce effective system performance as well. Using the OAR framework, we develop a closed form statistical analysis to mathematically analyze the interaction between attitude parameters and reward splitting and their relationship with different objective functions for a simple scenario. Though the scenario is simple, it does allow us to show that being able to adjust the attitude parameter and the reward splitting is important to an agent, whether self-interested or cooperative, in order to optimize its objective function. We also present a graph model and optimality graphs, which are used for visualizing the relationships among different parameters. Additionally, we discuss how agents’ expected rewards are affected by changing the local attitude parameters, varying reward splitting, and the method of calculating the relational reward. This work shows that we can create a formal model to analyze interactions among agents ranging from self-interested to fully cooperative.

Keywords: Negotiation, Task Allocation, Reward Splitting, Objective Function, Attitude Parameter, Multi-agent Systems, Mechanism Design, Statistical Analysis, Formal Model, System Performance.