  This note confirms a conjecture of [Bramoull\'{e}, Anti-coordination and
social interactions, Games and Economic Behavior, 58, 2007: 30-49]. The
problem, which we name the maximum independent cut problem, is a restricted
version of the MAX-CUT problem, requiring one side of the cut to be an
independent set. We show that the maximum independent cut problem does not
admit any polynomial time algorithm with approximation ratio better than
$n^{1-\epsilon}$, where $n$ is the number of nodes, and $\epsilon$ arbitrarily
small, unless P=NP. For the rather special case where each node has a degree of
at most four, the problem is still MAXSNP-hard.
