  A central question in quantum information theory and computational complexity
is how powerful nonlocal strategies are in cooperative games with imperfect
information, such as multi-prover interactive proof systems. This paper
develops a new method for proving limits of nonlocal strategies that make use
of prior entanglement among players (or, provers, in the terminology of
multi-prover interactive proofs). Instead of proving the limits for usual
isolated provers who initially share entanglement, this paper proves the limits
for "commuting-operator provers", who share private space, but can apply only
such operators that are commutative with any operator applied by other provers.
Commuting-operator provers are at least as powerful as usual isolated but
prior-entangled provers, and thus, limits for commuting-operator provers
immediately give limits for usual entangled provers. Using this method, we
obtain an n-party generalization of the Tsirelson bound for the Clauser-Horne-
Shimony-Holt inequality for every n. Our bounds are tight in the sense that, in
every n-party case, the equality is achievable by a usual nonlocal strategy
with prior entanglement. We also apply our method to a 3-prover 1-round binary
interactive proof for NEXP. Combined with the technique developed by Kempe,
Kobayashi, Matsumoto, Toner and Vidick to analyze the soundness of the proof
system, it is proved to be NP-hard to distinguish whether the entangled value
of a 3-prover 1-round binary-answer game is equal to 1 or at most 1-1/p(n) for
some polynomial p, where n is the number of questions. This is in contrast to
the 2-prover 1-round binary-answer case, where the corresponding problem is
efficiently decidable. Alternatively, NEXP has a 3-prover 1-round binary
interactive proof system with perfect completeness and soundness 1-2^{-poly}.
