Robust Coalition Structure Generation

Abstract

How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation ($\mathsf {CSG}$) involves partitioning a set of agents into coalitions so that the social surplus (i.e. the sum of the rewards obtained by each coalition) is maximized. In many cases, one is interested in computing a partition of the set of agents which maximizes the social surplus, but is robust as well, which means that it is not required to recompute new coalitions if some agents break down. In this paper, the focus is laid on the Robust Coalition Structure Generation ($\mathsf {RCSG}$) problem. A formal framework is defined and some decision and optimization problems for $\mathsf {RCSG}$ are pointed out. The computational complexity of $\mathsf {RCSG}$ is then identified. An algorithm for $\mathsf {RCSG}$ (called $\mathsf {AmorCSG}$) is presented and evaluated on a number of benchmarks.

1 Introduction

Coalition Structure Generation ($\mathsf {CSG}$) [14, 20] is a key issue for a number of applications related to multi-agent cooperation, e.g., waste-water treatment system [5], distributed vehicle routing [20] and multi-sensor networks [3]. $\mathsf {CSG}$ involves partitioning a set of agents into coalitions so that the sum of the values of all coalitions is maximized. In $\mathsf {CSG}$, it is well-known that finding an optimal coalition structure which maximizes the social surplus is $\mathbf {NP}$-hard. Indeed, the decision problem associated with $\mathsf {CSG}$ is equivalent to the complete set partition problem [23] which is $\mathbf {NP}$-complete.

Robustness (i.e., it is not required to recompute new coalitions of $\mathsf {CSG}$ even if some agents break down) is an expected property of $\mathsf {CSG}$. In this paper, the focus is laid on the Robust Coalition Structure Generation ($\mathsf {RCSG}$) problem. A formal framework for the $\mathsf {RCSG}$ problem is presented and some decision and optimization problems for $\mathsf {RCSG}$ are pointed out. A coalition structure is viewed as $k\text{- }robust$ (for a given non-negative integer k) if removing any subset of k agents from it leads the remaining coalitions to still be beneficial. The $\mathsf {RCSG}$ decision problem consists in determining whether there exists a u-beneficial and k-robust coalition structure, for a given reward threshold u and robustness threshold k. We identify the computational complexity of the $\mathsf {RCSG}$ decision problem. While the standard $\mathsf {CSG}$ problem is $\mathbf {NP}$-complete, we show that the $\mathsf {RCSG}$ decision problem is inherently harder unless the polynomial hierarchy collapses ($\mathsf {RCSG}$ is $\mathbf {\Sigma _2^p}$-complete). One of the optimization counterparts of this problem consists in fixing the robustness threshold k and finding one of the most beneficial coalition structures meeting the robustness requirement. Dually, one can also fix the reward threshold u and optimize the robustness of a u-beneficial coalition structure. Lastly, one can consider the bi-objective optimization problem where the aim is to optimize both the reward and the robustness of a coalition structure.

As an application domain, we believe that the vehicle routing problem [18] is promising area, which can be formalized as $\mathsf {CSG}$, where geographically dispersed dispatch centers of several companies cooperate. When we consider both the effectiveness and robustness of the drivers’ groups, this problem amounts to a robust $\mathsf {CSG}$ problem. Another application area is about the multi-sensor networks [3], which can be also formalized as $\mathsf {CSG}$. Consider several sensors in an airport or in a shopping center where some sensors collaborate and observe a certain area for the security reason. Then, forming effective and robust groups of sensors, amounts to solving a $\mathsf {RCSG}$ problem.

Related to our work is the team formation problem ($\mathsf {TF}$) [11, 22]. Compared to the $\mathsf {TF}$ problem, $\mathsf {CSG}$ is similar to the complete set partition problem [23], while $\mathsf {TF}$ is equivalent to the set cover problem [7]. The robustness issue has recently been considered in $\mathsf {TF}$ [13]. Our approach of robustness in $\mathsf {CSG}$ is similar to the one developed in this work. However, this paper focuses on the robustness issue for $\mathsf {CSG}$. Also, the significant difference between $\mathsf {RCSG}$ and robust $\mathsf {TF}$ lies in the complexity of each of the corresponding decision problems: $\mathsf {RCSG}$ is shown here to be $\mathbf {\Sigma _2^p}$-complete, whereas robust $\mathsf {TF}$ is “only” $\mathbf {NP}$-complete. To the best of our knowledge, the robustness issue for $\mathsf {CSG}$ have been left unaddressed so far in the literature.

2 Coalition Structure Generation

Let us start with some preliminary definitions. Let $A = \{a_1, a_2, \dots , a_n\}$ be a finite set of agents. A coalition from A, denoted as C, is a non-empty subset of A. A coalition structure on A, denoted as CS, is a partition on A, i.e., a jointly exhaustive set of pairwise disjoint coalitions from A. Formally, a coalition structure CS (on A) is a set of coalitions $\{C_1, \ldots , C_m\}$ such that for each $i, j \in \{1, 2, \dots , m\}$ such that $i \ne j$, we have that $C_i \cap C_j = \emptyset$ and $\bigcup _{C_i \in CS} C_i = A$.

Definition 1

($\mathsf {CSG}$ problem description). A coalition structure generation problem description is defined by a pair $\mathsf {CSG} = \langle A, v \rangle$ where $A = \{a_1, a_2, \dots , a_n\}$ is a set of agents and $v:2^{A} \rightarrow \mathbb {N}$ is a function called a characteristic function.

The value of a coalition C, denoted as v(C), is given by the characteristic function v. The value of a coalition structure CS, denoted as V(CS), is the sum of the values of each coalition, i.e., $V(CS) = \sum _{C_i \in CS} v(C_i).$ A coalition structure is said to be optimal, denoted as $CS^*$, if $CS^*$ satisfies the followings: $\forall CS, V(CS) \le V(CS^*).$

Example 1

($\mathsf {CSG}$). Let us consider the following scenario. The olympic games will be held in Tokyo and it requires some interpreters in different stadiums, e.g., athletics stadium, swimming stadium and basketball stadium etc. A service company dispatching interpreters with three employees (Ana, Becky and Carol) has received the requests of the simultaneous interpretation and send them employees to different stadiums: request 1 requires Ana, and the company gets $\$20$ for it; request 2 pays $\$30$ and needs Becky’s language skill; request 3 needs Carol and pays $\$10$; request 4 pays $\$80$ and needs Ana and Becky; request 5 pays $\$90$ and needs Ana and Carol; request 6 needs Becky and Carol and pays $\$70$; request 7 requires all employees and pays $\$110$. Assume that you are the manager of this service company and want to assign the employees to job(s) so that the sum of the rewards is maximized. Then, this problem can be represented as a $\mathsf {CSG}$: let $\mathsf {CSG} = \langle A, v \rangle$ be a $\mathsf {CSG}$ problem description with $A = \{Ana, Becky, Carol\}$, and the function v is characterized as follows:

