Based on the observation that every small window in a natural image has many similar windows in the same image, the nonlocal denoising methods perform denoising by weighted averaging all the pixels in a nonlocal window and have achieved very promising denoising results. However, the use of fixed parameters greatly limits the denoising performance. Therefore, an important issue in pixel-domain image denoising algorithms is how to adaptively choose optimal parameters. While the Stein's principle is shown to be able to estimate the true mean square error (MSE) for determining the optimal parameters, there exists a tradeoff between the accuracy of the estimate and the minimum of the true MSE. In this paper, we study the impact of such a tradeoff and formulate the image denoising problem as a coalition formation game. In this game, every pixel/block is treated as a player, who tries to seek partners to form a coalition to achieve better denoising results. By forming a coalition, every player in the coalition can obtain certain gains by improving the accuracy of the Stein's estimate, while incurring some costs by increasing the minimum of the true MSE. Moreover, we show that the traditional approaches using same parameters for the whole image are special cases of the proposed game theoretic framework by choosing the utility function without a cost term. Finally, experimental results demonstrate the efficiency and effectiveness of the proposed game theoretic method.