  We study the evolution of cooperation in the spatial prisoner's dilemma game
where players are allowed to establish new interactions with others. By
employing a simple coevolutionary rule entailing only two crucial parameters,
we find that different selection criteria for the new interaction partners as
well as their number vitally affect the outcome of the game. The resolution of
the social dilemma is most probable if the selection favors more successful
players and if their maximally attainable number is restricted. While the
preferential selection of the best players promotes cooperation irrespective of
game parametrization, the optimal number of new interactions depends somewhat
on the temptation to defect. Our findings reveal that the "making of new
friends" may be an important activity for the successful evolution of
cooperation, but also that partners must be selected carefully and their number
limited.
