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. Copyright The Econometric Society 2002.