Adapting the Social Network to Affect a Group’s Behavior

Abstract: We investigate the effect a social network could have on groups of rational agents, and whether a central organizer can utilize this effect to its advantage. We consider two settings: elections and coalition formation in order to complete k tasks.

In the first setting, we consider a group of self-interested agents where each agent has a strict preference order over a set of outcomes. Each agent votes strategically, taking into consideration both her preferences, and her (limited) information about the preferences of other voters. We assume that the information the agent has comes from her friends in the social network and from a public opinion poll. If agents were not strategic at all, the social network (and the poll) would not matter, since they would just vote according to their preferences. However, if the agents deviate and vote strategically the network plays a great effect. To measure this effect, we focus on iterative voting with the Plurality voting rule. We show, both in theory and in simulations, that for many networks, adding a linear number of edges can make any outcome the winner.

In the second setting, we consider the problem of computing effective coalition structures in situations where the coalitions that can be formed and the value of these coalitions is determined by a social network, indicating the strength of relationships between agents. We assume that a central organizer desires to build coalition structures to carry out a given set of tasks, and that it is possible for this central organizer to create new relationships between agents, although such relationship-building is assumed to incur some cost. Within this model, we investigate the problem of computing coalition structures that maximize social welfare. We identify tractable instances of the problem, present an algorithm for these cases, and show its effectiveness on real networks.

We view our results as yet another indication to the effect that a central organizer, such as a company that controls social media, could have on our lives – by introducing us to certain people it can affect our information and our decisions.