Evolutionary games in complex topologiesinterplay between structure and dynamics

Resumen

Muchos sistemas reales, tales como las redes tróficas, las redes sociales, la WWW o Internet eran prácticamente intratables hace sólo unos pocos a\~nos, debido por una parte a un enorme cantidad de componentes, y también a la complejidad de las conexiones entre ellos. Todos estos sistemas han sido recientemente caracterizados como Redes Complejas, y han abierto un nuevo y prometedor campo de estudio para muchos investigadores en todo el mundo. En pocas palabras, una red compleja puede definirse como un conjunto de nodos o individuos, y un conjunto de conexiones entre ellos, que representan algun tipo de interacción, ya sea física o de carácter abstracto. Específicamente, una red ser\'a considerada 'compleja' si posee un patrón de conexiones altamente no trivial. Estos sistemas han encontrado en la Teoría de Grafos una herramienta muy útil que permite estudiarlos, reproducirlos y describirlos de forma precisa, extrayendo ciertas características topológicas b\'asicas para poder caracterizarlos y clasificarlos. Sorprendentemente, muchos de estos sistemas reales, a pesar de proceder de campos muy diversos, comparten varias de estas características estructurales, con lo que se valida esta nueva disciplina, mucho más allá de la mera acumulación de datos anecdóticos. Otros sistemas de este tipo son las redes neuronales de los animales (donde los nodos son neuronas y los links representan las sin\'apsis), redes metabólicas (donde los nodos corresponden con distintas moléculas o metabolitos, y los enlaces entre dos de ellos significan que uno es el reactivo y otro el producto), las redes de actores o de co-autores de publicaciones científicas, la red de transporte aéreo internacional o la red de contactos sexuales en un determinado grupo. Además, esta estructura compleja se ha demostrado que afecta en gran medida al resultado final de los procesos que tengan lugar en el sistema. Así, modifican a veces drásticamente las hipótesis iniciales y conclusiones que pueden sacarse al estudiarlos. Por ejemplo, las dinámicas de propagación de enfermedades son muy distintas según si se considera que actúan sobre una población estructurada o no (e incluso, como veremos, depende del tipo concreto de estructura que presente), y por tanto, las medidas que deben ser tomadas para frenar dichos procesos, también pueden variar sustancialmente. Los primeros intentos sencillos de modelar redes reales fueron mediante euclideanas y redes aleatorias (introducidas por Erd\"os and Rényi -ER- ). Las primeras son ordenaciones regulares, donde los individuos se disponen a distancias bien definidas unos de otros, teniendo todos ellos el mismo número de vecinos. Las segundas están formadas por un conjunto de individuos con conexiones aleatorias entre sí, sin ninguna periodicidad espacial (de hecho, cuando tratamos con redes complejas, resulta difícil definir el concepto de dimensonalidad). Una forma muy útil de describir estas estructures es utilizando la distribución de grado o de conectividad,P(k), esto es, la probabilidad de encontrar un nodo con k vecinos. En el caso de las redes aleatorias, su distribucion de grado es de tipo Poisson, mientras que en una red euclideana, es una delta de Dirac. Estos primero modelos no conseguían reproducir algunas de las características básicas de las redes reales, tales como el fenómeno de los 'seis grados de separación' o el 'mundo pequeño' , que implica que dos individuos cualesquiera del sistema estarán con una muy alta probabilidad conectados entre sí a través de un número muy corto de pasos intermedios, y por otra parte, dos amigos distintos de una misma persona es muy probable que también se conozcan. Estos hechos han sido durante años una curiosidad conocida por todos, y después pasaron a ser un hecho sociológico estudiado, pero sólo recientemente se ha comprobado que su origen está en una propiedad topológica muy común en este tipo de sistemas complejos. Así, si uno pretende modelarlos, debería tener en cuenta dichas propiedades, y el primer modelo en hacerlo fue el de redes Small-word. Un esfuerzo posterior en el intento de recrear las redes reales fue el reproducir también la habitual distribución de conectividad en forma de ley de potencias. Así, aparecen los modelos de redes Scale-Free o libres de escala, el más conocido de los cuales es el de Barabási y Albert (BA). Los procesos que pueden tener lugar en las redes complejas son tan variados como los campos en los que éstas aparecen: desde fenómenos de sincronización o propagación de enfermedades y virus informáticos, a transporte o congestión de infraestructuras, sin olvidar fenómenos sociales como los rumores, la formación de guetos, el aprendizaje o la diseminación cultural. En nuestro caso, estamos interesados en el estudio de un tipo de procesos concretos en topologías complejas, que son las dinámicas de cooperación-traición entre individuos. Es muy habitual observar tanto en la Naturaleza como en la sociadad, ejemplos de cooperación. Desde las células que se organizan formando tejidos, a los individuos que se agrupan para cazar o perseguir un objetivo común. Sin embargo, todavá a fecha de hoy no se entienden totalmente los mecanismos por los cuales emerge y sobrevive la cooperación en entornos 'hostiles'. El individuo que coopera aporta al grupo su esfuerzo o un coste personal, pero puede darse el caso de que se encuentre con otro individuo que en cambio no aporte nada, y sólo se aproveche del grupo. Habitualmente, este conflicto se ha venido modelando mediante juegos: el Dilema del Prisionero, el Halcon y Paloma, la Caza del Ciervo o la Tragedia de los Comunes. Específicamente, nos centraremos en el ejemplo paradigmático del Dilema del Prisionero, donde además, se dan las condiciones más duras para la coopearción. En este juego, los dos contrincantes pueden elegir entre dos estrategias: cooperar o traicionar. Según dicta la Teoría Clásica de Juegos, la mejor estrategia en términos de beneficios (esto es, la 'solución racional') resulta ser traicionar siempre, independientemente de lo que elija el adversario. No obstante, si los dos cooperaran, obtendrían mayores beneficios que si los dos traicionan. El enfoque que proporciona la Teoría Evolutiva de Juegos, donde se asume que todo individuo puede interaccionar con todos los demás (hipótesis de well-mixed o de población bien mezclada), describe el problema en términos de concentraciones de las diferentes estrategias, mediante la llamada Ecuacion Replicador, y da como resultado la extinción asintótica de la cooperación. Se han propuesto varios mecanismos en los que puede apoyarse la cooperación, tales como la protección de la prole y la familia en general, la selección de grupo, la reciprocidad directa, o indirecta mediante un sistema de reputación. En nuestro caso nos interesa la llamada 'reciprocidad de la red', o en otras palabras, el hecho de que la estructura subyacente pueda servir como soporte a la cooperación en el sistema. En los últimos a\~nos se ha invertido un gran esfuerzo en el estudio del Dilema del Prisionero, implementádolo primero sobre sistemas con estructura sencilla como redes euclideanas y posteriormente sobre redes complejas. Se ha encontrado que, lejos de la asunción de población bien mezclada, donde los individuos tienen la posibilidad de interaccionar con todos los demás, la cooperación puede no solo sobrevivir, sino dominar el sistema en determinados rangos de los parámetros. Es decir, la existencia de una estructura interna que dicta con quién interacciona cada individuo, ayuda a sostener la cooperación, incluso cuando a corto plazo no es la estrategia más beneficiosa. Se ha encontrado que esto es debido a la formación de clusters o grupos de cooperadores interconectados entre sí, que forman un sistema de apoyo mutuo que les reporta beneficios y les permite resistir la invasión de los traidores. Con esta situación como punto de partida de la Tesis, nos interesaremos en profundizar en la evolución de la cooperación en redes complejas. Concretamente, en la Primera Parte de este trabajo nos centraremos en el estudio de las diferencias introducidas en la dinámica por topologías con distinto grado de heterogeneidad en cuanto a la distribución de conectividad. Así, observaremos no sólo los niveles de cooperación que alcanza el sistema en el estado de equilibrio, sino también la organización microscópica de las estrategias. Analizaremos además la influencia de las condiciones iniciales, es decir, del porcentaje inicial de cooperadores distribuidos en el sistema. Aunque también estudiaremos topologías con grados de heterogeneidad intermedios, estamos especialmente interesados en los casos extremos de redes aleatorias (homogeneas) y redes libres de escala. Por otra parte, aunque el juego principal en el que nos centraremos es el Dilema del Prisionero, también consideraremos el caso del Halcón y Paloma. Los resultados generales que encontraremos serán, por una parte, confirmar el hecho de que la heterogeneidad favorece a la cooperación, puesto que mediante la formación de clústers los cooperadores pueden resistir el ataque de los traidores. Además, para el caso de redes libre de escala, en el núcleo de dichos clústers siempre se encuentran los individuos mas conectados (o hubs), que perduran como cooperadores mientras las condiciones sean tales que el nivel medio de cooperación en el sistema no sea nulo. También hemos encontrado que existe una partición asintótica de los nodos del sistema en tres grupos bien diferenciados: los cooperadores puros (CP), o aquellos que cooperan durante todo el tiempo de observación (siempre posterior al período transitorio), los defectores puros (DP), y por último, un conjunto de individuos en los que no se fija ninguna estrategia de forma permanente, los fluctuantes (F). Además de observar esta partición independientemente de la topología del sistema y en general, de los valores de los parámetros del juego, demostraremos analíticamente su existencia mediante la utilización de un modelo de red sencillo pero suficientemente general. Dentro también de la Primera Parte, realizaremos un estudio analítico de la cooperación en redes libres de escala randomizadas, es decir, en las que todo tipo de correlaciones posibles entre nodos han sido destruídas. Para ello utilizaremos una aproximación de campo medio, en la que además, haremos una compartimentalización de las estrategias en clases de conectividad. Los resultados obtenidos no concuerdan con las simulaciones numéricas en el caso general, pero veremos que sí lo hacen cualitativamente en el caso de unas condiciones iniciales particulares, en las que establecemos como cooperadores sólo a los nodos con conectividad superior a un cierto valor $k^*$. En el último capítulo de la Primera Parte, analizaremos qué ocurre con la dinámica del Dilema del Prisionero, en su versión con coste por cooperar, implementada sobre redes libres de escala, cuando se considera la razonable hipótesis de que los individuos no pueden interaccionar a la vez con todos sus vecinos, si estos son muchos, puesto que existen limitaciones de tipo práctico, como el gasto de energía o el tiempo requerido. Así, estableceremos una restricción, k*, en el número de interaciones por individuo y por ronda de juego, pero respetando la distribución de conectividad original de la red. Sorprendentemente, encontraremos que para cierto rango de los parámetros del juego, la cooperación se beneficia de dicha restricción, dando niveles más altos que cuando se juega sin dicha imposición. Encontraremos que esto es debido al necesario compromiso que deben establecer los nodos entre el coste de cooperar con todos sus vecinos y los beneficios que les reportan estas interacciones. Es importante darse cuenta de que las redes reales no son en general estáticas, sino que evolucionan en el tiempo: nuevos nodos y conexiones se a\~naden y eliminan, y esto puede afectar a los procesos que tienen lugar en ellas. Así, en la Segunda Parte de esta Tesis, nos interesaremos por este hecho, incorporándolo en nuestros sistemas. Concretamente, expondremos dos modelos en los que el crecimiento de la red esta íntimamente relacionado con la dinámica que se está desarrollando simultáneamente en ella, de modo que los beneficios obtenidos durante una ronda del juego determinarán las probabilidades de los nodos existentes para adquirir links de los recién llegados. Las diferencias entre estos dos modelos son, por una parte, la forma funcional de esta probabilidad (lineal con los beneficios en el primer modelo, y exponencial en el segundo), y por otra, la forma de actualización de las estrategias (en el primer caso, la probabilidad de cambio es tipo Replicador, proporcional a la diferencia de beneficios entre los dos nodos implicados, mientras que en el segundo modelo, la probabilidad tiene la forma de la función de Fermi, por lo que los cambios irracionales están permitidos, y un nodo podrá así imitar a un vecino que gana menos que él). Encontraremos que, en función de los parámetros de cada modelo, podemos obtener distintas topologías, que van desde aleatoria a libre de escala en el primer caso, y además, podrán aparecer estructuras en forma de estrella en el segundo. Además de la distribución de grado, las redes obtenidas con estos modelos también reproducen otras características de las redes reales, como la dependencia en forma de ley de potencias del coeficiente de clustering con la conectividad de los nodos. También analizamos los niveles de cooperación alcanzados en la red, comparándolos no sólo los distintos casos en función de los parametros, sino también con modelos de redes estáticas bien conocidas, como las aleatorias y las libres de escala. Encontraremos que en algunos casos, la cooperación alcanza niveles mayores incluso que en estas últimas. Otro resultado importante que encontraremos, y que difiere notablemente con los casos de redes estáticas, es la organización microscópica de la cooperación, puesto que en algunos casos, los hubs podrán ser ahora traidores asintóticamente estables. Así, mediante los dos modelos mostramos no sólo que la interdependencia entre dinámica y crecimiento genera estructuras complejas, sino también que el resultado de la dinámica implementada sobre éstas es muy diferente al caso de redes estacionarias. Si en la Primera Parte se ponía de manifiesto la influencia de la topología sobre la dinámica, con el trabajo de la Segunda Parte, se cierra el círculo, mostrando la retroalimentación de la dinámica sobre el crecimiento de la red.