Coalition formation in social environments with logic-based agents 1

Abstract

Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of “neighbors” occurring with them in the coalition that emerged. Within this setting, the computational complexity of a number of relevant reasoning tasks is studied, by charting a clear picture of the intrinsic difficulty of finding “agreements” among the agents. Specific algorithmic approaches to reason about such social environments are proposed under the utilitarian perspective, where the collective utility of a coalition is the sum of the utilities of the individuals, as well as under the egalitarian perspective, with the goal being to maximize the utility of the least satisfied agent. These algorithms have been implemented and results of experimental activity are discussed, too.

Keywords

Social environments coalition formation propositional logic pseudo-Boolean solvers computational complexity

1. Introduction

The analysis of social environments and of the dynamics regulating the interactions among rational individuals/agents had attracted much attention in the literature. In particular, interesting problems that have been put under the lens of theoretical and practical investigations involve the study of the mechanisms underlying the aggregation of individual knowledge bases and beliefs into a global and collective behavior. This led to define an area of research that is well-established in a number of different disciplines – including economics, finance, epidemiology, social psychology, and political science, to name a few – and that, more recently, due to the proliferation of social networking services, gained attention in computer science, too (see, e.g., [36]).

A social environment can be very conveniently abstracted as network, whose nodes correspond to the individuals and whose edges encode their social interconnections giving rise to influence phenomena. By departing from classical approaches [11,22,28,29,55,59,64,74,82], which assume that neighbors communicate by propagating and diffusing “items”, such as technologies or diseases, richer models of social dynamics have been proposed in the last few years, which are tailored to study how “immaterial” things, such as opinions, form and diffuse over the network [2,13,19,20,39,48,50,62]. In fact, these studies are conceptually related to works in the field of group decision-making, where individuals are seen as thinking entities equipped with their own (in particular, logical) theories meant to express some preferences over a set of possible alternatives, and where mechanisms are conceived to reason about how these theories can be amalgamated in order to end up with some socially desirable outcome (see, e.g., [18,25,66]).

In the paper, we take the perspective of group decision-making and we consider a cardinal setting, where each agent models her preferences via a utility function mapping the available alternatives to some suitable numerical scale defined in terms of weighted propositional logic [34]. In more detail, by following earlier group decision-making studies based on this logic (e.g., [57,84]), we assume that each individual expresses her preferences as a set of propositional formulas associated with numerical values: Given an interpretation σ assigning a truth value to each variable, the utility of the agent is then defined as the sum of the values associated with the formulas belonging to her own theory and that are satisfied by σ [34,84].

An important advantage of this approach is that expressing utilities by weighted formulas is more succinct than expressing them directly, and is fully expressive, in the sense that every utility function can be expressed by some set of weighted formulas [47,51,65,85]. Indeed, weighted propositional logics has been used in a wide spectrum of AI applications, for instance in fair division [24] and to design bidding languages in combinatorial auctions [23,70]. In fact, even social environments populated by logic-based agents modeled via weighted propositional logics have been already studied in the literature [1], by focusing on questions related to the existence of Nash stable profiles (i.e., configurations of the environments where no agent finds convenient to adopt a different decision/opinion) as well as to the convergence of decentralized dynamics consisting of sequences of best response updates.

As a matter of fact, however, while competitive scenarios where agents are selfish interested and want to maximize their own utility have been already analyzed, less attention has been paid so far to analyze how such social environments behave when agents are willing to collaborate with each other in order to obtain higher worths than by staying in isolation.

The main conceptual contribution of the paper is to address this research question, by studying a setting where logic-based agents interact in social environments and can form coalitions (see, e.g., [45,79]), while carrying out the decision process. In more detail, our contribution can be summarized as follows:

We define a framework for reasoning in social environments, which founds on notions borrowed from coalitional games [72,89] and where the basic utilities associated with the agents are adjusted by considering the influence of the other agents. In particular, each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In fact, we model conformist agents which would like to stay with as many agents as possible. So, a tension will emerge between the number of agents staying together in the given coalition and the utility derived by the alternative on which such agents can agree.

We study the computational complexity of some relevant reasoning tasks arising within the proposed framework, such as, for instance, checking whether there is some coalition guaranteeing some desired level of utility to all the agents. In particular, we conduct an analysis that is parametric w.r.t. the underlying semantics for aggregating the utilities of the agents belonging to the same coalition. On the one hand, the utilitarian semantics is considered, where the collective utility of a coalition is the sum of the utilities of the individuals, called the utilitarian social welfare. On the other hand, an egalitarian perspective is also considered. In fact, in a number of application domains, a “fair” approach would be more appropriate with the goal being to maximize the egalitarian social welfare, that is, the satisfaction of the least satisfied agent (see, e.g., [17,24]).

We define concrete mechanisms for reasoning about some of the tasks we have proposed and characterized from the complexity viewpoint. The mechanisms are based on encoding that tasks via pseudo-Boolean constraints and on taking advantage of current state-of-the-art pseudo-Boolean solvers (see, e.g., [41]). In particular, we show that existing solvers can be smoothly adopted to deal with the utilitarian semantics. However, specific algorithms and methods have been required to deal with the egalitarian semantics.

We implemented the above algorithms and integrated them into a concrete solver we made available to the community. Notably, this is the first solver that explicitly supports forms of fair optimization and it is, therefore, of interest even independently of its specific usage in the application domain considered in the paper. Indeed, the usage of the solver in different application domains can be easily envisaged.

Finally, we discuss results of some experimental activity we have conducted to assess the practical behavior of the proposed algorithmic methods for reasoning about social environments. In particular, the discussion is focused on results obtained under the egalitarian semantics, given that this is a distinguishing feature of our solver.

Organization. The rest of the paper is organized as follows. The formal framework is presented in Section 2 and exemplifications are illustrated in Section 3. The computational complexity of a number of relevant reasoning tasks arising therein are discussed in Section 4. Moving from the general intractability of such tasks, restrictions leading to identify classes of tractable instances are discussed in Section 5. Concrete algorithmic methods to reason about social environments with logic-based agents are discussed in Section 6 and in Section 7, by considering the utilitarian and the egalitarian social welfare, respectively. The implementation of the proposed methods and results of experimental activity are illustrated in Section 8. Further works that are related to our research are illustrated and discussed in Section 9, while a few final remarks are eventually drawn in Section 10.

2. Formal framework

In this section, we formalize a framework for group decision-making where rational agents can group into coalitions in order to find better agreements on the decision that has to be taken. In particular, the coalition formation process will be guided by constraints imposed by the topology of an underlying interaction graph, which is meant to encode the social influence phenomena occurring in a social environment.

2.1. Agents and utility functions

Throughout the paper, we assume that a universe $V$ of propositional variables is given. An interpretation $σ : W \to {true, false}$ over $W \subseteq V$ is a function assigning a Boolean value to each variable in $W$ . We denote by $I (W)$ the set of all interpretations that are defined over $W$ . Intuitively, each propositional variable $X \in V$ is meant to encode some specific alternative that is provided to the agents and on which they have to express their own preferences. In particular, the truth value of X w.r.t. an interpretation σ denotes whether or not the given alternative is selected, based on whether $σ (X) = true$ or $σ (X) = false$ , respectively.

In our framework, a set $A = {A_{1}, \dots, A_{n}}$ of agents is given. Each agent $A_{i} \in A$ is associated with a domain $dom (A_{i})$ of variables taken from $V$ and with a utility function $u_{i} : I (dom (A_{i})) \to Q$ mapping any interpretation2

²
Whenever no confusion can arise, we transparently apply $u_{i}$ over interpretations defined on supersets of $dom (A_{i})$ , with the intended meaning that we get rid of the variables outside that domain.

σ \in I (dom (A_{i}))

to the rational number

u_{i} (σ)

. With a slight abuse of notation, we denote the domain of the set

A

dom (A) = ⋃_{i = 1}^{n} dom (A_{i})

Example 1.

Let us consider a very simple setting where two friends, say $A_{1}$ and $A_{2}$ , have to express their preferences about the possibility of going to the cinema or to stay at home. We model the scenario with a propositional variable X, so that the interpretation $σ_{cinema}$ (resp., $σ_{home}$ ) where X is mapped to true (resp., false) means that the agent goes to the cinema (resp., remains at home). For instance, if $A_{1}$ prefers the cinema while $A_{2}$ would like to stay at home, then we can assume that the agents are equipped with the functions $u_{1}$ and $u_{2}$ such that: $u_{1} (σ_{cinema}) = u_{2} (σ_{home}) = 1$ and $u_{1} (σ_{home}) = u_{2} (σ_{cinema}) = 0$ .

Note that, in the above example, the maximum and minimum values of the utility functions are 1 and 0, respectively. This is not by chance, as we can always rescale the utility functions of the agents from a given set $A$ , in a way that they become normalized, formally, such that ${max}_{σ \in I (dom (A_{i}))} u_{i} (σ) = 1$ and ${min}_{σ \in I (dom (A_{i}))} u_{i} (σ) = 0$ , for each agent $A_{i} \in A$ (see, e.g., [47,57]). Unless stated otherwise, all agents are hereinafter assumed to be normalized.

2.2. Social environments

The goal of the paper is to study the process of amalgamating the preferences of the agents in settings where they interact in a given social environment.

In particular, by following a standard modeling assumption, a social environment is described as a network $IG (A) = (A, E)$ , which we call the interaction graph of $A$ , whose nodes correspond to the agents and whose edges encode their social interconnections which give rise to influence phenomena. The role of the interaction graph is to prescribe which agents can directly communicate with each other, by exchanging opinions and beliefs, and which coalitions of agents are allowed to form. Intuitively, coalitions are groups of agents among which some agreement on the possible alternatives can be find more easily.

In fact, for reasons that might range from physical limitations and constraints to legal banishments, certain agents might not be allowed to form coalitions with certain others (see, e.g., [30], and the references therein). In these cases, it is natural to assume that if two disconnected agents are not connected by intermediaries in a given coalition, then they might not be able to cooperate at all. In particular, following Myerson’s influential work [69], this intuition has been often formalized (see, e.g., [21,31,88]) by stating that a coalition $C \subseteq A$ is allowed to form if the subgraph of $IG (A)$ induced over the nodes in C is connected. Coalitions of this kinds are hereinafter said to be legal.

Example 2.
Consider again the setting of Example 1, by assuming that another agent, say $A_{3}$ , joins the group. Assume that $u_{3} = u_{1}$ , that is, $A_{3}$ prefers to go to the cinema, and that the interactions among the agents are formalized via the interaction graph $({A_{1}, A_{2}, A_{3}}, E)$ where $E = {{A_{1}, A_{2}}, {A_{2}, A_{3}}}$ .

In this context, $A_{1}$ and $A_{3}$ are not related to each other, and hence they are not allowed to form a coalition (without the participation of $A_{2}$ , which might act as a bridge for them). This means that, based on their preferences, a natural outcome would be that $A_{1}$ and $A_{3}$ both go to the cinema, but independently on each other (for instance, looking for a different film).

Now, while taking part to the coalition formation process, agents can be influenced by their “social” relationships, in that their own utility functions can be affected by the number of neighbors belonging to the coalitions they belong to. To define this influence, we first define the concept of neighborhood w.r.t. the underlying interaction graph: For each legal coalition $C \subseteq A$ and agent $A_{i} \in C$ , we define $neigh (A_{i}, C)$ as the set of all agents $A_{j} \in C$ such that there is an edge connecting $A_{i}$ and $A_{j}$ in $IG (A)$ .

Belonging to a social environment, it makes sense to assume that the utilities of the agents depend not only of their absolute preferences but also on the number of neighbors occurring with them in the coalition that emerged. Accordingly, each agent $A_{i} \in A$ is also implicitly associated with a rational number $α_{i}$ with $0 ⩽ α_{i} ⩽ 1$ , which we call the social attitude of $A_{i}$ .

In particular, for each interpretation σ over a superset of $dom (C)$ , we define the following “adjusted” utility (indeed depending on C): $\begin{array}{rcl} \hat{u_{i}} (σ, C) & = & α_{i} \times \frac{| neigh (A_{i}, C) |}{| neigh (A_{i}, A) |} \\ + (1 - α_{i}) \times u_{i} (σ) . \end{array}$

Note that an agent $A_{i}$ with $α_{i} = 0$ does not care of the agents belonging to the given coalition. Instead, with $α_{i} = 1$ , the agent would like to stay as much as possible together with her neighbors, by completely getting rid of the original utility function.

Note that the modeling approach we have proposed is suited to deal with social agents that are “conformist” in their behavior, and it is fully consistent with traditional studies on opinion formation and diffusion in social environments based on influence models, such as the cascade, the tipping/treshold, and the homophilic models. Extending the analysis to “dissenter” agents, whose adjusted utility does not monotonically increase with the number of neighbors in the coalition, is an interesting avenue of further research – in the context of competing agents and when one looks for Nash solutions, both conformist and dissenter agents have been recently studied in the literature [1]. Example 3.
Let us continue our discussion about the running example over the set $A = {A_{1}, A_{2}, A_{3}}$ of agents. Consider a setting where $α_{1} = α_{3} = 0$ while $α_{2} = 1$ . In this case, agents $A_{1}$ and $A_{3}$ are still willing to maximize their own internal preferences and, hence, they would like to go to the cinema. However, agent $A_{2}$ now completely overrides the original attitude to stay at home in favor of the attitude to join other agents.

Then, given the interaction graph of Example 2 where $neigh (A_{2}, A) = {A_{1}, A_{3}}$ , there are four possible coalitions for $A_{2}$ , such that, no matter of the given interpretation σ:
$C^{i} = {A_{2}}$ , with $\hat{u_{2}} (σ, C^{i}) = \frac{| neigh (A_{2}, C^{i}) |}{| neigh (A_{2}, A) |} = \frac{0}{2} = 0$ ;

$C^{i i} = {A_{1}, A_{2}}$ , with $\hat{u_{2}} (σ, C^{i i}) = \frac{1}{2}$ ;

