Computational Complexity and Communication: Coordination in Two-Player Games
利用密码学技术，证明在两人博弈中，通过限制玩家的计算能力，可以用无中介沟通实现任何理性收益的相关均衡，说明计算限制有助于解决实施问题。
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of the computational power available to agents. We introduce the concept of limited computational complexity, and by borrowing results from cryptography, we construct a communication protocol to establish that every correlated equilibrium of a two-person game with rational payoffs can be achieved by means of computationally restricted unmediated communication. This result provides an example in game theory where limitations of computational abilities of players are helpful in solving implementation problems. More specifically, it is possible to construct mechanisms with the property that profitable deviations are too complicated to compute.