$$\begin{aligned} v(\{Ana\})=\$20, ~v(\{Becky\})=\$30, ~v(\{Carol\})=\$10, \\ v(\{Ana, Becky\})=\$80,~ v(\{Ana, Carol\})=\$90, ~v(\{Becky, Carol\})=\$70, \\ v(\{Ana, Becky, Carol\})=\$110. \end{aligned}$$

The optimal coalition structure is $CS^* = \{\{Becky\}, \{Ana, Carol\}\}$, and the obtained value by $CS^*$ is $V(CS^*) = v(\{Becky\}) + v(\{Ana, Carol\}) = \$30 + \$90 = \$120$.

An expected property for coalition structures is to ensure a given level of efficiency. Formally, this (quite standard) property can be stated as follows:

Definition 2

(Beneficialness). Let $CSG = \langle A, v \rangle$ be a $\mathsf {CSG}$ problem description. Given a coalition structure CS and a non-negative integer u, CS is said to be u-beneficial if the value of CS is larger than u: $V(CS) \ge u.$

Let us stress an important remark as to the representation of the characteristic function v in a CSG. In our running example about the service company dispatching interpreters, v is defined “implicitly”, i.e., it is viewed as an oracle. One possible generalization of our example above to an arbitrary number n of agents would be to associate with every coalition C a number depending on the size of C only; in such a case, the corresponding characteristic function v can be represented with a size in $\mathcal{O}(n)$. A number of representation settings for characteristic functions have been pointed out in the literature, and some of them have been adapted to CSG and studied from the computational complexity viewpoint [12]. Among the representation frameworks which have been developed are marginal contribution nets (MC-nets) [6] and synergy coalition groups (SCGs) [2]. Contrastingly, some early work [19, 20] assume that v is provided “fully extensionally” as an input of a CSG problem description, i.e., v is given as a table with $2^n - 1$ entries, associating with every coalition a number. Providing such an extensional representation of v makes the size of an input CSG to be exponential in the number of agents and may be an unrealistic assumption for relatively large problems. Yet there exist many real world applications involving only a dozen of agents (e.g. because of the limited resources), for which an extensional representation of v is feasible [3, 9, 18]. Thus, cooperative games can be used to analyze cost allocation problems, where the players are willing to form coalitions in order to get extra monetary savings as an effect of cooperation. For instance, in [5] the authors address the problem where nearby municipalities must take the decision on whether to cooperate in order to implement a Waste-water Treatment System (WTS). These types of problem can be represented formally as a CSG and it involves a few agents in essence, so that (i) considering a few number of agents for experimentations, and (ii) assuming an extensional representation of the characteristic function, can sometimes be considered as reasonable.

So both choices of representation for v (i.e., “implicit” vs.“extensional”) have been considered in the literature. It turns out that for a number of implicit representations of v (including MC-nets and SCG, see [12]), the complexity of computing a beneficial coalition structure (cf. Definition 2) is $\mathbf {NP}$-hard:

Definition 3

($\mathsf {DP}$-$\mathsf {CSG}$)

• Input: A coalition structure generation problem description $CSG = \langle A, v \rangle$, and a non-negative integer u,

• Question: Does there exist a coalition structure CS such that CS is u-beneficial?

As mentioned above, the complexity of $\mathsf {DP}$-$\mathsf {CSG}$ is $\mathbf {NP}$-complete in general:

Theorem 1

([19]). If the characteristic function v is computable in polynomial time, then $\mathsf {DP}$-$\mathsf {CSG}$ is $\mathbf {NP}$-complete.

In the next section, we will show that computing a “robust” coalition structure is an intrinsically harder problem than the traditional CSG problem.

3 Robust Coalition Structure Generation

In this section, a formal framework for Robust Coalition Structure Generation ($\mathsf {RCSG}$) is defined. Furthermore, both the decision and optimization problems for $\mathsf {RCSG}$ are considered. Also, the computational complexity of $\mathsf {RCSG}$ is identified.

Let $A = \{a_1, \dots , a_n\}$ be a set of agents and $A' \subseteq A$. The restriction on $A'$ of a coalition C from A is defined as the set $C \cap A'$. We extend this notion of restriction on coalition structures as follows. The restriction on $A'$ of a coalition structure $CS = \{C_1, \dots , C_m\}$ on A is defined as the coalition structure $CS' = \{C'_1, \dots , C'_m\} \setminus \{\emptyset \}$ on $A'$, where for each $i \in \{1, \dots , m\}$, $C'_i$ is the restriction on $A'$ of $C_i$. Consider the same coalition structure generation problem in our example of the service company dispatching interpreters. Let us consider the coalition structure $CS = \{\{Ana, Becky\}, \{Carol\}\}$ and $A' = \{Ana, Carol\}$. Then, the restriction on $A'$ of CS is the coalition structure $\{\{Ana\}, \{Carol\}\}$. Robustness can now be defined in formal terms as follows:

Definition 4

(Robust Coalition Structure). Let $CSG = \langle A, v \rangle$ be a $\mathsf {CSG}$ problem description. For a given coalition structure CS on A and non-negative integers u and k, CS is said to be (u, k)-robust if for every $A' \subseteq A$, such that $|A'| \ge n - k$, the restriction on $A'$ of CS is u-beneficial.

That is to say, a coalition structure is (u, k)-robust if whenever k agents are removed from it, the “remaining” coalition structure is u-beneficial. Obviously enough, robustness generalizes the usual notion of beneficialness in CSG. Indeed, we trivially have that for any non-negative integer u, a CSG is u-beneficial if and only if it is (u, 0)-robust.

Example 1

