Self-organizing Coalitions for Managing Complexity

A complex system is an entity composed of interconnected parts, such that the collective behavior of those parts is more than the sum of the individual components. Those collective behaviors that appear as the interaction of the interconnected parts are usually called emergent.

A complex network is a structure made up of nodes connected by one or more specific types of interdependency. Nodes represent individuals, groups, or organizations, while connections (links, edges or ties) represent relations such as friendship, economic deals, internet connections, neuron connections, protein interactions, etc. The resulting graph-based structures are often very complex, being social networks the most popular application, but the analysis of these structures has carried out a great number of research papers in fields like: Economics, Telecommunications, Biology, Artificial Intelligence, Bioinformatics, Anthropology, Information Science, Social Psychology, Sociolinguistics, among others. Network Theory has emerged as a key technique to be applied in order to model, analyze, simulate and understand those complex network topologies; from a static and a dynamic point of view.

The term agent derives from the latin participle agens, coming from the verb agere that means to do and denotes the capability of an entity to do or to act. But in practice the term refers to multiple meanings in different contexts, like a human agent, a hardware agent, a chemical agent, etc. In this book we are interested in the concept of autonomous agents, and for that purpose one of the classical and simple definitions comes from Russell and Norvig (Artificial Intelligence: A Modern Approach, 2014, [21]) and states that: an agent is any entity that can perceive its environment through sensors and change it by means of actuators.

Many natural systems work based on local interactions among their component entities, and some of them are described as self-organized (selforg). This term usually refers to a system that is able to change its internal organization in order to adapt to internal or external changes without the need for an explicit external control (Di Marzo-Serugendo et al., Informatica, 30:45–54, 2006, [8]). These collective systems are particularly robust, because of the inherent redundancy, provided by their multiple components; that allow them to adapt to changes in order to ensure their own survivability.

Game Theory (GT) is the formal study of conflict and cooperation among several agents, denoted as players, representing individuals, animals, computers, groups, firms, etc. The concepts of game theory provide a mathematical framework to formulate, structure, analyze, and understand such game scenarios, i.e., it provides useful mathematical models and tools to understand the possible strategies that agents may follow when competing or collaborating in games. The list of games to apply game theory is almost endless: entertaining games, political scenarios, competitions among firms, geopolitical issues between countries, and so on. This branch of applied mathematics is used nowadays in disciplines like economics, social sciences, biology, political science, international relations, computer science and philosophy among others.

This chapter analyzes the use of adaptive neighborhoods based on coalitions in evolutionary optimization frameworks. First, we introduce the concepts of evolutionary algorithms, population topologies and coalitions. We integrate all these topics to study how to avoid some of the drawbacks of previous evolutionary algorithms and to remove their typically required parameters. The main contribution of the chapter is a redefinition of the Evolutionary Algorithm with Coalitions (EACO), which uses cellular approaches with neighborhoods, allowing the formation of coalitions among cells as a way to create islands of evolution in order to preserve diversity. This idea speeds up the evolution of individuals grouped in high-quality coalitions that are quickly converging to promising solutions. In the results section, we successfully compare EACO with a canonical cGA (Cellular Genetic Algorithm), and provide evidences about the statistical significance of our results. We also analyze the influence of parameters in order to tune them up accordingly; and finally, we evaluate the performance of EACO under different complex network topologies.

In this chapter we consider the Time Series Prediction problem (TSP), and the use of Self-organizing Maps (SOM) as the basic neural network model to apply. We conduct a topology-based TSP performance analysis, based on extensive numerical simulations, taking into account different complex networks for connecting the neurons within the SOM. We introduce the use of coalitions, and a parameter free version of our Coalitional Algorithm for SOM (CASOM), which adapts the neuron neighborhood to the time series under analysis by means of dynamic coalitions. The results obtained by CASOM are better than the ones provided by SOM in all the topologies and time series considered in this chapter, even when the network structure changes along the training process. Besides, and more remarkable, the number of training epochs, needed by CASOM to stabilize the weights of its neurons, is much lower than SOM.