$C^{i i i} = {A_{2}, A_{3}}$ , with $\hat{u_{2}} (σ, C^{i i i}) = \frac{1}{2}$ ;

$C^{i v} = {A_{1}, A_{2}, A_{3}}$ , with $\hat{u_{2}} (σ, C^{i v}) = \frac{2}{2} = 1$ .

In particular, note that for $A_{2}$ it is convenient to form a coalition with $A_{1}$ and $A_{3}$ . This time, $A_{2}$ really acts as a bridge between such agents, and therefore it is natural to expect that they go to the cinema all together.

2.3. Goals in the aggregation process

The final ingredient of the formalization is to define the objective functions that we would like to optimize for modeling the agreement process among the agents.

To this end, we consider two classical approaches discussed in the literature, that is, the utilitarian and the egalitarian social welfare. In the former case we just look for maximizing the sum of the adjusted utilities, while in the latter a fair approach is considered where we maximize the utility of the least satisfied agent. More formally, for any given interpretation σ and coalition C, we will consider:

the utilitarian social welfare, denoted by $UT$ , where the utilities of the various agents are summed: $UT (σ, C) = \sum_{A_{i} \in C} \hat{u_{i}} (σ, C)$ ;

the egalitarian social welfare, denoted by $EG$ , where we take care of the least satisfied agent; hence, we define $EG (σ, C) = {min}_{A_{i} \in C} \hat{u_{i}} (σ, C)$ .

Based on the above notions, we then say that an interpretation σ is $UT$ -optimal for C if it has the maximum utilitarian social welfare $UT (σ, C)$ over all interpretations. The set of all $UT$ -optimal interpretations is denoted by $UT - O PT (C)$ , and their utilitarian social welfare is denoted by $UT - V AL (C)$ .

Similarly, σ is $EG$ -optimal for C if it has the maximum egalitarian social welfare $EG (σ, C)$ over all interpretations. The set of all $EG$ -optimal interpretations is denoted by $EG - O PT (C)$ , and their utilitarian social welfare is denoted by $EG - V AL (C)$ .

Example 4.
Consider again the setting discussed in Example 3. For the coalition $C^{i} = {A_{2}}$ , it is immediate to check that both $σ_{cinema}$ and $σ_{home}$ are (trivially) optimal interpretations, with respect to both the utilitarian and the egalitarian social welfare. Indeed, note that we just have $UT (σ, C^{i}) = EG (σ, C^{i}) = \hat{u_{i}} (σ, C^{i}) = 0$ , no matter of the given interpretation σ.

Consider instead the coalition $C^{i v}$ . In this case, for the interpretation $σ_{cinema}$ , we have: $\begin{array}{l} \begin{matrix} UT (σ_{cinema}, C^{i v}) & = \sum_{i = 1}^{3} \hat{u_{i}} (σ_{cinema}, C^{i v}) \\ = 1 + 1 + 1; \end{matrix} \\ EG (σ_{cinema}, C^{i v}) = 1; \end{array}$ whereas for the interpretation $σ_{home}$ we have: $\begin{array}{l} \begin{matrix} UT (σ_{home}, C^{i v}) & = \sum_{i = 1}^{3} \hat{u_{i}} (σ_{home}, C^{i v}) \\ = 0 + 1 + 0; \end{matrix} \\ EG (σ_{home}, C^{i v}) = 0 . \end{array}$

Therefore, it is immediate to check that $σ_{cinema}$ is optimal with respect to both the utilitarian and the egalitarian social welfare, as we have already informally argued in Example 3.

We leave this section by stressing that, in many practical real-world scenarios, one might want to study settings where agents can form a coalition structure, i.e., where they can partition themselves into a set Π of disjoint coalitions such that $⋃_{C \in Π} C = A$ .

Assessing which coalition structure might emerge in a given scenario is a fundamental problem in the study of multi-agent systems, which attracted much research in earlier literature (see, e.g., [45,79]). In particular, we are interested in those coalition structures Π that are optimal w.r.t. the utilitarian and the egalitarian social welfare, i.e., such that the values $UT - V AL (Π) = \sum_{C \in Π} UT - V AL (C)$ and $EG - V AL (Π) = {min}_{C \in Π} EG - V AL (C)$ , respectively, are maximized over all possible coalition structures.
Example 5.
Consider again Example 4 and note that $UT (σ_{cinema}, A) = 3$ and $EG (σ_{cinema}, A) = 1$ – indeed, just observe that $C^{i v} = A$ . Now, rather than assuming that all agents would like to stay all together, we assume that they form the coalition structure $Π = {{A_{1}}, {A_{2}}, {A_{3}}}$ , i.e., each agent stays alone in Π. In this extreme case, we would have $UT - V AL (Π) = 2$ , since we have already observed that the adjusted utility of agent $A_{2}$ is 0, by staying alone. Hence, we can also conclude that $EG - V AL (Π) = 0$ .

Eventually, the coalition structure where all agents stay together can be preferred to Π and it can be checked that such structure is the optimal coalition structure w.r.t. the utilitarian social welfare and the egalitarian social welfare.

In the above example, it emerged that it is convenient for the agents to stay all together. However, this is not in general the case, even when agents have some social attitude. An exemplification is discussed below. Example 6.
Let us go back to Example 1, where only agents $A_{1}$ and $A_{2}$ have been introduced. Recall that $A_{1}$ wants to go to the cinema, while $A_{2}$ wants to stay at home. By considering the social factors $α_{1}$ and $α_{2}$ (w.l.o.g., $α_{1} ⩽ α_{2}$ ), and by assuming that the agents are connected in the interaction graph, we get:
$UT - V AL ({{A_{1}}, {A_{2}}}) = \frac{α_{1}}{2} + (1 - α_{1}) + \frac{α_{2}}{2} + (1 - α_{2})$ ;

$UT - V AL ({{A_{1}, A_{2}}}) = α_{1} + (1 - α_{1}) + α_{2}$ .
In particular, note that when staying all together, since $α_{1} ⩽ α_{2}$ , the maximum welfare is obtained if agents go to the cinema, so the adjusted utility of $A_{1}$ is 1 (resp., of $A_{2}$ is 0). Moreover, it is immediate to check that, whenever $α_{2} < \frac{1}{2}$ , the optimal coalition structure is ${{A_{1}}, {A_{2}}}$ , where the two agents stay alone.

3. Further exemplifications

In this section, we exemplify a few possible applications of the general framework we have introduced for reasoning about social environments.

3.1. Voting and influence phenomena

Consider a scenario where a set $A = {A_{1}, A_{2}, A_{3}}$ of agents have to decide whether they will vote for the Democratic Party. The agents are all friends of each other, so that the interaction graph $IG (A)$ is a clique defined over them. We consider two propositional variables: D and V. The latter is meant to encode whether the agent will vote (i.e., does not abstain), while the former is meant to encode whether the vote actually expressed is for the Democratic Party. Of course, it is meaningless to consider the interpretation $σ^{*}$ where D is true and V is false. This is a kind of hard constraint, which can be easily encoded in our framework by assuming that $u_{i} (σ^{*}) = 0$ , for each $A_{i} \in A$ .

Now, agents $A_{1}$ and $A_{2}$ are strongly inclined to abstain, so that $u_{1} (σ) = u_{2} (σ) = 1$ , for the interpretation σ with $σ (V) = σ (D) = false$ . Moreover, they do not have any specific political preference, so that $u_{1} (σ) = u_{2} (σ) = \frac{1}{2}$ hold, for each other interpretation. On the other hand, agent $A_{3}$ is a Democrat, so that $u_{3} (σ) = 1$ if, and only if, $σ (V) = σ (D) = true$ – with all other interpretations being mapped to the value 0.

Concerning the social factors, assume for the moment that $α_{1} = α_{2} = α_{3} = 0$ , so that $\hat{u_{i}} = u_{i}$ , for each $A_{i} \in A$ , and let us consider the support over all the agents for the interpretation $σ^{dem}$ such that $σ^{dem} (D) = σ^{dem} (V) = true$ . It is immediate to check that $UT (σ^{dem}, A) = \frac{1}{2} + \frac{1}{2} + 1$ , while $EG (σ^{dem}, A) = \frac{1}{2}$ . Instead, for the interpretation σ with $σ (V) = σ (D) = false$ , we would have $UT (σ, A) = 1 + 1 + 0$ , while $EG (σ, A) = 0$ . This means that $σ^{dem}$ and σ are both optimal with respect to the utilitarian social welfare for $A$ . However, σ is optimal when considering the egalitarian social welfare, since for $A_{3}$ it is definitively more desirable to vote for the Democratic Party. In fact, we can check that $σ^{dem}$ is $EG$ -optimal for $A$ .

Finally, consider the scenario where $α_{3} = 0$ whereas $α_{1} = α_{2} = \bar{α}$ is a fixed value strictly greater than 0. In this case, we have $\hat{u_{1}} (σ^{dem}, A) = \hat{u_{2}} (σ^{dem}, A) = \bar{α} + (1 - \bar{α}) \times \frac{1}{2}$ , so that $UT (σ^{dem}, A) = 2 + \bar{α}$ , while $EG (σ^{dem}, A) = \frac{1 + \bar{α}}{2}$ . As above, consider then the interpretation σ with $σ (V) = σ (D) = false$ and note that we would have $UT (σ, A) = 1 + 1 + 0$ , while $EG (σ, A) = 0$ . Hence, such an interpretation is no longer $UT$ -optimal for $A$ , since $UT (σ, A) = 2 < 2 + \bar{α} = UT (σ^{dem}, A)$ . In particular, in this case, the interpretation $σ^{dem}$ is not only $EG$ -optimal for $A$ , but $UT$ -optimal for $A$ , too.

3.2. Influence in large networks

The proliferation of social networking services, such as FaceBook and Twitter, created novel and highly-dynamic forms of techno-social ecosystems where agents are deeply influenced by their social relationships. In a contest of this kind, consider an agent $A_{1} \in A = {A_{1}, \dots, A_{n + 1}}$ and an interpretation $\bar{σ}$ such that $u_{1} (\bar{σ}) = 0$ – that is, $\bar{σ}$ is definitively the worse possible interpretation for $A_{1}$ , whenever the agent does not take part to a group decision process. On the other hand, assume that all agents $A_{i} \in A ∖ {A_{1}}$ are such that $u_{i} (\bar{σ}) = 1$ . Therefore, we immediately have that $EG (\bar{σ}, A) = 0$ and that $UT (\bar{σ}, A) = α_{1} + n$ . In particular, note that the adjusted utility function for $A_{1}$ when grouping all agents in $A$ is such that ${\hat{u}}_{1} (σ) = α_{1}$ , which is greater than $u_{1} (\bar{σ})$ provided $α_{1} > 0$ .

At the extreme opposite of being all together, consider the coalition structure Π where each agent stays alone. In this case, each agent $A_{j} \in A$ can select the best possible individual interpretation (whose value is 1, as we are considering normalized agents), then getting $1 - α_{j}$ as the resulting adjusted utility.

Therefore, by looking at the sum of the utilities of the agents, we get the overall value $UT - V AL (Π) = \sum_{j = 1}^{n + 1} (1 - α_{j})$ , so that being in isolation, whenever $\bar{σ}$ is selected, is convenient only if: $\sum_{j = 1}^{n + 1} (1 - α_{j}) > α_{1} + n$ . For instance, assuming that $α_{j} = α > 0$ , for each $A_{j} \in A$ , we get that the above inequality reduces to asking that $n < \frac{1}{α} - 2$ . That is, for every sufficiently large value of n, provided that $A_{1}$ has some social attitude, it is never convenient to form the coalition structure Π where each agent stays alone. In fact, for a sufficiently large value of n, it can be checked that staying all together in the coalition $A$ is optimal w.r.t. the utilitarian and the egalitarian social welfare.

4. Complexity analysis

Now that we have entirely formalized the framework for reasoning about social environments, we move to analyzing the amount of computational resources that are intrinsically needed to reason about it.

4.1. Preliminaries on complexity theory

For the sake of completeness, we next present some preliminaries on complexity theory. For expanding on these concepts, the reader is referred to [73].

For the complexity analysis reported in the paper, we abstract the reasoning tasks in terms of decision problems. Formally, decision problems are maps from strings (encoding the input instance over a fixed alphabet, e.g., the binary alphabet ${0, 1}$ ) to the set ${“ y e s ”, “ n o ”}$ . The class P is the set of decision problems that can be solved by a deterministic Turing machine in polynomial time with respect to the input size $‖ x ‖$ , that is, with respect to the length of the string x.

We are often interested in computations carried out by non-deterministic Turing machines. Unlike deterministic Turning machines, at some points of the computation, these machines may not have one single next action to perform, but a choice between several possible next actions. A non-deterministic Turing machine answers a decision problem if, on any input x, (i) there is at least one sequence of choices leading to halt in an accepting state if x is a “yes” instance (such a sequence is called accepting computation path); and (ii) all possible sequences of choices lead to a rejecting state if x is a “no” instance.

The class of decision problems that can be solved (resp., whose complement can be solved) by non-deterministic Turing machines in polynomial time is denoted by $NP$ (resp., $co- NP$ ). Note that $P \subseteq NP$ and $P \subseteq co- NP$ hold, with the inclusions being likely to be strict. In the paper, we also deal with the class $DP$ of all those problems that can be written as a conjunction of a problem in $NP$ and a problem in the complementary class $co- NP$ . A decision problem $A_{1}$ is polynomially reducible to a decision problem $A_{2}$ , if there is a polynomial-time computable function h (called reduction) such that, for every x, $h (x)$ is defined and x is a “yes” instance of $A_{1}$ if, and only if, $h (x)$ is a “yes” instance of $A_{2}$ . A decision problem A is C-hard, with $C \in {NP, DP}$ , if every problem in C is polynomially reducible to A; if A is C-hard and belongs to C, then A is said to be C-complete.

4.2. Computational setting and problems of interest

In order to formalize the reasoning problems that will be analyzed, it is sensible to first discuss the specific encoding mechanisms we adopt to define the utility functions of the agents.

