Formal Analysis of Negotiation Protocols for Task Allocation
Pp. 149-190 (42)
Victor Lesser, Jiaying Shen, Ingo Weber and Xiaoqin Shelley Zhang
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.
Negotiation, Task Allocation, Reward Splitting, Objective
Function, Attitude Parameter, Multi-agent Systems, Mechanism Design,
Statistical Analysis, Formal Model, System Performance.
Computer and Information Science Department, University of Massachusetts at Dartmouth, 285 Old Westport Rd., North Dartmouth, MA 02747-2300, USA.