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 concept social group on 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 literal, but not remotely adequate, or simply metaphorical. 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 a computational 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)

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 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)

Qualitative Coalitional Games are a variant of coalitional games in which an agent's desires are represented as goals that are either satisfied or unsatisfied, and each choice available to a coalition is a set of goals, which would be jointly satisfied if the coalition made that choice. A coalition in a QCG will typically form in order to bring about a set of goals that will satisfy all members of the coalition. Our goal in this paper is to develop and (...) study logics for reasoning about QCGs. We begin by introducing a logic for reasoning about “static” QCGs, where participants play a single game, and we then introduce and study Temporal QCGs , i.e., games in which a sequence of QCGs is played. In order to represent and reason about such games, we introduce a linear time temporal logic of QCGs, called ℒ. We give a complete axiomatisation of ℒ, use it to investigate the properties of TQCGs, identify its expressive power, establish its complexity, characterise classes of TQGCs with formulas from our logical language, and use it to formulate several solution concepts for TQCGs. (shrink)