By following well-known logic-based encoding approaches [34,57,84], we assume to this end that each agent $A_{i} \in A$ is transparently viewed as a finite set of pairs $⟨ φ, w ⟩$ , called weighted formulas, where φ is a cube, i.e., a formula built by using the Boolean connectives ∧ over variables that can be possible negated (via the monadic operator ¬), and where $w \in Q$ is a rational number. Eventually, for any given interpretation σ, the utility $u_{i} (σ)$ is defined as the sum of all values w for the pairs $⟨ φ, w ⟩ \in A_{i}$ such that σ satisfies φ, shortly denoted as $σ ⊧ φ$ . Hence, $A_{i}$ is just encoded by its associated underlying weighted formulas.

Note that, while adopting the perspective of earlier logic-based approaches, we actually depart from them by considering formulas that only consist of conjunctions of literals, i.e., variables or their negation. In fact, weighted formulas of this kinds have been already proven to be useful for expressing values of coalitions in cooperative games and hedonic games, in so-called marginal contribution nets [44,46,60]. Here, we argue that this language, which is clerkly more restricted that full propositional logic, is still powerful enough to model real-world setting in social environments, while being conceptually simple and easy to manipulate.

Example 7.
For the running example discussed in Section 2, the utility function of agents $A_{1}$ and $A_{2}$ can be modeled by the set of weighted formulas ${⟨ C, 1 ⟩}$ , where the cube just consists of the propositional variable C meant to encode that the agents get 1 as their utility whenever the go to the cinema. Moreover, we have $A_{3} = {⟨ \neg C, 1 ⟩}$ , which encodes that $A_{3}$ would like to stay at home.

For the example discussed in Section 3.1, instead, the utility functions of agents $A_{1}$ and $A_{2}$ can be modeled by the set ${⟨ \neg D \land \neg V, 1 ⟩, ⟨ V, \frac{1}{2} ⟩}$ , while the utility function of $A_{3}$ can be modeled as ${⟨ D \land V, 1 ⟩}$ .

Within this setting, we next embark on the study of a number of decision problems, being defined parametrically w.r.t. the specific kind of social welfare $X \in {UT, EG}$ we would like to consider. All these problems receive as input a set $A$ of normalized agents (together with the underlying interaction graph $IG (A) = (A, E)$ ) plus a rational number γ:
x-Check:
Given a legal coalition $C \subseteq A$ , does $X - V AL (C) ⩾ γ$ hold?
x-Existence:
Is there any legal coalition $C \subseteq A$ such that $X - V AL (C) ⩾ γ$ ?
x-CS-Existence:
Is there any coalition structure Π such that $X - V AL (Π) ⩾ γ$ ?
x-Maximal:
Given a legal coalition $C \subseteq A$ , is C $X$ -maximal for γ, i.e., such that $X - V AL (C) ⩾ γ$ and for which no coalition $C^{'} \supset C$ exists with $X - V AL (C^{'}) ⩾ γ$ ?

Note, in particular, that the latter problem is meant to identify maximal coalitions on which good “agreements” can be found. Instead, the former problems directly reflect the concepts we have defined in our formal framework, so far.
4.3. Results and technical elaborations

We start our analysis by focusing on the most basic problem, that is, x-Check.

Theorem 1.
For each $X \in {UT, EG}$ , x - Check is $NP$ -complete. Hardness holds on sets $A$ of agents with $α_{i} < 1$ , $\forall A_{i} \in A$ .
Proof.
(Membership) The problem ut-Check (resp., eg-Check) can be solved in polynomial time by a nondeterministic Turing machine that guesses σ and then checks that $UT (σ, C) ⩾ γ$ (resp., $EG (σ, C) ⩾ γ$ ).

(Hardness) Recall that deciding whether a Boolean formula in conjunctive normal form $φ = c_{1} \land \dots \land c_{n}$ , where $c_{1}, \dots, c_{n}$ are clauses, i.e., disjunction of literals, is a well-known $NP$ -hard problem. Given a formula of this kind, consider a variable X not occurring in φ, and define $A_{i} = {⟨ \neg X, 1 ⟩} \cup {⟨ X \land s c_{1}, 1 ⟩ ∣ s c_{1} is a conjunction of literals over variables in c_{i} and satisfying that clause}$ and consider the agent $A_{n + 1} = {⟨ X, 1 ⟩}$ . Note that the role of X is to guarantee that all the agents are normalized. For an example, if $c_{1} = Y \lor Z$ holds, then the conjunctions of literals included in $A_{i}$ are $Y \land Z$ , $Y \land \neg Z$ , $\neg Y \land \neg Z$ , and $\neg Y \land Z$ . Moreover, note that these conjunctions are mutually exclusive.

Let $A = {A_{1}, \dots, A_{n}, A_{n + 1}}$ be a set of agents and assume that $IG (A)$ is the complete interaction graph over $A$ . So, for any interpretation σ, we have $UT (σ, A) = \sum_{i} α_{i} + \sum_{i} (1 - α_{i}) \times u_{i} (σ)$ . Since we know that $\sum_{A_{i} \in A} α_{i} < | A |$ , we immediately derive that $UT (σ, A) = | A |$ if, and only if, X is true in σ and σ satisfies all clauses in φ. Hence, ut-Check is $NP$ -hard.

In order to conclude, let us consider the egalitarian social welfare. Assume that φ is not satisfiable. Then, for each interpretation σ with $σ (X) = true$ , there is at least an agent $A_{i}$ such that $u_{i} (σ) = 0$ and, hence, $\hat{u_{i}} (σ, A) = α_{i} < 1$ . therefore, $EG - V AL (A) ⩾ 1$ holds if, and only if, φ is satisfiable, which shows that eg-Check is $NP$ -hard, too. □

A similar result can be proven for x-Existence and for its counterpart to coalition structures, i.e., for the problem x-CS-Existence.
Theorem 2.
For each $X \in {UT, EG}$ , x - existence is $NP$ -complete. Hardness holds on sets $A$ of agents with $α_{i} < 1$ (and $α_{i} \neq 0$ if $X = EG$ ), $\forall A_{i} \in A$ .
Proof.
(Membership) The problem ut-Existence can be solved in polynomial time by a nondeterministic Turing machine that guesses a coalition $C \subseteq A$ and an interpretation σ and then checks that $UT (σ, C) ⩾ γ$ . With the same line of reasoning, it can be checked that eg-Existence belongs to $NP$ .

(Hardness) Consider again the reduction we have exhibited in the proof of Theorem 1. For each possible legal coalition $C \subseteq A$ , $UT (σ, C) ⩽ C$ , because agents are normalized. Therefore, $UT (σ, C) ⩾ | A |$ might hold only if $C = A$ . But, in this case, we know that checking whether there is an interpretation σ such that $UT (σ, A) = | A |$ is equivalent to checking whether a given Boolean formula in conjunctive normal form is satisfiable, which is a $NP$ -hard problem.

To conclude, let us consider the egalitarian social welfare. Note that, for each interpretation σ, coalition C and agent $A_{i} \in C$ with $C < | A |$ , it is the case that $\hat{u_{i}} (σ, C) ⩽ α_{i} \times q + (1 - α_{i})$ with $q < 1$ . Hence, $\hat{u_{i}} (σ, C) < 1$ holds, too. Therefore, given that $α_{i} \neq 0$ , for each $A_{i} \in A$ , $EG (σ, C) ⩾ 1$ might hold only if $C = A$ . But, again, we know that checking whether there is an interpretation σ such that $EG (σ, A) ⩾ 1$ is equivalent to checking whether a given Boolean formula is satisfiable, which is a $NP$ -hard problem. □
Theorem 3.
For each $X \in {UT, EG}$ , x - CS - existence is $NP$ -complete. Hardness holds on sets $A$ of agents with $α_{i} < 1$ (and $α_{i} \neq 0$ if $X = EG$ ), $\forall A_{i} \in A$ .
Proof.
(Membership) The problem can be solved in polynomial time by a nondeterministic Turing machine that guesses a coalition structure Π and an interpretation $σ_{C}$ , for each coalition $C \in Π$ , and then checks that $\sum_{C \in P ı} UT (σ, C) ⩾ γ$ or ${min}_{C \in Π} EG (σ, C) ⩾ γ$ .

(Hardness) Consider again the reduction the proof of Theorem 1 and the arguments in the proof of Theorem 2. Note that the inequalities $\sum_{C \in Π} UT (σ, C) ⩾ | A |$ and ${min}_{C \in Π} EG (σ, C) ⩾ 1$ can hold only if $Π = {A}$ . In both cases, hardness follows as checking whether there is an interpretation σ with $UT (σ, A) = | A |$ or $EG (σ, A) = 1$ is $NP$ -hard. □

To complete the picture of the complexity results, we now consider x-Maximal for which a complexity increase occurs. Theorem 4.
For each $X \in {UT, EG}$ , x - Maximal is $DP$ -complete. Hardness holds on sets $A$ of agents with $α_{i} < 1$ (and $α_{i} \neq 0$ if $X = EG$ ), $\forall A_{i} \in A$ .
Proof.
(Membership) Let $C \subseteq A$ be the legal coalition provided as input, and recall that C is x-maximal for γ if (C1) $X - V AL (C) ⩾ γ$ , and (C2) there is no legal coalition $C^{'} \supset C$ such that $X - V AL (C^{'}) ⩾ γ$ . We observe that (C1) can be checked in $NP$ , as we shown in Theorem 1. Consider, then, the condition complementary to (C2), that is, that there is some legal coalition $C^{'} \supset C$ such that $UT - V AL (Γ, C^{'}) ⩾ γ$ . To verify whether the condition holds, we can just guess a legal coalition $C^{'} \supset C$ and an interpretation σ, by subsequently checking that $UT (σ, C^{'}) ⩾ γ$ hold. This is feasible in $NP$ , and hence (C2) can be checked in $co- NP$ . Overall, the problem is in $DP$ .

(Hardness) Recall that the problem receiving a pair $(φ^{1}, φ^{2})$ of Boolean formulas in conjunctive normal form defined over different propositional variables and asking whether $φ^{1}$ is satisfiable and $φ^{2}$ is not satisfiable is $DP$ -hard. Let $A^{1}$ (resp., $A^{2}$ ) denote the set of agents that can be associated with the formula $φ^{1}$ (resp., $φ^{2}$ ) based on the encoding discussed in the proof of Theorem 1. In particular, assume that the variable X used there to guarantee that all agents are normalized is replaced by the fresh variable $X_{1}$ (resp., $X_{2}$ ). Consider then the set of agents $A = A^{1} \cup A^{2}$ and note that $A^{1}$ and $A^{2}$ are defined over different propositional variables. Moreover, assume that $IG (A)$ consists of two cliques, one defined over the agents in $A^{1}$ and the other defined over the agents in $A^{2}$ . That is, the agents in these two sets do not interact.

Now, by Theorem 1, we know that $EG - V AL (A^{1}) ⩾ 1$ (resp., $EG - V AL (A^{2}) ⩾ 1$ ) if, and only if, $φ^{1}$ (resp., $φ_{2}$ ) is satisfiable. Given that the two sets of agents are defined over different propositional variables, it can be checked that $EG - V AL (A^{1} \cup C) ⩾ 1$ with $\emptyset \subset C \subseteq A^{2}$ if, and only if, $C = A^{2}$ and both $φ^{1}$ and $φ_{2}$ are satisfiable. Hence, $A^{1}$ is eg-maximal for 1 if, and only if, $φ^{1}$ is satisfiable and $φ^{2}$ is not satisfiable. That is, eg-Maximal is $DP$ -hard.

A more technical reduction based on the same kinds of ingredients can be then used to show the $DP$ -hardness for the utilitarian social welfare, too. □

5. Islands of tractability

The results derived in the previous section are bad news concerning the possibility of dealing efficiently with the framework we have proposed for reasoning about social environment. This motivates the study of restrictions leading to identify classes of instances that are tractable. In particular, in the rest of the section we shall study qualitative as well as structural restrictions.

5.1. Qualitative restrictions

The first natural restriction pertains the social factors associated with the agents in $A$ . Indeed, the careful reader might have already noticed that all intractability results derived so far assume $α_{i} < 1$ , for each $A_{i} \in A$ , and $α_{i} \neq 0$ when the egalitarian social welfare is considered. We now show that the problems are tractable, when they are confined over these extreme cases.

Theorem 5.
For each $X \in {UT, EG}$ , problems x - Check , x - Existence , x - CS-Existence , and x - Maximal are tractable on sets $A$ with $α_{i} = 1$ , $\forall A_{i} \in A$ . The latter three problems are also tractable for $α_{i} = 0$ , $\forall A_{i} \in A$ , if $X = EG$ .
Proof.
For an agent $A_{i} \in A$ , we have $\hat{u_{i}} (σ, C) = | neigh (A_{i}, C) | / | neigh (A_{i}, A) |$ , since $α_{i} = 1$ . This means that for the agent, it is convenient to stay together with all the other agents in $A$ , by getting 1 as utility, no matter of the given interpretation and the semantics adopted for the social welfare.

Finally, for the egalitarian social welfare, note that if $α_{i} = 0$ , then by staying alone, agent $A_{i}$ can always get the utility 1. Therefore, in this case, all problems are actually immaterial, but x-Check where the coalition is actually a-priori given and, in fact, intractability has already emerged (cf. Theorem 1). □

Another interesting restriction is analyzed below about the language used for representing the utility functions, which similarly to the above case leads to a monotonic behavior and, ultimately, to tractability. Theorem 6.
For each $X \in {UT, EG}$ , problems x - Check , x - Existence , x - CS-Existence , and x - Maximal are tractable when negation is not allowed in the definition of the propositional formulas and all weights are non-negative.
Proof.
Consider the interpretation $σ^{}$ mapping each propositional variable to true. In the given setting, for an agent $A_{i} \in A$ , it is immediate to check that $u_{i} (σ^{}) = 1$ , since the agent is also known to be normalized. Therefore, $\hat{u_{i}} (σ^{*}, C) = α_{i} \times | neigh (A_{i}, C) | / | neigh (A_{i}, A) | + (1 - α_{i})$ . Hence, the maximum is again achieved when all agents stay together, no matter of the given interpretation and the semantics adopted for the social welfare. □

