A task delegation model in multi-agent systems: managing sub-delegations and delegation chains under agent behavioral changes

Abstract

In this work, we propose a task delegation model capable of supporting sub-delegations through task decomposition and recursive delegation. Our model considers social and cognitive components derived from trust and reputation theories (e.g., success rate, agents’ preferences, social image, reputation, and know-how), as well as how agents connect and establish social relationships, with the aim of refining the partner selection process. The proposed model was designed to deal with task delegation scenarios in which agents can achieve their goals through delegation or execution actions. Specifically, the delegation model is employed in the partner selection process, where a delegator agent must decide which partner to select as the delegatee. In this process, in addition to personal and shared evaluations of a partner, the delegator can extract information directly from delegation chains. This includes direct and transitive dependencies based on agents’ connections, the accumulated success probability as tasks are sub-delegated, and the penalty degrees assigned to parnters in cases of failure propagation. In particular, a delegation chain is a common structure in applications where agents work as a team and depend on one another to achieve their goals. However, few delegation models in the literature consider sub-delegations as a comprehensive and integrated process. Most existing approaches address task delegation from a mono-episodic perspective, disregarding the formation and impact of delegation chains, and treating sub-delegations as mere repetitions of isolated delegation instances. In our experiments, we evaluate the effectiveness of the proposed delegation model in a dynamic environment where agents can change their social behavior over time. In this context, social behavior refers to an agent’s capability to accurately fulfill its performance estimations when acting as a partner, as well as the likelihood of failure associated with the agent during task execution. These characteristics can be learned by the delegators as they interact with other agents in the system. As the main contribution of this work, we demonstrate that agents benefit from a delegation model that explicitly handles sub-delegations and delegation chains. Our approach leads to significant improvements in task accomplishment when compared to mono-episodic approaches. Specifically, we observe increased success rates and higher satisfaction levels among agents regarding their tasks, as well as a reduction in the time required for delegators to learn the new social behaviors adopted by their partners in a dynamic environment. Therefore, we argue that when agents can explicitly manage delegation chains, they achieve better performance and adapt more quickly to the evolving behaviors of other agents over time. Statistical analyses confirmed that the proposed model significantly outperformed baseline approaches in terms of success rate, satisfaction, and learning efficiency under different network topologies and delegation strategies.