Resumen de Structure in artificial societies

Josep Maria Pujol

• This thesis is focused on understanding the role that structures of interactions have on multi-agent systems, which are probably the prototypical instances of arti cial societies.

  This thesis can hopefully be read as a contribution to the research area dealing with the interdependence between a system and its components. We frame our research in systems in which the components of the system are social, regardless of the fact that components might be computational entities, as it is the case of multi-agent systems. Our aim is twofold, since we hope to study the e ect that these structures of interaction between agents have both at the level of individuals and at the level of the system. The leitmotif of the research presented in this thesis is the social structure, and we address the role played by this structure from di erent perspectives.

  First, we attend to the task of drawing implicit information embedded in the relationships between individuals. To that end, we present a several algorithms that are able to extract knowledge by means of analyzing the structure of the social network. While the rst algorithm relies on the analysis of the social network to infer a reputation measure for the agents, the second one is intended to identify the underlying community structure that exists in the social network. After addressing structure as a source of knowledge we turn our attention towards the e ect that certain structures - patterns of interactions - have on a system's dynamics. We study which structures favor the emergence of cooperation between agents and show that certain structures, speci cally complex networks, facilitate the emergence of autonomously-agreed normative behavior | a convention. Furthermore, we show that when one convention is more bene cial than alternative conventions, the same properties of the network promote the adoption of the most desirable convention. Last but not least, we also study the process of formation of complex networks, we show that agents performing a local optimization process, grounded in sociologically plausible assumptions, can arrange themselves so that they display di erent structures of interactions, networks being complex one of them.

  Although the focus of our research is on a particular case of arti cial societies, the conclusions derived from this thesis are not limited to multi-agent systems. Our research is an inter-disciplinary approach to complex social systems. We use di erent methodologies borrowed from Physics, Complex Systems, Sociology, Computer Science and, of course, Arti cial Intelligence in order to contribute to a better understanding of social systems in general, and multi-agent systems in particular.