(continued). Let us consider the service company dispatching interpreters with three employees. The manager of this company planed to assign Becky to the request 2 and Ana and Carol to the request 5 so that he/she gets the maximal rewards. However, what’s happen if one of them cannot work on the day because of the illness or other unexpected matters. For instance, let $u=\$70$ and $k=1$, that is, the manager wants to have at least $\$70$ even if such an event would occur. In this example, the optimal coalition structure planed in advance is $CS^* = \{\{Becky\}, \{Ana, Carol\}\}$. To check whether $CS^*$ is (70, 1)-robust, we check for each removed agent from $CS^*$ whether the remaining coalition structure is 70-beneficial. We have that: $V(CS^* \setminus \{Ana\}) = v(\{Becky\}) + v(\{Carol\}) = \$40,$ $V(CS^* \setminus \{Becky\}) = v(\{Ana, Carol\}) = \$90,$ $V(CS^* \setminus \{Carol\}) = v(\{Ana\}) + v(\{Becky\}) = \$50.$ When we remove Ana from $CS^*$, the remaining coalition structure is not 70-beneficial. Intuitively, this comes from the fact that it is not “safe” to form the coalition $\{Ana, Carol\}$ to get a reward of $90, since the absence of Ana from this coalition would leave Carol alone, getting a reward of $10. Thus, $CS^*$ is not (70, 1)-robust. However, $CS = \{\{Ana, Becky, Carol\}\}$ is (70, 1)-robust, since all remaining coalition structures are 70-beneficial after we remove each agent from CS, i.e., $V(CS \setminus \{Ana\}) = \$70$, $V(CS \setminus \{Becky\}) = \$90$, and $V(CS \setminus \{Carol\}) = \$80.$

