El control coalicional en el marco de la teoría de juegos cooperativos

Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 www.revista-riai.org El control coalicional en el marco de la teor´ ıa de juegos cooperativos Muros, F. J.a,b,∗ aDepartamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Camino de los Descubrimientos, s/n, 41092, Sevilla, Espa˜na. bDepartamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad Loyola Andaluc´ıa, Avda. de las Universidades s/n, 41704, Dos Hermanas, Sevilla, Espa˜na To cite this article: Muros, F. J. 2021. Coalitional control in the framework of cooperative game theory. Revista Iberoamericana de Automática e Informática Industrial 18, 97-112. https://doi.org/10.4995/riai.2020.13456 Resumen El control coalicional es una rama incipiente del control distribuido donde los distintos agentes se agrupan de forma din´ amica en coaliciones en funci´ on de los enlaces de comunicaci´ on activos/inactivos en cada instante de tiempo. Gracias a ello, se reduce la carga de comunicaci´ on sin comprometer las prestaciones del sistema. En este tutorial, se analizan las principales caracter´ ısticas de estos esquemas dentro del marco de la teor´ ıa de juegos cooperativos, estando el juego definido por la funci´ on de coste a optimizar en el esquema de control, y correspondiendo los jugadores bien a los enlaces de comunicaci´ on o bien a los propios agentes. En este contexto, se estudiar´ an diversas herramientas de teor´ ıa de juegos cooperativos, con objeto de clasificar jugadores, imponer restricciones en los mismos, proponer v´ ıas de c´ alculo m´ as eficientes, realizar particionado de sistemas, etc., examinando las caracter´ ısticas m´ as relevantes presentadas por cada herramienta. Palabras clave: Control coalicional, Control por agrupamiento, Control distribuido, Control ´ optimo, Realimentaciones lineales, Teor´ ıa de juegos cooperativos, Valor de Shapley, Desigualdades matriciales lineales. Coalitional control in the framework of cooperative game theory Abstract Coalitional control is a fairly new branch of distributed control where the agents merge dynamically into coalitions according to the enabled/disabled communication links at each time instant. Therefore, with these schemes there is a reduction of the communication burden without compromising the system performance. In this tutorial, the main features of these schemes will be introduced in the framework of cooperative game theory, being the game related to the cost function that is optimized by the control approach, and with the players corresponding to either the communication links or the agents involved. In this context, several cooperative game theory tools will be considered in order to: rank the players, impose constraints on them, provide more efficient ways of calculation, perform system partitioning, etc., hence analyzing the main features related to each tool. Keywords: Coalitional control, Control by clustering, Distributed control, Optimal control, Linear feedbacks, Cooperative game theory, Shapley value, Linear matrix inequalities. 1. Introducci´ on La teor´ ıa de control y la teor´ ıa de juegos son dos ramas interdisciplinarias de la ingenier´ ıa y las matem´ aticas que lidian, respectivamente, con el comportamiento de sistemas din´ amicos mediante el uso de dispositivos conocidos como controladores, y con situaciones de conflicto o de cooperaci´ on llamadas juegos, mantenidas entre entidades inteligentes y racionales o jugadores (Muros, 2019). En este tutorial se interrelacionan ambas disciplinas asumiendo fundamentalmente que los controladores –o sus conexiones– son los jugadores de un determinado juego. Para ello haremos uso de esquemas de control ´optimo, que persiguen optimizar un cierto ´ ındice de coste, y aplicaremos t´ ecnicas de realimentaci´on lineal del vector de estados. N´ otese que los problemas derivados de la comunicaci´ on, como velo- ∗Autor para correspondencia: [email protected], [email protected] Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) cidades de datos, tecnolog´ ıa y seguridad de la red, o retardos y p´ erdida de paquetes, que est´ an dentro del ´ ambito de los sistemas de control en red o networked control systems (NCSs) (Zhang et al., 2020), no ser´ an abordados en este trabajo. Tradicionalmente, los esquemas de control ´ optimo se han implementado de forma centralizada, i.e., un ´ unico controlador gobierna el sistema completo. Es obvio que si se asume acceso ilimitado a toda la informaci´ on del sistema en cualquier instante, las soluciones centralizadas ofrecen las mejores prestaciones (Maestre, 2010). Sin embargo, hay muchos escenarios donde no es posible trabajar con esquemas centralizados debido a cuestiones como complejidad del sistema, extensi´ on geogr´ afica o privacidad, cobrando sentido las propuestas no centralizadas. En este caso, el problema de control se divide en piezas m´ as peque˜ nas o subsistemas, asignando cada una a controladores locales o agentes. Algunas de las ventajas m´ as conocidas de estos esquemas son su modularidad, escalabilidad, facilidad de implementaci´ on o robustez, lo que los hace ideales para el control de sistemas de gran escala, como redes de tr´ afico (De Souza et al., 2015), el´ ectricas (Negenborn et al., 2008; Yazdanian and Mehrizi-Sani, 2014), o cadenas de suministro (Maestre et al., 2011). Buenos recopilatorios de t´ ecnicas no centralizadas en un marco de control predictivo, conocido como model predictive control o MPC (Camacho and Bordons, 2013), se encuentran en (Scattolini, 2009; Maestre and Negenborn, 2014). Dentro de las soluciones no centralizadas, dependiendo del grado de interacci´ on entre los subsistemas, los agentes pueden o no necesitar coordinarse entre ellos, distingui´ endose entre control descentralizado, si no existe comunicaci´ on entre los agentes, y control distribuido, cuando los agentes comparten cierta informaci´ on. T´ ıpicamente, los esquemas distribuidos consideran que los grupos de agentes que colaboran se mantienen fijos en el tiempo, es decir, no se modifica la forma en la que los agentes se agrupan (Negenborn et al., 2009; Maestre et al., 2011). Sin embargo, en los ´ ultimos a˜ nos han aparecido diversas estrategias que consideran de forma expl´ ıcita una evoluci´on din´amica de vecindades entre agentes, tales como los sistemas switching (Philippe et al., 2016), el particionado variable en el tiempo (Barreiro-Gomez et al., 2019), los esquemas plug-and- play (Riverso et al., 2013, 2014), o el control por agrupamiento oclustering (D¨ orfler et al., 2014; Zheng et al., 2018). En este tutorial, nos centraremos en el control coalicional (Maestre et al., 2014), una estrategia de control por clustering donde los subsistemas est´ an conectados en red y los recursos de comunicaci´ on se penalizan din´ amicamente para disuadir a los agentes de intercambiar informaci´ on innecesaria. Como consecuencia, los enlaces de comunicaci´ on se activan/desactivan estableciendo topolog´ıas de red distintas seg´ un las necesidades del sistema, consigui´ endose una reducci´ on del coste de comunicaci´ on sin p´ erdida relevante de prestaciones. Cada coalici´on resultante coordina de forma aut´ onoma las acciones de control de sus agentes miembros. Esta implementaci´ on coalicional, m´ as escalable que los esquemas distribuidos tradicionales, se ha extendido al MPC (Fele et al., 2017, 2018; Baldivieso- Monasterios and Trodden, 2021; Chanfreut et al., 2021b), con aplicaciones a sistemas de agua (Fele et al., 2014; N´ u˜ nez et al., 2015; Maestre and Ishii, 2017; Muros et al., 2018a,b), fuentes de energ´ ıa renovables (Masero et al., 2020, 2021), o redes de carreteras (Chanfreut et al., 2021a), entre otras. La estructura de los esquemas no centralizados, y en particular la de los coalicionales, nos invita a considerar bien los agentes o bien sus enlaces de comunicaci´ on como jugadores en un cierto juego (Muros, 2019). B´ asicamente, es posible diferenciar entre juegos cooperativos yjuegos no cooperativos, bas´ andose los ´ ultimos en que cada jugador trata de maximizar su propio beneficio de forma ego´ ısta (Nash, 1951). Por contra, en los juegos cooperativos cada jugador puede hacer ciertos acuerdos y sacrificios en b´ usqueda de un bien com´ un, i.e., unas prestaciones globales (Peleg and Sudh¨ olter, 2007). En ambos casos, el objetivo del jugador es maximizar el valor esperado de una cierta regla de pagos, medido en una cierta escala de utilidad o satisfacci´ on. Buenas referencias generales de teor´ ıa de juegos son (Maschler et al., 2013; Owen, 2013; Peters, 2015). Centr´ andonos en los juegos cooperativos, es evidente que sus aplicaciones a la ingenier´ ıa son cada vez m´ as comunes, con contribuciones a las redes de comunicaci´ on (Saad et al., 2009; Zhang et al., 2011; Han et al., 2012), las redes inteligentes o smart grids (Saad et al., 2012; Marzband et al., 2017), las estructuras sociales (Gilles, 2010), o el propio control predictivo (Fele et al., 2017), o robusto (Bauso and Timmer, 2009, 2012; Nedi´ c and Bauso, 2013), desarrollando algoritmos de consenso en (Olfati-Saber and Murray, 2004; Ren and Beard, 2005; Olfati-Saber et al., 2007; Cai and Ishii, 2011; Bauso and Notarstefano, 2015; Bauso and Cannon, 2018). En este sentido, es destacable la visi´ on de (Maestre et al., 2014), donde se combinan de forma natural la teor´ ıa de juegos cooperativos y el control coalicional. En este tutorial, se analizar´ a una l´ ınea de investigaci´ on (Muros et al., 2017a,b,c, 2016, 2018a,b) desarrollada a partir de dicho trabajo, donde se aplican al control coalicional herramientas de teor´ ıa de juegos cooperativos como el valor de Shapley (Shapley, 1953b), posici´ on (Borm et al., 1992), Banzhaf (Banzhaf, 1965), o las soluciones de poder de Harsanyi (van den Brink et al., 2011), con objeto de imponer restricciones a los jugadores, medir su relevancia, o proponer v´ ıas de c´ alculo m´ as eficientes, analizando aqu´ ı las principales caracter´ ısticas de cada herramienta. El resto del art´ ıculo est´ a organizado de la siguiente forma. En la secci´ on 2 se introduce el control coalicional, presentando el esquema jer´ arquico usado en este tutorial. La secci´ on 3 incluye un an´ alisis de diversas herramientas de teor´ ıa de juegos cooperativos, distinguiendo situaciones de comunicaci´ on completa y restringida. Las aplicaciones de dichas herramientas al control coalicional se comentan espec´ ıficamente en la secci´ on 4, incluyendo ideas para reducir la carga computacional. En la secci´ on 5 se proponen un ejemplo acad´ emico de simulaci´ on y algunos casos pr´ acticos de sistemas reales que ilustran las aplicaciones presentadas. Finalmente, las conclusiones derivadas de este trabajo se detallan en la secci´ on 6. 2. Introducci´ on al Control Coalicional Sea un conjunto N={1,2, . . . , |N|} de subsistemas interconectados, pertenecientes a la clase de sistemas distribuidos lineales. Cada subsistema est´ a gobernado por un controlador local o agente, cuya din´ amica se describe como: xi(k+1) =Aiixi(k)+Biiui(k)+zi(k), zi(k)=X j,ihAi jxj(k)+Bi juj(k)i,(1) 98 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 Figura 1: Ejemplo de red de cinco agentes y cuatro enlaces donde xi(k)∈Rnxies el vector de estados del agente i,ui(k)∈ Rnuidefine su vector de entradas, y Aii ∈Rnxi×nxi,Ai j ∈Rnxi×nxj yBii ∈Rnxi×nui,Bi j ∈Rnxi×nujson las matrices de transici´ on de estados y de entradas, respectivamente. El t´ ermino zi(k)∈Rnxi refleja la influencia sobre el agente idel resto de agentes. 2.1. Arquitectura de control en red Con el objetivo de intercambiar informaci´ on, asumimos que los agentes en Nest´ an interconectados a trav´ es de una red definida mediante un grafo no dirigido (N,E), donde E⊆N×N es el conjunto de enlaces l∈Eque define las conexiones de comunicaci´ on. Cada enlace se asumir´ a activo o inactivo en un cierto instante de control k, considerando un coste por enlace σl∈R+\{0}si el enlace lest´ a activo. Este razonamiento nos lleva de forma natural al concepto de topolog´ıa de red Λ(k) (Maestre et al., 2014; Muros et al., 2017c), que se define como el conjunto de enlaces activos en el instante de control k, con Λ(k)⊆ E. Dados |E|enlaces existen 2|E|topolog´ ıas de red posibles, denotadas mediante el conjunto T={Λ0,Λ1, . . . , Λ2|E|−1}. Ejemplo 1. Consid´erese la red representada en la Figura 1. Las diferentes topolog´ıas de red, i.e., T={Λ0,Λ1, . . . , Λ15}, y sus correspondientes enlaces activos y componentes de comunicaci´on, aparecen detallados en la Tabla 1. Cuando una cierta topolog´ ıa est´ a activa en un instante de control concreto, se generan un conjunto de coaliciones de agentes o componentes de comunicaci´on C⊆Nque coexisten en dicho instante. Los agentes dentro de una componente son libres de intercambiar toda la informaci´ on necesaria para coordinarse. Es decir, cada componente Coptimiza el coste de sus miembros, que deciden sus entradas de forma cooperativa, i.e., uC(k)=(ui(k))i∈C, defini´ endose un modelo an´ alogo a (1) a nivel de coaliciones xC(k+1) =ACC xC(k)+BCC uC(k)+zC(k), zC(k)=X j<ChACjxj(k)+BCjuj(k)i,(2) Tabla 1: Topog´ ıas y componentes de comunicaci´ on de la red de la Figura 1 Enlaces Enlaces ΛI II III IV Componentes ΛI II III IV Componentes Λ0X X X X {1},{2},{3},{4},{5}Λ8XX X X{1},{2,3,4},{5} Λ1XX X X {1,3},{2},{4},{5}Λ9XXXX{1},{2,3},{4,5} Λ2XXX X {1},{2,3},{4},{5}Λ10 X X X X {1},{2},{3,4,5} Λ3X X XX{1},{2},{3,4},{5}Λ11 X X X X{1,2,3,4},{5} Λ4X X X X{1},{2},{3},{4,5}Λ12 X X XX{1,2,3},{4,5} Λ5X X X X {1,2,3},{4},{5}Λ13 XXX X {1,3,4,5},{2} Λ6XXXX{1,3,4},{2},{5}Λ14 XX X X {1},{2,3,4,5} Λ7XX X X{1,3},{2},{4,5}Λ15 X X X X N={1,2,3,4,5} donde xC(k)∈RnxC,uC(k)∈Rnuison los vectores de estado y entradas de la componente C, con zC(k) siendo la influencia sobre Cque tienen los agentes fuera de dicha coalici´ on, y donde ACC ∈RnxC×nxC,ACj∈RnxC×nxj,BCC ∈RnxC×nuC,BCj∈RnxC×nuj son matrices de las dimensiones apropiadas. Por ´ ultimo, para modelar de forma distribuida el esquema centralizado basta con hacer C=Nen (2), es decir xN(k+1) =ANxN(k)+BNuN(k),(3) donde xN(k)∈RnxN,uN(k)∈RnuNson los vectores agregados de estados y entradas, y AN∈RnxN×nxN,BN∈RnxN×nuNson las matrices globales de transici´ on de estados y de entradas, respectivamente. Trivialmente, al trabajar con una coalici´ on compuesta por todos los agentes, zN(k)=0 en este caso. 2.2. Objetivo de control L´ ogicamente, el prop´ osito de un esquema de control ´ optimo se basa en la minimizaci´ on de una cierta funci´ on de coste, que en nuestro caso combina una componente debida al esfuerzo de control y otra que penaliza el coste de comunicaci´ on. J(xN(k),uN(k),Λ(k)) = Js(xN(k),uN(k),Λ) z }| {  ∞ X =0hxT N(k+)QNxN(k+)+uT N(k+)RNuN(k+)i+ Jc(Λ(k)) z }| { X l∈Λ(k) σl, (4) con Js(xN(k),uN(k),Λ), Jc(Λ(k)) ∈R+siendo el cost-to-go y el coste de comunicaci´ on, respectivamente, donde QN∈ RnxN×nxNyRN∈RnuN×nuNson matrices de ponderaci´ on semidefinida y definida positiva, y con σl∈R+\{0}denotando el coste por enlace previamente introducido. N´ otese que si no se penalizase la comunicaci´ on innecesaria, la optimizaci´ on de (4) nos llevar´ ıa trivialmente a la soluci´ on centralizada. En cualquier caso, ser´ ıa posible penalizar dicha comunicaci´ on con propuestas alternativas a σl, como por ejemplo a trav´ es de la cardinalidad de las componentes de comunicaci´ on. En general, no es posible resolver la minimizaci´ on de (4) de forma directa porque dicho problema pertenece a la clase de los problemas NP-completos (Fletcher and Leyffer, 1998). Para resolver este inconveniente se considera una cota superior de la soluci´ on del problema asumiendo lo siguiente: Suposici´ on 1. Para cada topolog´ıa Λ∈T, existe una matriz KΛ∈RnuN×nxN, que establece una ley de control global uN(k)=KΛxN(k),(5) y una matriz definida positiva PΛ∈RnxN×nxN, que nos proporciona una funci´on de Lyapunov f (xN(k)) =xT N(k)PΛxN(k). Esta funci´on de Lyapunov decrece en el tiempo y nos da una cota superior del cost-to-go del sistema en bucle cerrado cuando la ley de control es (5) xT N(k)PΛxN(k)≥Js(xN(k),uN(k),Λ),(6) donde la igualdad estricta en (6) es la soluci´on optima para el caso centralizado, i.e., con comunicaci´on completa. 2 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 99 Bas´ andonos en la suposici´ on 1, denotando σΛ=Pl∈Λ(k)σl y de acuerdo a (Maestre et al., 2014), es posible definir una cota superior de la funci´ on de coste (4) (Muros et al., 2017b) rv(Λ,xN(k)) =xT N(k)PΛxN(k)+σΛ,(7) que puede minimizarse con respecto a Λpara encontrar en el instante kla topolog´ ıa m´ as apropiada del conjunto Tpara nuestro esquema. En definitiva, el problema del c´ alculo de (7) se reduce a computar previamente las matrices KΛyPΛpara todas las topolog´ ıas Λ∈T, para lo que se necesita cierta informaci´ on centralizada del sistema. Por ´ ultimo, n´ otese que bajo la perspectiva coalicional los cambios de topolog´ ıa afectan a la din´ amica de la ley de control (5) pero no a la del sistema global (3). 2.3. Desigualdades matriciales lineales En este tutorial, para el dise˜ no de las matrices de control KΛyPΛse implementar´ an m´ etodos de optimizaci´ on basados en desigualdades matriciales lineales, conocidas como LMIs por su acr´ onimo en ingl´ es, i.e., linear matrix inequalities. En esencia, dado un conjunto de variables de decisi´ on matriciales Y1, . . . , Yny una funci´ on matricial de las mismas H(Y1, . . . , Yn) decimos que la expresi´ on H(·)>0 es una LMI en Y1, . . . , Ynsi H(·) es sim´ etrica para todas las variables y la dependencia de H(·) respecto a las mismas es af´ ın. Las LMIs representan una herramienta muy potente para resolver problemas de control con resultados muy satisfactorios tanto a nivel de estabilidad como de tiempo de computaci´ on (Alamo et al., 2006; Boyd et al., 1994), en esencia debido a que imponen restricciones convexas en las variables de decisi´ on. Ejemplos recientes de m´ etodos de control basados en LMIs aparecen en (Ebihara et al., 2014; Witczak et al., 2016; Jiang, 2019). Utilizando la cota (6) y la funci´ on objetivo (4) es posible relacionar el coste de control Js(xN(k),uN(k),Λ) en dos instantes de tiempo sucesivos ≥J+ s(xN(k),uN(k),Λ) z }| { xT+ N(k)PΛx+ N(k)+ coste de etapa z }| { xT N(k)QNxN(k)+xT N(k)KT ΛRNKΛxN(k) ≤ ≥Js(xN(k),uN(k),Λ) z }| { xT N(k)PΛxN(k), (8) donde el super´ ındice ‘+’ indica el instante siguiente, i.e., x+ N(k)=xN(k+1). Utilizando (8), la suposici´ on 1, y siguiendo (Maestre et al., 2014), el c´ alculo de las matrices KΛ, que estabilizan el sistema global, y PΛ, que nos dan una cota superior del cost-to-go, se puede realizar ∀Λ∈T, a partir de PΛ>0, PΛ−(AN+BNKΛ)TPΛ(AN+BNKΛ)−QN−KT ΛRNKΛ>0, (9a) iΛ =j=⇒Ki j Λ=Kji Λ=0,Pi j Λ=Pji Λ=0,(9b) donde iΛ =jindica que no hay ning´ un camino de comunicaci´ on entre los agentes iyjcuando la topolog´ ıa Λ∈Test´ a activa. El sistema de ecuaciones anterior no es un sistema LMI ya que existe una dependencia no lineal con las variables de deci- si´ on a calcular, i.e., las matrices KΛyPΛ. Este problema se puede resolver con un cambio de variables. Usando el complemento de Schur (Zhang, 2005), y siguiendo (Maestre et al., 2014), se puede reescribir (9) como el sistema LMI .  WΛWΛAT N+YT ΛBT NWΛQ1/2 NYT ΛR1/2 N ANWΛ+BNYΛWΛ0 0 Q1/2 NWΛ0I0 R1/2 NYΛ0 0 I  >0, (10a) iΛ =j=⇒Yi j Λ=Yji Λ=0,Wi j Λ=Wji Λ=0,(10b) con Isiendo la matriz identidad, y donde la relaci´ on entre las nuevas y las antiguas variables de decisi´ on viene dado por WΛ=P−1 Λ,YΛ=KΛP−1 Λ.(11) 2.4. Esquema de control Una vez calculadas las matrices de dise˜ no del controlador, i.e., KΛyPΛ,∀Λ∈T, se propone el siguiente esquema de control s´ıncrono bicapa (Muros et al., 2017b): Esquema de control 1) Sea ks∈N+un n´ umero espec´ ıfico de instantes de tiempo yTsim el n´ umero total de instantes de simulaci´ on. Para cada instante de control k, repetir hasta alcanzar Tsim 1. Cada agente env´ ıa su estado a todos los agentes con los que est´ e conectado, directa o indirectamente, a trav´ es de la topolog´ ıa habilitada en dicho instante Λ(k). 2. Si kes m´ ultiplo de ks, los controladores locales situados en la capa inferior env´ ıan sus estados a la entidad centralizada de la capa superior, que calcula la topolog´ ıa que minimiza (7). La topolog´ ıa resultante Λmin se activar´ a durante el instante actual y los siguientes ks−1 instantes, si se verifica la siguiente condici´ on respecto a la topolog´ ıa previamente habilitada Λprev: xT N(k)PΛmin xN(k)+σΛmin <xT N(k)PΛprev xN(k)+σΛprev . (12) 3. Cada agente usa la informaci´ on recibida para actualizar su acci´ on de control. Globalmente, se implementa la ley uN(k)=KΛxN(k) y los enlaces innecesarios se deshabilitan de manera din´ amica hasta alcanzar la configuraci´ on descentralizada en r´ egimen permanente. Es decir, con la condici´ on (12) forzamos a que solo haya conmutaci´ on o switch de topolog´ ıa en un cierto km´ ultiplo de ks, si la topolog´ ıa Λmin que minimiza (7) proporciona un coste inferior al que origina la topolog´ ıa previamente habilitada Λprev, evaluadas ambas en el instante del switch. El siguiente teorema, demostrado en (Maestre et al., 2014; Muros et al., 2017b), nos prueba la estabilidad asint´ otica del esquema de control 1. Teorema 1. Sea un sistema descrito por una red (N,E)gobernada por el esquema de control 1. Consid´erense las matrices de control KΛyPΛcorrespondientes a las distintas topolog´ıas Λ∈T. Si dichas matrices han sido calculadas resolviendo un algoritmo de optimizaci´on sujeto a (10), entonces el sistema en bucle cerrado es asint´oticamente estable. 2 100 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 N´ otese que la implementaci´ on del esquema de control 1 requiere de cierta informaci´ on centralizada, aunque esto no limita la escalabilidad de la soluci´ on propuesta, pues la comunicaci´ on con la capa superior se realiza ´ unicamente en instantes muy limitados, i.e., en los cambios de topolog´ ıa cada ks. Adem´ as, es suficiente con que dicha capa maneje un modelo simplificado de la capa inferior. El resto de instantes los agentes dentro de cada coalici´ on se comunican para implementar las acciones de control de manera aut´ onoma. Es destacable que el esquema de control 1 representa un ejemplo de implementaci´ on del controlador con el fin de introducir la idea coalicional en un marco de teor´ ıa de juegos cooperativos. En cualquier caso, existen resultados de estabilidad en los switchings independientemente del esquema de control usado, basados en encontrar una funci´ on de Lyapunov com´ un a todas las topolog´ ıas (Muros et al., 2017b), y por tanto, la filosof´ ıa coalicional admite implementaciones del esquema alternativas. Por ejemplo, se pueden encontrar soluciones que identifican regiones donde los switchings satisfacen propiedades como convexidad o invarianza (Chanfreut et al., 2021c), o propuestas basadas en el uso de una matriz Pcom´ un, ∀Λ∈T, como el incipiente control modular (Lopez-Rodriguez et al., 2020; Maestre et al., 2021). Asimismo, tambi´ en hay implementaciones coalicionales que no requieren capa centralizada, como los esquemas predictivos tipo bottom-up, donde los agentes ´ unicamente conocen informaci´ on parcial de los vecinos (Fele et al., 2015; Maestre et al., 2015). En cualquier caso, sin informaci´ on centralizada las matrices del controlador no podr´ ıan definirse a nivel de topolog´ ıa, sino dise˜ narse de forma ego´ ısta por cada agente usando unas cotas de perturbaci´ on como datos de los vecinos y asumiendo que desde un punto de vista global conducen a un comportamiento estable (Darivianakis et al., 2020). Por ´ ultimo, aunque el esquema de control propuesto es s´ ıncrono, la filosof´ ıa coalicional es perfectamente implementable en esquemas as´ıncronos, como los esquemas disparados por eventos o eventbased, donde en lugar de un periodo constante de muestreo la transmisi´ on de informaci´ on se realiza bajo demanda. Un ejemplo son los sistemas auto-disparados o self-triggered, donde el instante siguiente donde se ejecutan las tareas se calcula en funci´ on del estado actual. Una excelente panor´ amica de esquemas basados en eventos se da en (Aranda-Escol´ astico et al., 2020)1. 3. Herramientas de Teor´ ıa de Juegos Cooperativos Como se ha comentado, la teor´ ıa de juegos cooperativos maneja situaciones de cooperaci´ on entre entidades llamadas jugadores. Un primer concepto necesario para trabajar en esta l´ ınea es el de juego cooperativo de utilidad transferible ojuego TU (von Neumann and Morgenstern, 1944), que se define como el par formado por un conjunto de jugadores y una funci´ on caracter´ ıstica que asocia un coste o beneficio a cada coalici´ on de jugadores, satisfaciendo un coste nulo para el conjunto vac´ ıo. El punto de vista cl´ asico es identificar a los jugadores con el conjunto de agentes N, asumiendo que toda coalici´ on C⊆N es factible. En ese caso, si la funci´ on de coste se denota por v, hablamos del juego (N,v). Por contra, en este tutorial se continuar´ a la idea iniciada en (Maestre et al., 2014) de interpretar el par (E,rv) como un juego TU de enlaces (Borm et al., 1992), donde el conjunto Eson los jugadores y con cada componente de rvdefinida para cada topolog´ ıa Λpor (7)2. En particular, se trabajar´ a con un juego de costes, donde los jugadores m´ as ´ utiles obtienen los pagos m´ as peque˜ nos. N´ otese que cada topolog´ ıa Λ tiene informaci´ on impl´ ıcita de la conexi´ on de todos los agentes en N, lo que no ocurre al trabajar con coaliciones C⊆N. Por tanto, el juego de enlaces nos soluciona de forma natural ciertos problemas de indefinici´ on. Para que el juego de enlaces sea propiamente un juego TU el coste debe ser nulo para el conjunto vac´ ıo de enlaces, i.e., rv(Λ0,xN)=0. Por tanto, (7) debe redefinirse, ∀Λ∈T, como rv0(Λ,xN)=rv(Λ,xN)−rv(Λ0,xN)=xT NPΛ−PΛ0xN+σΛ, (13) donde el coste de comunicaci´ on de la topolog´ ıa descentralizada es trivialmente nulo, i.e., σΛ0=0. N´ otese que (13) es equivalente a (7) a efectos del esquema de control 1, ya que ambas funciones solo difieren en una constante. Es tambi´ en destacable que no se trata a (13) como un juego multiobjetivo, pues no se busca optimizar por separado dos objetivos distintos. Por contra, el objetivo de control consiste en minimizar la suma de cost-to-go y coste de comunicaci´ on como un ´unico objetivo, en el contexto de los juegos escalares cl´ asicos. Dado el enfoque cooperativo de los juegos TU, es inmedia- to pensar que su objetivo natural es distribuir el valor de la gran coalici´ on, i.e., rv(E,xN), entre los jugadores. Con ese fin aparecen las llamadas reglas de reparto o de pagos para referirse a los conceptos de soluci´on. En este tutorial, se aplicaran diversas reglas de pagos al juego coalicional (E,rv) con rvdefinido por (13) para repartir dicho coste entre los enlaces. A diferencia de algunos trabajos de Bauso y sus colaboradores (Bauso and Timmer, 2012; Nedi´ c and Bauso, 2013; Bauso and Notarstefano, 2015; Bauso and Cannon, 2018), que emplean herramientas basadas en restricciones de conjuntos como el core (Gillies, 1959), en este tutorial se trabajar´ a con reglas de reparto basadas en ponderar las contribuciones marginales de los jugadores, las cuales garantizan existencia de la soluci´ on y la posibilidad de expresar la misma de forma expl´ıcita en funci´ on del juego. En muchos casos, este tipo de conceptos de soluci´ on se ha introducido en la literatura de forma axiom´atica, i.e., primero se establece un conjunto de propiedades deseables y posteriormente se prueba que solo existe un valor (o conjunto) caracterizado por las mismas. En este tutorial se enumerar´ an las propiedades satisfechas por las axiomatizaciones m´ as conocidas de cada concepto de soluci´ on, aunque por simplicidad no se explicar´ an en detalle. Para m´ as informaci´ on, consultar (Muros, 2019). N´ otese que, en general, en los juegos TU cada jugador es capaz de cooperar con el resto. Sin embargo, hay muchos escenarios donde algunos jugadores no pueden –o no quieren– compartir informaci´ on. Este tipo de juegos TU con cooperaci´on restringida se modelan mediante las llamadas situaciones de comunicaci´on, que consideran la situaci´ on entre el juego (N,v) 1En el resto de secciones del art´ ıculo, por cuestiones de claridad, se omitir´ a la dependencia de todas las variables con el instante de control k. 2En este art´ ıculo se ha adoptado la notaci´ on cl´ asica introducida en (Borm et al., 1992) para el juego de enlaces. Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 101 o (E,rv) y el grafo (N,E) (ver (Jackson, 2008)), y definen las comunicaciones bilaterales entre los jugadores. A continuaci´ on se introducen algunos conceptos de soluci´ on de teor´ ıa de juegos cooperativos en el contexto del juego coalicional presentado, distinguiendo entre comunicaci´ on completa y restringida. 3.1. Conceptos de soluci´on en juegos TU con comunicaci´on completa En esta subsecci´ on se presentan algunas reglas de reparto para juegos TU donde se asume comunicaci´ on completa, i.e., cualesquiera dos jugadores pueden compartir informaci´ on. 3.1.1. Valor de Shapley y valores de Shapley ponderados El valor de Shapley (Shapley, 1953b) es el concepto de soluci´ on m´ as conocido y utilizado de la teor´ ıa de juegos cooperativos, con aplicaciones en campos tan variados como redes sociales (Narayanam and Narahari, 2011), enolog´ ıa (Ginsburgh and Zang, 2012), finanzas (Tarashev et al., 2016), redes el´ ectricas (Marzband et al., 2017; Barreiro-Gomez et al., 2017; Fletscher et al., 2018; Saracho et al., 2020), o reducci´ on de contaminaci´ on (Petrosjan and Zaccour, 2003; Zhang et al., 2014). Ver (Algaba et al., 2019) para un compendio de ideas te´ oricopr´ acticas sobre el mismo. El valor de Shapley se define de forma cl´ asica como la ´ unica regla de pagos que satisface las propiedades de jugador nulo,simetr´ıa,aditividad yeficiencia, asignando al juego (E,rv) el vector φ(E,rv), definido ∀l∈Ecomo φl(E,rv)=X Λ⊆E:l<Λ |Λ|!(|E|−|Λ| − 1)! |E|![rv(Λ∪{l},xN)−rv(Λ,xN)], (14) es decir, la contribuci´ on marginal de cada enlace se promedia entre todas las posibles topolog´ ıas a las que puede formar parte. N´ otese que en este valor los pesos asignados a cada topolog´ ıa Λdependen de su tama˜ no, seg´ un el t´ ermino |Λ|!(|E|−|Λ|−1)! |E|!. Es particularmente interesante la propiedad de eficiencia, que se cumplir´ a en la mayor´ ıa de las reglas de pagos comentadas en este tutorial, y que indica que la suma de todos los valores de Shapley es igual al valor de la funci´ on de coste evaluada en la gran coalici´ on, i.e., rv(E,xN)=X l∈E φl(E,rv).(15) El valor de Shapley pertenece al conjunto de los valores de Shapley ponderados (Shapley, 1953a; Kalai and Samet, 1987), que se caracterizan por las propiedades de jugador nulo,aditividad,eficiencia,monotonicidad ycompa˜nerismo. Dado un vector de pesos ω=(ωl)l∈E∈R|E| +, el conjunto de valores de Shapley ponderados se define por el vector φω(E,rv), que asigna el pago, ∀l∈E φω l(E,rv)=X Λ⊆E:l∈Λ ωl ωΛ λrv(Λ),(16) con ωΛ=Pl∈Λωly donde λrv(Λ) son los conocidos dividendos de Harsanyi (Harsanyi, 1959), definidos por λrv(Λ)=X L⊆Λ (−1)|Λ|−|L|rv(L,xN),∀Λ⊆E.(17) Se puede comprobar que si se asigna el mismo peso a todos los enlaces, se cumple φω l(E,rv)=φl(E,rv). Es decir, el ´ unico valor de Shapley ponderado sim´etrico es el propio valor de Shapley. 3.1.2. Valor de Banzhaf Este valor fue introducido para juegos de votaci´ on (Penrose, 1946; Banzhaf, 1965), y est´ a presente en ´ ambitos como la biolog´ ıa (Lucchetti et al., 2010), o la pol´ ıtica (Monroy and Fern´ andez, 2014), entre otros. Al igual que el valor de Shapley posee varias axiomatizaciones, caracteriz´ andolo la cl´ asica por las propiedades de jugador nulo,simetr´ıa,aditividad, y superaditividad (Lehrer, 1988). El valor de Banzhaf asigna al juego coalicional (E,rv) el vector β(E,rv), definido ∀l∈Ecomo βl(E,rv)=1 2|E|−1X Λ⊆E:l<Λ [rv(Λ∪ {l},xN)−rv(Λ,xN)],(18) donde se puede apreciar que, a diferencia de para el valor de Shapley, todas las topolog´ ıas son equiprobables. Existe otra axiomatizaci´ on del valor de Banzhaf (Nowak, 1997), que demuestra que es la ´ unica regla de pagos que satisface las propiedades de jugador nulo,simetr´ıa,marginalidad y2-eficiencia, siendo especialmente interesante esta ´ ultima. M´ as espec´ ıficamente, dados dos jugadores lpylq, y definiendo el juego amalgamado EA,rvAcomo un nuevo juego sin esos dos jugadores pero con un nuevo jugador fusi´on la={lp,lq}, la propiedad de 2-eficiencia garantiza que el pago del nuevo jugador laen el juego amalgamado es la suma de los pagos individuales a los jugadores lpylqen el juego original. Esta propiedad satisfecha por el valor de Banzhaf –y no por el valor de Shapley– nos permitir´ a reducir el coste de computaci´ on como veremos en la secci´ on 4. 3.1.3. Semivalores Los semivalores representan un conjunto de reglas de pagos caracterizados axiom´ aticamente por las propiedades de jugador nulo,simetr´ıa yaditividad (Dubey et al., 1981), y con aplicaciones en pol´ ıtica, econom´ ıa y sociolog´ ıa (Carreras and Freixas, 2002). Dado un juego coalicional (E,rv), el vector de semivalores ψ(E,rv) se define ∀l∈Epor ψl(E,rv)=X Λ⊆E:l<Λ ζ(|Λ|)[rv(Λ∪ {l})−rv(Λ)],(19a) con |E|−1 X |Λ|=0 |E| − 1 |Λ|!ζ(|Λ|)=1.(19b) Dadas las propiedades que caracterizan a este conjunto, es posible deducir que contiene a los valores de Shapley y Banzhaf, pues ambos las satisfacen. Otros semivalores son los ´ındices dictatorial y marginal (Owen, 1978). 3.2. Conceptos de soluci´on en juegos TU con comunicaci´on restringida En esta subsecci´ on se habla de conceptos de soluci´ on para juegos TU con comunicaci´ on restringida, es decir, situaciones de comunicaci´ on de juegos restringidos por grafos. 3.2.1. Valor de posici´on y valor de posici´on generalizado Hasta este punto hemos trabajado con el juego coalicional (E,rv) que es un juego de enlaces. Es posible realizar un an´ alisis por agentes a trav´ es del valor de posici´ on (Borm et al., 1992), caracterizado para cualquier grafo por las propiedades de eficiencia por componentes yenlaces con contribuciones 102 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 equilibradas (Slikker, 2005). Dicho valor proporciona un pago a cada agente i∈Na partir del valor de Shapley del juego de enlaces seg´ un la situaci´ on de comunicaci´ on (N,v,E), generando el vector π(N,v,E) definido por πi(N,v,E)=1 2X l∈Ei φl(E,rv),∀i∈N,(20) donde Eies el subconjunto de enlaces conectados al agente i. El valor de posici´ on (20) divide el valor de Shapley de un enlace sim´etricamente entre los dos agentes que conecta. Sin embargo, es posible generalizar dicho concepto mediante un reparto no sim´etrico del valor de Shapley. Con ese fin, la clase introducida y caracterizada en (Ghintran, 2013), utiliza medidas de poder (van den Brink et al., 2011), es decir, funciones α que asignan un valor no negativo o poder αi(N,E) a cada agente i∈N, para el reparto del coste entre los jugadores seg´ un la red (N,E). El valor de posici´ on generalizado παde una situaci´ on de comunicaci´ on (N,v,E), ponderado por la medida de poder α, se define para cada agente i∈Ncomo πα i(N,v,E)=X l∈Ei l={i,j} αi z }| { ¯αil(N,E) ¯αil(N,E)+¯αjl(N,E)φl(E,rv),(21) donde para juegos de coste, el t´ ermino ¯αil(N,E) se define por (Muros et al., 2016) como αil(N,E) si φl(E,rv)<0 o 1 αil(N,E)si φl(E,rv)≥0. Por tanto, la participaci´ on de cada jugador se determina de acuerdo al signo del valor de Shapley del enlace y de los pesos relativos de los dos jugadores implicados seg´ un la red (N,E) (Ghintran, 2013). 3.2.2. Soluciones de poder de Harsanyi Esta soluciones fueron introducidas para juegos restringidos por grafos en (van den Brink et al., 2011), y aplicadas a juegos coalicionales en (Muros et al., 2017b), donde adem´ as se presentan las medidas de poder de enlaces como concepto an´ alogo a las medidas de poder. Es decir, se trata de funciones ωque asocian a cada enlace l∈Eun valor no negativo ωl(N,E) que representa el poder del enlace dentro de la red (N,E). En nuestro contexto, dada una situaci´ on de comunicaci´ on (N,rv,E), la soluci´ on de poder de Harsanyi denotada por ϕω(N,rv,E), asigna ∀l∈Eel vector de pagos (Muros et al., 2017b) ϕω l(N,rv,E)=X Λ⊆E:l∈Λ ωl(N,Λ) ωΛ(N,Λ)λrv(Λ),(22) con ωΛ(N,Λ)=Pl∈Λωl(N,Λ), y donde λrv(Λ) son los dividendos de Harsanyi dados por (17). Es decir, las soluciones de poder de Harsanyi ponderan la influencia de los dividendos de Harsanyi seg´ un el poder de cada enlace evaluado en el subgrafo (N,Λ). N´ otese que a diferencia de (21), los poderes en (22) dependen de la topolog´ ıa Λ. Entre otras propiedades, estas soluciones satisfacen eficiencia por componentes yaditividad para cualquier grafo (van den Brink et al., 2011). Por ´ ultimo, es f´ acil deducir a la vista de (16) que para una medida de poder fija y que no dependa del grafo, las soluciones de poder de Harsanyi se reducen a los valores de Shapley ponderados ϕω l(N,rv,E)ω(N,Λ)=ω=φω l(E,rv).(23) Ejemplo 2. Consid´erese la red representada en la Figura 1, cuyas topolog´ıas se ilustran en la Tabla 1. Asimismo, sea un juego de enlaces (E,rv)donde E={I,II,III,IV}, y cuyo valor de la funci´on de coste rv(Λ)evaluada en cada topolog´ıa Λ viene dado por el vector rv=[0 1 2 2 1 4 0 2 1 3 5 4 3 2 5 6]T. En la Tabla 2 se detallan los valores espec´ıficos de todos los conceptos de soluci´on presentados, donde como medidas de poder αyωse han considerado respectivamente la medida de grado di=|Ei|(Sun and Tang, 2011; van den Brink et al., 2008), y la an´aloga medida de grado para enlaces dl=|Ei|n|Ej|n(Muros et al., 2017b), con l ={i,j} ∈ Ey tomando n =1. Asimismo, los pesos de los valores de Shapley ponderados se han escogido coincidentes con ωl(N,E),∀l∈E. N´otese que en todos los conceptos de soluci´on, a excepci´on del valor de Banzhaf y los semivalores, se cumple eficiencia o eficiencia por componentes. Finalmente, los semivalores se han expresado de forma gen´erica, pues ser´ıa v´alida cualquier soluci´on que satisfaga (19b), i.e., ζ(0) +3ζ(1) +3ζ(2) +ζ(3) =1.(24) 4. Aplicaciones al Control Coalicional En este apartado presentamos diversas aplicaciones de la teor´ ıa de juegos cooperativos al control coalicional, en particular usando las herramientas presentadas en la secci´ on anterior. 4.1. Imponer restricciones en jugadores Existen situaciones en las que puede ser ´ util restringir o favorecer el uso de ciertas interconexiones de un sistema, v.g., la regulaci´ on del tr´ afico en carreteras ante un accidente. Con ese fin, se propone un m´ etodo para aplicar restricciones en los valores de Shapley de determinados enlaces para premiar o penalizar su uso. Consideraremos como restricciones cualquier combinaci´ on lineal de la forma (Muros and Maestre, 2021) X l∈Er κlφl(E,rv)≥T,(25) donde Er⊆Ees el conjunto de enlaces con restricciones, κl∈R,l∈Ery siendo T∈Run valor constante. En (Muros et al., 2017b,c) se demuestra que es posible representar el valor de Shapley de cualquier enlace lde forma cerrada en funci´ on del coste (13) φl(E,rv)=σl+X Λ⊆E mlΛhxT NPΛxNi,(26) donde mlΛ= (|Λ|−1)!(|E|−|Λ|)! |E|!l∈Λ, −|Λ|!(|E|−|Λ|−1)! |E|!,l<Λ, (27) Tabla 2: Valores de los conceptos de soluci´ on para el juego del ejemplo 2 φlφω lβlψlϕω lπiπα i Enlaces I7 12 213 308 3 8ζ(0)+ζ(1)+ζ(3) 209 420 Agentes 17 24 7 16 II 9 4 689 308 15 82ζ(0)+4ζ(1)+5ζ(2)+4ζ(3) 839 420 29 8 27 16 III 19 12 27 14 9 82ζ(0)+2ζ(1)+2ζ(2)+3ζ(3) 37 21 353 24 161 120 IV 19 12 8 7 13 8ζ(0)+5ζ(1)+5ζ(3)+2ζ(3) 61 35 419 12 133 90 519 24 19 18 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 103 son los elementos de la matriz est´ andar de Shapley M∈ R|E|×2|E|(Xu et al., 2008), que verifica φ(E,rv)=Mrv, y con las filas correspondiendo a los enlaces l∈E, y las columnas a las topolog´ ıas Λ⊆E, en orden lexicogr´ afico. Usando (26) es posible reescribir (25) en formato LMI como (Muros et al., 2017c; Muros and Maestre, 2021) S≥0,con S= X l∈Er κlσl−T0 0X Λ⊆EX l∈Er κlmlΛPΛ  ,(28) donde se requiere que el primer menor principal sea no negativo. Por ´ ultimo, todas las condiciones LMI (28) consideradas se agrupar´ an en el llamado set de restricciones S. N´ otese que es posible considerar restricciones an´ alogas en otras reglas de pagos (Muros et al., 2017a,b,c; Muros and Maestre, 2021). Es destacable que las condiciones LMI (28) no dependen de las mismas variables que el sistema LMI (10), necesario para garantizar la estabilidad del esquema de control 1 seg´ un el teorema 1. Con idea de agrupar ambas condiciones se considera aqu´ ı un m´ etodo iterativo desarrollado en (Muros et al., 2017c) para el c´ alculo offline de las matrices del controlador. B´ asicamente, al igual que en las llamadas iteraciones DK (Skogestad and Postlethwaite, 2001), se alterna en cada paso la optimizaci´ on con respecto a KΛyPΛ, dejando la otra matriz fija: Algoritmo de dise˜ no 1) Sean un ´ ındice de iteraci´ on ly un contador r, inicializados al=1 y r=0. Realizar lo siguiente: 1. Para obtener un valor inicial de KΛyPΛ, calcular m´ ax WΛ,YΛ Tr(WΛ),∀Λ∈T, sujeto a (10), de donde obtenemos las matrices W(r) ΛyY(r) Λ, y por tanto, K(r) ΛyP(r) Λ. 2. Sea K(r+1) Λ=K(r) Λ, y calcular m´ ın PΛX Λ Tr(PΛ)sujeto a (9) y al set S,∀Λ∈T. Como resultado obtenemos P(r+1) Λ. 3. Sea ξΛ∈R+\{0}. Calcular m´ ın ξΛ,KΛX Λ ξΛ, sujeto a3  P(r+1) ΛQ1/2 NKT ΛR1/2 N(AN+BNKΛ)T Q1/2 NξΛI0 0 R1/2 NKΛ0ξΛI0 AN+BNKΛ0 0 P(r+1) Λ−1  >0,(29a) iΛ =j=⇒Ki j Λ=Kji Λ=0,(29b) y al conjunto de restricciones S,∀Λ∈T. Como resultado obtenemos K(r+2) Λy recalculamos P(r+2) Λ=ξΛP(r+1) Λ. 4. Hacer r=r+2, l=l+1 y volver al paso 2, mientras l<lm´ ax (siendo lm´ ax un m´ aximo n´ umero de iteraciones prefijado) o hasta que el algoritmo converja seg´ un alg´ un ´ ındice que dependa de P(r) Λ(ver (Muros et al., 2017c)). En resumen, en el paso 1, resolvemos un problema inicial de optimizaci´ on en el plano (YΛ,WΛ), sin considerar restricciones en el valor de Shapley, que se incluyen en los pasos 2 y 3. Precisamente por esta raz´ on necesitamos resolver el problema en el plano (KΛ,PΛ), obteniendo LMIs an´ alogas a (10) en dicho plano –dadas por (9) y (29)– al tomar como constante cierta informaci´ on de las matrices de control del paso anterior. N´ otese que a˜ nadir nuevas restricciones LMIs reduce el espacio de soluciones factibles pero no afecta las propiedades garantizadas por (10). Por tanto, seg´ un el teorema 1, el sistema definido por las matrices obtenidas seg´ un el algoritmo de dise˜ no 1 sigue siendo estable. Una vez computadas las matrices, se aplicar´ ıa en cada instante el esquema de control 1 durante un periodo de simulaci´ on Tsim, pudiendo medir el coste acumulado del esquema de control mediante el siguiente ´ ındice: Jacum = Tsim X k=0 [xT N(k)QNxN(k)+uT N(k)RNuN(k)+σΛ].(30) 4.1.1. Especificaciones a priori Adicionalmente, adem´ as de restricciones a posteriori en la l´ ınea de (28), es posible considerar especificaciones a priori, que afecten a la evoluci´ on de las reglas de reparto mediante una matriz caracter´ ıstica que dependa de cada enlace, manteniendo inalteradas las matrices del controlador. Bajo algunos supuestos, esto puede suponer una reducci´ on del coste computacional. Dos conceptos de soluci´ on que encajan de forma natural en este contexto son los valores de Shapley ponderados y las soluciones de poder de Harsanyi, pues ambos dependen de los pesos/poderes de cada enlace. De hecho, como vimos en (23), en un contexto coalicional el primer valor es un caso particular del segundo. Por tanto, es posible poder trabajar con ambos valores usando la matriz est´ andar de Harsanyi Hω∈R|E|×2|E|(Muros et al., 2017b), con las filas y columnas correspondiendo respectivamente a cada enlace l∈Ey topolog´ ıa Λ∈T, y donde cada elemento hω lΛse define como hω lΛ=X L⊆E:Λ∪{l}⊆L (−1)|Λ|−|L|ωl(N,L) ωL(N,L),(31) verific´ andose la relaci´ on ϕω(N,rv,E)=Hωrv, que para el caso de los valores de Shapley ponderados queda reducida, ∀l∈E, a (Muros et al., 2017b) ϕω l(N,rv,E)=σl+X Λ⊆E hω lΛhxT NPΛxNi.(32) N´ otese que los pesos influyen a trav´ es de los elementos hω lΛen la manera en la que se combinan los costes de control de las topolog´ ıas para computar la regla de pago. 4.2. Proporcionar v´ıas alternativas de c´alculo Como adelantamos en el apartado 3.1.2, dado un juego amalgamado (EA,rvAla propiedad de 2-eficiencia garantiza βlp(E,rv)+βlq(E,rv)=βlaEA,rvA.(33) 3Existe un teorema demostrado en (Muros et al., 2017c) que asegura la estabilidad del sistema en problemas de optimizaci´ on sujetos al LMI (29). 104 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 Figura 2: Juegos amalgamados que intervienen en la red de la Figura 1. Se alcanza la gran coalici´ on con un nivel de recurrencia +=3. Considerando (33), definimos como δΛ l=δl∩Λal conjunto de enlaces que pertenece simult´ aneamente a la terna δl= {l,lp,lq}, con l∈E\{lp,lq}, y a una cierta topolog´ ıa Λ. Dado que los juegos originales y amalgamados solo difieren en los jugadores que se amalgaman, es posible usar δΛ lpara conectar los valores de Banzhaf de un enlace l∈E\{lp,lq}de los juegos original y amalgamado (Muros et al., 2017a) βl(E,rv)=βlEA,rvA−X Λ⊆E b∗ lΛhxT NPΛxNi,∀l∈E\{lp,lq}, (34) con los t´ erminos b∗ lΛdefinidos como b∗ lΛ= 1 2|E|−1,|δΛ l|=1,3, −1 2|E|−1,|δΛ l|=0,2.(35) El valor de Banzhaf de los enlaces amalgamados se obtendr´ ıa como (Muros et al., 2017a) βlp,q (E,rv)=βlaEA,rvA−X Λ⊆E blq,pΛhxT NPΛxNi−σlq,p .(36) 4.2.1. Amalgamiento recursivo El amalgamiento puede realizarse de forma recursiva, reduciendo uno a uno el n´ umero de jugadores. Por tanto, en el juego +-amalgamado los jugadores se agrupan en |E| − +subcojuntos no vac´ ıos llamados amalgamas. En (Muros et al., 2017a) se demuestra que el valor de Banzhaf de un juego se puede obtener mediante combinaciones lineales de los valores de Banzhaf apropiados de los juegos +-amalgamados de dos amalgamas. N´ otese que el n´ umero de formas de dividir un conjun- to de |E|elementos en dos amalgamas viene dado por el n´umero de Stirling de segunda especie (Becker and Riordan, 1948), denotado por n|E| 2o. En este contexto, el conjun- to G=nGt:t=1, . . . , n|E| 2oocontiene todos los juegos +- amalgamados con dos amalgamas Gt=E(|E|−2)At,rv,(|E|−2)At, donde E(|E|−2)At={ςa(Gt), ςb(Gt)}, con ςa(Gt)∪ςb(Gt)=Ey ςa(Gt)∩ςb(Gt)=∅. En la Figura 2 se detallan los juegos amalgamados implicados en redes de cuatro enlaces como la de la Figura 1. El conjunto Gestar´ ıa formado por G1:{I-II-III,IV},G2:{I-II-IV,III},G3:{I-III-IV,II},G4:{I,II-III-IV}, G5:{I-II,III-IV},G6:{I-III,II-IV},G7:{I-IV,II-III}. (37) El valor de Banzhaf de ambas amalgamas para cada juego de Gviene dado por (Muros et al., 2017a) βςa(Gt)E(|E|−2)At,rv,(|E|−2)At=1 2−rv ∅+rv ςa(Gt)−rv ςb(Gt)+rv E, βςb(Gt)E(|E|−2)At,rv,(|E|−2)At=1 2−rv ∅−rv ςa(Gt)+rv ςb(Gt)+rv E. (38) Usando (38), es posible obtener informaci´ on del juego original a partir de combinaciones lineales de juegos con menos –dos– jugadores. M´ as espec´ ıficamente, el valor de Banzhaf de un enlace len el juego original se calcula mediante bien la adici´ on del valor de Banzhaf de la amalgama ςa(Gt), o bien la sustracci´ on del valor de Banzhaf de ςb(Gt), para cada juego de dos amalgamas Gt∈G, y asumiendo l∈ςa(Gt),l<ςb(Gt). En otras palabras, es posible llegar a (Muros et al., 2017a) βl(E,rv)=1 2|E|−2"X Gt∈G1 βςa(Gt)E(|E|−2)At,rv,(|E|−2)At −X Gt∈G2 βςb(Gt)E(|E|−2)At,rv,(|E|−2)At#, (39) con G1yG2cualesquiera dos subconjuntos que verifiquen G1∪G2=G,G1∩G2=∅,|G1|−|G2|=1.(40) N´ otese que mediante (39) (u otras expresiones an´ alogas detalladas en (Muros, 2019)) es posible el particionado del c´ alculo del valor de Banzhaf de una forma natural, mediante la resoluci´ on de juegos simples de dos jugadores, lo que reduce la carga computacional. Finalmente, es posible consultar resultados adicionales sobre cotas del valor de Banzhaf y su propagaci´ on con el nivel de recurrencia +en (Muros et al., 2017a). 4.3. Clasificar jugadores Puede resultar de gran utilidad detectar qu´ e jugadores son los m´ as relevantes dentro de una red desde una perspectiva de control. Con ese fin, se propone un m´ etodo offline de tipo Montecarlo (Zio, 2013) para ordenar y comparar los jugadores –enlaces o agentes– mediante los valores de Shapley y de posici´ on generalizado. Es necesario tomar un n´ umero alto de muestras de distintos estados iniciales factibles para que los resultados sean precisamente independientes del estado, y posteriormente evaluar las reglas de pagos en los mismos, mediante el siguiente procedimiento: Procedimiento de toma de datos 1) Sea un ´ ındice de iteraci´ on sy un valor lo suficientemente grande L∈N+. Comenzando en s=1: 1. Tomar una muestra aleatoria del estado inicial, i.e., x0 N, donde asumimos que x0 N∈X0 N⊆RnxN. 2. Evaluar la funci´ on de coste (13) para cada topolog´ ıa Λ∈ T, donde las matrices PΛse han obtenido mediante alg´ un m´ etodo de optimizaci´ on sujeto al sistema LMI (10). 3. Calcular el valor de Shapley φl(E,rv),∀l∈Econ (14), y/o el valor de posici´ on generalizado πα i(N,v,E),∀i∈N mediante (21), para una αdada. 4. Hacer s=s+1 e ir al paso 1 mientras s<L. Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112 105 Monroy, L., Fern´ andez, F. R., April 2014. Banzhaf index for multiple voting systems. an application to the European Union. Annals of Operations Research 215, 215–230. Muros, F. J., 2019. Cooperative Game Theory Tools in Coalitional Control Networks. Springer Theses Series. Springer, Zug, Switzerland. Muros, F. J., Algaba, E., Maestre, J. M., Camacho, E. F., June/July 2016. Cooperative game theory tools to detect critical nodes in distributed control systems. In: Proceedings of the 15th European Control Conference (ECC 2016). Aalborg, Denmark, pp. 190–195. Muros, F. J., Algaba, E., Maestre, J. M., Camacho, E. F., June 2017a. The Banzhaf value as a design tool in coalitional control. Systems & Control Letters 104, 21–30. Muros, F. J., Algaba, E., Maestre, J. M., Camacho, E. F., July 2017b. Harsanyi power solutions in coalitional control systems. IEEE Transactions on Automatic Control 62 (7), 3369–3381. Muros, F. J., Maestre, J. M., 2021. Generalized framework for coalitional feedback control with semivalues constraints. Submitted to the Journal of the Franklin Institute. No publicado. Muros, F. J., Maestre, J. M., Algaba, E., Alamo, T., Camacho, E. F., April 2017c. Networked control design for coalitional schemes using gametheoretic methods. Automatica 78, 320–332. Muros, F. J., Maestre, J. M., Ocampo-Martinez, C., Algaba, E., Camacho, E. F., August 2018a. A game theoretical randomized method for large-scale systems partitioning. IEEE Access 6, 42245–42263. Muros, F. J., Maestre, J. M., Ocampo-Martinez, C., Algaba, E., Camacho, E. F., June 2018b. Partitioning of large-scale systems using game-theoretic coalitional methods. In: Proceedings of the 16th European Control Conference (ECC 2018). Limassol, Cyprus, pp. 2517–2522. Narayanam, R., Narahari, Y., January 2011. A Shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering 8 (1), 130–147. Nash, J. F., September 1951. Non-cooperative games. Annals of Mathematics 54 (2), 286–295. Nedi´ c, A., Bauso, D., June 2013. Dynamic coalitional TU games: Distributed bargaining among players’ neighbors. IEEE Transactions on Automatic Control 58 (6), 1363–1376. Negenborn, R. R., De Schutter, B., Hellendoorn, J., April 2008. Multi–agent model predictive control for transportation networks: Serial versus parallel schemes. Engineering Apps. of Artificial Intelligence 21 (3), 353–366. Negenborn, R. R., van Overloop, P.-J., Keviczky, T., De Schutter, B., June 2009. Distributed model predictive control of irrigation canals. Networks and Heterogeneous Media 4 (2), 359–380. Nowak, A. S., March 1997. On an axiomatization of the Banzhaf value without the additivity axiom. International Journal of Game Theory 26 (1), 137–141. N´ u˜ nez, A., Ocampo-Martinez, C., Maestre, J. M., Schutter, B. D., August 2015. Time-varying scheme for noncentralized model predictive control of largescale systems. Mathematical Problems in Engineering 2015, 560702. Ocampo-Martinez, C., Bovo, S., Puig, V., June 2011. Partitioning approach oriented to the decentralised predictive control of large-scale systems. Journal of Process Control 21 (5), 775–786. Ocampo-Martinez, C., Puig, V., Cembrano, G., Quevedo, J., February 2013. Application of MPC strategies to the management of complex networks of the urban water cycle. IEEE Control Systems Magazine 33 (1), 15–41. Olfati-Saber, R., Fax, J. A., Murray, R. M., January 2007. Consensus and cooperation in networked multi-agent systems. Proc. of the IEEE 95 (1), 215–233. Olfati-Saber, R., Murray, R. M., September 2004. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control 49 (9), 1520–1533. Owen, G., September 1978. Characterization of the Banzhaf-Coleman index. SIAM Journal of Applied Mathematics 35 (2), 315–327. Owen, G., 2013. Game Theory, 4th Ed. Emerald Group Pub. Lim., Bingley, UK. Peleg, B., Sudh¨ olter, P., October 2007. Introduction to the Theory of Cooperative Games. Theory and Decision Library C. Springer. Penrose, L. S., 1946. The elementary statistics of majority voting. Journal of the Royal Statistical Society 109 (1), 53–57. Peters, H., June 2015. Game Theory. A Multi-Leveled Approach, 2nd Edition. Springer Texts in Business and Economics. Springer, Heidelberg, Germany. Petrosjan, L., Zaccour, G., Jan. 2003. Time-consistent Shapley value allocation of pollution cost reduction. Journ. of Econ. Dyn. & Control 27 (3), 381–398. Philippe, M., Essick, R., Dullerud, G. E., Jungers, R. M., October 2016. Stability of discrete-time switching systems with constrained switching sequences. Automatica 72, 242–250. Ren, W., Beard, R. W., May 2005. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Transactions on Automatic Control 50 (5), 655–661. Riverso, S., Farina, M., Ferrari-Trecate, G., October 2013. Plug-and-play decentralized model predictive control for linear systems. IEEE Transactions on Automatic Control 58 (10), 2608–2614. Riverso, S., Farina, M., Ferrari-Trecate, G., August 2014. Plug-and-play model predictive control based on robust control invariant sets. Automatica 50 (8), 2179–2186. Saad, W., Han, Z., Debbah, M., Hjørungnes, A., Bas¸ar, T., September 2009. Coalitional game theory for communication networks. IEEE Signal Processing Magazine 26 (5), 77–97. Saad, W., Han, Z., Poor, H. V., Bas¸ar, T., September 2012. Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Processing Magazine 29 (5), 86–105. Saracho, D., Muros, F. J., Maestre, J. M., July 2020. Efficient design of fault detection architectures for power networks by using game theory. In: Proc. of the 21st IFAC World Congr. (IFAC 2020). Berlin, Germ., pp. 13828–13833. Scattolini, R., May 2009. Architectures for distributed and hierarchical model predictive control – A review. Journal of Process Control 19 (5), 723–731. Shapley, L. S., 1953a. Additive and non-additive set functions. Ph.D. thesis, Princeton University, New Jersey, USA. Shapley, L. S., 1953b. A value for n-person games. In: Kuhn, H. W., Tucker, A. W. (Eds.), Contributions to the Theory of Games II. Annals of Mathematics Studies, vol. 28. Princeton University Press, Princeton, New Jersey, USA, pp. 307–317. Skogestad, S., Postlethwaite, I., August 2001. Multivariable Feedback Control - Analysis and Design, 2nd Edition. John Wiley and Sons, New York, USA. Slikker, M., July 2005. A characterization of the position value. International Journal of Game Theory 33 (4), 505–514. Sun, J., Tang, J., 2011. A survey of models and algorithms for social influence analysis. In: Aggarwal, C. C. (Ed.), Social Network Data Analytics. Springer, New York, USA, pp. 177–214. Tarashev, N., Tsatsaronis, K., Borio, C., May 2016. Risk attribution using the Shapley value: Methodology and policy applications. Review of Finance 20 (3), 1189–1213. Tarkowski, M. K., Szczepa´ nski, P. L., Michalak, T. P., Harrenstein, P., Wooldridge, M., October 2018. Efficient computation of semivalues for gametheoretic network centrality. Journal of Artif. Intell. Research 63, 145–189. van den Brink, R., Borm, P., Hendrickx, R., Owen, G., June 2008. Characterizations of the β- and the degree network power measure. Theory and Decision 64 (4), 519–536. van den Brink, R., van der Laan, G., Pruzhansky, V., February 2011. Harsanyi power solutions for graph-restricted games. International Journal of Game Theory 40 (1), 87–110. von Neumann, J., Morgenstern, O., 1944. Theory of Games and Economic Behaviour. Princeton University Press, Princeton, New Jersey, USA. Witczak, M., Buciakowski, M., Puig, V., Rotondo, D., Nejjari, F., May 2016. An LMI approach to robust fault estimation for a class of nonlinear systems. International Journal of Robust and Nonlinear Control 26 (7), 1530–1548. Xu, G., Driessen, T. S. H., Sun, H., April 2008. Matrix analysis for associated consistency in cooperative game theory. Linear Algebra and its Applications 428 (7), 1571–1586. Yazdanian, M., Mehrizi-Sani, A., November 2014. Distributed control techniques in microgrids. IEEE Transactions on Smart Grid 5 (6), 2901–2909. Zhang, F., 2005. The Schur Complement and Its Applications. Vol. 4 of Numerical Methods and Algorithms. Springer, New York, USA. Zhang, G., Yang, K., Liu, P., Ding, E., February 2011. Achieving user cooperation diversity in TDMA-based wireless networks using cooperative game theory. IEEE Communication Letters 15 (2), 154–156. Zhang, X.-M., Han, Q.-L., Ge, X., Ding, D., Ding, L., Yue, D., Peng, C., January 2020. Networked control systems: a survey of trends and techniques. IEEE/CAA Journal of Automatica Sinica 7 (1), 1–17. Zhang, Y.-J., Wang, A.-D., Da, Y.-B., November 2014. Regional allocation of carbon emission quotas in China: Evidence from the Shapley value method. Energy Policy 74, 454–464. Zheng, Y., Wei, Y., Li, S., October 2018. Coupling degree clustering-based distributed model predictive control network design. IEEE Transactions on Automation Science and Engineering 15 (4), 1749–1758. Zio, E., 2013. The Monte Carlo Simulation Method for System Reliability and Risk Analysis. Springer, London, UK. 112 Muros, F. J. / Revista Iberoamericana de Automática e Informática Industrial 18 (2021) 97-112