Robustness in Discrete Preference Games

In a discrete preference game, each agent is equipped with an internal belief and declares her preference from a discrete set of alternatives. The payoff of an agent depends on whether the declared preference agrees with the belief of the agent and on the coordination with the preferences declared by the neighbors of the agent in the underlying social network. These games have been used to model the formation of opinions and the adoption of innovations in social networks. Recently, researchers have obtained bounds on the Price of Anarchy and on the Price of Stability of discrete preference games and they have studied to which extent the winning preference reached via best-response dynamics disagrees with the majority of beliefs. In this work, we investigate the robustness of these results to variants of the model. Our starting point is the observation that bounds on the Price of Anarchy and Stability can be very dependent on the way the quality of an equilibrium is measured. On the other side, results about the disagreement between majority at equilibria and majority among beliefs continue to hold even if we consider different classes of dynamics, such as no-worse-response dynamics, best response with multiple players updating at the same time, or with weighted neighbors.