In the following, we assume that the characteristic function v of $\mathsf {CSG} = \langle A, v\rangle$ satisfies the property of monotonicity, i.e., for all coalitions C, $C'$, if $C \subseteq C'$ then $v(C) \le v(C')$. This property requires that adding an agent to a given coalition is harmless, or stated otherwise, removing an agent from a coalition does not result in an increase of its value. This assumption is very natural when considering the robustness issue, as we are interested in dealing with the “damages” caused to a coalition structure when removing a number of agents from it.¹ Nonetheless, this assumption does not affect the following complexity results, that is, it does not make the $\mathsf {RCSG}$ problem computationally easier.

Definition 5

($\mathsf {DP}$-$\mathsf {RCSG}$)

• Input: A $\mathsf {CSG}$ problem description $CSG = \langle A, v \rangle$, with v computable in polynomial time, and two non-negative integers u and k,

• Question: Does there exist a coalition structure CS such that CS is (u, k)-robust?

In the general case, computing a robust coalition structure is a harder problem than computing a beneficial one (unless the polynomial hierarchy collapses):

Proposition 1

$\mathsf {DP}$-$\mathsf {RCSG}$ is $\mathbf {\Sigma _2^p}$-complete. $\mathbf {\Sigma _2^p}$-hardness holds even if the characteristic function satisfies monotonicity.

Proof

Let us first prove that $\mathsf {RCSG}$ is in $\mathbf {\Sigma _2^p}$. Let $CSG = \langle A, v \rangle$ be a $\mathsf {CSG}$ problem description such that $A = \{a_1, \dots , a_n\}$, and u and k be two non-negative integers. Consider the following non-deterministic polynomial algorithm with $\mathbf {NP}$ oracle:

• 1. Guess a set $CS = \{C_1, \dots , C_m\}$ of coalitions from A;

• 2. Check that CS is a coalition structure on A;

• 3. Check using an $\mathbf {NP}$ oracle that there does not exist a set of agents $A' \subseteq A$ such that $|A'| = n - k$ and such that the restriction of CS on $A'$ is not u-beneficial.

This algorithm decides $\mathsf {RCSG}$, showing that $\mathsf {RCSG}$ is in $\mathbf {\Sigma _2^p}$.

We prove that $\mathbf {\Sigma _2^p}$-hardness holds for $\mathsf {RCSG}$ by consider a reduction in polynomial time to the complementary problem of $\mathsf {RCSG}$ from the following $\mathbf {\Pi _2^p}$-hard problem, that is, the validity problem for 3-CNF quantified boolean formulas (QBFs) of the form $\forall X \exists Y. \alpha$ where $X = \{x_1, \dots , x_n\}$ and $Y = \{y_1, \dots , y_n\}$ are two disjoint sets of propositional atoms and $\alpha$ is 3-CNF propositional formula such that $Var(\alpha ) = X \cup Y$. Consider such a QBF $\forall X \exists Y. \alpha$, and let us associate with it an $\mathsf {RCSG}$ problem description $\langle A, v\rangle$, where A is the set of agents $A = \{a_1, {\bar{a}}_1, b_1, {\bar{b}}_1, \dots , a_n, {\bar{a}}_n, b_n, {\bar{b}}_n\}$, and v is a characteristic function $v : 2^A \mapsto \mathbb {N}$ given as follows. Let us first define:

• the mapping x associating any literal over X with a pair of agents from A, defined for every (possibly negated) literal $x_i$ as $x(x_i) = \{a_i, \bar{a_i}\}$ if $x_i$ is a positive literal, otherwise $x(x_i) = \{b_i, \bar{b_i}\}$;

• the mapping y associating any literal over Y with a pair of agents from A, defined for every (possibly negated) literal $y_i$ as $y(y_i) = \{a_i, b_i\}$ if $y_i$ is a positive literal, otherwise $y(y_i) = \{\bar{a_i}, \bar{b_i}\}$.

Additionally, we assume that $\alpha$ is viewed as a set of clauses written as $(l_i, l_j, l_k)$, where $l_i, l_j, l_k$ are literals from $X \cup Y$, and such that the literals $l_i, l_j, l_k$ are ordered in such a way that if $l_i \in Y$ (resp. $l_j \in Y$) then $l_j, l_k \in Y$ (resp. $l_k \in Y$). Then a clause $(l_i, l_j, l_k) \in \alpha$ can be of the form $(x_i, x_j, y_k)$, $(x_i, y_j, y_k)$ or $(y_i, y_j, y_k)$, since the presence of clauses of the form $(x_i, x_j, x_k)$ make the QBF trivially not valid.

Then given the QBF $\forall X \exists Y. \alpha$, the characteristic function v is defined as follows. Consider the function p associating any literal $p_q$ from $X \cup Y$ with a pair of agents from A, defined as $p(p_q) = x(x_l)$ if $p_q = x_l$, otherwise $p(p_q) = y(y_m)$ when $p_q = y_m$. For each coalition $C \subseteq A$, we set:

• (i) $v(C) = 2n + 1$ if there exists $i \in \{1, \dots , n\}$ such that $\{a_i, \bar{a_i}\} \subseteq C$ or $\{b_i, \bar{b_i}\} \subseteq C$;

• (ii) $v(C) = n + 1$ if there exists a clause $(p_i, p_j, p_k)$ from $\alpha$ such that $p(p_q) \cap C \ne \emptyset$, for any $q \in \{i, j, k\}$;

• (iii) $v(C) = 1$ in the remaining cases.

We often refer to these conditions as (i), (ii) and (iii) in the rest of the proof.

First, one can easily check that v satisfies (monotonicity). Indeed, one can see that for any coalition $C \subseteq A$, if C satisfies condition (i) (resp., condition (ii), (iii), (iv)), then any coalition $C'$ such that $C \subseteq C'$ also satisfies condition (i) (resp., condition (ii), (iii), (iv)). Hence, for all coalitions $C, C' \subseteq A$, if $C \subseteq C'$ then $v(C) \le v(C')$. Therefore, v satisfies (monotonicity).

We intend now to prove that the QBF $\forall X \exists Y. \alpha$ is valid if and only if there does not exist any coalition structure which is $(2n + 1, 2n)$-robust, i.e., if and only if for every coalition structure CS on A, there exists a set $A' \subseteq A$, $|A'| = 2n$, such that the restriction on $A'$ of CS is not $(2n + 1)$-beneficial. This would show that the complementary problem of $\mathsf {RCSG}$ is $\mathbf {\Pi _2^p}$-hard, thus that $\mathsf {RCSG}$ is $\mathbf {\Sigma _2^p}$-hard.

(If part) We show the contraposite of the claim. Assume that the QBF $\forall X \exists Y. \alpha$ is not valid, i.e., $\exists X \forall Y. \lnot \alpha$ is satisfiable, and let us prove that there exists a coalition structure which is $(2n + 1, 2n)$-robust. So let $\omega _X$ be an interpretation over X such that for any interpretation $\omega _Y$ over Y, one the clauses of $\alpha$ is not satisfied by $\omega _X \cup \omega _Y$. Define the coalition structure $CS_r$ as $CS_r = \{C_r, C_r^1, \dots , C_r^n\}$, where:

• $C_r \!= \!\{a_i, \bar{a_i} \mid i \in \{1, \dots , n\}, \omega _X(x_i) \!=\! 0\} \cup \{b_i, \bar{b_i} \mid i \in \{1, \dots , n\}, \omega _X(x_i) = 1\}$;

• for each $i \in \{1, \dots , n\}$, $C_r^i = \{a_i, \bar{a_i}, b_i, \bar{b_i}\} \setminus C_r$.

Let us show that CS is $(2n, 2n + 1)$-robust, i.e., for any set $A' \subseteq A$ such that $|A'| = 2n$, the restriction on $A'$ of CS is $(2n + 1)$-beneficial. From condition (i), we know that for any coalition C, if there exists $i \in \{1, \dots , n\}$ such that $\{a_i, \bar{a_i}\} \subseteq C$ or $\{b_i, \bar{b_i}\} \subseteq C$, then $v(C) = 2n + 1$, so that for any coalition structure CS containing such a coalition C we would get that $v(CS) \ge 2n + 1$. Yet by construction of our coalition structure $CS_r = \{C_r, C_r^1, \dots , C_r^n\}$, for every $i \in \{1, \dots , n\}$ we have that $\{a_i, \bar{a_i}\} \subseteq C$ for some coalition $C \in CS_r$ and $\{b_i, \bar{b_i}\} \subseteq C$ for some coalition $C \in CS_r$. And we have 4n elements in A, thus for any set $A' \subseteq A$ such that $|A'| = 2n$, in the case where $\{a_i, \bar{a_i}\} \subseteq A'$ or $\{b_i, \bar{b_i}\} \subseteq A'$ for some $i \in \{1, \dots , n\}$, we get that $v(C \cap A') = 2n + 1$ for some coalition $C \in CS_r$ (cf. condition (i)), i.e., the restriction $CS'_r$ on $A'$ of $CS_r$ satisfies $v(CS'_r) \ge 2n + 1$, and thus $CS'_r$ is $(2n+1)$-beneficial, which makes $CS_r$ $(2n, 2n + 1)$-robust, that was to be shown. So consider the remaining cases and assume that $A'$ is formed of exactly one element among $\{a_i, \bar{a_i}\}$ and exactly one element among $\{b_i, \bar{b_i}\}$, for each $i \in \{1, \dots , n\}$. So now, for any coalition $C^i_r \in CS_r$ ($i \in \{1, \dots , n\}$), it can be checked by definition of $C_r^i$ that $C_r^i \cap A'$ contains exactly one element from A. This means that none of the conditions (i), (ii), (iii) are satisfied by $C \cap A'$, and thus $v(C \cap A') = 1$ (cf. condition (iv)). To sum up, we have that $v(C^i_r \cap A') = 1$ for each coalition $C^i_r \in CS_r$ ($i \in \{1, \dots , n\}$), and we need to prove that the restriction $CS'_r$ of $CS_r$ on $A'$ satisfies $v(CS'_r) \ge 2n + 1$; yet $v(CS'_r) = \sum _{C \in CS_r}{v(C \cap A')}$, so $v(CS'_r) = \sum _{C^i_r \in CS_r, i \in \{1, \dots , n\}}{v(C^i_r \cap A')} + v(C_r \cap A') = n + v(C_r \cap A')$. Then we need to prove that $v(C_r \cap A') \ge (2n + 1) - n$, i.e., we must prove that $v(C_r \cap A') \ge n + 1$. Let us show that $v(C_r \cap A') = n + 1$. This is enough to show that $C_r \cap A'$ satisfies condition (ii) or (iii). Let us associate with $C_r$ and $A'$ the interpretation $\omega _Y$ over Y defined as follows, for each $i \in \{1, \dots , n\}$:

• in the case where $\{a_i, \bar{a_i}\} \subseteq C_r$, then: $\omega _Y(y_i) = 0$ if $a_i \in A'$, otherwise $\omega _Y(y_i) = 1$ (i.e., if $\bar{a_i} \in A'$);

• in the remaining case (i.e., $\{b_i, \bar{b_i}\} \subseteq C_r$) then: $\omega _Y(y_i) = 0$ if $b_i \in A'$, otherwise $\omega _Y(y_i) = 1$ (i.e., if $\bar{b_i} \in A'$);

