Coalitional games for networked controllers with constraints on semivalues: A randomized design approach

Available online at www.sciencedirect.com Journal of the Franklin Institute 359 (2022) 9836–9859 www.elsevier.com/locate/jfranklin Coalitional games for networked controllers with constraints on semivalues: A randomized design approach Francisco Javier Muros a , b , ∗, José María Maestre a a Dep. of Systems and Automation Engineering, University of Seville, Seville, 41092, Spain b Dep. of Engineering, Loyola University Andalusia, Dos Hermanas, Seville, 41704, Spain Received 5 October 2021; received in revised form 30 April 2022; accepted 26 August 2022 Available online 5 September 2022 Abstract In a networked control architecture, the semivalues of a coalitional game where the communication links are the players can be used to provide information regarding their relevance. The linear relationship between the characteristic function of the game and the semivalues can be exploited to impose constraints on the design of the corresponding networked controllers to promote or penalize the use of certain links considering their impact on the overall system performance. In previous works, this approach was restricted to small networks due to the combinatorial growth of the problem size with the number of links. This work proposes a method to mitigate this issue by performing a random sampling in the set of topologies, i.e., coalitions of links, and employing a mild bound to reflect the impact of nonsampled topologies in the calculations. The simulation results show that the proposed approach can lead to significant reductions in computation time with moderate loss of performance. © 2022 The Authors. Published by Elsevier Ltd on behalf of The Franklin Institute. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ ) ∗Corresponding author. E-mail addresses: [email protected] , [email protected] (F.J. Muros), [email protected] (J.M. Maestre). https://doi.org/10.1016/j.jfranklin.2022.08.048 0016-0032/© 2022 The Authors. Published by Elsevier Ltd on behalf of The Franklin Institute. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ ) F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 1. Introduction Distributed control schemes split overall control problems into smaller tightly coupled pieces, which are assigned to local controllers or agents. As the coupling between subproblems grows, communication becomes necessary to avoid undesired interactions and increase overall performance. In this regard, dynamical changes in coupling can be exploited to rearrange agents into disjoint loosely coupled clusters that can neglect their mutual interaction and do not need to communicate, thereby minimizing coordination efforts with minimum impact on the system performance [1] . This basic idea appears under different names in the literature, such as switching systems [2] , time-varying partitioning [3] , plug-and-play schemes [4] , sparsitypromoting control [5] , coupling degree clustering [6] , and coalitional control [7] , on which we will focus. In this context, it is possible to characterize the relevance of links in the networked control architecture by modeling the situation as a cooperative link-game [8] . More specifically, links become the players and a characteristic function has to be defined to assess the impact on the overall performance of each coalition of links or topology [7] . Then, semivalues [9] – payoff rules from cooperative game theory based on marginal contributions – can be computed for the game to provide an indication of the specific contribution of each link. Similarly, constraints on semivalues can be imposed in the design of the networked controller to promote or discourage the use of certain links in relation to the system performance, thereby influencing the topologies implemented in the control architecture. For example, constraints on the Shapley [10] and Banzhaf [11] values, which belong to the set of semivalues, are respectively considered in [12] and [13] , by means of linear matrix inequalities (LMIs). Likewise, in [14] this approach is employed to associate regions of the state space with the most appropriate topologies and guarantee the relevant properties of convexity, invariance, and submodularity in the design. Besides identifying the most relevant links, coalitional methods can be used to design control networks with limitations in their size [15] , and to distribute the costs or benefits that derive from the cooperation between the control agents [8] . These tools are also relevant, for example, for practical applications in the context of cybersecurity, because they can detect the critical links in the control system and impose limits in their use considering their impact on performance. The coalitional approach has also been extended to model predictive control [16,17] and has been applied among others to water systems [15] , renewable energy sources [18] , and freeways traffic networks [19] , considering different partitioning criteria. Other connections with cooperative game theory have been explored, e.g., in schemes based on coalitional treatments [20–22] , with applications as studying opinion dynamics [23,24] , and where the LMI approach is also employed [25] . The contribution of this work is two-fold. On the one hand, it deals with the full set of semivalues, generalizing previous works as [12,13] , whose results now become particular applications of the proposed framework. On the other hand, the main drawback of the LMI approach of [12–14] is the combinatorial explosion in the number of variables of the problem with the number of links, which limits the applicability of their results to small networks. To deal with this issue, we propose a random sampling method that replaces the value of nonsampled topologies in the characteristic function by mild bounds, leading to significant improvements regarding computational burden with small performance loss. Finally, note that a very preliminary version of this article including constraints on semivalues following the exhaustive approach of [12–14] was presented at a conference [26] , and did not include all 9837 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 the semivalues considered here. Also, the proofs of some relevant properties are not contained in the conference version. The rest of the article is organized as follows. In Section 2 , the problem formulation is stated in a coalitional setting. In Section 3 , the set of semivalues is formally defined, and some properties of interest are presented. In Section 4 , constraints on semivalues are included by LMIs in the design, and the coalitional control scheme is also introduced. Next, a random sampling method to relieve the computational burden is presented in Section 5 . An academic example that illustrates the proposed approach is given in Section 6 . Finally, concluding remarks and lines of future work are commented in Section 7 . 2. Problem formulation Consider a system composed of a set N = { 1 , 2, . . . , N } of possibly coupled subsystems. The dynamics of each subsystem i ∈ N are described by x i (k + 1) = A ii x i (k) + B ii u i (k) + d i (k) , d i (k) =  j = i A ij x j (k) + B ij u j (k) , (1) where x i (k) ∈ R n x i and u i (k) ∈ R n u i are respectively the state and input vectors, and with A ij ∈ R n x i ×n x j , B ij ∈ R n x i ×n u j denoting the state and input-to-state matrices of proper dimensions. Term d i (k) comprises the effect of neighbor interactions on the dynamics of subsystem i. From a global viewpoint, the dynamics of the overall system become x N (k + 1) = A N x N (k) + B N u N (k) , (2) where subscript N emphasizes the aggregation of local subsystems, i.e., x N = [ x i ] i∈N , u N = [ u i ] i∈N , A N = [ A ij ] i,j∈N , and B N = [ B ij ] i,j∈N . Note that mutual interactions are implicitly considered. 2.1. Control infrastructure Subsystems in N are governed by local controllers or agents, which are interconnected by a network described by an undirected graph (N , E) , with E ⊆E N = N ×N being edges, i.e., the set of available communication links between agents. Each link l ∈ Ecan be enabled or disabled at each time instant k, considering here a constant cost ˆ c ∈ R + , per enabled link. In any case, the extension to link-dependent costs ˆ c l ∈ R + , ∀ l ∈ E, is straightforward. Definition 1. Let (N , E) be the controller’s communication network. The set of enabled links at time step kis defined as network topology and it is symbolized by (k) ⊆E. The set of possible topologies T = { 0 , 1 , . . . , 2 |E| −1 } , with |T | = 2 |E| , includes all combinations of enabled links from the decentralized topology 0 (all links disabled) to the centralized one 2 |E| −1 (all links enabled). When a specific topology ∈ T is active, communication components , i.e., disjoint neighborhoods or clusters of agents derived by subgraph (N , ) , arise. Also, note that it is possible to connect the topologies by their common links through the following definition: Definition 2. Let (k) ∈ T be the specific topology at time k. The topologies that contain at least (at most) the links enabled in topology (k) are named ascendant (descendant) topologies of (k) , and are denoted by set T ( T ). 9838 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 1. An example of an 8-link network. By using combinatorial analysis we can calculate the number of ascendants and descendants of a given topology  |T | = |E|−| |  n=1 |E| −| | n , |T | = | |  n=1 | | n . (3) Example 1. Let the 8-link network depicted in Fig. 1 , where |T | = 256 and with the elements in T sorted following a lexicographic order. Consider for instance topology 133 = { II , III , V , VII } ∈ T . The number of ascendants and descendants are given by |T | = |T | = 15 . The explicit topologies in those sets and their communication components are detailed in Table 1 and also drawn in a Hasse diagram in Fig. 2 . Table 1 Descendants and ascendants of topology 133 = { II , III , V , VII } . Descendants of 133 Ascendants of 133 I II III IV V VI VII VIII Components I II III IV V VI VII VIII Components 0 X X X X X X X X { 1 } , { 2} , { 3 } , { 4} , { 5 } , { 6 } 168    X  X  X { 1 , 2, 3 , 4, 5 } , { 6 } 2 X  X X X X X X { 1 , 4} , { 2} , { 3 } , { 5 } , { 6 } 199 X     X  X { 1 , 3 , 4, 5 } , { 2, 6 } 3 X X  X X X X X { 1 , 5 } , { 2} , { 3 } , { 4} , { 6 } 204 X   X    X { 1 , 3 , 4, 5 , 6 } , { 2} 5 X X X X  X X X { 1 } , { 2} , { 3 , 4} , { 5 } , { 6 } 206 X   X  X   { 1 , 3 , 4, 5 , 6 } , { 2} 7 X X X X X X  X { 1 } , { 2} , { 3 } , { 4, 5 } , { 6 } 220      X  X N 16 X   X X X X X { 1 , 4, 5 } , { 2} , { 3 } , { 6 } 225    X    X N 18 X  X X  X X X { 1 , 3 , 4} , { 2} , { 5 } , { 6 } 227    X  X   N 20 X  X X X X  X { 1 , 4, 5 } , { 2} , { 3 } , { 6 } 240 X       X N 23 X X  X  X X X { 1 , 5 } , { 2} , { 3 , 4} , { 6 } 242 X     X   N 25 X X  X X X  X { 1 , 4, 5 } , { 2} , { 3 } , { 6 } 244 X   X     { 1 , 3 , 4, 5 , 6 } , { 2} 32 X X X X  X  X { 1 } , { 2} , { 3 , 4, 5 } , { 6 } 247        X N 59 X   X  X X X { 1 , 3 , 4, 5 } , { 2} , { 6 } 249      X   N 61 X   X X X  X { 1 , 4, 5 } , { 2} , { 3 } , { 6 } 251    X     N 68 X  X X  X  X { 1 , 3 , 4, 5 } , { 2} , { 6 } 254 X        N 78 X X  X  X  X { 1 , 3 , 4, 5 } , { 2} , { 6 } 255         N 9839 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 2. Hasse diagram of ascendants/descendants for topology 133 . Same colors have been utilized for symmetric levels of generations. 2.2. Control goal The overall objective from a centralized viewpoint is to regulate the system towards the origin while minimizing the following cost function at time instant k: J (k) = J s (k)    ∞  j =0 x T N (k + j ) Q N x N (k + j ) + u T N (k + j ) R N u N (k + j ) + J c (k)    ˆ c ∞  j =0 | (k + j ) | , (4) which is composed of terms J s (k) ∈ R + and J c (k) ∈ R + , which are respectively related to the cost-to-go of the closed-loop system and the cooperation costs, where ˆ c ∈ R + is the cost per enabled link introduced previously, and with Q N ∈ R n x N ×n x N and R N ∈ R n u N ×n u N being positive semi-definite and definite weighting matrices. Since the choice regarding the state of each link can be modeled as a binary decisionvariable and the input vectors are continuous, the minimization of Eq. (4) is a mixed-integer NP-complete problem [27] . In general, these problems cannot be minimized in an straightforward manner. Next, a heuristic suboptimal solution for the optimization problem is presented, based on finding an upper-bound of cost function (4) . To this end, some simplifications are considered by the following assumptions: Assumption 1. Pair (A N , B N ) is stabilizable by means of a feedback matrix K ∈ R n u N ×n x N for each ∈ T , i.e., the overall control law for this topology becomes u N (k) = K x N (k) . (5) Likewise, there exists a positive definite matrix P ∈ R n x N ×n x N that defines a Lyapunov function f (x N (k)) = x T N (k) P x N (k) , which in turn provides us with a bound on the cost-to-go 9840 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 of the closed-loop system, i.e., x T N (k) P x N (k) ≥J s (k) . (6) Assumption 2. The decentralized topology 0 is reached by the controller in a finite number of time instants. Therefore, it can be found a bound δ∈ N + on this number of instants, which in turn provides a bound on the cooperation costs ˆ c δ| | ≥J c (k) . (7) As a result, an upper-bound of cost function (4) is obtained by Maestre et al. [7] , Muros et al. [12,13] r v (, x N (k)) = x T N (k) P x N (k) + c| | , (8) where c = ˆ c δ. Equation (8) can be minimized with respect to to find the most suitable topology in a given time step. Remark 1. Assumptions 1 and 2 are introduced to focus on the randomized method. Nevertheless, it can be proven that Assumption 1 holds iff the overall system can be controlled using a decentralized controller [14] . Assumption 2 follows from there and is proven in [7] . 2.3. Linear matrix inequalities With the aim of computing Eq. (8) , matrices K and P need to be calculated ∀ ∈ T . To this end, we impose ≥J s (k+1)    x T N (k + 1) P x N (k + 1) + stage cost    x T N (k) Q N x N (k) + x T N (k) K T R N K x N (k) ≤ ≥J s (k)    x T N (k) P x N (k) . (9) Then, as done in [7] , matrices K and P can be computed by the following LMI, which is derived from Eq. (9) by applying recursively the Schur complement [28] : ⎡ ⎢ ⎢ ⎣ W W A T N + Y T B T N W Q 1 / 2 N Y T R 1 / 2 N A N W + B N Y W 0 0 Q 1 / 2 N W 0 I 0 R 1 / 2 N Y 0 0 I ⎤ ⎥ ⎥ ⎦ > 0, (10a) i   j ⇒  Y ij = Y ji = 0, W ij = W ji = 0, (10b) where W = P −1 and Y = K P −1 are ancillary decision variables, and with i   jsymbolizing that agents iand jare not connected by topology . Notice that constraints (10b) impose a sparsity pattern in the controller directly related to the communication constraints of the network topology. Finally, from now on, the dependence on time step kwill be omitted for the sake of clarity. 3. The set of semivalues Following [7,12,13] , pair (E, r v ) can be interpreted as a coalitional link-game , with E being the set of players and Eq. (8) the characteristic function. Once the game is defined, we 9841 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 introduce in this work the set of semivalues [9] as a tool to allocate the cost of each topology among the links. The set of semivalues comprises a collection of payoff rules from cooperative game theory that assign to each player a weighted average of its marginal contribution to any coalition it belongs to. In a coalitional setting, the vector of semivalues ψ (E, r v ) is defined ∀ l ∈ Eas ψ l (E, r v ) =  ⊆E: l / ∈  ζ(| | )[ r v ( ∪ { l} ) −r v ()] , (11a) with |E|−1  | | =0 |E| −1 | | ζ(| | ) = 1 , (11b) where ζ(| | ) is the specific weight considered by each semivalue to average the marginal contribution [ r v ( ∪ { l} ) −r v ()] . The set of semivalues is formally characterized by three properties detailed below [9] : • Null player : If the presence of a link l ∈ Ehas no influence in the cost of every coalition inside the network, then its payoff is zero, i.e., If r v ( ∪ { l} ) = r v () , ∀ ⊂E, l / ∈ −→ ψ l (E, r v ) = 0. (12) • Symmetry : If two links l p , l q ∈ Econtribute equally to every coalition that does not include them, then they have the same payoffs, i.e., If r v ( ∪ { l p } ) = r v ( ∪ { l q } ) , ∀ ⊂E, l p , l q / ∈ −→ ψ l p (E, r v ) = ψ l q (E, r v ) . (13) • Additivity : Let (E, r v ) , (E, r w ) be two different games. The payoffs of the sum-game coincide with the addition of the individual game payoffs, i.e., ψ l (E, r v + r w ) = ψ l (E, r v ) + ψ l (E, r w ) . (14) Other interesting properties satisfied by these values can be consulted in [29–32] . Also, some applications of semivalues to political, economic, and sociological problems are detailed in [33] . The two most well-known and studied semivalues are the Shapley [10] and Banzhaf [11] values, which are present in very heterogeneous fields as social networks [34] , wine ranking [35] , electricity [36,37] , biology [38] , water systems [15] , voting [39] , finance [40] , and pollution reduction [41,42] . They are commonly denoted by φ(E, r v ) and β(E, r v ) , respectively, verifying ∀| | ∈ [0, |E| −1] ζ(| | ) | φ= | | !(|E| −| | −1)! |E| ! , ζ( | | ) | β= ζ| β= 1 2 |E|−1 , (15) which, as can be checked, satisfy condition (11b) . Likewise, it can also be seen that both values coincide for simple games with one or two players, i.e., ζ(| | ) | φ= ζ(| | ) | β, with |E| = 1 , 2. Besides the Shapley and Banzhaf values, other semivalues have been studied in the literature. For instance, if ζ(| | ) > 0, ∀ ⊆E, we speak of regular semivalues [43] . Also, the so-called binomial semivalues [44] , denoted by ψ q (E, r v ) , are characterized by ζ(| | ) = q | | (1 −q) |E|−| |−1 , 0 ≤q ≤1 , (16) 9842 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 where, by convention 0 0 = 1 . For q = 0 and q = 1 , we obtain respectively the only two binomial nonregular semivalues, namely the dictatorial index ψ 0 and the marginal index ψ 1 , defined respectively by Owen [45] ψ 0 (E, r v ) = r v ({ l} ) −r v (∅ ) , ψ 1 (E, r v ) = r v (E) −r v (E\{ l} ) . (17) Note that the Banzhaf value corresponds with the binomial semivalue for q = 0. 5 , i.e., ψ 0. 5 (E, r v ) = β(E, r v ) , and that the Shapley value does not belong to this subgroup. Finally, for convenience, we consider the following matrix notation [26] : Definition 3. Consider matrix ∈ R |E|×2 |E| , denoted as semivalues standard matrix , where rows refer to links l ∈ Eand columns to topologies ∈ T . Element s lof is given by s l=  ζ(| | −1) , l ∈ , −ζ(| | ) , l / ∈ , (18) with terms ζ(| | ) in s lsatisfying Eq. (11b) . Matrix , with its elements s ldefined by Eq. (18) , is unique for any link-game with |E| links, and verifies [26] ψ (E, r v ) = ⎡ ⎢ ⎢ ⎢ ⎣ ψ I ψ II . . . ψ |E| ⎤ ⎥ ⎥ ⎥ ⎦ = ⎡ ⎢ ⎢ ⎢ ⎣ r v (0 , x N ) r v (1 , x N ) . . . r v (2 |E| −1 , x N ) ⎤ ⎥ ⎥ ⎥ ⎦ = r v . (19) Exploring Eq. (19) , it follows that topologies corresponding to a null column in matrix  have no impact on the semivalue. 3.1. Promoting/penalizing the control network links by semivalues The semivalue of a link provides us with a measure of its relevance inside the control network. Then, considering constraints on semivalues, some communication paths between controllers, and consequently some network topologies, can be promoted/penalized. To this end, we present an interesting property satisfied by elements s lof matrix to obtain a closed expression for the semivalue of a link, which in turn will be used afterwards to derive LMI conditions on the semivalues. Property 1. Let (N , E) and (E, r v ) be a control network and a coalitional link-game, respectively. Consider also s las the elements of matrix , defined by Eq. (18) . The following expressions are satisfied, ∀ l, :  ⊆E s l= 0, (20a)  ⊆E s l| | = 1 . (20b) The proof of Property 1 is presented in Appendices A and B . 9843 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Also, it is necessary to provide the following redefinition of Eq. (8) , given that the characteristic function of a game has to be zero for empty set 0 : r v  (, x N ) = r v (, x N ) −r v (0 , x N ) = x T N P −P 0 x N + c| | , ∀ ⊆E. (21) At this point, using the aforementioned additivity property of the semivalues, it is possible to represent the semivalue of any link in Efor the redefined game (21) as ψ l (E, r v  ) = ψ l (E, r v ) −ψ l (E, r v ) | =0 =  ⊆E s lr v (, x N ) − ⊆E s lr v (0 , x N ) =  ⊆E s lx T N P x N + c  ⊆E s l| | − constant    x T N P 0 x N  ⊆E s l+  * 0 c  ⊆E s l0. (22) Finally, by applying Property 1 , we get ψ l (E, r v  ) = ψ l (E, r v ) = c +  ⊆E s lx T N P x N , (23) which coincides for the original (8) and the redefined (21) games. This result is simply reduced to ψ ss l (E, r v ) = c, (24) when the system reaches the origin in steady state. Notice that, from a control viewpoint, expression (24) represents an a priori value for the links, related to communication costs. Then, the semivalue (23) can be interpreted as an a posteriori value providing the payoff of the links that captures their effect on the performance of the overall system. Equations (19) and (23) provide closed expressions for the set of semivalues, which generalize those given in [12,13] for the Shapley and Banzhaf values, respectively. Example 2. By using Eq. (18) we can easily calculate matrix . For instance, its expression for any 4-link network is given by matrix (25) , with ζ(| | ) verifying Eq. (11b) . As can be checked, Property 1 is trivially satisfied. 4 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ −ζ(0) ζ(0) −ζ(1) −ζ(1) −ζ(1) ζ(1) ζ(1) ζ(1) −ζ(2) −ζ(2) −ζ(2) ζ(2) ζ(2) ζ(2) −ζ(3) ζ(3) −ζ(0) −ζ(1) ζ(0) −ζ(1) −ζ(1) ζ(1) −ζ(2) −ζ(2) ζ(1) ζ(1) −ζ(2) ζ(2) ζ(2) −ζ(3) ζ(2) ζ(3) −ζ(0) −ζ(1) −ζ(1) ζ(0) −ζ(1) −ζ(2) ζ(1) −ζ(2) ζ(1) −ζ(2) ζ(1) ζ(2) −ζ(3) ζ(2) ζ(2) ζ(3) −ζ(0) −ζ(1) −ζ(1) −ζ(1) ζ(0) −ζ(2) −ζ(2) ζ(1) −ζ(2) ζ(1) ζ(1) −ζ(3) ζ(2) ζ(2) ζ(2) ζ(3) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . (25) Remark 2. An analysis by agents from the link-game can be performed by considering a generalization of the original position value [8] , focused on the Shapley value, to allocate the semivalue of the links among the agents involved in the control network, by πψ i (N , v , E) = 1 2  l∈E i ψ l (E, r v ) , ∀ i ∈ N , (26) with E i being the subset of links connected to agent i. 9844 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 4. Efficiency index η(h) for the different semivalues analyzed. The convergence is obtained with h = 9 for the Banzhaf value, with h = 10 for the Shapley value and dictatorial index, and with h = 11 for the marginal index. by Eq. (17) . The following semivalues constraints are considered: ψ III (E, r v ) < 2 ψ V (E, r v ) , 3 ψ IV (E, r v ) −1 2 ψ VI (E, r v ) > 1 3 , 1 + ψ V (E, r v ) < 4 ψ VII (E, r v ) −ψ II (E, r v ) , (42a) ψ VII (E, r v ) ≥ψ II (E, r v ) ≥ψ VIII (E, r v ) ≥ψ I (E, r v ) , (42b) which can be rewritten as in Eq. (27) , and satisfy Eq. (29) . Set Shas been calculated by using Eqs. (28) and (30) for constraints (42a) and (42b) , respectively. Then, considering (36) , set S con has been derived by matrices P LQR and P 0 . In this example, we selected a set fix compatible with the four semivalues analyzed in this work to provide a qualitative comparison using similar constraints. Therefore, sets T cri related to degenerate semivalues were included in fix , for a full number of p = 50 samples, i.e., fix = { 0 , 1 , . . . , |E| , 2 |E| −|E|−1 , . . . , 2 |E| −2 , 2 |E| −1 } , = { fix , rand (50, T \ fix ) } . (43) The design algorithm proposed in Section 4.1 has been implemented using Matlab® tools LMI Control Toolbox [51] and the class for coalitional control NetV0 [52] , in a 2.2 GHz quad-core Intel® Core TM i7/16 GB RAM computer. As stopping criteria, we have considered whichever comes first from: a maximum number of iterations h max = 20, and η(h) −η(h − 1) < 0. 005 , with η(t) given by Eq. (31) , and where only topologies ∈ were considered. The evolution of η(h) with the number of iterations his shown in Fig. 4 . As a result of the algorithm considered, a feasible solution for matrices K , P ∈ R 6 ×6 , ∀ ∈ , is obtained. Once the design problem is solved, Control Scheme 1 is executed taking k s = 3 and considering the randomly generated initial state x 0 N = [ 1 . 4455 5 . 8405 −1 . 6053 0. 6507 8 . 5141 −2. 8324 ] . (44) 9851 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 5. Network topology evolution for the unconstrained and the four constrained scenarios. The evolution of the topologies for the unconstrained scenario and also when constraints (42) on the four semivalues are considered is represented in Fig. 5 . Furthermore, the specific change in the semivalues before and after considering constraints is detailed in Fig. 6 , where Eq. (39) has been used for the representation, and coincides with Eq. (23) for the dictatorial and marginal indices so as all their topologies that lead to nonnull columns in belong to . It is interesting to observe the degenerate evolution of the marginal index before applying constraints, which occurs because their representative topologies imply at most one disconnecting link, leading to the same solution for LMI (10) , and therefore to the same K and P matrices for the grand coalition of agents (recall Fig. 1 ). Once the semivalues constraints come into play, they modify the control matrices and the semivalues vary. Notice that each semivalue evolves in its own way to satisfy the specifications, which, in turn, may lead to a different network topology evolution depending on the semivalue. In any case, despite the fact that eligible topologies are limited to those in set , in general the most expensive/economic links are deactivated/enabled according to specifications (42) . Indeed, links V and IV, the most expensive ones for the Shapley and Banzhaf values, respectively, are disconnected in the respective full topology trajectories. Conversely, links I, VI and VIII, the most economical ones for these semivalues, are normally activated. Regarding dictatorial and marginal indices, although they share the evolution of topologies, they permanently disable links III and VI, respectively the first and third most costly ones. Similarly, both indices promote links IV and I, respectively their most economical ones. Note also that all semivalues tend to c = 1 . 5 , as expected from Eq. (24) , until reaching decentralized topology 0 in steady state. Finally, the cumulated cost (32) is given by J φ cum = 1233 . 1 , J β cum = 1251 . 7 , J ψ 0 cum = 656 . 4, J ψ 1 cum = 657 . 9 . As can be seen, the two degenerate semivalues, with few representative topologies (recall (37) ), generate the lowest cumulated costs. The simulation lasted only 11.2 min for the chosen size of , while with the full topology set T the overall time increases to 41.6 h. The performance loss was computed by averaging index α(recall Eq. (40) ) by each ∈ and also by the four semivalues, obtaining αaver = 14. 2% , where a set of 10 5 random states was considered. This strong computational 9852 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 6. Semivalues evolution with and without considering constraints. 9853 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Fig. 7. Tradeoff between performance degradation (in %) and computation time (in s) as a function of the size of the set of sampled topologies. burden reduction of 99.6% together with the reasonable performance loss, illustrates the applicability of the random sampling method presented here. In any case, beyond the experiments performed in this section, a few additional simulations were run, using different random sets  and initial states. In any case, we achieve: i) a feasible solution for the control matrices and asymptotical stability for the system; ii) the satisfaction of all the constraints (42) imposed; and iii) the disabling (enabling) of the most expensive (economic) links in the evolution of the topologies. Finally, we investigate the sensitivity of the design method regarding the size of . Figure 7 shows, for the case of the Shapley value, how the tradeoff between the performance index α and the average computation time per iteration of the design method varies with the cardinality of , with fix = { 0 , 2 |E| −1 } . As can be seen, the larger the sampling set, the less the degradation in performance, but the greater the computation time. This result suggests that the problem can be solved for an increasingly larger sampling size to obtain better performance. Eventually, the computation time will become unaffordable, but since marginal performance improvements tend to decrease, the size of does not need to be too large. 7. Conclusions This article presents a method for designing coalitional controllers based on linear matrix inequalities (LMIs). Our approach substantially reduces the computational burden of previous methods [12–14,26] at the expense of increasing their conservativeness, making the coalitional strategy suitable for larger systems. The key idea is to simplify the LMI problem by selecting a collection of topologies from the full set and using more conservative and lighter constraints on the payoff rules. Furthermore, the complete set of semivalues has been considered here, generalizing previous contributions. To this end, a closed semivalues expression as a function of the game has been derived. The proposed method has been applied to an academic example, where the communication links were promoted/penalized according to semivalues constraints in four scenarios, where the optimal network topology in terms of cooperation costs and control performance was 9854 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 Table 2 Combinatorial results for different cardinalities and number of topologies. Number of topologies Sum for all cardinalities Cardinality | | ( |E| | | ) , | |∈ [0, |E| ]  |E| | | =0 ( |E| | | ) =2 |E| Cardinality | | , l / ∈ ( |E|−1 | | ) , | |∈ [0, |E|−1]  |E|−1 | | =0 ( |E|−1 | | ) =2 |E|−1 Cardinality | | + 1 , l ∈ ( |E| | | +1 ) , | | +1 ∈ [1 , |E| ]  |E| | | =1 ( |E|−1 | |−1 ) =2 |E|−1 implemented at each time step. The size of the example allows us to compare the results in terms of computational burden with respect to previous approaches, revealing a strong saving in computation time with low performance losses, which highlights the suitability of the presented approach. Future work should include algorithms based on designing control matrices in a distributed fashion following [53] . Also, alternative samplings that allow for a partitioning of the semivalues constraints computation and nonrandom ways of pre-selecting the samples could be considered. Finally, the replacement of conservative constraints by chance ones in the design method will be object of further research. Declaration of Competing Interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Acknowledgments This work has been supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation funding programme (OCONTSOLAR, grant agreement No. 789051), and the Spanish Ministry of Science and Innovation (C3PO- R2D2 , reference No. PID2020-119476RB-I00 ). Appendix A. Proof of Property 1 .1 Consider a network (N , E) , which contains 2 |E| topologies according to Definition 1 . Taking into account Eq. (18) , it is possible to rewrite the left side of Eq. (20a) as  ⊆E s l=  ⊆E: l∈  ζ(| | −1) − ⊆E: l / ∈  ζ(| | ) , (45) where topologies that include and do not include a given link lare separated. Note that by using combinatorial analysis, it can be checked that the number of topologies with cardinality | | that do not contain a specific link lcoincides with the number of topologies with cardinality | | + 1 that contain this link, which is shown in Table 2 . Taking these results into account, it is deduced that the terms contained in Eq. (45) are canceled in pairs, obtaining  ⊆E: l∈  ζ(| | −1) − ⊆E: l / ∈  ζ(| | ) 9855 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 = − 1    ζ(0) + ⎛ ⎝ 1    ζ(0) − 2    (|E| −1) ζ(1) ⎞ ⎠ + ⎛ ⎜ ⎜ ⎝ 2    (|E| −1) ζ(1) − 3    (|E| −1)(|E| −2) 2 ζ(2) ⎞ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎝ 3    (|E| −1)(|E| −2) 2 ζ(2) − 4    (|E| −1)(|E| −2)(|E| −3) 6 ζ(3) ⎞ ⎟ ⎟ ⎠ + ··· + ⎛ ⎜ ⎜ ⎜ ⎝ |E|−2    (|E| −1)(|E| −2) . . . 3 (|E| −3)! ζ(|E| −3) − |E|−1    (|E| −1)(|E| −2) . . . 2 (|E| −2)! ζ(|E| −2) ⎞ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎝ |E|−1    (|E| −1)(|E| −2) . . . 2 (|E| −2)! ζ(|E| −2) − |E|    (|E| −1)(|E| −2) . . . 1 (|E| −1)! ζ(|E| −1) ⎞ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎝ |E|    (|E| −1)(|E| −2) . . . 1 (|E| −1)! ζ(|E| −1) ⎞ ⎟ ⎟ ⎟ ⎠ = 0. (46)  Appendix B. Proof of Property 1 .2 Let (N , E) be a network, with ∈ T being their corresponding topologies. Analogously to what is done in Eq. (45) , it is possible to use Eq. (18) to rewrite the left side of Eq. (20b) as  ⊆E s l| | =  ⊆E: l∈  ζ(| | −1) | | − ⊆E: l / ∈  ζ(| | ) | | . (47) Then, using a similar reasoning that in the proof of Property 1 .1, we have  ⊆E: l∈  ζ(| | −1) | | − ⊆E: l / ∈  ζ(| | ) | | = 0 −ζ(0) + 1 ζ(0) −(|E| −1) ζ(1) + 2 (|E| −1) ζ(1) −(|E| −1)(|E| −2) 2 ζ(2)  + 3 (|E| −1)(|E| −2) 2 ζ(2) −(|E| −1)(|E| −2)(|E| −3) 6 ζ(3)  + ··· + (|E| −2) (|E| −1)(|E| −2) . . . 3 (|E| −3)! ζ(|E| −3) −(|E| −1)(|E| −2) . . . 2 (|E| −2)! ζ(|E| −2)  9856 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 + (|E| −1) (|E| −1)(|E| −2) . . . 2 (|E| −2)! ζ(|E| −2) −(|E| −1)(|E| −2) . . . 1 (|E| −1)! ζ(|E| −1)  + |E | (|E | −1)(|E| −2) . . . 1 (|E | −1)! ζ(|E | −1) . (48) Finally, notice that most of the terms in Eq. (48) are recursively canceled in pairs by the rule (| | + 1) −| | ζ(| | ) = ζ(| | ) , achieving the following simplified expression:  ⊆E: l∈  ζ(| | −1) | | − ⊆E: l / ∈  ζ(| | ) | | = ζ(0) + (|E| −1) ζ(1) + (|E| −1)(|E| −2) 2 ζ(2) + (|E| −1)(|E| −2)(|E| −3) 6 ζ(3) + ··· + (|E| −1)(|E| −2) . . . 3 (|E| −3)! ζ(|E| −3) + (|E| −1)(|E| −2) . . . 2 (|E| −2)! ζ(|E| −2) + (|E| −1)(|E| −2) . . . 1 (|E| −1)! ζ(|E| −1) = |E|−1  | | =0 (|E| −1)(|E| −2)(|E| −3) . . . (|E| −| | ) | | ! ζ(| | ) = |E|−1  | | =0 (|E| −1)! (|E| −(| | + 1))! | | ! ζ(| | ) = |E|−1  | | =0 |E| −1 | | ζ(| | ) , (49) which is trivially equal to 1, considering condition Eq. (11b) .  References [1] P. Chanfreut , J.M. Maestre , E.F. Camacho , A survey on clustering methods for distributed and networked control systems, Annu. Rev. Control 52 (2021) 75–90 . [2] M. Philippe , R. Essick , G.E. Dullerud , R.M. Jungers , Stability of discrete-time switching systems with constrained switching sequences, Automatica 72 (2016) 242–250 . [3] J. Barreiro-Gomez , C. Ocampo-Martinez , N. Quijano , Time-varying partitioning for predictive control design: density-games approach, J. Process Control 75 (2019) 1–14 . [4] S. Riverso , M. Farina , G. Ferrari-Trecate , Plug-and-play model predictive control based on robust control invariant sets, Automatica 50 (8) (2014) 2179–2186 . [5] F. Dörfler , M.R. Jovanovi´c , M. Chertkov , F. Bullo , Sparsity-promoting optimal wide-area control of power networks, IEEE Trans. Power Syst. 29 (5) (2014) 2281–2291 . [6] Y. Zheng , Y. Wei , S. Li , Coupling degree clustering-based distributed model predictive control network design, IEEE Trans. Autom. Sci. Eng. 15 (4) (2018) 1749–1758 . [7] J.M. Maestre , D. Muñoz de la Peña , A. Jiménez Losada , E. Algaba , E.F. Camacho , A coalitional control scheme with applications to cooperative game theory, Opt. Control Appl. Methods 35 (5) (2014) 592–608 . [8] P. Borm , G. Owen , S. Tijs , On the position value for communication situations, SIAM J. Discrete Math. 5 (3) (1992) 305–320 . [9] P. Dubey , A. Neyman , R.J. Weber , Value theory without efficiency, Math. Oper. Res. 6 (1) (1981) 122–128 . [10] L.S. Shapley , A value for N-person games, in: H.W. Kuhn, A.W. Tucker (Eds.), Contributions to the Theory of Games II. Annals of Mathematics Studies, vol. 28, Princeton University Press, Princeton, New Jersey, USA, 1953, pp. 307–317 . [11] J.F. Banzhaf , Weighted voting doesn’t work: a mathematical analysis, Rutgers Law Rev. 19 (1965) 317–343 . [12] F.J. Muros , J.M. Maestre , E. Algaba , T. Alamo , E.F. Camacho , Networked control design for coalitional schemes using game-theoretic methods, Automatica 78 (2017a) 320–332 . 9857 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 [13] F.J. Muros , E. Algaba , J.M. Maestre , E.F. Camacho , The Banzhaf value as a design tool in coalitional control, Syst. Control Lett. 104 (2017b) 21–30 . [14] P. Chanfreut , J.M. Maestre , F.J. Muros , E.F. Camacho , Clustering switching regions for feedback controllers: a convex approach, IEEE Trans. Control Netw. Syst. 8 (4) (2021) 1730–1742 . [15] F.J. Muros , J.M. Maestre , C. Ocampo-Martinez , E. Algaba , E.F. Camacho , A game theoretical randomized method for large-scale systems partitioning, IEEE Access 6 (2018) 42245–42263 . [16] F. Fele , J.M. Maestre , E.F. Camacho , Coalitional control: cooperative game theory and control, IEEE Control Syst. Mag. 37 (1) (2017) 53–69 . [17] P.R. Baldivieso-Monasterios , P.A. Trodden , Coalitional predictive control: consensus-based coalition forming with robust regulation, Automatica 125 (2021) 109380 . [18] E. Masero , L.A. Fletscher , J.M. Maestre , A coalitional model predictive control for the energy efficiency of next-generation cellular networks, Energies 13 (24) (2020) 6546 . [19] P. Chanfreut , J.M. Maestre , E.F. Camacho , Coalitional model predictive control on freeways traffic networks, IEEE Trans. Intell. Transp. Syst. 22 (11) (2021) 6772–6783 . [20] D. Bauso , J. Timmer , On robustness and dynamics in (un)balanced coalitional games, Automatica 48 (10) (2012) 2592–2596 . [21] A. Nedi´c , D. Bauso , Dynamic coalitional TU games: distributed bargaining among players’ neighbors, IEEE Trans. Autom. Control 58 (6) (2013) 1363–1376 . [22] D. Bauso , G. Notarstefano , Distributed n-player approachability and consensus in coalitional games, IEEE Trans. Autom. Control 60 (11) (2015) 3107–3112 . [23] D. Bauso , M. Cannon , Consensus in opinion dynamics as a repeated game, Automatica 90 (2018) 204– 211 . [24] D. Prenga , General features of the q-XY opinion model, J. Hum. Earth, Future 1 (2) (2020) 87–96 . [25] M. Smyrnakis , D. Bauso , H. Tembine , Game-theoretic learning and allocations in robust dynamic coalitional games, SIAM J. Control Optim. 57 (4) (2019) 2902–2923 . [26] F.J. Muros , J.M. Maestre , An LMI-based approach for semivalues constraints in coalitional feedback control, in: Proceedings of the 21st IFAC World Congress, 2020, pp. 3958–3963 . Berlin, Germany [27] A. Bemporad , M. Morari , Control of systems integrating logic, dynamics, and constraints, Automatica 35 (3) (1999) 407–427 . [28] F. Zhang , The Schur Complement and its Applications, Numerical Methods and Algorithms, vol. 4, Springer, New York, USA, 2005 . [29] I. Dragan , On the coalitional rationality of the Banzhaf value and other non-efficient semivalues, Appl. Math. 6 (12) (2015) 2069–2076 . [30] M. Domènech , J.M. Giménez , M.A. Puente , Semivalues: weighting coefficients and allocations on unanimity games, Optim. Lett. 12 (2018) 1841–1854 . [31] E. Algaba , V. Fragnelli , J. Sánchez-Soriano (Eds.) , The Handbook of the Shapley Value, CRC Press Series in Operations Research, Chapman & Hall/CRC, Boca Raton, Florida, USA, 2019 . [32] F. Carreras , J. Freixas , A note on regular semivalues, Int. Game Theory Rev. 2 (4) (2000) 345–352 . [33] F. Carreras , J. Freixas , Semivalue versatility and applications, Ann. Oper. Res. 109 (1–4) (2002) 343–358 . [34] R. Narayanam , Y. Narahari , A Shapley value-based approach to discover influential nodes in social networks, IEEE Trans. Autom. Sci. Eng. 8 (1) (2011) 130–147 . [35] V. Ginsburgh , I. Zang , Shapley ranking of wines, J. Wine Econ. 7 (2) (2012) 169–180 . [36] M. Marzband , R.R. Ardeshiri , M. Moafi, H. Uppal , Distributed generation for economic benefit maximization through coalition formation-based game theory concept, Int. Trans. Electr. Energy Syst. 27 (6) (2017) e2313 . [37] J. Barreiro-Gomez , C. Ocampo-Martinez , N. Quijano , J.M. Maestre , Non-centralized control for flow-based distribution networks: a game theoretical insight, J. Franklin Inst. 354 (14) (2017) 5771–5796 . [38] R. Lucchetti , S. Moretti , F. Patrone , P. Radrizzani , The Shapley and Banzhaf values in microarray games, Comput. Oper. Res. 37 (8) (2010) 1406–1412 . [39] L. Monroy , F.R. Fernández , Banzhaf index for multiple voting systems. an application to the European Union, Ann. Oper. Res. 215 (2014) 215–230 . [40] N. Tarashev , K. Tsatsaronis , C. Borio , Risk attribution using the Shapley value: methodology and policy applications, Rev. Financ. 20 (3) (2016) 1189–1213 . [41] L. Petrosjan , G. Zaccour , Time-consistent Shapley value allocation of pollution cost reduction, J. Econ. Dyn. Control 27 (3) (2003) 381–398 . [42] Y.- J . Zhang , A.-D. Wang , Y. -B . Da , Regional allocation of carbon emission quotas in China: evidence from the Shapley value method, Energy Policy 74 (2014) 454–464 . 9858 F. J. Muros and J.M. Maestre Journal of the Franklin Institute 359 (2022) 9836–9859 [43] F. Carreras , J. Freixas , Some theoretical reasons for using (regular) semivalues, in: H. de Swart (Ed.), Logic, Game Theory and Social Choice, Tilburg University Press, 1999, pp. 140–154 . [44] M.A. Puente , Aportaciones a la representabilidad de juegos simples y al cálculo de soluciones de esta clase de juegos (in Spanish), Technical University of Catalonia, Spain, 2000 Ph.D. thesis . [45] G. Owen , Characterization of the Banzhaf-Coleman index, SIAM J. Appl. Math. 35 (2) (1978) 315–327 . [46] E. Zio , The Monte Carlo Simulation Method for System Reliability and Risk Analysis, Springer, London, UK, 2013 . [47] J. Castro , D. Gómez , J. Tejada , Polynomial calculation of the Shapley value based on sampling, Comput. Oper. Res. 36 (5) (2009) 1726–1730 . [48] J. Castro , D. Gómez , E. Molina , J. Tejada , Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation, Comput. Oper. Res. 82 (2017) 180–188 . [49] H. Ishii , R. Tempo , Distributed randomized algorithms for the PageRank computation, IEEE Trans. Autom. Control 55 (9) (2010) 1987–2002 . [50] M.K. Tarkowski , P.L. Szczepa´nski , T.P. Michalak , P. Harrenstein , M. Wooldridge , Efficient computation of semivalues for game-theoretic network centrality, J. Artif. Intell. Res. 63 (2018) 145–189 . [51] P. Gahinet , A.S. Nemirovskii , A.J. Laub , M. Chilali , LMI Control Toolbox for Use with MATLAB®, The MathWorks, Inc., Natick, Massachusetts, USA, 1995 . [52] J.M. Maestre , F.J. Muros , F. Fele , E.F. Camacho , An assessment of coalitional control in water systems, in: Proceedings of the 14th European Control Conference (ECC), 2015, pp. 3291–3296 . Linz, Austria [53] G. Darivianakis , A. Eichler , J. Lygeros , Distributed model predictive control for linear systems with adaptive terminal sets, IEEE Trans. Autom. Control 65 (3) (2020) 1044–1056 . 9859