We discuss some new algorithmic and complexity issues in coalitional and dynamic/evolutionary games, related to the understand- ing of modern sel¯sh and Complex networks. In particular: (a) We examine the achievement of equilibria via natural distributed and greedy approaches in networks. (b) We present a model of a coalitional game in order to capture the anarchy cost and complexity of constructing equilibria in such situations. (c) We propose a stochastic approach to some kinds of local interactions in networks, that can be viewed also as extensions of the classical evolutionary game theoretic setting.