We know that there is at least one clause c from $\alpha$ which is not satisfied by $\omega _X \cup \omega _Y$. Such a clause c is of the form $(x_i, y_j, y_k)$ or $(y_i, y_j, y_k)$, but in any of the two cases we have that none of the literals of the clause is satisfied by $\omega _X \cup \omega _Y$. It can be a literal from X (denoted $x_i$ below) or from Y (denoted $y_i$ below). Let us denote l this literal, we fall into one of the two following cases:

• l is a literal $x_i$. If $x_i$ is a positive literal, then $\omega _X(x_i) = 0$. Yet we know by definition of the coalition $C_r \in CS_r$ that $\{a_i, \bar{a_i}\} \subseteq C_r$, and we already know that $A'$ contains exactly one element from $\{a_i, \bar{a_i}\}$, thus we get that $\{a_i, \bar{a_i}\} \cap (C_r \cap A') \ne \emptyset$. If $x_i$ is a negative literal, then $\omega _X(x_i) = 1$. By a similar reasoning, we get that $\{b_i, \bar{b_i}\} \cap (C_r \cap A') \ne \emptyset$. Stated otherwise, we get that $x(x_i) \cap (C_r \cap A') \ne \emptyset$.

• l is a literal $y_i$. If $y_i$ is a positive literal, then $\omega _Y(y_i) = 0$. Yet we know by definition of $\omega _Y$ that we are in the case where ($\{a_i, \bar{a_i}\} \subseteq C_r$ and $a_i \in A'$) or ($\{b_i, \bar{b_i}\} \subseteq C_r$ and $b_i \in A'$). Thus $C_r \cap A' = \{a_i\}$ or $C_r \cap A' = \{b_i\}$. Hence, $\{a_i, b_i\} \cap (C_r \cap A') \ne \emptyset$. If $x_i$ is a negative literal, then $\omega _Y(y_i) = 1$. Yet similarly by definition of $\omega _Y$ we are in the case where ($\{a_i, \bar{a_i}\} \subseteq C_r$ and $\bar{a_i} \in A'$) or ($\{b_i, \bar{b_i}\} \subseteq C_r$ and $\bar{b_i} \in A'$). Thus $C_r \cap A' = \{\bar{a_i}\}$ or $C_r \cap A' = \{\bar{b_i}\}$. Hence, $\{\bar{a_i}, \bar{b_i}\} \cap (C_r \cap A') \ne \emptyset$. Stated otherwise, we get that $y(y_i) \cap (C_r \cap A') \ne \emptyset$.

From these two points, we can claim for the clause c which is not satisfied by $\omega _X \cup \omega _Y$ that: if c is of the form $(x_i, y_j, y_k)$, then $x(x_i) \cap (C_r \cap A') \ne \emptyset$, $y(y_j) \cap (C_r \cap A') \ne \emptyset$ and $y(y_k) \cap (C_r \cap A') \ne \emptyset$; and if c is of the form $(y_i, y_j, y_k)$, then $y(y_i) \cap (C_r \cap A') \ne \emptyset$, $y(y_j) \cap (C_r \cap A') \ne \emptyset$ and $y(y_k) \cap (C_r \cap A') \ne \emptyset$. By definition of the characteristic function v (cf. conditions (ii) and (iii)), we get that $v(C_r \cap A') = n + 1$, that was left to be shown and concludes this part of the proof.

(Only if part) We show the contraposite of the claim. Assume that there exists a coalition structure which is $(2n + 1, 2n)$-robust, and let us prove that the QBF $\forall X \exists Y. \alpha$ is not valid, i.e., $\exists X \forall Y. \lnot \alpha$ is satisfiable.

Let us introduce a preliminary notion. For a given $q \in \{0, \dots , n\}$, we say that a coalition structure CS is q-normal if $CS = \{A\}$ when $q = 0$, and if $CS = \{C, C^1, \dots , C^q\}$ when $q \in \{1, \dots , n\}$ such that:

• for all $i \in \{1, \dots , q\}$, $C^i = \{a_i, \bar{a_i}\}$ or $C^i = \{b_i, \bar{b_i}\}$;

• $C = A \setminus \bigcup \{C^i \mid C^i \in CS,\, i \in \{1, \dots , q\}\}$.

For instance, when $n = 4$, the coalition structure $CS = \{C, C^1, C^2, C^3\}$ defined such that $C^1 = \{a_1, \bar{a_1}\}$, $C^2 = \{b_2, \bar{b_2}\}$, $C^3 = \{b_3, \bar{b_3}\}$ and $C = \{b_1, \bar{b_1}, a_2, \bar{a_2}, a_3, \bar{a_3}, a_4$, $\bar{a_4}, b_4, \bar{b_4}\}$ is 3-normal.

What we first intend to prove is that there exists a coalition structure which is n-normal and $(2n + 1, 2n)$-robust. Beforehand, we want to show that for each $q \in \{1, \dots , n\}$, there exists a coalition structure CS which is q-normal and such that for any $A' \subseteq A$, $|A'| = 2n$, there exists a coalition $C' \in CS_{\downarrow A'}$ which satisfies condition (i), (ii) or (iii), where $CS_{\downarrow A'}$ denotes the restriction of CS on $A'$ (for short, we say that CS is (i)-(ii)-(iii)-consistent in the following). So to recap, we want to show that for each $q \in \{1, \dots , n\}$, there exists a coalition structure CS which is q-normal and (i)-(ii)-(iii)-consistent. We prove it by recursion on q:

• Base case ($q = 0$): since the only 0-normal coalition structure is defined as $CS^0 = \{A\}$, it is enough to show that $CS^0$ is (ii)-(iii)-consistent, i.e., that for every set $A' \subseteq A$ such that $|A'| = 2n$, $A \cap A'$ satisfies condition (ii) or (iii). Yet we know that there exists a coalition structure which is $(2n + 1, 2n)$-robust, so let $CS_r$ be such a coalition structure. So for every set $A' \subseteq A$ such that $|A'| = 2n$, the restriction of $CS_r$ on $A'$ is $(2n + 1)$-beneficial. Let $A' \subseteq A$, $|A'| = 2n$, such that for each $i \in \{1, \dots , n\}$, $A'$ contains exactly one element among $\{a_i, \bar{a_i}\}$ and exactly one element among $\{b_i, \bar{b_i}\}$. We can see then that no coalition from $CS_{r\downarrow A'}$ satisfies condition (i). Let us prove there exists a coalition from $CS_{r\downarrow A'}$ satisfying condition (ii) or (iii). Toward a contradiction, assume that there is no such coalition. Then for every coalition $C \in CS_{r\downarrow A'}$, $v(C) = 1$ (cf. condition (iv)). Yet there are 2n elements in $A'$, which means that $v(CS_{r\downarrow A'}) \le 2n$ (we get that $v(CS_{r\downarrow A'}) = 2n$ in the case where each coalition from $CS_{r\downarrow A'}$ is a singleton set). And yet $CS_r$ is $(2n + 1, 2n)$-robust, so $CS_{r\downarrow A'}$ is $(2n + 1)$-beneficial, which leads to a contradiction. Hence, there exists a coalition from $CS_{r\downarrow A'}$ satisfying condition (ii) or (iii); let $C'$ be such a coalition. We know that $C'$ is a coalition from $CS_{r\downarrow A'}$, so $C' \subseteq A'$. But we also have $C' \subseteq A$, thus $C' \subseteq A \cap A'$. Hence, since $C'$ satisfies condition (ii) or (iii), it is easy to see that $A \cap A'$ satisfies condition (ii) or (iii) as well. Therefore, $CS^0$ is (i)-(ii)-(iii)-consistent.

• Recursion step: let $CS^q = \{C, C^1, \dots , C^q\}$ be a q-normal coalition structure for some $q \in \{0, \dots , n - 1\}$ ($CS^0 = \{A\}$), and assume that $CS^q$ is (i)-(ii)-(iii)-consistent. Let us prove that there exists a coalition structure $CS^{q+1}$ which is $(q+1)$-normal and (i)-(ii)-(iii)-consistent. Let us associate with $CS^q = \{C, C^1, \dots ,$ $C^q\}$ the coalition structure $CS^{q+1}_a = \{C_a, C^1, \dots , C^q, C_a^{q+1}\}$ where $C_a = C \setminus \{a_{q+1},$ $\bar{a_{q+1}}\}$ and $C_a^{q+1} = \{a_{q+1}, \bar{a_{q+1}}\}$; similarly, we associate with $CS^q = \{C, C^1, \dots , C^q\}$ the coalition structure $CS^{q+1}_b = \{C_b, C^1, \dots , C^q, C_b^{q+1}\}$ where $C_b = C \setminus \{b_{q+1}, \bar{b_{q+1}}\}$ and $C_b^{q+1} = \{b_{q+1}, \bar{b_{q+1}}\}$. It is easy to verify that $CS_a^{q+1}$ and $CS_b^{q+1}$ are well-defined coalitions structures, and that both of them are $(q+1)$-normal. So this is enough to show that one of these coalitions is (i)-(ii)-(iii)-consistent. Since $CS^q$ is either (i)-(ii)-(iii)-consistent, for any $A' \subseteq A$, $|A'| = 2n$, there exists a coalition $C' \in CS^q_{\downarrow A'}$ which satisfies condition (i), (ii) or (iii). So let $A' \subseteq A$, $|A'| = 2n$, and let $C' \in CS^q_{\downarrow A'}$, we know that $C'$ satisfies condition (i), (ii) or (iii). Yet by construction of $CS_a^{q+1}$ and $CS_b^{q+1}$ it is easy to see that if $C'$ satisfies condition (i) (resp. condition (ii)), then both $CS_{a \downarrow A'}^{q+1}$ and $CS_{b \downarrow A'}^{q+1}$ contain a coalition which satisfies condition (i) (resp. condition (ii)). So assume that $C'$ does not satisfy condition (i) nor (ii), so that $C'$ satisfies condition (iii). But then, it is easy to verify that one of the two following cases holds: (1) for every $A'' \subseteq A$, $|A''| = 2n$, $CS_{a \downarrow A''}^{q+1}$ contains a coalition which satisfies condition (iii), or (2) for every $A'' \subseteq A$, $|A''| = 2n$, $CS_{b \downarrow A''}^{q+1}$ contains a coalition which satisfies condition (iii). Overall, we have shown that either $CS_a^{q+1}$ or $CS_b^{q+1}$ is (i)-(ii)-(iii)-consistent.

