Emergence of Stable Coalitions via Task Exchanges

摘要

We have been interested in agent strategies for interactions with other agents that can promote cooperation in groups of self-interested agents. We assume that typical real-world environments abound in cooperation possibilities: situations where one agent can help another agent by sharing work such that the helping cost of the helper is less than the cost saved by the helped agent. We evaluate the hypotheses that in an environment with sufficient cooperation possibilities, self-interested agents with complementary expertise can learn to recognize cooperation possibilities and develop stable, mutually beneficial coalitions. They should also be able to outperform malevolent agents by resisting their exploitative tendencies. Previous work in this area has prescribed a strategy of reciprocal behavior for promoting and sustaining cooperation among self-interested agents. A restriction of the previous work on reciprocity was the incorporation of only a single cost metric, time, used by the agents. In real-life scenarios multiple objectives like time, quality, dependability, etc. will be involved when an agent evaluates the benefit of interacting with another agent. As a first step to handling such a scenario, we expand on the set of cost metrics by including both time and quality in an agent's evaluation scheme. The measures of time and quality of a work need clarification. The time attribute refers to the absolute time units required for completing a particular task, and the quality attribute is a measure of the effectiveness of executing a task. These values will depend on the expertise level of agents on different task various task types. A second restriction in the previous work was the explicit assumption that all agents had the same capabilities i.e. agents were homogeneous in task expertise. In this work, we remove that restrictive assumption and allow different agents to have different skill sets. We require agents to learn the capabilities of themselves and others through repeated task performance and interaction. The goal of this work is to evaluate whether self-interested agents can learn to recognize agents with complementary expertise and develop a self-sustaining relationship through exchange of help. This can be described as an augmentation of the basic probabilistic reciprocity model with the concept of learning to select a partner. Our hypothesis is that when combined with an appropriate learning scheme, probabilistic reciprocity based strategies will enable the development of stable, mutually beneficial coalitions of self-interested agents with complementary skill sets.