  An active line of research has considered games played on networks in which
payoffs depend on both a player's individual decision and also the decisions of
her neighbors. Such games have been used to model issues including the
formation of opinions and the adoption of technology. A basic question that has
remained largely open in this area is to consider games where the strategies
available to the players come from a fixed, discrete set, and where players may
have different intrinsic preferences among the possible strategies. It is
natural to model the tension among these different preferences by positing a
distance function on the strategy set that determines a notion of "similarity"
among strategies; a player's payoff is determined by the distance from her
chosen strategy to her preferred strategy and to the strategies chosen by her
network neighbors. Even when there are only two strategies available, this
framework already leads to natural open questions about a version of the
classical Battle of the Sexes problem played on a graph.
  We develop a set of techniques for analyzing this class of games, which we
refer to as discrete preference games. We parametrize the games by the relative
extent to which a player takes into account the effect of her preferred
strategy and the effect of her neighbors' strategies, allowing us to
interpolate between network coordination games and unilateral decision-making.
When these two effects are balanced, we show that the price of stability is
equal to 1 for any discrete preference game in which the distance function on
the strategies is a tree metric; as a special case, this includes the Battle of
the Sexes on a graph. We also show that trees form the maximal family of
metrics for which the price of stability is 1, and produce a collection of
metrics on which the price of stability converges to a tight bound of 2.