We have now proved that there exists a coalition structure $CS = \{C, C^1, \dots , C^n\}$ which is n-normal and such that for any $A' \subseteq A$, $|A'| = 2n$, there exists a coalition $C' \in CS_{\downarrow A'}$ which satisfies condition (i), (ii) or (iii). Let us show that such a coalition structure CS is $(2n, 2n + 1)$-robust. Let $A' \subseteq A$, $|A| = 2n$ and let us show that $CS_{\downarrow A'}$ is $(2n + 1)$-beneficial. Let $C' \in CS_{\downarrow A'}$. Assume first that $C'$ satisfies condition (i), then one can see that $v(C') = 2n + 1$ and thus $CS_{\downarrow A'}$ is $(2n + 1)$-beneficial. So assume that $C'$ does not satisfy condition (i), i.e., $C'$ satisfies condition (ii) or (iii). Note that in this case (because $C'$ does not satisfy condition (i)), we know that $A'$ contains exactly one element from $\{a_i, \bar{a_i}\}$ and exactly one element from $\{b_i, \bar{b_i}\}$, for each $i \in \{1, \dots , n\}$. Then for each coalition $C^i \in CS$, $i \in \{1, \dots , n\}$, we get that $C^i \cap A'$ is a singleton set and $C^i$ satisfies none of the conditions (ii) and (iii), and thus $v(C^i \cap A') = 1$ (condition (iv)). We have that $v(CS_{\downarrow A'}) = v(C \cap A') + v(C^1 \cap A') + \dots + v(C^n\cap A') = v(C \cap A') + n = v(C') + n = (n+1) + n = 2n + 1$. Hence, $CS_{\downarrow A'}$ is $(2n + 1)$-beneficial.

