Discrete Preference Games: Social Influence Through Coordination, and Beyond

We study discreet preference games that have been used to model issues such as the formation of opinions or the adoption of innovations in the context of a social network. In these games, the payoff of each agent depends on the agreement of her strategy to her internal belief and on its coordination with the strategies of her neighbours in the social network. We consider the question of whether the public opinion can be different than the public belief. We show that strategic behaviour typically leads to changes of the public opinion compared to the public belief. We completely characterise the social networks where such changes can happen and furthermore study the complexity of such transitions. We show that deciding whether a minority belief can become the majority opinion is NP-hard even when the initial number of supporters of this belief is very close to 1/4 of the social network size. Next, motivated by the limited expressive power of discrete preference games, we define and study the novel class of generalised discrete preference games. These games have additional characteristics and can model social relations to allies or competitors, introduce different levels of strength for each relation, and personalise the dependence of each agent to its neighbourhood. We show that these games admit generalised ordinal potential functions. More importantly, we show that every two-strategy game that admits a generalised ordinal potential function is structurally equivalent to a generalised discrete preference game. This implies that these new games capture the full generality of two-strategy games in which the existence of equilibria is guaranteed by topological arguments.