  First, we consider the problem of deciding whether a nonlocal game admits a
perfect entangled strategy that uses projective measurements on a maximally
entangled shared state. Via a polynomial-time Karp reduction, we show that
independent set games are the hardest instances of this problem. Secondly, we
show that if every independent set game whose entangled value is equal to one
admits a perfect entangled strategy, then the same holds for all symmetric
synchronous games. Finally, we identify combinatorial lower bounds on the
classical and entangled values of synchronous games in terms of variants of the
independence number of appropriate graphs. Our results suggest that independent
set games might be representative of all nonlocal games when dealing with
questions concerning perfect entangled strategies.