We have proved that there exists a coalition structure which is n-normal and $(2n, 2n + 1)$-robust, denote it $CS_r = \{C_r, C_r^1, \dots , C_r^n\}$. Now, it remains to show that the QBF $\exists X \forall Y . \lnot \alpha$ is valid. Let us associate with $CS_r$ the interpretation $\omega _X$ over X defined for each $i \in \{1, \dots , n\}$ as $\omega _X(x_i) = 0$ if $C_r^i = \{b_i, \bar{b_i}\}$, otherwise $\omega _X(x_i) = 1$ (in the remaining case where $C^i = \{a_i, \bar{a_i}\}$). Now, let $\omega _Y$ be any interpretation over Y. It remains to show that $\omega _X \cup \omega _Y$ does not satisfy $\alpha$, i.e., there exists a clause from $\alpha$ which is not satisfied by $\omega _X \cup \omega _Y$. With $\omega _Y$ we associate the set $A' \subseteq A$ characterized as follows: for each $i \in \{1, \dots , n\}$, $\{a_i, b_i\} \subseteq A'$ and $\{\bar{a_i}, \bar{b_i}\} \cap A' = \emptyset$ if $\omega _Y(y_i) = 0$, otherwise $\{\bar{a_i}, \bar{b_i}\} \subseteq A'$ and $\{a_i, b_i\} \cap A' = \emptyset$. Note that for each $i \in \{1, \dots , n\}$, $A'$ contains exactly one element among $\{a_i, \bar{a_i}\}$ and exactly one element among $\{b_i, \bar{b_i}\}$. This means that for each $i \in \{1, \dots , n\}$, $C_r^i \cap A'$ is a singleton set and thus $v(C_r^i \cap A') = 1$ (condition (iv)). So $v(CS_{r \downarrow A'}) = v(C_r \cap A') + v(C_r^1 \cap A') + \dots + v(C_r^n \cap A') = v(C_r \cap A') + n$. Yet $CS_r$ is $(2n, 2n + 1)$-robust, so that $v(CS_{r \downarrow A'}) \ge 2n + 1$, and thus $v(C_r \cap A') \ge n+1$, which means that $C_r \cap A'$ satisfies condition (i), (ii) or (iii). But by construction of $A'$, one can see that $C_r \cap A'$ does not satisfy condition (i), so it satisfies condition (ii). We will show that the clause that enables condition (ii) to be satisfied, is not satisfied by $\omega _X \cup \omega _Y$. Let $p_q$ be a literal from a clause from condition (ii):

• Assume first that $p_q = x_l$ for some $l \in \{1, \dots , n\}$.

  • If $x_l$ is a positive literal, then we know that $p(p_q) = x(x_l) = \{a_l, \bar{a_l}\}$. Since $\{a_l, \bar{a_l}\} \cap C_r \cap A' \ne \emptyset$, it follows that $C_r^l = \{b_l, \bar{b_l}\}$. But then $\omega _X(x_l) = 0$.

  • If $x_l$ is a negative literal, we analogously conclude that $\omega _X(x_l) = 1$.

  In both cases $\omega _X$ does not satisfy the clause when $p_q = x_l$ for some $l \in \{1, \dots , n\}$.

• So assume now the remaining case holds, i.e., that $p_q = y_m$ for some $m \in \{1, \dots , n\}$.

  • If $y_m$ is a positive literal, then $p(p_q) = y(y_m) = \{a_m, b_m\}$. Since $\{a_m, b_m\} \cap C_r \cap A' \ne \emptyset$, we can conclude that $\{a_m, b_m\} \subseteq A'$ and thus $\omega _Y(y_m) = 0$.

  • If $y_m$ is a negative literal, we analogously conclude that $\omega _Y(y_m) = 1$.

  In both cases $\omega _Y$ does not satisfy the clause when $p_q = y_m$ for some $m \in \{1, \dots , n\}$.

We have just shown that the QBF $\exists X \forall Y . \lnot \alpha$ is valid, which concludes this part of the proof.

We have shown that the QBF $\forall X \exists Y . \alpha$ is valid if and only if there does not exist a coalition structure CS which is $(2n + 1, 2n)$-robust, which means that the complementary problem $\mathsf {RCSG}$ is $\mathbf {\Pi _2^p}$-hard. Therefore, $\mathsf {RCSG}$ is $\mathbf {\Sigma _2^p}$-hard. $\square$

Beyond the decision problem of $\mathsf {RCSG}$, the following optimization problem could be considered: one sets a robustness threshold k and intend to optimize the beneficialness of the coalition structure; or one sets a beneficialness threshold u and intend to optimize the robustness of the coalition structure. We can also view the $\mathsf {RCSG}$ problem as a bi-objective constraint optimization problem, and be interested in computing Pareto optimal (i.e., non-dominated) coalition structures.

4 The $\mathsf {AmorCSG}$ Algorithm

We now describe $\mathsf {AmorCSG}$, our complete algorithm to compute the coalition structure of maximum beneficialness. The algorithm is based on the integer-partitioning (IP) approach [10, 17]. We briefly describe the IP-approach and refer to the original works [10, 17] for more details. It starts by decomposing the search space into disjoint parts (integer partitions) and applies branch-and-bound to each subspace. Every integer partition of n (the number of agents) defines a subspace by associating the integers in the partition to the number of agents in each coalition (e.g. $1+3$ is a subspace with two coalitions with one and three agents). Note that the integer partitions generated by n are non-overlapping. The main advantage of the decomposition is that effective upper bounds can be calculated for partial solutions from a particular partition, which is an essential for pruning the search space in the branch-and-bound algorithm. Our algorithm follows the same structure as the IP algorithm, with the addition of the following important components: calculation of the robustness for coalitions and coalition structures, robust upper bounds, and our pruning technique for branch-and-bound. These are described in detail below. The pseudo-code of $\mathsf {AmorCSG}$ is given in Algorithm 1 and .

We considered extending other state-of-the-art $\mathsf {CSG}$ algorithms for $\mathsf {RCSG}$ namely ODP [10], ODP-IP [10], and inclusion-exclusion DP [1]. However, these approaches are not applicable to $\mathsf {RCSG}$, as they are based on dynamic programming and the Bellman property does not hold for $\mathsf {RCSG}$. Our method uses dynamic programming during its execution but the core part of the algorithm is branch-and-bound.

Definition 6

(Robustness of a Coalition (Structure)). Let $CSG = \langle A, v \rangle$ be a $\mathsf {CSG}$ problem description. For a given coalition structure CS on A and non-negative integer k, the k-robustness of CS, denoted r(CS, k), is the maximal value u such that CS is (u, k)-robust. Similarly, the k-robustness of a coalition C, denoted r(C, k), is the maximal value u if the coalition structure $\{\{C\}\}$ is (u, k)-robust.

Robustness Values for Each Coalition. For every coalition C we calculate $r(C, k')$ for each $k' \in [1, min(k, |C|)]$ as a preprocessing step, which represents the lowest beneficial value obtainable after removing $k'$ agents from C. We compute $r(C, k')$ using a dynamic programming:

$$\begin{aligned}&r(C, 0)=v(C),\\&r(C, k')\,{=}\,{\min \limits _{C' \subset C \atop |C'| = |C| - 1}}\,(r(C', k'-1)),\,\forall k^\prime \,{\in }\,[1,\min (k, |C|)].\nonumber \end{aligned}$$

(1)

Robustness Values for a Particular Coalition Structure. For a given coalition structure CS we compute its robust value as $r(CS, k) = V(CS) - e(CS, k)$, where e(CS, k) is defined as the optimal value of the following multidimensional knapsack problem:

$$\begin{aligned} e(CS, k) = \max \sum _{C \in CS} \sum _{j \in [1, |C|]} r(C, j) * x_{(C, j)} \end{aligned}$$

(2)

$$\begin{aligned} \sum _{C \in CS} \sum _{j \in [1, |C|]} j*x_{(C, j)} \le k \end{aligned}$$

(3)

$$\begin{aligned} \sum _{j \in [1, |C|]} x_{(C, j)} \le 1 \qquad \forall C \in CS \end{aligned}$$

(4)

$$\begin{aligned} x_{(C, j)} \in \{0, 1\} \qquad \forall C \in CS, j \in [1, |C|] \end{aligned}$$

(5)

The value e(CS, k) denotes the maximum penalty that can be achieved by removing k agents. The variables $x_{(C, j)}$ indicates if j agents are selected for removal from coalition C.

Robust Upper Bounds. For a given subspace generated by the partition $I = [I_0, I_1, \ldots ,$ $I_{m-1}]$ we compute the upper bound as:

$$\begin{aligned} UB^{rob}(I) = \max _{\sum _{j} y_j \le k \atop y_j \in \mathbb {N}_0} (\sum _{j \in [0, m)}(UB(max(0, I_j - y_j))) ) \end{aligned}$$

(6)

In other words, we calculate maximum upper bound of all subspaces that can be generated by removing at most k agents from the subspace I. The upper bound of a partition I, UB(I), is computed as in the integer-partition approach [10, 17].

Branch-And-Bound Pruning. The partial solution CS can be pruned if it cannot be extended to a solution with a higher beneficial value than the best solution found so far (denoted $LB^{best})$. This is determined based on the upper bounds of the unassigned coalitions and $LB^{best}$:

$$\begin{aligned} r(CS, k) + \sum _{j \in [d+1, m)}(UB(I_i)) \le LB^{best} \end{aligned}$$

(7)

The solution CS can be pruned from the search if the above equation holds. Note that the (partial) solution CS has its first d coalitions assigned at search tree depth d.

4.1 Incremental Computation of R(CS, K)

The robust value r(CS, k) is computed in each iteration incrementally using dynamic programming. Let c be the coalition that is added to the partial solution CS, we then have:

$$\begin{aligned} r(CS \cup c, k) = min\{ r(CS, k - i) + r(c, i) | i \in [0, k]\} \end{aligned}$$

(8)

Fig. 1.

Average runtime (five benchmarks for each n, the number of agents) on a variety of distributions with different values for k. Number of timeouts with a limit of 1 h shown in brackets.

5 Experimental Evaluation

We implemented $\mathsf {AmorCSG}$ and the integer-partition approach for $\mathsf {CSG}$ [10, 17] in C++. The experiments were run on an Intel i7-7700HQ CPU @ 2.80 GHz with 32 GB of RAM. We experimented with instances based on several probability distributions for the characteristic function v used in the literature:

• Uniform: $v(C) = Uniform(0, |C|)$ [8].

• Normal: $v(C) = Normal(\mu = 10*|C|, \sigma ^2 = 0.1)$ [16].

• NDCS: $v(C) = Normal(\mu = |C|, \sigma ^2 = \sqrt{|C|})$ [17].

• Modified uniform: $v(C) = Uniform(0, 10*|C|) + a$, where $a = Uniform(0, 50)$ with probability 0.2 and $a=0$ otherwise [21].

• Modified normal: $v(C)= Normal(10*|C|, 0.01) + a$, where a is as above [15].

• Beta: $v(C) = |C|*Beta(\alpha = \beta = 0.5)$ [10].

The benchmarks were adjusted to ensure monotonicity. We compared the runtime for different values of n (number of agents) and $k \in [0, 3]$ (robustness parameter). Note that $\mathsf {RCSG}$ with $k=0$ degenerates to $\mathsf {CSG}$. The results are summarized in Fig. 1, averaged over five instances for each n.

The distribution used plays an important role in the execution time, more so than for standard $\mathsf {CSG}$ ($k=0$). The main reason is that bounds on robustness cannot be approximated as accurately in general and this is further amplified for certain distributions. Furthermore, the strength of the robust bounds weakens with the increase in k. Hence, the algorithm must explicitly explore a large part of the search space, leading to higher run times when compared to $\mathsf {CSG}$. In return, guarantees on robustness are provided.

6 Conclusion

In this paper, the robustness issue for $\mathsf {CSG}$ has been investigated. The contributions of this paper are as follows: A notion of robustness in the $\mathsf {CSG}$ framework has been formalized and shown useful. Furthermore, the corresponding decision and (bi-objective) optimization problems for $\mathsf {RCSG}$ have been studied and the computational complexity has been identified. Finally. a complete algorithm has been presented for solving a $\mathsf {RCSG}$ problem.

This work paves the way for a number of perspectives. Our complete algorithm ($\mathsf {AmorCSG}$) can solve $\mathsf {RCSG}$ problem instances such as waste-water treatment system. For addressing large-scale $\mathsf {RCSG}$ instances, we plan to develop approximate algorithms. Another perspective will consist in considering the robustness issue in a probabilistic setting. In the framework presented in this paper, the robustness of a coalition structure is evaluated from the “worst-case” viewpoint. Another approach would be to consider each agent as “reliable” to a certain extent, e.g., by associating with each agent $a_i$ a value $\alpha (a_i) \in [0, 1]$ standing for the probability that the agent may remain in its coalition at the next step. Obviously enough, this probabilistic setting departs from the one we proposed here. Lastly, we plan to extend our framework to a dynamic setting in which the set of agents A may change w.r.t. time, with the objective to apply it to a distributed robot team reconfiguration problem [4].