Abstract
In this work we suggest a Belief-Desires-Intentions mental model that provides agents with the social competence to capture and reason about their goals with respect to the goals of other agents/humans in the environment. The suggested architectural model would enable the implementation of generic social competent agents that would interact differently towards different groups.
We explore the agent’s behavior on the social spectrum by computationally describing the maximum attainable benefit when it belongs to different types of social groups. In addition, as the mental model requires the agent to have an ability to reason about group membership, which we prove to be NP-complete, we present a way to formulate the problem as a constraints satisfaction problem and evaluate possible heuristics to speed-up the search.
Introduction
In human society individuals are pursing their own interests while considering the impact of their actions on their surrounding. Accordingly, an important aspect of Social Intelligence is the ability to correctly capture the social structure and use it to navigate and achieve ones goals. In this work we suggest a mental model that provides agents with similar social capabilities. The model captures the entire social behavior spectrum [9], and provides design principles that will allow agents to reason and change their behavior according to their subjective perception of the cooperative/competitive nature of the society.
The main goal of the model it to assist software engineers with the implementation of generic social competent agents that would interact differently towards different groups. Such agents might, for instance, act cooperatively on some occasions, and on others they might reason (according to their beliefs) that competitive behavior should be applied to achieve their goals. Possible applications are quite obvious and span any autonomous agent (robot) that represents the interests of humans in virtual (physical) social environments. The model also intend to address a new class of important problems, where an agent can be part of different types of groups and acts accordingly (see [27]), thus it must consider how its actions affects other group members. Classifying different types of desires and behaviors is an important step in allowing it to do so.
Our model builds upon Bratman’s philosophical foundations of the Belief-Desire-Intention (BDI) model [4] that was developed to explain human practical reasoning. The model was proved to be highly applicable as a software model for developing bounded rational intelligent agents (e.g. [12]). However, while previous adaptation of the model described only specific parts of the social behavior spectrum (in particular joint and individual desires), in the first part of this work we aim to provide a formal model that spans the entire social spectrum, including relations that have not yet received any attention.
To do so we first extend the common Desires model to account for different relationship between desires. We then present the Social Behavior Activity (SBA) model, a BDI-based mental model that spans the social spectrum. The contribution of the SBA mental model is twofold: first, it provides a formal, valid theoretical foundation that could be used to explain and predict agent’s social behavior in realistic environment. Second, it serves as a set of design principles to guide the creation of agents that would be able to engage in behaviors that span the entire social spectrum.
Following the presentation of the model, we explore the agent’s behavior on the spectrum by computationally describing the maximum attainable benefit when it belongs to different types of social groups. The computational analysis provides a basis for building agents that are able to switch from competitive to cooperative interactions, or to individualistic behavior. The main goal of this analysis is to provide agents with the capabilities to reason about their different goals and to compute whether they should coordinate with the others, or form cooperative/competitive groups with them. Our analysis will define the different social groups and present a way to reason on them with the suggested mental architecture. In addition, as the mental model and social groups analysis require the agent to have an ability to reason about group membership, which we prove to be NP-complete, we also present a way to formulate the problem as a constraints satisfaction problem and evaluate possible heuristics to speed-up the search.
To summarize, our main contributions can be seen as the following:1
This work extends the conference paper presented in [37].
The presentation of the Social Behavioral Activity (SBA) mental model for the construction of social competent agents. This mental model is an architectural framework that will allow engineering agents that have some reasoning capabilities about their social surroundings. An analytical exploration of different social groups, which will allow an agent to decide which group to member (if any). As the above item is computationally expensive, we also present a reduction to the constraints satisfaction problem, and present and evaluate several heuristics to the group membership problem. Following our presentation of the SBA model, we will explore its relationship to prior BDI models: SharedPlans (SP) [17], SharedActivity (SA) [18] and AdversarialActivity (AA) [38].
The social oriented multi-agent literature includes domain-specific algorithms that provide some adaptability to agents with different personalities or social behaviors. For example, in [21] the authors used a joint social welfare function and allowed agents to change the weight of their social tendency level. In [29] the authors used the Colored Trails game to study a model in which agents’ helpfulness is characterized in terms of cooperation and reliability. Another interesting approach in the form of a dependency graph that is used to describe and capture the relationships inside a multi-agent system environment was presented in [26], while another line of work that explores agents’ social interactions comes from agent-based simulation approach [8]. While these work provide some reasoning capabilities about the agents or the emergent dynamics of the multi-agent system, they do not consider the architectural aspect of agent design within the BDI framework, that is the main focus of this work.
Another related line of work is on group beliefs. These are usually defined as collectively intentional attitudes that are based on what the group members accept as the group’s belief [13,19,32]. Group beliefs, as oppose to individual beliefs (or mutual beliefs in our context), are attributed only to the collective. The fact that all the group members believe that A is not sufficient (or necessary) for a group belief in A. It is required for group belief that the group members take A to be true when they are acting in the group context, that is, that the individuals accept A when they are acting as group members. In our case we are dealing solely with individual beliefs (and mutual beliefs which are based on those) and the formation of different social groups does not require the adaptation of group beliefs to become members in that group.
Other works explore the notion of norms as a regulatory mechanism to agents’ behavior. However, norm-regulated environments may experience problems when norms associated with their agents are in conflict. For instance, actions that are forbidden in one social context, may, at the same time, also be permitted in another context. There are works that try to cope with these inconsistencies by presenting various mechanisms to detect and solve these contradictions (e.g. [35]). Nevertheless, we are not aware of any work in which these inconsistencies affect the agent decision regarding group membership.
BDI stands for Beliefs-Desires-Intentions. It is a model of human planning and decision making procedure that its philosophical foundations were developed by Bratman [4] as a way to explain how beliefs and desires (goals) should be connected to intentions. One of its main point was that a desire is idle until a plan is explicitly constructed to achieve it. In other words, until there is an explicit intention to pursue it.
Over the years, formal BDI based models of cooperation and teamwork activities have been extensively explored in multiagent worlds, producing various works on the problem’s philosophical foundations (e.g. [5,31]). These foundations were the main building blocks for different formal models, each with its own strengths and weaknesses (e.g. [17,22,36]). Part of these models followed with architectural works and implementations (e.g. [6,30]) which made an important proof of concept for the underlying models. More recently, with the advancements in agent-based programming solutions, new BDI-based practical abstract programming languages have emerged including 3APL [20], AgentsSpeak [25], and GOAL [7], which gave birth to several practical platform (see [2,3] for more information on these).
When interactions are guided by diverse interests, participants may have to overcome disagreements, uncooperative interactions, and even intentional attempts to damage one another. When these types of interactions occur, environments require appropriate behavior from the agents situated in them. Reviewing the BDI literature we can see that most works focus on the cooperative part of the social behavior spectrum [22], while other focus on various specific parts. For example, the Adversarial Activity model presented in [38] looks at the competitive part of the spectrum, while the Shared Activity model [18] disregards aggressive behavior. Additional work by Montagna et al. [23] did consider classification to “friends” and “enemies” in the formal language, however these are regarded as simplified predefined and static labels and are not connected to the agents’ set of desires. Jamroga et al. [34] extended ATL to facilitate game-like multi-agent reasoning capabilities, but still builds upon the classic structure of Desires.
The suggested framework in this work supports the full range of social interactions, from complete cooperation, through individualism, to zero-sum conflict.
The BDI language
The aim of our work is to be used as guidelines for the design of social competent agents that supports the full range of social interactions, from complete cooperation, through individualism, to zero-sum conflict. As such, while we have selected to use the SharedPlans formalism [17] as the underlying BDI based language, it is possible to use most of the above formal models [22,23,34] and augment the extended Desire model onto them.
Basic definitions
Our BDI formalism is derived from the one proposed in [14], and [15]. We have a basic propositional language L which is used by the agent to express beliefs about the world. We will simply assume that it contains the usual classical logic connectives (
Next, we assume a set
BDI structures
Given the set of beliefs
We require that
Another option is to assume
Additionally, where
Next, we defined a function
Our formalization extends former BDI frameworks by providing the ability to reason whether one should be part of a social group
Cooperative Desire (
Individual Desire (
Competitive Desire (
Consider an academic department with three faculty members: Alice, Bob and Chen. Bob is already in a tenure track, while Alice and Chen have temporary positions. In addition, there is one newly available tenured position. Alice has three desires: (1) submitting a proposal. (2) winning an open tenured position in the department. (3) writing a paper. Bob’s desires are: (1) submit a proposal. (2) writing a paper. Chen’s desires are: (1) winning a tenured position in the department. (2) submitting a proposal.
Formally, the set of agents is
Adding the information that the proposal desires are cooperative as all three are working jointly on the same proposal, i.e.,
The definitions of the different relations between goals yield the following:
These properties satisfy the desire model:
Mutual Exclusion (with respect to a single agent) –
Additivity – Let
Containment –
Self Desires –
The Mutual Exclusion, that its existence can be seen from direct inspection of the definitions, provides the ability to ascribe the desire of agent i to one of the three types of desires. Mutual exclusion is with respect to a specific observable agent j. That is, agent’s i desire that is classified as a cooperative desire with respect to agent j, cannot be classified as an individualistic or a competitive desire towards j. The Additivity property, stating that the value of the union of desires is their individual sum, is a corollary of Mutual Exclusion. The Containment property is obvious from its definition. The Self Desires property is derived using propositions Mutual Exclusion and Containment; For every From the above basic properties we can see that agent i’s set of desires (

Social behaviors spectrum.
Figure 1 describes a two-person preference model of the major interpersonal orientations that can occur between players. In this model [16], the player’s utility is defined on the horizontal axis, and the outcome of the “other” player is on the vertical axis. Each outcome increases monotonically along each axis, and the values reflect a linear combination of payoffs to both players. Multiple agents will be regarded as pairwise aggregation of the two-person model.3
Note that the behaviors on the left side of the graph are deliberately excluded from our work, since besides behaviors such as sacrifice or gifts, in which ones outcome is reduced, most of them are considered mental disorders (e.g. Masochism, Sado-Masochism).
To allow the description of different relationships between the agents’ desires, we now describe a set of behavioral axioms that correspond to the interpersonal orientations exhibited in the social behavior spectrum. The presented axioms, together with the mental state model presented later on, will constitute the design guidelines for the construction of social agents. In order to avoid describing a BDI framework from scratch, we build our presentation on a well-known framework, the SharedPlans [17], that provide all the operators and predicates for facilitating a joint activity.4
Nevertheless, our extension is general and can be used to extend any other model.
Next we present the main components of the SharedPlans formalism, but refer the reader to [17] for a complete description. The operator
Agent i may consider adopting an intention to achieve an altruistic desire with respect to j, even if i does not obtain any benefit from attaining it (hence, altruism). The axiom states that an agent i will adopt an intention which achieves
It is important to note that as researchers still debate on the nature of altruistic behavior and whether they do provide some implicit benefit to its actuator, our definition does not consider these implicit benefits.
The formulation of the cooperative axiom is based on the theory presented in [18] that differentiate between a task and a treatment cooperative groups. Formally, an agent i may consider adopting an intention to achieve a cooperative desire with respect to j. This axiom states that if i believes that it shares the same desire with j, then there are two cases of cooperation. The first case states that i believes that j loses from completing the desire itself, then i may consider adopting an intention to achieve the desire. In the second case both agents, i and j, do not lose by performing α which achieves the desire (the α’s may be different), and there are three options. First, i may consider doing α by itself. Second, i may adopt a potential intention that α will be done by j. Third, α will be performed by i and j jointly.
Formally, agent i may consider adopting an intention to achieve an individualistic desire when it believes that this desire does not belong to the other agent’s set of desires.
Formally, agent i may consider adopting an intention to achieve a competitive desire with respect to j when it obtains a positive benefit from achieving the desire, even when i believes that agent j holds another desire, where when both desires will be achieved, agent i might lose.
Formally, agent i may consider adopting an intention to achieve an aggressive desire with respect to j, if it loses from achieving d, as long as member j also loses. The axiom states that an agent i will consider adopting the intention of performing α which may decrease its benefit up to some lower bound
The Social Behavior Activity model (SBA) describes the mental states of a member in a social interaction; these possible mental states span the spectrum as presented above, whereby the agent’s valuation of the desire relations affects its competitive/cooperative position on the spectrum. The SBA model defines a social behavior activity for a group of agents
As the profile definition is domain dependent, we refer the reader to [18] for an example of profile usage in an application.
Members of
[all members of
[being a member obtains a better benefit value:
First, SBA implies the ability of the agents to identify themselves as members of some social group (item 1) (an autonomous agent working in isolation will not be part of a social activity). Second, each individual in the group is characterized by life histories, development patterns, needs, goals, and behavior patterns. These characteristics might be known to some extent and are represented in each member’s profile. Thus, the members must have beliefs concerning a partial profile of the others (item 2). The profiles may be given explicitly or implicitly (e.g., learning the profile by observation, overhearing, etc.), and their exact structure is domain dependent. The third item represents two forms of mutual inter-group dependence. Dependence refers to the relation in which the benefit that one member obtains from its own behaviors is affected at least partly by the activities of another party. Mutual dependence (item 3) means that the benefits of all the parties are affected to some extent by the behaviors of the other members [9]. We differentiate (using exclusive or, ⊕) between two cases of mutual dependence: competitive (
(a) Agent i which his
(a) When i satisfies
(a) Agent i which his
(a) As the cooperative social group does not incentivize aggressive actions, a null-action will be always preferred to an aggressive action which lowers both his benefits. (b) It is intuitive to construct an example in which a “sacrificing” type of action will increase the gap in benefits, which is consistent with 3.1. In a cooperative scenario (
In this section we will explore the spectrum by way of utility computation which will allow an agent to compute and find out which social group will be most beneficial for him, according to its beliefs about the desires’ relationships. This spectrum will allow him to reason about which group is expected to be most beneficial for himself, and adopt its intentions accordingly. We exemplify the various groups using the running example.
The agent’s total benefit as an individual when there is no other agent in the surrounding is composed of its own desires
As seen before, when a rational agent is alone in its environment it selects the set of desires that maximizes its own benefit. Nevertheless, the same agent still follows the same set of desires, even as a part of an uncoordinated social group, as they are still the ones that optimize its benefit. However, as there are other agents in the environment, they can affect the agent in two ways: (1) positive impact – by achieving part of its desires from its set of cooperative desires (
(Benefits of uncoordinated social group).
If
In the first case, since the agent has no competitive desires, the total benefit from its desires can not increase due to other agents’ intentions, thus
The above proposition states that i is always better off being part of an uncoordinated social group, when it does not have competitive goals, or when it believes that the contribution of others to its cooperative desires will be greater than its loss from the competitive desires it will give. In the example we have a cooperative desire that is shared among all three agents, as such much effort is being spent without coordination. We also have a competitive desire between Alice and Chen, therefore without coordinating, the benefit will be computed as follows.
Trivial by simple arithmetic manipulations.
Proposition (5) justifies the need for strong negotiation skills in agents, as they may attain higher benefits from coordinating their actions. Going back to the example in this case (and the two that follow) we cannot know exactly which of the possible solutions will be agreed upon by the agents. It will also depend on the agents individual negotiation skills and strategic reasoning capabilities. If might be direct negotiations between the agents, or it might be that a central mechanism will be the reasoning side who simply dictates the agents which intentions to adopt, and which one to avoid. This will change according to the type of BDI agents in question. Nevertheless, we can assume that an optimal solution will not suddenly emerge due to computation limitation (we discuss this problem in depth in Section 7). One solution that might emerge is that Alice will drop its intention to be elected and will be the one who submits the proposal. As such,
As we noticed in the previous group type, when the agent is part of a coordinated group, Proposition 5 holds (otherwise a rational agent would leave the group). The next proposition states the basic condition in which the agent would prefer to “upgrade” the coordinated group to a cooperative one.
if
By aligning equations and canceling out
The main condition in the above proposition is that the coordinated social group achieves a higher benefit for the agent, than the uncoordinated group. Otherwise, the question of whether to join a cooperative social group is not solely related to altruistic actions. □
If
In order for the social group to be cooperative, its group members must have a mutual belief that being part of the group will yield higher benefits for them (item 3.b). Therefore, corollary 1 states that when agent i wants to be in a cooperative social group with another agent j, but it believes that it is not beneficial for j to be in the group (as
When examining the competitive social group, we can see that the situation worsens in terms of the agent’s total benefit as the benefit from the individual’s set of desires decreases, and new aggressive desires are added. Thus, we can conclude the following:
If
In a competitive group, both
Following the presentation of the
The individual agent’s task of computing whether to join a cooperative social group is NP-Complete.
The reduction is to the Knapsack problem, where the set of n agents with individual payoff functions Specifically, we can use the above problem as an instance of the 0-1 knapsack problem by trying to optimize the vector However, as the optimal solution is not accessible, oftentimes the agents will settle with some approximated solution that they can attain rather promptly, as a function of the available computational resources, and the requested precision. As human being in real life are able to get an approximated decision to the membership question using fast computed heuristic function [33], we might as well not aspire for an optimal solution, but settle with some approximated solution that bounded rational automated agents can get rather promptly, as a function of the available computational resources, and the requested precision. □
In order to empirically evaluate the practicality of the membership query in real applications that the SBA model is directed to, we formulated the membership problem as a boolean constraints satisfaction problem: The set of agents, each with its own set of desires, for a total of N desires. Each of the N desires will be formulated as an individual node, that can get the value of 0 or 1 which signifies whether this desire will be fulfilled. Edges between nodes will model relationships between desires. The division to the cooperative, individualistic or competitive groups of desires, will be modeled as follows: (1) Cooperative desires – will be modeled with “or” constraint edges connecting the nodes. (2) Individual desires – are simply the nodes themselves. (3) Competitive desires – will be modeled with “exclusive or” constraint edge. A solution will be an assignment of values 1 or 0 to nodes s.t. the following constraints hold:
The local desires constraints are not violated.
Individual Benefit constraint:
Social Welfare constraint:

Example graph representation.
According to the previous example Alice has three desires
Recall that we assume all parties have an equal chance of attaining competitive desires, and compute the expected benefit accordingly.
The above solution is one of many existing solutions, and the small size of the problem (7 desires) constitutes a relatively easy problem to solve using brute-force search. However, for larger problems, bounded resources automated agents will need some heuristics to guide their search for a solution.7
Heuristics are often used in CSP type of problems to influence both the order of the evaluated variables and their values, to speed up the search.
– This heuristic dictates searching first for a solution that satisfies the agent with the smallest number of desires. Obviously, less desires makes it easier to fully satisfies their goals.
– This heuristic tries to assign the agents with the largest number of competitive desires. The intuition here is that competitive desires provide more constraint as they always affect at least two agents.
– As cooperative desires are usually easier to assign (as at least two options are available), this function tries first to assign the agents that have the smallest amount of these.
– This function aggregates the rational behind the first three functions and dictates starting with the agent that maximizes the sum of
– This function is very different from the previous four as it looks at the maximum benefit that an agent gets from being part of an uncoordinated social group. In other words, it will start by assigning the agent that would be in the best situation if such coordination effort would not take place at all.
In order to evaluate the usefulness of the suggested heuristics in guiding the search process, we used the ECLiPSe Constraint Logic Programming System. Our aim was to evaluate the different functions in 3 types of environments: cooperative, individualists, and competitive. The environments’ names describe them in terms of the proportions of the respective desires. Let us define

Simulations results.
The results depicted in Fig. 3, provide several insights on the behavior of the functions and the effect of the environment’s characteristics on the solution time. The y-axis is the time in minutes that it took before getting a solution to the problem. First, it is easy to see that competitive environments proved to be significantly more challenging than the other environments. One has to wait almost twice as long before getting the first solution. Second, it is easy to see that
The SharedPlans formalism, which we extend in this work, is a good exemplar of the golden age of BDI frameworks in the 90s. This formalism dictates all agents to have a joint utility function, thus describing a case of full cooperation. While joint group goal (or a “task group” as coined in the Psychology literature) is extremely important in multi-agent interactions, it obviously does not describe other forms of interactions. One example is a “treatment group” in which individuals are working on different goals, but can help or be helped by others. Such group describe well the interaction in a graduate students lab: each student is working on his own work, but mutual help still exist in various forms. Such form of interaction was describe using the SharedActivity notation in [18] and was exemplified in a touring museum domain. Another, more recent model was presented in [38]. The AdversarialActivity model presents a BDI framework for the competitive part of the spectrum.
It is of crucial importance to connect any newly presented formalism to older versions in order to conclude whether systems that implement any of the older frameworks, can be easily converted to include the new formalism. As such, we would like to show that the SBA model contains these three models. In other words, we show that the SBA can be regarded as a generalization of them without losing descriptive or behavioral power. We will show that through a series of containment relationships that show the following:
SharedPlans ⊆ SharedActivity ⊆ SocialBehaviorActivity
AdversarialActivity ⊆ SocialBehaviorActivity
To prove that a model is contained in another, we show that: (1) The definition of the first entails the definition of the second (i.e., an agent that holds mental states of the second model must also hold these mental states in the first); (2) All the axioms in the first model hold, and do not contradict the second model. SharedActivity ⊆ SocialBehaviorActivity. This containment is quite obvious, as the definition of SA is equivalent to SharedPlan ⊆ SharedActivity. To show definition entailment we suggest explicitly adding two axioms to the SP model that hold during rational behavior, but were implicit in the definition. The first axiom (N1) states that having a mutual belief by a group With those axioms in mind, it is easy to see that clause (0) of the partial SP model entails clause (1) of the AdversarialActivity ⊆ SocialBehaviorActivity. The AdversarialActivity (AA) model reflects the interactions from a single agent point of view (agent Intuitively, AA models a zero-sum interaction while the SBA model is general and spans the whole individual-aggression range. The heart of the containment comes from clause 2 of the AA model. All A’s agents are in a
We presented the full social behavior spectrum as it has been modeled in social science research, and suggested the multiagent
We then presented a way to tackle the “group membership” problem by remodeling the problem as a constraints satisfaction problem, and evaluated several heuristic functions to guide the search process on large problems. Regarding future research, we plan to implement the architecture in a simplified environment in which agents can be cooperative and competitive at different times. Our first step will be to implement an automated agent in the Du-Board game, and then continue to a more complex environment. This will allow us to empirically explore the benefits of using our architectural guidelines as a basis for the social agent’s design. Another limitation of our framework is the strong requirement for an explicit utility values and evaluation functions. Future iterations might tackle this by adding probabilistic values or fuzziness to the decision procedure.
Footnotes
Proof of containment relation
To show definition entailment we suggest explicitly adding two axioms to the SP model that hold during rational behavior, but were implicit in the definition. The first axiom states that having a mutual belief by a group
The second axiom states that a group
With those axioms in mind, it is easy to see that clause (0) of the partial SP model
Clause (2) of SBA requires a belief in a (partial) profile of other members; the profile was defined as life histories, development patterns, needs, goals, and behavioral patterns. In the SP model, the agent’s intentions, capabilities and situations can be considered the profile. Those parts are represented in the SP model by the meta-predicates CBA(…) (“can bring about”) and CBAG(…) (“can bring about group”). Clause (1b1) of the partial SP definition entails FSP (“Full Shared Plan”) for selecting a recipe (using the Select_Rec_GR predicate), which in turn entails beliefs about the capabilities of the agent (i.e., about the CBA(…) and CBAG(…) meta-predicates).
Clause (3.b) of the
To prove that the
