We introduce a reciprocity criterion for coalition formation among goal-directed agents, which we call the indecomposable do-ut-des property. It refines an older reciprocity property, called the do-ut-des or give-to-get property by considering the fact that agents prefer to form coalitions whose components cannot be formed independently. A formal description of this property is provided as well as an analysis of algorithms and their complexity. We provide an algorithm to decide whether a coalition has the desired property, and we show that (...) the problem to verify whether a single coalition satisfies the property is tractable. Moreover, we provide an algorithm to search all the sub-coalitions of a given coalition satisfying the new property. Even if this problem is not computationally tractable, we show that in several cases, also the complexity of this problem may decrease considerably. (shrink)

In multiple robot systems, the problem of allocation of complex tasks to heterogeneous teams of robots, also known as the multiple robot coalition formation problem, has begun to receive considerable attention. Efforts to address the problem range from heuristics based approaches that search the subspaces of the coalition structure to evolutionary learning approaches. Conventional approaches typically strive to optimize a single objective function such as the number of tasks executed or the time required to execute all tasks, or a weighted (...) function of such objectives. In real world applications, objectives such as minimizing distance traveled and maximizing the number of tasks completed are often conflicting in nature. The coalition formation problem thus naturally lends itself to a multi-objective optimization approach based on evolutionary learning. In this paper, we formulate the problem of mapping coalitions of robots to a set of tasks as a multi-objective optimization problem and propose a variant of non-dominated sorting genetic algorithm to arrive at trade-off solutions. Additionally, we extend the solution to domains where robot resources are non-additive. Simulations demonstrate the efficacy of the proposed approach in generating the set of Pareto-optimal solutions. (shrink)

We don't yet have adequate theories of what the human mind is representing when it represents a social group. Worse still, many people think we do. This mistaken belief is a consequence of the state of play: Until now, researchers have relied on their own intuitions to link up the conceptsocial groupon the one hand and the results of particular studies or models on the other. While necessary, this reliance on intuition has been purchased at a considerable cost. When looked (...) at soberly, existing theories of social groups are either (i) literal, but not remotely adequate (such as models built atop economic games), or (ii) simply metaphorical (typically a subsumption or containment metaphor). Intuition is filling in the gaps of an explicit theory. This paper presents a computational theory of what, literally, a group representation is in the context of conflict: It is the assignment of agents to specific roles within a small number of triadic interaction types. This “mental definition” of a group paves the way for acomputational theory of social groups– in that it provides a theory of what exactly the information-processing problem of representing and reasoning about a group is. For psychologists, this paper offers a different way to conceptualize and study groups, and suggests that a non-tautological definition of a social group is possible. For cognitive scientists, this paper provides a computational benchmark against which natural and artificial intelligences can be held. (shrink)