In the multi-agent systems community, dependence theory and game theory are often presented as two alternative perspectives on the analysis of agent interaction. The paper presents a formal analysis of a notion of dependence between players, given in terms of standard game-theoretic notions of rationality such as dominant strategy and best response. This brings the notion of dependence within the realm of game theory providing it with the sort of mathematical foundations which still lacks. Concretely, the paper presents two results: first, it shows how the proposed notion of dependence allows for an elegant characterization of a property of reciprocity for outcomes in strategic games; and second, it shows how the notion can be used to define new classes of coalitional games, where coalitions can force outcomes only in the presence of reciprocal dependencies.

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing NP-hardness and parametrised complexity results for its occurrence and elimination.

The emergence of cooperation among self-interested agents has been a key concern of the multi-agent systems community for decades. With the increased importance of network-mediated interaction, researchers have shifted the attention to the impact of social networks and their dynamics in promoting or hindering cooperation, drawing various context-dependent conclusions. For example, some lines of research, theoretical and experimental, suggest the existence of a threshold effect in the ratio of timescales of network evolution, after which cooperation will emerge, whereas other lines dispute this, suggesting instead a Goldilocks zone. In this paper we provide an evolutionary game theory framework to understand coevolutionary processes from a bottom up perspective - in particular the emergence of a cooperator-core and defector-periphery - clarifying the impact of partner selection and imitation strategies in promoting cooperative behaviour, without assuming underlying communication or reputation mechanisms. In doing so we provide a unifying framework to study imitation-based cooperation in dynamic social networks and show that disputes in the literature can in fact coexist in so far as the results stem from different equally valid assumptions.