5.2. Structural restrictions

Many $NP$ -hard problems are known to be efficiently solvable when restricted to instances whose underlying structures can be modeled via acyclic graphs.

More generally, practical instances while being not properly acyclic are often not very intricate and exhibit some rather limited degree of cyclicity, which suffices to retain most of the nice properties of acyclic instances. Indeed, many efforts have been spent to investigate graph properties that are best suited to identify nearly-acyclic graph, leading to the definition of a number of structural decomposition methods (see, e.g., [53]). The goal of this section is to check whether these methods are effective to identify islands of tractability also in our setting defined for reasoning in social environments.

Actually, before going on with the formalization, we observe that there is no hope to exploit these methods if reasoning with one single agent is already an intractable problem. Therefore, to keep confined the intrinsic complexity of this task, we consider agents with bounded reasoning capabilities. Formally, for any fixed natural number $h > 0$ , we say that a set $A$ is h-bounded if $| dom (A_{i}) | ⩽ h$ holds, for each $A_{i} \in A$ , and if an edge ${A_{i}, A_{j}}$ is in the interaction graph $IG (A)$ if, and only if, $dom (A_{i}) \cap dom (A_{j}) = \emptyset$ – note that the latter condition is meant to provide a natural semantics to the edges of the interaction graph.

By focusing on h-bounded agents, we shall consider the concept of treewidth [78] as the reference measure of graph acyclicity. Indeed, there are different possible notions to measure how far a graph is from a tree, that is, to measure its degree of cyclicity or, dually, its tree-likeness (see, e.g., [54]). Among them, the treewidth is provably the most powerful one, in that it is able to extend the nice computational properties of trees to the largest possible classes of graphs, in many applications from different fields.

For the sake of completeness, we recall that a tree decomposition of a graph $G = (N, E)$ is a pair $⟨ T, χ ⟩$ , where $T = (V, F)$ is a tree, and χ is a labeling function assigning to each vertex $p \in V$ a set of vertices $χ (p) \subseteq N$ , such that the following three conditions are satisfied: (1) for each node b of G, there exists $p \in V$ such that $b \in χ (p)$ ; (2) for each edge $(b, d) \in E$ , there exists $p \in V$ such that ${b, d} \subseteq χ (p)$ ; and (3) for each node b of G, the set ${p \in V ∣ b \in χ (p)}$ induces a connected subtree of T. The width of $⟨ T, χ ⟩$ is the number ${max}_{p \in V} (| χ (p) | - 1)$ . The treewidth of G, denoted by $t w (G)$ , is the minimum width over all its tree decompositions. In fact, treewidth is a true generalization of graph acyclicity. Indeed, a graph G is acyclic if, and only if, $t w (G) = 1$ .

Now, all definitions are in place to state the main result of this section, which refers to the tractability of the reasoning problems we have defined over the utilitarian social welfare and over interaction graphs having bounded treewidth – the proposed proof method cannot be immediately generalized to deal with the egalitarian social welfare, so that checking whether that setting is tractable over bounded treewidth interaction graphs remains an interesting technical question to be addressed in further research.

Theorem 7.
Let h and k be fixed natural numbers. Then, problems ut-Check , ut-Existence , ut-CS-Existence , and ut-Maximal are tractable on h-bounded sets $A$ such that $t w (IG (A)) ⩽ k$ .

In order to establish the above result, we notice that the proofs of ut-CS-Existence and ut-Existence can be derived by applying the methods recently proposed by [56], where a general framework to derive complexity results for coalition formation processes (even under additional constraints) has been defined and analyzed, with special care for tree-like structural restrictions. Moreover, we notice that ut-Maximal can be easily solved by using polynomial time oracles for ut-Check and (a simple variant of) ut-Existence, so that the corresponding proof again easily follows from the machineries in [56].

Hence, we next focus on the proof of ut-Check, where a coalition C of interest is given at hand (rather than being looked for).
5.3. Proof of Theorem 7: ut-Check

The proof approach uses, as a technical tool, results about structurally tractable constraint satisfaction problems (CSPs). This is a well-known method to prove tractability results over structures having bounded treewidth. The method has been used in a number of different contexts (see, e.g., [53]) and even to derive structural tractability results for problems related to coalition structure generation (see, e.g., [56]).

Here, we apply the method to the case of the problem ut-Check. For the sake of completeness, we first present CSPs and then show how our problem can be encoded as CSPs to derive the claimed result.

Preliminaries CSPs. We start with some preliminaries on constraint satisfaction. The reader interested in expanding on this formalism is referred to [37].

A constraint satisfaction problem instance is a triple $J = ⟨ Var, U, C ⟩$ , where $Var$ is a finite set of variables, U is a domain of values, and $C = {C_{1}, C_{2}, \dots, C_{q}}$ is a finite set of constraints. Each constraint $C_{v}$ , for $1 ⩽ v ⩽ q$ , is a pair $(S_{v}, r_{v})$ , where $S_{v} \subseteq Var$ is a set of variables called the constraint scope, and $r_{v}$ is a set of substitutions from variables in $S_{v}$ to values in U indicating the allowed combinations of simultaneous values for the variables in $S_{v}$ . A substitution θ satisfies a constraint $C_{v}$ if its restriction to $S_{v}$ occurs in $r_{v}$ . A solution to $J$ is a substitution $θ : Var \mapsto U$ for which q substitutions $t_{1} \in r_{1}, \dots, t_{q} \in r_{q}$ exist such that $θ = t_{1} \cup \dots \cup t_{q}$ . Thus, a solution satisfies all constraints.

