On Finding Better Friends in Social Networks
The authors study the dynamics of a social network. Each node has to decide locally which other node it wants to befriend, i.e., to which other node it wants to create a connection in order to maximize its welfare, which is defined as the sum of the weights of incident edges. This allows them to model the cooperation between nodes where every node tries to do as well as possible. With the limitation that each node can only have a constant number of friends, they show that every local algorithm is arbitrarily worse than a globally optimal solution.