Abstract
We study the complexity of equilibrium computation in discrete preference games. These games
were introduced by Chierichetti, Kleinberg, and
Oren (EC ’13, JCSS ’18) to model decision-making
by agents in a social network that choose a strategy
from a finite, discrete set, balancing between their
intrinsic preferences for the strategies and their desire to choose a strategy that is ‘similar’ to their
neighbours. There are thus two components: a social network with the agents as vertices, and a metric space of strategies. These games are potential
games, and hence pure Nash equilibria exist. Since
their introduction, a number of papers have studied
various aspects of this model, including the social
cost at equilibria, and arrival at a consensus. We
show that in general, equilibrium computation in
discrete preference games is PLS-complete, even
in the simple case where each agent has a constant
number of neighbours. If the edges in the social
network are weighted, then the problem is PLScomplete even if each agent has a constant number
of neighbours, the metric space has constant size,
and every pair of strategies is at distance 1 or 2.
Further, if the social network is directed, modelling
asymmetric influence, an equilibrium may not even
exist. On the positive side, we show that if the metric space is a tree metric, or is the product of path
metrics, then the equilibrium can be computed in
polynomial time