In this chapter, we introduce the use of self-organised coalitions in smart grid scenarios for finding a coalition structure that maximises the systems’ utility. The complexity of such a task is exponential with the number of agents, and optimal coalition formation has been considered impractical. Several heuristic alternatives have been proposed in the research literature to handle such a problem. However, most existing methods approach coalition formation neglecting important aspects like maximising the total revenue or ensuring stability. Nonetheless, these points are fundamental in the context of smart grids, especially when we refer to virtual power plants (VPPs) of plug-in electric vehicles (PEVs), which have very limited energy capacity and small profits. In this chapter, we present two classes of constraints: (i) geographic-based, where the geographic position of PEVs is considered to avoid overloading the energy distribution network; and (ii) user-based, where the preferences of the PEV-users (owners) are taken into account to promote lasting coalitions. We also propose three methods for addressing coalition formation within such constrained scenarios: (i) DCCF, where agents invite neighbours to join their coalitions; (ii) SACF, where agents ask to join their neighbours’ coalitions; and (iii) SACF\(^+\), which is a natural evolution of SACF, where agents can change their coalitions, thus making the process much more dynamic. In all cases, agents negotiate the formation of coalitions among themselves, each on behalf a single PEV. The presented approaches were evaluated in closed and open world scenarios. Regarding the results, all three methods run in a few milliseconds regardless of the number of agents, achieving near-optimal solutions. In all tested cases, results were above 90% of optimum, on average. In comparison, despite delivering optimal solutions, traditional approaches took several hours and run for up to 20 agents, which represents a small and unrealistic scenario for smart grids. Thus, the proposed approaches show that providing approximate solutions for the coalition formation problem is attainable in smart grids scenarios.

In this chapter we introduce a networked version of the Possessor’s and Trader’s game, where, among the two basic strategies used in the Hawks-Dove game, hawks (H) and doves (D), it includes two other strategies based on the property of resources: Possession (P), as the right to occupy or possess what one owns; and Trade (T), as the right to buy and sell ownership. The simulations presented in this chapter describe how evolutionary forces, depending on the simulation parameters, allow the emergence of the different type of populations (D, C, P or T) over several complex topologies. The evolution of these populations clearly depends on several parameters as the cost of fighting, the trading values, the network topology, the owner’s probability and, under certain conditions, the neighborhood size. We also study the effect of partner switching (a.k.a. rewiring) to discover that, in all the topologies and conditions analyzed, the results are worse than without rewiring, and the global payoff decreases due to the effect of hawks. We also consider the effect of allowing the agents to accumulate payoff during a certain number of rounds, and we have discovered that the global payoff improves significantly when agents accumulate resources during five rounds or more. Finally, we introduce the possibility to create an informal trading social network, where traders seek for other traders, and connect to them; avoiding the hawks in their own neighborhoods. This trading social network is much more successful for traders, and for the global payoff, than the previous all-to-all attempt.

In this chapter we explore an indirect reputation scenario using the donation game, where agents are connected in a social network; and any agent may interact with any other in the population. Agents’ neighbors are their close related contacts from which they obtain information, as strategy, payoff and reputation. Besides the agent direct neighborhood, we also model a second set of contacts using coalitions (p.e., mates in a club or in a team), as a way to share information about the environment where agents play. We also include a rewiring mechanism using the neighbors’ reputation as a criteria to improve agents’ neighborhood, using coalition information as a way to rewire to the best coalition members. Along the chapter, we study in detail how the use of rewiring and mainly coalitions indeed improve cooperation when playing the donation game in a social framework. We also consider other strategy dynamics, using several alternatives for imitating or spreading information about the best decisions to take. Finally, we study the dependency of the model on the initial percentage of defectors, and the results show a strong dependency on the initial conditions, that have a significative influence in the game outcomes.

This chapter introduces the interesting Conway’s Game of Life, describing first its simple rules; and then some static, oscillating and moving patters that emerge from the game iteration depending deterministically on its initial configuration. We also describe some Life properties concerning the complexity that emerges from simple local interactions, its capabilities for self-replicating patterns and several variants of this game described in the Life literature. Afterwards, a coalitional version of Life (CoaLife) is introduced as an upper layer, keeping the basic rules used by Life; and using new ones to create, modify or release coalitions along the game execution. Finally, we consider an Iterated Prisoner’s Dilemma (IPD) extension for CoaLife (IPD-CoaLife), as another upper layer over CoaLife, where alive cells play the IPD with their alive neighbors. As an illustrative example, we provide a comparison between an IPD-Life (without coalitions) and the IPD-CoaLife, where the latter shows a better cooperation level. The aim of this last chapter is to show how the combination of coalitions and classical game theory models allows to explore competition and cooperation among cells in complex and rich environments such as the Game of Life.