Computational Complexity and Communication: Coordination in Two-Player Games

Amparo Urbano and Jose Vila ()

Econometrica, 2002, vol. 70, issue 5, 1893-1927

Abstract: 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.

Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (31)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ecm:emetrp:v:70:y:2002:i:5:p:1893-1927

Ordering information: This journal article can be ordered from
https://www.economet ... ordering-back-issues

Access Statistics for this article

Econometrica is currently edited by Guido Imbens

More articles in Econometrica from Econometric Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().