A weighted CSP (short: WCSP) instance consists of a tuple $⟨ J, w_{r_{1}}, \dots, w_{r_{q}} ⟩$ , where $J = ⟨ Var, U, C ⟩$ with $C = {C_{1}, C_{2}, \dots, C_{q}}$ is a CSP instance, and where, for each $t_{v} \in r_{v}$ , $w_{r_{v}} (t_{v}) \in Q$ denotes the weight associated with $t_{v}$ . For a solution $θ = t_{1} \cup \dots \cup t_{q}$ to $J$ , we define $w (θ) = \sum_{v = 1}^{q} w_{r_{v}} (t_{v})$ its associated weight. An optimal solution to $⟨ J, w_{r_{1}}, \dots, w_{r_{q}} ⟩$ is a solution θ to $J$ such that $w (θ) ⩾ w (θ^{'})$ , for each solution $θ^{'}$ to $J$ .

From ut-Check to CSPs. With any coalition $C \subseteq A$ of h-bounded agents, we associate the CSP instance $CSP (C) = ⟨ Var, U, C ⟩$ defined as follows. For each agent $A_{i} \in C$ and for each variable $X \in dom (A_{i})$ , $Var$ contains the variable $X_{i}$ ; the domain U consists of the Boolean values $true$ and $false$ ; for each agent $A_{i} \in C$ , C contains the constraint $C_{i} = ({X_{i} ∣ X \in dom (A_{i})}, r_{i})$ where $r_{i}$ contains all possible substitutions for the variables in the scope; moreover, for each pair of agents $A_{i} \in C$ and $A_{j} \in C$ such that $A_{i} \in neigh (A_{j}, A)$ , i.e., such that they are neighbors in the scenario, C contains the constraint $C_{i, j} = (S_{i, j}, r_{i, j})$ where $S_{i, j} = {X_{i}, X_{j}}$ and where $r_{i, j}$ is the set of all substitutions θ such that $θ (X_{i}) = θ (X_{j})$ ; no further constraint is in C.

Since the scenario is h-bounded, it can be easily checked that the construction of the above CSP instance is feasible in polynomial time – indeed, note that h is a fixed natural number.

Concerning the properties of the encoding, instead, we can just observe that, because of the constraints having the form $C_{i, j}$ , any solution θ corresponds to an interpretation over $dom (C)$ , as formalized below. Let $θ_{C}$ denote the function mapping each variable $X \in dom (C)$ to the value $θ (X_{i})$ , with i being the minimum index over the agents in C such that $A_{i} \in C$ and $X \in dom (A_{i})$ hold. Clearly enough, $θ_{C}$ is an interpretation over C.

Fact 1.
If θ is a solution to $CSP (C)$ , then $θ_{C}$ is an interpretation over C by definition.

On the other hand, every interpretation can be derived from some solution.
Lemma 1.
For each interpretation σ over C, there is a solution θ to $CSP (C)$ such that $σ = θ_{C}$ .
Proof.
Let σ be an interpretation and consider the substitution θ such that, for each agent $A_{i} \in C$ and variable $X \in dom (A_{i})$ , $θ (X_{i}) = σ (X)$ . By construction, θ satisfies all constraints in C and is such that $σ = θ_{C}$ . □

In order to complete the analysis, we now define $WCSP (C)$ as the weighted CSP instance whose underlying CSP instance is $CSP (C)$ and where each constraint relation $r_{i}$ is equipped with the function $w_{r_{i}}$ defined as follows. For each substitution $θ \in r_{i}$ , $w_{r_{i}} (θ) = (1 - α) \times u_{i} (θ_{C})$ . Moreover, $w_{r_{i, j}} (θ) = α \times \frac{1}{| neigh (A_{i}, A) |}$ . In all the other cases, w is the constant function mapping all interpretations to 0. By definition, it is immediate that the following holds.
Lemma 2.
Let θ be a solution to $CSP (C)$ . Then, $w (θ) = \sum_{A_{i} \in C} \hat{u_{i}} (θ_{C}, C)$ .

In the light of the above fact and two lemmas, the problem of finding an interpretation σ over $dom (C)$ whose associated utilitarian social welfare $UT (σ, C)$ is greater than a given threshold γ is restated in terms of finding a solution θ to $CSP (C)$ such that $w (θ) ⩾ γ$ .

Therefore, to complete the proof, we can show that computing an optimal solution to a weighted CSP instance is feasible in polynomial time. In fact, that problem is $NP$ -hard in general, but it is known to be tractable over instances having bounded treewidth. In particular, the structure of an instance $J$ is defined as the graph $G (J)$ whose nodes are the variables and where an edge occurs between two variables if they occur together in the scope of some constraint (see, e.g., [52]). Hence, the proof is completed by considering the result below. Lemma 3.
Let $A$ be a set of h-bounded agents and let $C \subseteq A$ be a coalition with $t w (IG (A)) ⩽ k$ . Then, $t w (G (CSP (C))) < h \times (k + 1)$ .
Proof.
Let $⟨ T, χ ⟩$ be a tree decomposition of $(IG (A))$ , and consider the labeling function $χ^{'}$ such that: For each vertex p of T, if $A_{i} \in χ (p) \cap C$ , then $χ^{'} (p)$ includes all variables in the scope of the constraint $C_{i}$ (hence, h variables at most). It can be checked that $⟨ T, χ^{'} ⟩$ is a tree decomposition of $G (CSP (A))$ .

In particular, note that the connectedness condition of tree decompositions follows by the condition of h-bounded agents prescribing that an edge ${A_{i}, A_{j}}$ is in the interaction graph $IG (A)$ if, and only if, $dom (A_{i}) \cap dom (A_{j}) = \emptyset$ . To conclude, note that the width of $⟨ T, χ^{'} ⟩$ is clearly bounded by $h \times (k + 1) - 1$ , where k is the width of $⟨ T, χ ⟩$ . □

6. Algorithms for reasoning about the utilitarian social welfare

In this section, we define concrete strategies to address the most basic reasoning problems we have defined and analyzed so far, namely ut-Check and ut-Existence. In fact, we go beyond by considering their optimization versions, where the goal is to compute an assignment/coalition with the maximum possible utilitarian social welfare.

Our algorithmic approach is to take advantage of efficient pseudo-Boolean solvers, by associating a given set $A$ of normalized agents, whose interaction graph is $IG (A) = (A, E)$ , with a pseudo-Boolean theory $Γ_{A}$ .

Let us first recall a few preliminary notions on pseudo-Boolean theories (see, e.g., [41]).

6.1. Preliminaries on pseudo-Boolean theories

A pseudo-Boolean function f is of the following form: $w_{1} \cdot φ_{1} + \dots + w_{n} \cdot φ_{n}$ , where n and $w_{i}$ ( $i \in [1.. n]$ ) are rational numbers, while $φ_{i}$ ( $i \in [1.. n]$ ) is a Boolean formula. Let $pairs (f)$ be the set ${⟨ φ_{i}, w_{i} ⟩ ∣ i [1.. n]}$ .

A pseudo-Boolean constraint ψ is of the form $f ⩾ k$ , where f is a pseudo-Boolean function, and k is a rational number. Let $pairs (ψ)$ be the set $pairs (f)$ , and $bound (ψ)$ be the rational number k. A pseudo-Boolean theory Γ is a set of pseudo-Boolean constraints. To ease the presentation, pseudo-Boolean constraints of the form $1 \cdot φ ⩾ 1$ will be simply denoted as φ, that is, Γ may include Boolean formulas.

An assignment σ maps each pseudo-Boolean function f to the following rational number: $\begin{matrix} σ (f) = \sum_{⟨ φ, w ⟩ \in pairs (f)} w \cdot σ (φ), \end{matrix}$ where $σ (φ)$ equals 1 if $σ ⊧ φ$ , and 0 otherwise. For a pseudo-Boolean constrain ψ, $σ ⊧ ψ$ if the following inequality is satisfied: $\begin{matrix} σ (ψ) = \sum_{⟨ φ, w ⟩ \in pairs (ψ)} w \cdot σ (φ) ⩾ k . \end{matrix}$ For a pseudo-Boolean theory Γ, $σ ⊧ Γ$ if $σ ⊧ ψ$ for all $ψ \in Γ$ . In this case, σ is called a model of Γ.

Example 8.
Consider a pseudo-Boolean theory Γ consisting of the following pseudo-Boolean constraint: $\begin{matrix} 5 \cdot X_{1} + 3 \cdot X_{2} + 2 \cdot X_{3} + 1 \cdot X_{4} ⩾ 6 . \end{matrix}$ The models of Γ are ${X_{1}, X_{2}}$ , ${X_{1}, X_{3}}$ , ${X_{1}, X_{4}}$ , ${X_{2}, X_{3}, X_{4}}$ , and their supersets.

In some cases, pseudo-Boolean theories Γ can be equipped with a pseudo-Boolean function f to be maximized. In this case, we say that a model σ is optimal w.r.t. f if there is no model $σ^{'}$ such that $f (σ^{'}) > f (σ)$ .
6.2. Pseudo-Boolean encodings for ut-Check

Recall that ut-Check is the problem of deciding whether, given a legal coalition $C \subseteq A$ and a threshold γ, it is the case that $UT - V AL (C) ⩾ γ$ holds.

Based on $A$ , our encoding strategy builds a theory $Γ_{A}$ which has variables $C_{i}$ , for each agent $A_{i} \in A$ , and variables $E_{i j}$ for each edge ${A_{i}, A_{j}}$ in the underlying interaction graph $IG (A) = (A, E)$ . Intuitively, $C_{i}$ is intended to be true whenever agent $A_{i}$ belongs to coalition C, while $E_{i j}$ is intended to be true whenever $A_{j} \in neigh (A_{i}, C)$ . Hence, variables $C_{i}$ are fixed to a specific value according to the coalition C given in input, and variables $E_{i j}$ are defined in terms of $C_{i}$ and $C_{j}$ ; specifically, $Γ_{A}$ contains the following constraints: $\begin{array}{l} (1) & C_{i} \forall A_{i} \in C; \\ (2) & \neg C_{i} \forall A_{i} \in A ∖ C; \\ (3) & E_{i j} \leftrightarrow C_{i} \land C_{j} \forall {A_{i}, A_{j}} \in E . \end{array}$

Concerning utility functions, for every agent $A_{i} \in A$ , $u_{i}$ and ${\hat{u}}_{i}$ can be restated as follows: $\begin{array}{l} u_{i} = \sum_{⟨ φ, w ⟩ \in A_{i}} w \cdot φ; \\ \begin{matrix} {\hat{u}}_{i} & = \sum_{A_{j} \in neigh (A_{i}, A)} \frac{α_{i}}{| neigh (A_{i}, A) |} \cdot E_{i j} \\ + \sum_{⟨ φ, w ⟩ \in A_{i}} (1 - α_{i}) \cdot w \cdot φ . \end{matrix} \end{array}$

In particular, note that in the above expressions the coalition C provided as input to ut-Check is directly encoded in the definition of the utility functions. Therefore, ${\hat{u}}_{i}$ is actually a function mapping assignments to rational numbers – that is, both $u_{i}$ and ${\hat{u}}_{i}$ are pseudo-Boolean functions. In more detail, the number of neighbors of $A_{i}$ is a constant fixed by the interaction graph $IG (A)$ , while the number of neighbors in the induced interaction graph is given by the variables $E_{i j}$ such that $σ (E_{i j}) = 1$ ; constants $α_{i}$ and $1 - α_{i}$ are finally pushed in the formula so to obtain a pseudo-Boolean representation. With the above encoding at hand, $Γ_{A}$ finally includes the following pseudo-Boolean constraint: $\begin{matrix} (4) & \sum_{A_{i} \in A} {\hat{u}}_{i} (σ) ⩾ γ . \end{matrix}$

It is immediate to check that the theory $Γ_{A}$ , built according to (1)–(4) above, admits a model if, and only if, $UT - V AL (C) ⩾ γ$ holds.

Example 9.
Consider the setting of Example 3, that is, agents $A = {A_{1}, A_{2}, A_{3}}$ with interactions $E = {{A_{1}, A_{2}}, {A_{2}, A_{3}}}$ , $α_{1} = α_{3} = 0$ and $α_{2} = 1$ . Let X be a Boolean variable denoting whether the agents go to the cinema and observe that $Γ_{A}$ is the following: $\begin{array}{l} E_{12} \leftrightarrow C_{1} \land C_{2} \\ E_{23} \leftrightarrow C_{2} \land C_{3} \\ \underset{{\hat{u}}_{1}}{\underset{︸}{1 \cdot X}} + \underset{{\hat{u}}_{2}}{\underset{︸}{\frac{1}{2} \cdot E_{12} + \frac{1}{2} \cdot E_{23}}} + \underset{{\hat{u}}_{3}}{\underset{︸}{1 \cdot X}} ⩾ γ \end{array}$ plus formulas encoding the input coalition C.

For example, if C is ${A_{2}}$ , then $Γ_{A}$ contains $\neg C_{1}$ , $C_{2}$ , and $\neg C_{3}$ ; in this case, any model σ of $Γ_{A}$ is such that $σ (E_{12}) = σ (E_{23}) = 0$ , so that the pseudo-Boolean constraint associated with utility functions can be simplified as $2 \cdot X ⩾ γ$ .

For C being ${A_{1}, A_{2}, A_{3}}$ , instead, $Γ_{A}$ contains $C_{1}$ , $C_{2}$ , $C_{3}$ ; in this case, any model σ of $Γ_{A}$ is such that $σ (E_{12}) = σ (E_{23}) = 1$ , so that the pseudo-Boolean constraint associated with utility functions can be simplified as $2 \cdot X ⩾ γ - 1$ .

We leave the section by noticing that the natural optimization variant of ut-Check is to ask for the interpretation over the coalition C maximizing the utilitarian value. To model this problem, constraint (4) is not added to $Γ_{A}$ , and the following objective function is considered to be maximized: $\begin{matrix} (5) & \sum_{A_{i} \in A} {\hat{u}}_{i} (σ) . \end{matrix}$ Example 10.
Continuing Example 9, for $C = {A_{2}}$ the objective function is $2 \cdot X$ and the optimum is 2, for σ such that $σ (X) = 1$ . For $C = {A_{1}, A_{2}, A_{3}}$ , instead, the objective function is $2 \cdot X + 1$ and the optimum is 3, for σ such that $σ (X) = 1$ .

6.3. Pseudo-Boolean encodings for ut-Existence

Let us now move to presenting an encoding for the problem ut-Existence. In this case, the only inputs are the threshold γ and the set $A$ of agents. Based on $A$ , we build a theory $Γ_{A}$ (again) over the variables $C_{i}$ and $E_{i j}$ . Additionally, $Γ_{A}$ has variables $C_{i}^{k}$ , for each $A_{i} \in A$ and $k \in [1.. | A |]$ , whose intent is to discard illegal coalition. More formally, as in the previous encoding, $Γ_{A}$ contains the following constraints: $\begin{matrix} (6) & E_{i j} \leftrightarrow C_{i} \land C_{j} \forall {A_{i}, A_{j}} \in E . \end{matrix}$

Variables $C_{i}$ are left free, so that coalition C can be guessed (rather than being pre-fixed as in the encoding of ut-Check). Moreover, legality of C is enforced by the following formulas added to $Γ_{A}$ , for each $A_{i} \in A$ : $\begin{array}{l} (7) & C_{i} \to C_{i}^{| A |} \\ (8) & C_{i}^{k + 1} \to C_{i}^{k} \lor \underset{A_{j} \in neigh (A_{i}, A)}{⋁} C_{j}^{k} \forall k < | A | \\ (9) & C_{i}^{1} \to \neg C_{1} \land \dots \land \neg C_{i - 1} \land C_{i} \\ (10) & \neg C_{i} \to \neg C_{i}^{k} \forall k < | A | \end{array}$

Intuitively, variables $C_{i}^{k}$ are used to mark reachable agents from a starting agent. The starting agent is the agent $A_{i}$ in C with the smallest index, which is captured by the third formula above. Hence, for each coalition C, there is only one i such that $C_{i}^{1}$ is true. After that, agents in the neighborhood of the reached agents at step k are reached at step $k + 1$ , which is encoded by the second formula above, while the first formula above enforces that all agents in the coalition are reached at step $A$ (note that a fixed point for the set of reached agents must be reached in at most $A$ steps). Finally, all $C_{i}^{k}$ are assigned false whenever $C_{i}$ is false because of the last formula above.

As in the previous encodings, for the decisional problem, the theory $Γ_{A}$ built over (6)–(10) is extended with (4), while for the optimization problem the objective function (5) is considered to be maximized. The correctness of the encoding is immediately seen, and an example is discussed below.

Example 11.
Consider the setting of Example 3. Then, $Γ_{A}$ is the following: $\begin{array}{l} E_{12} \leftrightarrow C_{1} \land C_{2} \\ E_{23} \leftrightarrow C_{2} \land C_{3} \\ \underset{{\hat{u}}_{1}}{\underset{︸}{1 \cdot X}} + \underset{{\hat{u}}_{2}}{\underset{︸}{\frac{1}{2} \cdot E_{12} + \frac{1}{2} \cdot E_{23}}} + \underset{{\hat{u}}_{3}}{\underset{︸}{1 \cdot X}} ⩾ γ \end{array}$ plus the following formulas to enforce legal coalitions: $\begin{matrix} C_{1} \to C_{1}^{3} & \neg C_{1} \to \neg C_{1}^{1} \\ C_{1}^{3} \to C_{1}^{2} \lor C_{2}^{2} & \neg C_{1} \to \neg C_{1}^{2} \\ C_{1}^{2} \to C_{1}^{1} \lor C_{2}^{1} & \neg C_{1} \to \neg C_{1}^{3} \\ C_{1}^{1} \to C_{1} \\ C_{2} \to C_{2}^{3} & \neg C_{2} \to \neg C_{2}^{1} \\ C_{2}^{3} \to C_{2}^{2} \lor C_{1}^{2} \lor C_{3}^{2} & \neg C_{2} \to \neg C_{2}^{2} \\ C_{2}^{2} \to C_{2}^{1} \lor C_{1}^{1} \lor C_{3}^{1} & \neg C_{2} \to \neg C_{2}^{3} \\ C_{2}^{1} \to \neg C_{1} \land C_{2} \\ C_{3} \to C_{3}^{3} & \neg C_{3} \to \neg C_{3}^{1} \\ C_{3}^{3} \to C_{3}^{2} \lor C_{2}^{2} & \neg C_{3} \to \neg C_{3}^{2} \\ C_{3}^{2} \to C_{3}^{1} \lor C_{2}^{1} & \neg C_{3} \to \neg C_{3}^{3} \\ C_{3}^{1} \to \neg C_{1} \land \neg C_{2} \land C_{3} \end{matrix}$ Note that for σ such that $σ (C_{1}) = σ (C_{2}) = σ (C_{3}) = 1$ , if σ is a model of the above formulas then the following literals are necessarily assigned 1: $C_{1}^{1}$ , $\neg C_{2}^{1}$ , $\neg C_{3}^{1}$ , $C_{1}^{2}$ , $C_{2}^{2}$ , $\neg C_{3}^{2}$ , $C_{1}^{3}$ , $C_{2}^{3}$ , and $C_{3}^{3}$ . Indeed, σ encodes a legal coalition: starting from $A_{1}$ , we can first reach $A_{2}$ , and then $A_{3}$ . On the other hand, for σ such that $σ (C_{1}) = σ (C_{3}) = 1$ , and $σ (C_{2}) = 0$ , the following literals should be true: $C_{1}^{1}$ , $\neg C_{2}^{1}$ , $\neg C_{3}^{1}$ , $C_{1}^{2}$ , $\neg C_{2}^{2}$ , $\neg C_{3}^{2}$ , $C_{1}^{3}$ , $\neg C_{2}^{3}$ , $\neg C_{3}^{3}$ , and $C_{3}^{3}$ . Since $\neg C_{3}^{3}$ and $C_{3}^{3}$ cannot be both true, it turns out that σ cannot be extended to a model: In this case, σ encodes an illegal coalition.

For γ being 3, the only model of $Γ_{A}$ corresponds to the coalition ${A_{1}, A_{2}, A_{3}}$ , and assigns true to X, that is, agents go to the cinema. This is also the optimum model for the encoding associated with the optimization variant of the problem.

7. Algorithms for reasoning about the egalitarian social welfare

In this section, we consider encoding strategies for the counterparts, over the egalitarian social welfare, of the problems already considered in Section 6. Actually, it can be observed that decision problems can be addressed by pseudo-Boolean encodings similar to those we have already discussed. In particular, under the egalitarian social welfare, it suffices to replace the pseudo-Boolean constraint (4) with the following set of constraints: $\begin{matrix} {\hat{u}}_{i} (σ) ⩾ γ \forall A_{i} \in A . \end{matrix}$

More care is needed, instead, for the optimization variants, in which we would like to replace the objective function (5) with the following nonlinear function: $\begin{matrix} min_{A_{i} \in A} {\hat{u}}_{i} (σ) . \end{matrix}$

Example 12.
For the setting of Example 3, and for a given γ, the encodings presented in Examples 9–11 are modified by replacing the constraint associated with utility functions with the following set of constraints: $\begin{array}{l} 1 \cdot X ⩾ γ (for A_{1} and A_{3}) \\ \frac{1}{2} \cdot E_{12} + \frac{1}{2} \cdot E_{23} ⩾ γ (for A_{2}) \end{array}$ Hence, when $γ = 1$ , the only model of $Γ_{A}$ corresponds to the coalition ${A_{1}, A_{2}, A_{3}}$ , and assigns true to X, that is, agents go to the cinema. This is also the optimum model for the encoding associated with the optimization variant of the problem.

Now, the main problem emerging with the use of the nonlinear encoding is that this is a kind of feature that is currently not supported by existing pseudo-Boolean solvers. Consequently, specific solution approaches have to be proposed to deal with the optimization problem under the egalitarian semantics.

In the rest of the section, we face this problem and we present algorithms (linear, binary, and progression search) that are capable of supporting natively the form of fair optimization related to the maximization of the minimum value over a given set of functions.
7.1. Formal framework for fair optimization

We consider a general setting where the input consists of a pair $⟨ Γ, O ⟩$ , with Γ being a pseudo-Boolean theory, and O being a set of pseudo-Boolean objective functions. The goal is to compute a model $σ^{*}$ of Γ (i.e., $σ^{*} ⊧ Γ$ ) that maximizes ${min}_{o \in O} σ (o)$ .

In the following, all numbers in $⟨ Γ, O ⟩$ are assumed to be positive integers; that is, rational numbers have been normalized previously via algebraic manipulations of pseudo-Boolean constraints and functions.

Example 13.
Consider the pseudo-Boolean constraints in Example 12. For $γ = \frac{2}{3}$ , they are equivalent to the following constraints: $\begin{matrix} 6 \cdot X ⩾ 4 3 \cdot E_{12} + 3 \cdot E_{23} ⩾ 4 \end{matrix}$ obtained by multiplying all numbers by 6, the least common multiple of all denominators.

In the algorithms presented in this section, intermediate solutions are obtained by means of calls to a pseudo-Boolean solver (PBS) oracle. Formally, for a set of constraints Γ, and a set of assumptions $A \subseteq V$ , let $solve (Γ, A)$ be a function returning an interpretation σ such that both $σ ⊧ Γ$ and $σ (X) = 1$ for all $X \in A$ , if such a σ does exist; otherwise, $solve (Γ, A)$ returns ⊥. The algorithms presented in this section are such that all calls to function $solve$ share the same set of constraints, which is thus fixed at the beginning of the computation, and only the set of assumptions vary at each call.

A key ingredient for the definition of such procedures is the representation of objective functions as pseudo-Boolean constraints. Specifically, for a pseudo-Boolean objective function o, the pseudo-Boolean representation of o, denoted $pb (o)$ , is defined as follows: $\begin{matrix} (11) & \sum_{⟨ φ, w ⟩ \in pairs (o)} w \cdot φ + \sum_{i = 0}^{⌊ {log}_{2} t ⌋} 2^{i} \cdot \neg S^{i} ⩾ t \end{matrix}$ where $t = \sum_{⟨ φ, w ⟩ \in pairs (o)} w$ , and each $S^{i}$ is a fresh variable called selector. Moreover, for any $n \in N$ , we hereinafter use $ge (o, n)$ to denote the following set of assumptions: $\begin{array}{l} {\neg S^{i} ∣ i \in [0.. ⌊ {log}_{2} t ⌋], ⌊ (t - n) / 2^{i} ⌋ mod 2 ≢ 0} \\ \cup {S^{i} ∣ i \in [0.. ⌊ {log}_{2} t ⌋], ⌊ (t - n) / 2^{i} ⌋ mod 2 \equiv 0} \end{array}$ which essentially fix the interpretation of selector variables so that (11) becomes equivalent to the following constraint: $\begin{matrix} \sum_{⟨ φ, w ⟩ \in pairs (o)} w \cdot φ ⩾ n . \end{matrix}$ Example 14.
Consider the following objective functions: $\begin{array}{l} o_{1} = 3 \cdot X_{1} + 2 \cdot X_{2} + 1 \cdot X_{3} \\ o_{2} = 1 \cdot X_{1} + 1 \cdot X_{2} + 5 \cdot X_{3} \end{array}$ and their pseudo-Boolean representation: $\begin{array}{l} \begin{matrix} pb (o_{1}) & = 3 \cdot X_{1} + 2 \cdot X_{2} + 1 \cdot X_{3} \\ + 1 \cdot \neg S_{1}^{0} + 2 \cdot \neg S_{1}^{1} + 4 \cdot \neg S_{1}^{2} ⩾ 6 \end{matrix} \\ \begin{matrix} pb (o_{2}) & = 1 \cdot X_{1} + 1 \cdot X_{2} + 5 \cdot X_{3} \\ + 1 \cdot \neg S_{2}^{0} + 2 \cdot \neg S_{2}^{1} + 4 \cdot \neg S_{2}^{2} ⩾ 7 \end{matrix} \end{array}$ Note that the assumptions $ge (o_{1}, 5) = {\neg S_{1}^{0}, S_{1}^{1}, S_{1}^{2}}$ and $ge (o_{2}, 5) = {S_{2}^{0}, \neg S_{2}^{1}, S_{2}^{2}}$ correctly set the above constraints to enforce the satisfaction of $3 \cdot X_{1} + 2 \cdot X_{2} + 1 \cdot X_{3} ⩾ 5$ and $1 \cdot X_{1} + 1 \cdot X_{2} + 5 \cdot X_{3} ⩾ 5$ .

7.2. Linear search

The intuition behind linear search is to compute a possibly non-optimal solution, and then iteratively ask for new solutions of better weight, until the weight of the current solution cannot be further improved. At that point, an interpretation of optimum weight is found.

Algorithm 1:

Linear Search

Algorithm 1 is the proposed linear search procedure. Initially, the set Γ of clauses is extended by adding the pseudo-Boolean representation of all objective functions in O (line 2). Moreover, the current solution is stored in variable $σ^{*}$ , and the associated utility in $lb$ , initially set to ⊥ and $- 1$ , respectively (line 3). Variable $ub$ , instead, is used to store the maximum possible utility, that is, the minimum sum of weights among the objective functions. At this point, a first solution is searched by calling function $solve$ (line 5). Note that assumptions are set so to improve the current lower bound, if possible. Indeed, if a new solution is found, its stored in variable $σ^{*}$ , and its weight is used to update $lb$ (line 7). Otherwise, if no solution exists, then the upper bound is set to the $lb$ (line 6). The process is repeated until the two bounds coincide, meaning that the current lower bound cannot be further improved.

Example 15.

Consider the setting of Example 3 and the optimization variant of the problem eg-Check for the coalition ${A_{1}, A_{2}, A_{3}}$ . Algorithm 1 starts by adding the pseudo-Boolean representation of the (normalized) objective functions: $\begin{array}{l} 2 \cdot X + 1 \cdot \neg S_{1}^{0} + 2 \cdot \neg S_{1}^{1} ⩾ 2 \\ 1 \cdot E_{12} + 1 \cdot E_{23} + 1 \cdot \neg S_{2}^{0} + 2 \cdot \neg S_{2}^{1} ⩾ 2 \end{array}$ Variable $lb$ is set to $- 1$ , and variable $ub$ to 2. A first solution is thus searched, with the assumptions set to ${S_{1}^{0}, \neg S_{1}^{1}, S_{2}^{0}, \neg S_{2}^{1}}$ so to trivially satisfy the two constraints above. One is actually found, say σ such that $σ (X) = 0$ , and $σ (E_{12}) = σ (E_{23}) = 1$ . Hence, the lower bound $lb$ is set to 1, and a new solution is searched; this time, assumptions are set to ${S_{1}^{0}, S_{1}^{1}, S_{2}^{0}, S_{2}^{1}}$ so that the above constraints are equivalent to $\begin{array}{l} 2 \cdot X + 1 \cdot ⩾ 2 \\ 1 \cdot E_{12} + 1 \cdot E_{23} ⩾ 2 \end{array}$ A model is eventually found, say σ such that $σ (X) = σ (E_{12}) = σ (E_{23}) = 1$ . Hence, $lb$ is set to 2 and the algorithm terminates.

7.3. Binary search

Binary search requires to store a lower bound and an upper bound, so that the call to the PBS oracle will check the existence of an interpretation whose weight is at least the mean of the two bounds. If such an interpretation does exist, then the lower bound is increased; otherwise, the upper bound is decreased. The process terminates when the two bounds coincide.

Algorithm 2:

Binary Search

Algorithm 2 is the proposed binary search procedure. Initially, lower bound $lb$ and upper bound $ub$ are set to $- 1$ and ${min}_{o \in O} \sum_{⟨ φ, w ⟩ \in pairs (o)} w$ , respectively (line 3). Hence, the upper bound represents the best possible utility that might be achieved, while the lower bound stores the utility of the current solution. A solution with utility greater than or equal to $(lb + ub + 1) / 2$ is then searched (line 5). If none is found, then the upper bound is decreased in line 6; otherwise, the new solution is stored (line 7). The process is repeated until the two bounds are equal, i.e., until an assignment of optimum utility is found.

7.4. Progression search

Progression search is similar to binary search. The main difference is that new solutions are not required to have utility greater than or equal to the mean of lower bound and upper bound, but instead a geometric progression is used.

Algorithm 3:

Progression Search

Algorithm 3 is the proposed procedure. Initially, the progression $pr$ is set to 1 (line 3). A solution with utility greater than or equal to $lb + pr$ is then searched (line 6). At each iteration, $pr$ is doubled (line 9), and possibly reset to 1 if $lb + pr$ exceeds $ub$ (line 5).

8. Implementation and evaluation

The encodings and algorithms discussed in the previous sections have been implemented and experimentation has been conducted to assess the scalability of the overall approach. Actually, the encodings discussed in Section 6 can be straightforwardly provided as input to a pseudo-Boolean solver and the nice scaling of the approach will emerge with no surprise, because of the scaling of the underlying solver. In the light of this observation, details on experimentation on this basic setting are hence omitted and we next focus on illustrating the behavior of our implementation under the egalitarian social welfare.

In fact, from the conceptual viewpoint, assessing the scalability under the egalitarian social welfare is even more relevant than focusing on the utilitarian social welfare, since our solver is the first one in the literature that explicitly supports forms of fair optimization. Therefore, the experimental analysis we shall discuss in this section is of interest even independently of the specific application domain considered in the paper. The analysis will be focused on encodings discussed in Section 7, with the three algorithms presented there being implemented in maxino [9], a PBS solver extending glucose 4.0 [12]. Pseudo-Boolean constraints are internally handled by maxino, similarly to clasp [49] and wasp [8].

8.1. Benchmark problems

In order to analyze the performances of the proposed algorithms on standard datasets (possibly taken from real-world applications), we focused our experimentation on optimization problems already considered in the literature. In fact, rather than considering standard optimization, we looked for the fair optimization required by the egalitarian social welfare. In particular, all problems have been modeled in our framework by considering egalitarian scenarios where the goal is to compute $EG$ -optimal interpretations over $A$ .

The first problem we considered in our experiments is referred to as Fair Movie Partitioning: Let M be a list of movies, where each movie m is associated with one or more genres. We considered a setting where we would like to compute an assignment corresponding to mapping movies in M to n persons such that the minimum number of genres covered by each person is maximized. Instances of this problem are obtained from the MovieLens Datasets [58], with $n \in {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}$ .

The second problem we considered is referred to as Fair Graph Partitioning: Let $G = (V, E)$ be a graph, and n be a positive integer. For a partition of V into n sets $V_{1}, \dots, V_{n}$ , the degree of connection of $V_{i}$ ( $i \in [1.. n]$ ) is defined as the number of edges connecting nodes in $V_{i}$ with nodes in $V ∖ V_{i}$ . Given G and n, our goal is to compute a partition $V_{1}, \dots, V_{n}$ such that the minimum degree of connection is maximized. Instances of this problem are obtained from some social network graphs in the Stanford Large Network Dataset Collection [67], for $n \in [2..16]$ .

Additional testcases were obtained from the crafted instances of the 2015 MaxSAT Evaluation: Soft clauses are distributed among n different agents, for $n \in {4, 8, 16}$ , so to obtain non-trivial synthetic instances. The goal is to compute a model such that the value of the minimum objective function is maximized.

8.2. Results

Experiments have been conducted on an Intel Xeon CPU 2.4 GHz with 16 GB of RAM. Time and memory were limited to 600 seconds and 15 GB, respectively. Resource usage is measured by pyrunlim,3

³
https://github.com/alviano/python/tree/master/pyrunlim

a Python tool also used in the latest ASP Competitions [26,27].

Table 1

Solved instances (S), average execution time (T, in seconds), and average memory consumption (M, in MB)

Dataset	LS			BS			PS

	S	T	M	S	T	M	S	T	M
ml-100k (11)	4	0.0	5	4	0.2	9	4	0.3	7
ml-1m (11)	5	0.3	28	5	0.3	26	5	5.3	35
ml-10m (11)	7	6.1	211	7	33.0	233	7	19.7	247
ml-20m (11)	6	9.2	306	8	43.3	949	7	11.3	526
ml-latest-small (11)	7	15.2	253	7	7.3	222	7	9.8	234
ml-latest (11)	7	23.5	649	7	14.2	649	7	15.1	649
ego-Facebook (15)	0	–	–	0	–	–	0	–	–
wiki-Vote (15)	0	–	–	0	–	–	0	–	–
CSG (30)	30	6.8	136	30	6.7	139	30	6.6	135
auctions (120)	115	10.8	13	114	33.7	27	114	19.2	18
causal-disc. (105)	104	45.3	94	105	17.2	91	104	23.8	92
frb (102)	32	14.7	31	32	11.6	26	32	18.8	35
min-enc (144)	140	0.1	7	140	0.1	7	140	0.1	6
PSeudo (36)	20	33.4	16	19	11.2	11	21	32.3	16
ramsey (45)	40	3.9	9	40	0.0	3	40	2.9	7
random-net (96)	47	13.2	17	47	4.7	7	47	3.3	6
set-covering (135)	76	4.1	17	80	12.2	19	79	7.9	17
wmaxcut (144)	19	8.1	11	21	28.1	20	22	65.0	27
TOT (1053 inst.)	662	13.5	45	666	13.5	55	666	13.4	48

Special care has been devoted to compare the performances of the three algorithms presented in Section 7. The overall results are reported in Table 1. The three algorithms have a similar performance in terms of solved instances: binary search and progression search solved the highest number of instances, 4 instances more than linear search. Also in terms of average execution time and memory usage the three algorithms have a similar performance. A better view on the execution time is provided by the cactus plot reported in Fig. 1. Indeed, the plot highlights that binary and progression searches are often faster than linear search in solving instances in our benchmark. A detaield view of the execution time of the three algorithms on Fair Movie Parititioning is given in Fig. 2, where it can be observed that binary and progression searches provide optimal values for instances involving up to 128 agents in 67% of the cases.

Fig. 1.

Cactus plot of the overall performance.

Fig. 2.

Fair Movie Partitioning: execution time for increasing number of agents.

As shown in Table 1, none of the implemented algorithms can solve instances of Fair Graph Partitioning in the allotted time. Nevertheless, the performance of the three algorithms on these instances is different in terms of suboptimal solutions provided to the user. Within this regards, Table 2 reports the weight of the best computed solution by the three algorithms on each instance of Fair Graph Partitioning. It is interesting to observe that binary search cannot provide any solution within the allotted time. The other two algorithms complement each other, as also shown in Fig. 3.

More details regarding the computation of suboptimal solutions are given by the plots in Fig. 4, where the time at which suboptimal solutions are provided to the user is also reported. It can be observed that progression search requires less invocations of the PBS solver, which however are sometimes really challenging to complete. This is the case, for example, of the instance of ego-Facebook for $n = 8$ , where the last completed invocation of the PBS solver required around 527 seconds of CPU time, still resulting in a solution worse than the one provided by linear search within the first 300 seconds of computation. Such challenging invocations to the PBS solver also explain why binary search does not provide any suboptimal solution for these instances: The sum of weights of the smallest instance of Fair Graph Partitioning is 88 234, and therefore binary search starts by looking for a solution of weight greater or equal than 44 117. Such a solution is unlikely to exist, and anyhow the PBS solver is unable to find it or to prove its nonexistence.

9. Related works

In the paper we have formalized and studied the process of amalgamating the preferences of the agents, formalized via weighted propositional logic, in a setting where they interact in a given social environment. On the one hand, our framework has been influenced by the large body of literature related to information and opinion diffusion that we have already discussed in the Introduction. On the other hand, the reasoning problems we have formalized and studied can be better positioned within the area of research that is devoted to the study of coalition formation in multi-agent systems. For the sake of completeness, we review in this section some of the literature in this field, by stressing the conceptual and technical differences of our approach w.r.t. earlier proposals.

According to a classical classification in the literature [79], coalition formation is a process that involves three distinct activities. The first activity is related to the fact that agents have to joint coalitions and form a coalition structure, either endogenously or being coordinated by a system designer. In both cases, we are usually interested in the coalition structures that enjoy desirable properties, such as optimizing the utilitarian social welfare or minimizing the agents’ incentive to deviate from their coalitions. The second activity is related to how the agents can coordinate in order to optimize the worth they can guarantee to themselves by collaborating with each other, rather than by acting in isolation. Finally, the third activity is related to dividing this worth according to distribution methods that can be perceived as fair and stable. The research discussed in this paper clearly fits the first of the above three activities. In abstract terms, this activity (known as coalition structure generation) can be defined over a pair $⟨ N, v ⟩$ , referred to as a coalitional game, where N is a set of agents and where v is a valuation function that, for each coalition $C \subseteq N$ returns the worth $v (C)$ that the members of C can jointly achieve by cooperating (see, e.g., [72,89]). The goal is very often to find an optimal coalition structure, i.e., a partition ${C_{1}, \dots, C_{k}}$ of the agents into disjoint and exhaustive coalitions whose total value $\sum_{i = 1}^{k} v (C_{i})$ is maximized.

Table 2
Fair Graph Partitioning: Weight of the best solution computed for instances of ego-Facebook and wiki-Vote

Instance n LS BS PS

ego-Facebook 2 89 – 290

ego-Facebook 3 153 – 373

ego-Facebook 4 10 – 241

ego-Facebook 5 434 – 227

ego-Facebook 6 67 – 160

ego-Facebook 7 180 – 8

ego-Facebook 8 112 – 77

ego-Facebook 9 55 – 37

ego-Facebook 10 234 – 64

ego-Facebook 11 160 – 0

ego-Facebook 12 67 – 67

ego-Facebook 13 38 – 66

ego-Facebook 14 62 – 0

ego-Facebook 15 2 – 6

ego-Facebook 16 15 – 0

wiki-Vote 2 770 – 533

wiki-Vote 3 353 – 5426

wiki-Vote 4 2212 – 2975

wiki-Vote 5 6828 – 1012

wiki-Vote 6 85 – 214

wiki-Vote 7 927 – 283

wiki-Vote 8 297 – 4146

wiki-Vote 9 198 – 61

wiki-Vote 10 72 – 1392

wiki-Vote 11 24 – 3

wiki-Vote 12 29 – 38

wiki-Vote 13 0 – 124

wiki-Vote 14 19 – 36

wiki-Vote 15 15 – 75

wiki-Vote 16 173 – 2

Instance	n	LS	BS	PS
ego-Facebook	2	89	–	290
ego-Facebook	3	153	–	373
ego-Facebook	4	10	–	241
ego-Facebook	5	434	–	227
ego-Facebook	6	67	–	160
ego-Facebook	7	180	–	8
ego-Facebook	8	112	–	77
ego-Facebook	9	55	–	37
ego-Facebook	10	234	–	64
ego-Facebook	11	160	–	0
ego-Facebook	12	67	–	67
ego-Facebook	13	38	–	66
ego-Facebook	14	62	–	0
ego-Facebook	15	2	–	6
ego-Facebook	16	15	–	0
wiki-Vote	2	770	–	533
wiki-Vote	3	353	–	5426
wiki-Vote	4	2212	–	2975
wiki-Vote	5	6828	–	1012
wiki-Vote	6	85	–	214
wiki-Vote	7	927	–	283
wiki-Vote	8	297	–	4146
wiki-Vote	9	198	–	61
wiki-Vote	10	72	–	1392
wiki-Vote	11	24	–	3
wiki-Vote	12	29	–	38
wiki-Vote	13	0	–	124
wiki-Vote	14	19	–	36
wiki-Vote	15	15	–	75
wiki-Vote	16	173	–	2

In the paper, we have analyzed coalition structure generation from the computational and algorithmic perspectives. In fact, there is an extensive literature studying computational issues and proposing efficient solution algorithms for coalition structure generation, which we can partition in two groups based on the kinds of game encoding considered in the research. Classically, valuation functions are viewed as “black boxes” that, on input a coalition C, return the value $v (C)$ . This setting has been extensively studied in the literature with the aim of either defining exact algorithm (i.e., capable of finding the optimal solution) and approximation algorithms (e.g., [35,68,76,77,79,86]) or proposing specific heuristics that can be effective to handle real-world scenarios (e.g., [63,80,81]). Orthogonally to these approaches, efforts have been spent to define methods for representing valuation functions (hence, coalitional games) concisely. With this respect, the crucial and well-known observation is that explicitly listing all possible coalitions, with attached their associated valuations, would require exponential space hence making the coalition structure generation hardly viable in practice. Rather, it has been experimentally observed that coalition structure generation can be more efficiently solved by applying optimization techniques to the compact representation directly [71]. Moreover, this approach has been the subject of numerous theoretical studies, and to date there is a wide range of available compact representations for games and valuation functions, including marginal contribution networks [61,71], games with synergy coalition groups [33,71], coalitional skill games [16], games with agent-type representations [14,87], weighted voting games [43], and graph games [14,15,40].

Our model departs from the approaches discussed above in three respects. First, in addition to the maximization of the social welfare, we have considered the maximization of the egalitarian social welfare – which is an optimization function rather popular in the computational social choice community, but whose application in the context of coalition formation has been largely unexplored in earlier literature.

Fig. 3.

Fair Graph Partitioning: Weight of the best solution computed for instances of ego-Facebook and wiki-Vote (0 normalized to 0.1).

Fig. 4.

Fair Graph Partitioning: Weight of suboptimal solutions computed for instances of ego-Facebook and wiki-Vote.

Second, we have considered a logic-based modeling of the agents, which is semantically richer than traditional valuation functions. In fact, by looking at our contribution from this perspective, it might be relevant to mention here some of the most popular logic-based approaches in the multi-agent community, namely, alternating-time temporal logic [7] and coalition logic [75], which influenced further proposals, including epistemic coalition logic [3], and resource-bounded temporal logic [6,38]. Moreover, specific logic-based formalisms for defining coalitional games include Qualitative Coalitional Games [90], Temporal Qualitative Coalitional Games [4], Coalitional Resource Games [42], and Coalitional Game Logic [5]. Our work can be positioned within this avenue of research, but it must be observed that the utility function we have considered is very specific to reflect a logic-based formalization that interplays (in a way that is entirely novel in the literature) with the innate social attitude of the agents. On the one hand, this is a conceptual novelty and a distinguishing modeling feature of our proposal; on the other hand, when we consider the technical contribution and given the specificity of the functions we have dealt with, it clearly emerges that earlier complexity results in the literature do not apply to our setting and an ad-hoc analysis was in order.

The third distinguishing feature of our work is that we have positioned our agents in a social environment where only certain coalitions were allowed to form based on agents’ interactions. In fact, this latter aspect is not entirely novel, as it is reminiscent of coalition structure generation methods imposing constraints on the allowed coalitions [21,31,56,88]. However, in our modeling perspective, the underlying social networks is not only responsible of defining hard constraints on the coalitions that are allowed to form, but it also impacts the valuations of the agents in a measure that is proportional to their social attitude.

10. Conclusion and discussion

Social environments are usually modeled in the literature as networks, whose nodes correspond to the individuals and whose edges encode their social interconnections which give rise to influence phenomena, because of reasons ranging from similarity and social ties [10], to conformity [83], and to compliance [32], just to name a few. In particular, classical studies focuses their analysis on understanding how information diffuses over the newtwork by exploiting such phenomena (see, e.g., [22,28,29,55,59,64]).

In fact, richer models of social environments have been also proposed to study the process of opinion diffusion, rather than just information diffusion (see, e.g., [1,48]). The paper position itself within this avenue of research, by studying the problem of assessing how a general consensus can be reached over a network where agents are seen as thinking entities equipped with their own logical theories. In particular, we have proposed a framework where agents can form coalitions, i.e., we do not necessarily require that a general consensus is reached, and where their reasoning capabilities are encoded via weighted propositional formulas. On the one hand, a number of exemplifications have been provided to illustrate the expressiveness of the framework. On the other hand, a thorough complexity analysis has been conducted in order to assess the amount of resources that are intrinsically needed to reason in the resulting setting.

Our theoretical investigations have been complemented by designing concrete algorithms to solve the problems of interest. In particular, we have proposed rewriting in terms of pseudo-Boolean constraints, which can be used on top of current state-of-the-art pseudo-Boolean solvers. In particular, existing solvers can be smoothly adopted to deal with the utilitarian semantics. Instead, to deal with the egalitarian social welfare, an ad-hoc solver has been implemented which is capable of supporting forms of fair optimization – hence being of interest independently of its specific usage in our application domain.

In the paper, we left open a number of specific technical questions (such as the identification of islands of tractability under the egalitarian social welfare and the definition of encodings for the reasoning tasks currently not covered in Section 6 and in Section 7). In addition to facing them, a natural avenue of further research is to study different optimization functions in the coalition structure generation problem. Indeed, while our focus on the egalitarian social welfare is rather novel in the coalition structure generation literature, there might be cases where neither this kinds of social welfare not the classical utilitarian social welfare are appropriate. For instance, it might be natural to study settings with a strategy that aims to minimize the differences between the individual utilities of the coalition agents and to maximize the global utility of the coalition.

Finally, another avenue of further research might lead to face different problems in social environments, beside those we have already considered. For instance, it would be interesting to apply, within our framework, solutions concepts from cooperative game theory, leading to establishing criteria of fairness and stability in the agreements over the agents. Then, it would be interesting to assess whether the computational problems arising with them can be encoded in a way that can be smoothly handled by our solver.

Footnotes

Acknowledgements

We thank the anonymous reviewers for their useful comments and suggestions. Mario Alviano was partially supported by the POR CALABRIA FESR 2014-2020 project “DLV Large Scale”, by the EU H2020 PON I&C 2014-2020 project “S2BDW”, and by GNCS-INdAM. Gianluigi Greco was partially supported by the POR CALABRIA FESR 2014-2020 project “Explora Process” and by the EU H2020 PON I&C 2014-2020 project “S2BDW”. Antonella Guzzo was partially supported by the EU H2020 PON I&C 2014-2020 project “IDService: Digital Identity and Service Accountability”.

References

Acar,

Greco and

Manna, Group reasoning in social environments, in: Proc. of AAMAS, 2017, pp. 1296–1304.

Acemoglu and

Ozdaglar, Opinion dynamics and learning in social networks, Dynamic Games and Applications 1(1) (2011), 3–49. doi:10.1007/s13235-010-0004-1.

Ågotnes and

Alechina, Epistemic coalition logic: Completeness and complexity, in: Proc. of AAMAS, 2012, pp. 1099–1106.

Ågotnes,

van der Hoek and

Wooldridge, Temporal qualitative coalitional games, in: Proc. of AAMAS, 2006, pp. 177–184. doi:10.1145/1160633.1160662.

Ågotnes,

van der Hoek and

Wooldridge, Reasoning about coalitional games, Artificial Intelligence 173 (2009), 45–79. doi:10.1016/j.artint.2008.08.004.

Alechina,

Logan,

N.H.

Nga and

Rakib, A logic for coalitions with bounded resources, in: Proc. of IJCAI, 2009, pp. 659–664.

Alur,

T.A.

Henzinger and

Kupferman, Alternating-time temporal logic, Jorunal of the ACM 49(5) (2002).

Alviano,

Dodaro,

Leone and

Ricca, Advances in WASP, in: Proc. of LPNMR, 2015, pp. 40–54.

Alviano,

Dodaro and

Ricca, A MaxSAT algorithm using cardinality constraints of bounded size, in: Proc. of IJCAI, 2015, pp. 2677–2683.

10.

Anagnostopoulos,

Kumar and

Mahdian, Influence and correlation in social networks, in: Proc. of KDD, 2008, pp. 7–15.

11.

Aral,

Muchnik and

Sundararajan, Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks, Proceedings of the National Academy of Sciences 106(51) (2009), 21544–21549. doi:10.1073/pnas.0908800106.

12.

Audemard and

Simon, Predicting learnt clauses quality in modern SAT solvers, in: Proc. of IJCAI, 2009, pp. 399–404.

13.

Auletta,

Caragiannis,

Ferraioli,

Galdi and

Persiano, Generalized discrete preference games, in: Proc. of IJCAI, 2016, pp. 53–59.

14.

Aziz and

de Keijzer, Complexity of coalition structure generation, in: Proc. of AAMAS, 2011, pp. 191–198.

15.

Bachrach,

Kohli,

Kolmogorov and

Zadimoghaddam, Optimal coalition structure generation in cooperative graph games, in: Proc. of AAAI, 2013, pp. 81–87.

16.

Bachrach,

Meir,

Jung and

Kohli, Coalitional structure generation in skill games, in: Proc. of AAAI, 2010, pp. 703–708.

17.

Bansal and

Sviridenko, The Santa Claus problem, in: Proc. of STOC, 2006, pp. 31–40.

18.

Bezáková and

Dani, Allocating indivisible goods, SIGecom Exchanges 5(3) (2005), 11–18. doi:10.1145/1120680.1120683.

19.

Bhawalkar,

Gollapudi and

Munagala, Coevolutionary opinion formation games, in: Proc. of STOC, 2013, pp. 41–50.

20.

Bindel,

Kleinberg and

Oren, How bad is forming your own opinion?, Games and Economic Behavior 92 (2015), 248–265. doi:10.1016/j.geb.2014.06.004.

21.

Bistaffa,

Farinelli,

Cerquides,

Rodríguez-Aguilar and

Ramchurn, Anytime coalition structure generation on synergy graphs, in: Proc. of AAMAS, 2014, pp. 13–20.

22.

Borodin,

Filmus and

Oren, Threshold models for competitive influence in social networks, in: Internet and Network Economics, Springer, 2010, pp. 539–550. doi:10.1007/978-3-642-17572-5_48.

23.

Boutilier and

Hoos, Bidding languages for combinatorial auctions, in: Proc. of IJCAI, 2001, pp. 1211–1217.

24.

Bouveret and

Lang, Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity, J. Artificial Intelligence Res. (JAIR) 32 (2008), 525–564. doi:10.1613/jair.2467.

25.

Brandt,

Conitzer and

Endriss, Multiagent systems, MIT Press, 2012, Chap. Computational Social Choices.

26.

Calimeri,

Gebser,

Maratea and

Ricca, Design and results of the fifth answer set programming competition, Artificial Intelligence 231 (2016), 151–181. doi:10.1016/j.artint.2015.09.008.

27.

Calimeri,

Ianni and

Ricca, The third open answer set programming competition, TPLP 14(1) (2014), 117–135.

28.

Carnes,

Nagarajan,

S.M.

Wild and

van Zuylen, Maximizing influence in a competitive social network: A follower’s perspective, in: Proc. of EC, 2007, pp. 351–360.

29.

Cha,

Mislove and

K.P.

Gummadi, A measurement-driven analysis of information propagation in the Flickr social network, in: Proc. of WWW, 2009, pp. 721–730.

30.

Chalkiadakis,

Greco and

Markakis, Characteristic function games with restricted agent interactions: Core-stability and coalition structures, Artificial Intelligence 232 (2016), 76–113. doi:10.1016/j.artint.2015.12.005.

31.

Chalkiadakis,

Greco and

Markakis, Characteristic function games with restricted agent interactions: Core-stability and coalition structures, Artificial Intelligence 232 (2016), 76–113. doi:10.1016/j.artint.2015.12.005.

32.

R.B.

Cialdini and

N.J.

Goldstein, Social influence: Compliance and conformity, Annu. Rev. Psychol. 55 (2004), 591–621. doi:10.1146/annurev.psych.55.090902.142015.

33.

Conitzer and

Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Artificial Intelligence 170(6–7) (2006), 607–619. doi:10.1016/j.artint.2006.01.005.

34.

Coste-Marquis,

Lang,

Liberatore and

Marquis, Expressive power and succinctness of propositional languages for preference representation, in: Proc. of KR, 2004, pp. 203–212.

35.

V.D.

Dang and

N.R.

Jennings, Generating coalition structures with finite bound from the optimal guarantees, in: Proc. of AAMAS, 2004, pp. 564–571.

36.

David and

Jon, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.

37.

Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.

38.

Della Monica,

Napoli and

Parente, On a logic for coalitional games with priced-resource agents, Electronic Notes in Theoretical Computer Science 278 (2011), 215–228.

39.

DeMarzo,

Vayanos and

Zwiebel, Persuasion bias, social influence, and unidimensional opinions, The Quarterly Journal of Economics 118(3) (2003), 909–968. doi:10.1162/00335530360698469.

40.

Deng and

C.H.

Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research 19(2) (1994), 257–266. doi:10.1287/moor.19.2.257.

41.

H.E.

Dixon,

M.L.

Ginsberg and

A.J.

Parkes, Generalizing Boolean satisfiability I: Background and survey of existing work, Journal of Artificial Intelligence Research 21 (2004), 193–243. doi:10.1613/jair.1353.

42.

P.E.

Dunne,

Kraus,

Manisterski and

Wooldridge, Solving coalitional resource games, Artificial Intelligence 174(1) (2010), 20–50. doi:10.1016/j.artint.2009.09.005.

43.

Elkind,

Chalkiadakis and

N.R.

Jennings, Coalition structures in weighted voting games, in: Proc. of ECAI, 2008, pp. 393–397.

44.

Elkind,

L.A.

Goldberg,

P.W.

Goldberg and

Wooldridge, A tractable and expressive class of marginal contribution nets and its applications, Mathematical Logic Quarterly 55(4) (2009), 362–376. doi:10.1002/malq.200810021.

45.

Elkind,

Rahwan and

N.R.

Jennings, Computational coalition formation, in: Multiagent Systems, MIT Press, 2013.

46.

Elkind and

Wooldridge, Hedonic coalition nets, in: Proc. of AAMAS, 2009, pp. 417–424.

47.

Escoffier,

Gourvès and

Monnot, Fair solutions for some multiagent optimization problems, Autonomous Agents and Multi-Agent Systems 26(2) (2013), 184–201. doi:10.1007/s10458-011-9188-z.

48.

N.E.

Friedkin and

E.C.

Johnsen, Social influence and opinions, Journal of Mathematical Sociology 15 (1990), 193–206. doi:10.1080/0022250X.1990.9990069.

49.

Gebser,

Kaminski,

Kaufmann,

Romero and

Schaub, Progress in clasp series 3, in: Proc. of LPNMR, 2015, pp. 368–383.

50.

Golub and

M.O.

Jackson, Naïve learning in social networks and the wisdom of crowds, American Economic Journal: Microeconomics 2(1) (2010), 112–149.

51.

Gonzales,

Perny and

Queiroz, Preference aggregation with graphical utility models, in: Proc. of AAAI, 2008, pp. 1037–1042.

52.

Gottlob,

Greco and

Scarcello, Tractable optimization problems through hypergraph-based structural restrictions, in: Proc. of ICALP, 2009, pp. 16–30.

53.

Gottlob,

Greco and

Scarcello, Treewidth and hypertree width, in: Tractability: Practical Approaches to Hard Problems, 2012.

54.

Gottlob,

Leone and

Scarcello, A comparison of structural CSP decomposition methods, Artificial Intelligence 124(2) (2000), 243–282. doi:10.1016/S0004-3702(00)00078-3.

55.

Granovetter, Threshold models of collective behavior, American Journal of Sociology 83(6) (1978), 1420–1443. doi:10.1086/226707.

56.

Greco and

Guzzo, Constrained coalition formation on valuation structures: Formal framework, applications, and islands of tractability, Artificial Intelligence 249 (2017), 19–46. doi:10.1016/j.artint.2017.04.005.

57.

Greco and

Lang, Group decision making via weighted propositional logic: Complexity and islands of tractability, in: Proc. of IJCAI, 2015, pp. 3008–3014.

58.

F.M.

Harper and

J.A.

Konstan, The MovieLens datasets: History and context, TiiS 5(4) (2016), 19.

59.

He,

Song,

Chen and

Jiang, Influence blocking maximization in social networks under the competitive linear threshold model, in: Proc. of SDM, 2012, pp. 463–474.

60.

Ieong and

Shoham, Marginal contribution nets: A compact representation scheme for coalitional games, in: Proc. of EC, 2005, pp. 193–202.

61.

Ieong and

Shoham, Marginal contribution nets: A compact representation scheme for coalitional games, in: Proc. of EC ’05, 2005, pp. 193–202. doi:10.1145/1064009.1064030.

62.

M.O.

Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, USA, 2008.

63.

Keinänen, Simulated annealing for multi-agent coalition formation, in: Proc. of KES-AMSTA, 2009, pp. 30–39.

64.

Kempe,

Kleinberg and

Tardos, Maximizing the spread of influence through a social network, in: Proc. of KDD ’03, 2003, pp. 137–146. doi:10.1145/956750.956769.

65.

Lafage and

Lang, Logical representation of preferences for group decision making, in: Proc. of KR, 2000, pp. 457–468.

66.

Lang and

Xia, Voting in combinatorial domains, in: Handbook of Computational Social Choice, 2014, pp. 1193–1195.

67.

Leskovec and

Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, 2014.

68.

Michalak,

Sroka,

Rahwan,

Wooldridge,

McBurney and

N.R.

Jennings, A distributed algorithm for anytime coalition structure generation, in: Proc. of AAMAS, 2010, pp. 1007–1014.

69.

R.B.

Myerson, Graphs and cooperation in games, Mathematics of Operations Research 2(3) (1977), 225–229. doi:10.1287/moor.2.3.225.

70.

Nisan, Bidding languages for combinatorial auctions, in: Combinatorial Auctions,

Cramton,

Shoham and

Steinberg, eds, MIT Press, 2006, Chap. 9.

71.

Ohta,

Conitzer,

Ichimura,

Sakurai,

Iwasaki and

Yokoo, Coalition structure generation utilizing compact characteristic function representations, in: Proc. of CP, 2009, pp. 623–638.

72.

M.J.

Osborne and

Rubinstein, A Course in Game Theory, The MIT Press, Cambridge, MA, USA, 1994.

73.

C.H.

Papadimitriou, Computational Complexity, Addison Wesley, Reading, MA, USA, 1994.

74.

Pathak,

Banerjee and

Srivastava, A generalized linear threshold model for multiple cascades, in: Proc. of ICDM, 2010, pp. 965–970.

75.

Pauly, A modal logic for coalitional power in games, Journal of Logic and Computation 12(1) (2002), 149–166. doi:10.1093/logcom/12.1.149.

76.

Rahwan and

N.R.

Jennings, An improved dynamic programming algorithm for coalition structure generation, in: Proc. of AAMAS, 2008, pp. 1417–1420.

77.

Rahwan,

S.D.

Ramchurn,

N.R.

Jennings and

Giovannucci, Anytime algorithm for optimal coalition structure generation, Journal of Artificial Intelligence Research 34 (2009), 521–567. doi:10.1613/jair.2695.

78.

Robertson and

P.D.

Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. of Algorithms 7(3) (1986), 309–322. doi:10.1016/0196-6774(86)90023-4.

79.

Sandholm,

Larson,

Andersson,

Shehory and

Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence 111(1–2) (1999), 209–238. doi:10.1016/S0004-3702(99)00036-3.

80.

Sen and

P.S.

Dutta, Searching for optimal coalition structures, in: Proc. of ICMAS, 2000, pp. 287–292.

81.

Shehory and

Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence 101(1–2) (1998), 165–200. doi:10.1016/S0004-3702(98)00045-9.

82.

Simon and

Apt, Choosing products in social networks, in: Internet and Network Economics, Vol. 7695, Springer, 2012, pp. 100–113. doi:10.1007/978-3-642-35311-6_8.

83.

Tang,

Wu and

Sun, Confluence: Conformity influence in large social networks, in: Proc. of KDD, 2013, pp. 347–355.

84.

Uckelman,

Chevaleyre,

Endriss and

Lang, Representing utility functions via weighted goals, Mathematical Logic Quarterly 55(4) (2009), 341–361. doi:10.1002/malq.200810024.

85.

Uckelman and

Endriss, Compactly representing utility functions using weighted goals and the max aggregator, Artificial Intelligence 174(15) (2010), 1222–1246. doi:10.1016/j.artint.2010.07.003.

86.

Ueda,

Iwasaki,

Yokoo,

M.-C.

Silaghi,

Hirayama and

Matsui, Coalition structure generation based on distributed constraint optimization, in: Proc. of AAAI, 2010, pp. 197–203.

87.

Ueda,

Kitaki,

Iwasaki and

Yokoo, Concise characteristic function representations in coalitional games based on agent types, in: Proc. of AAMAS, 2011, pp. 1271–1272.

88.

Voice,

S.D.

Ramchurn and

N.R.

Jennings, On coalition formation with sparse synergies, in: Proc. of AAMAS, 2012, pp. 223–230.

89.

von Neumann and

Morgenstern, Theory of Games and Economic Behavior, 3rd edn, Princeton University Press, Princeton, NJ, USA, 1953.

90.

Wooldridge and

P.E.

Dunne, On the computational complexity of qualitative coalitional games, Artificial Intelligence 158(1) (2004), 27–73. doi:10.1016/j.artint.2004.04.002.

Coalition formation in social environments with logic-based agents 1

Abstract

Keywords

1. Introduction

2. Formal framework

2.1. Agents and utility functions

2 Whenever no confusion can arise, we transparently apply u i over interpretations defined on supersets of dom ( A i ) , with the intended meaning that we get rid of the variables outside that domain.

3.1. Voting and influence phenomena

3.2. Influence in large networks

4. Complexity analysis

4.1. Preliminaries on complexity theory

4.2. Computational setting and problems of interest

5.1. Qualitative restrictions

6.1. Preliminaries on pseudo-Boolean theories

8.1. Benchmark problems

8.2. Results

3 https://github.com/alviano/python/tree/master/pyrunlim

Footnotes

Acknowledgements

References

²
Whenever no confusion can arise, we transparently apply $u_{i}$ over interpretations defined on supersets of $dom (A_{i})$ , with the intended meaning that we get rid of the variables outside that domain.

³
https://github.com/alviano/python/tree/master/pyrunlim