IDEAS home Printed from https://ideas.repec.org/a/ecm/emetrp/v70y2002i5p1893-1927.html
   My bibliography  Save this article

Computational Complexity and Communication: Coordination in Two-Player Games

Author

Listed:
  • Amparo Urbano

    () (Universidad de Valencia, Spain)

  • Jose E. Vila

    () (Universidad de Valencia, Spain)

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.

Suggested Citation

  • Amparo Urbano & Jose E. Vila, 2002. "Computational Complexity and Communication: Coordination in Two-Player Games," Econometrica, Econometric Society, vol. 70(5), pages 1893-1927, September.
  • Handle: RePEc:ecm:emetrp:v:70:y:2002:i:5:p:1893-1927
    as

    Download full text from publisher

    File URL: http://www.blackwellpublishing.com/ecta/asp/abstract.asp?iid=5&aid=357&vid=70
    File Function: link to full text
    Download Restriction: Access to full text is restricted to subscribers.

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hansen, Lars Peter, 1982. "Large Sample Properties of Generalized Method of Moments Estimators," Econometrica, Econometric Society, vol. 50(4), pages 1029-1054, July.
    2. Orme, Chris, 1990. "The small-sample performance of the information-matrix test," Journal of Econometrics, Elsevier, vol. 46(3), pages 309-331, December.
    3. Altonji, Joseph G & Segal, Lewis M, 1996. "Small-Sample Bias in GMM Estimation of Covariance Structures," Journal of Business & Economic Statistics, American Statistical Association, vol. 14(3), pages 353-366, July.
    4. Cosslett, Stephen R, 1981. "Maximum Likelihood Estimator for Choice-Based Samples," Econometrica, Econometric Society, vol. 49(5), pages 1289-1316, September.
    5. Hall, Peter & Horowitz, Joel L, 1996. "Bootstrap Critical Values for Tests Based on Generalized-Method-of-Moments Estimators," Econometrica, Econometric Society, vol. 64(4), pages 891-916, July.
    6. Newey, Whitney K. & McFadden, Daniel, 1986. "Large sample estimation and hypothesis testing," Handbook of Econometrics,in: R. F. Engle & D. McFadden (ed.), Handbook of Econometrics, edition 1, volume 4, chapter 36, pages 2111-2245 Elsevier.
    7. Newey, Whitney K, 1985. "Maximum Likelihood Specification Testing and Conditional Moment Tests," Econometrica, Econometric Society, vol. 53(5), pages 1047-1070, September.
    8. Tauchen, George, 1985. "Diagnostic testing and evaluation of maximum likelihood models," Journal of Econometrics, Elsevier, vol. 30(1-2), pages 415-443.
    9. Hansen, Lars Peter & Heaton, John & Yaron, Amir, 1996. "Finite-Sample Properties of Some Alternative GMM Estimators," Journal of Business & Economic Statistics, American Statistical Association, vol. 14(3), pages 262-280, July.
    10. K. Newey, Whitney, 1985. "Generalized method of moments specification testing," Journal of Econometrics, Elsevier, vol. 29(3), pages 229-256, September.
    11. Back, Kerry & Brown, David P, 1993. "Implied Probabilities in GMM Estimators," Econometrica, Econometric Society, vol. 61(4), pages 971-975, July.
    12. Andrew Chesher & Richard J. Smith, 1997. "Likelihood Ratio Specification Tests," Econometrica, Econometric Society, vol. 65(3), pages 627-646, May.
    13. Chesher, Andrew & Spady, Richard, 1991. "Asymptotic Expansions of the Information Matrix Test Statistic," Econometrica, Econometric Society, vol. 59(3), pages 787-815, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. R. Vijay Krishna, 2004. "Extended Conversations in Sender-Receiver Games," ESE Discussion Papers 126, Edinburgh School of Economics, University of Edinburgh.
    2. Ben-Porath, Elchanan, 2003. "Cheap talk in games with incomplete information," Journal of Economic Theory, Elsevier, vol. 108(1), pages 45-71, January.
    3. John Hillas & Min Liu, 2016. "Correlated equilibria of two person repeated games with random signals," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 137-153, March.
    4. Forges, Francoise & Koessler, Frederic, 2005. "Communication equilibria with partially verifiable types," Journal of Mathematical Economics, Elsevier, vol. 41(7), pages 793-811, November.
    5. R. Vijay Krishna, 2004. "Communication in Games of Incomplete Information: The Two-player Case," ESE Discussion Papers 125, Edinburgh School of Economics, University of Edinburgh.
    6. Vida, Péter & Āzacis, Helmuts, 2013. "A detail-free mediator," Games and Economic Behavior, Elsevier, vol. 81(C), pages 101-115.
    7. Izmalkov, Sergei & Lepinski, Matt & Micali, Silvio, 2011. "Perfect implementation," Games and Economic Behavior, Elsevier, vol. 71(1), pages 121-140, January.
    8. Forges, Françoise & Vida, Péter, 2013. "Implementation of communication equilibria by correlated cheap talk: The two-player case," Theoretical Economics, Econometric Society, vol. 8(1), January.
    9. Gerardi, Dino & Myerson, Roger B., 2007. "Sequential equilibria in Bayesian games with communication," Games and Economic Behavior, Elsevier, vol. 60(1), pages 104-134, July.
    10. Urbano, A. & Vila, J. E., 2004. "Unmediated communication in repeated games with imperfect monitoring," Games and Economic Behavior, Elsevier, vol. 46(1), pages 143-173, January.
    11. repec:spr:jogath:v:46:y:2017:i:4:d:10.1007_s00182-017-0569-7 is not listed on IDEAS
    12. Lance Fortnow & Rahul Santhanam, 2009. "Bounding Rationality by Discounting Time," Discussion Papers 1481, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    13. Ferenc Forgó, 2011. "Generalized correlated equilibrium for two-person games in extensive form with perfect information," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 19(2), pages 201-213, June.
    14. F. Forges & B. von Stengel, 2002. "Computionally Efficient Coordination in Games Trees," THEMA Working Papers 2002-05, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    15. Heller, Yuval & Solan, Eilon & Tomala, Tristan, 2012. "Communication, correlation and cheap-talk in games with public information," Games and Economic Behavior, Elsevier, vol. 74(1), pages 222-234.
    16. Heller, Yuval, 2010. "Minority-proof cheap-talk protocol," Games and Economic Behavior, Elsevier, vol. 69(2), pages 394-400, July.
    17. repec:dau:papers:123456789/5279 is not listed on IDEAS
    18. Kar, Anirban & Ray, Indrajit & Serrano, Roberto, 2010. "A difficulty in implementing correlated equilibrium distributions," Games and Economic Behavior, Elsevier, vol. 69(1), pages 189-193, May.
    19. Aumann, Robert J., 2003. "Presidential address," Games and Economic Behavior, Elsevier, vol. 45(1), pages 2-14, October.
    20. Wagner, P.Achim, 2011. "Unmediated communication with partially verifiable types," Journal of Mathematical Economics, Elsevier, vol. 47(1), pages 99-107, January.
    21. Gerardi, Dino, 2004. "Unmediated communication in games with complete and incomplete information," Journal of Economic Theory, Elsevier, vol. 114(1), pages 104-131, January.
    22. Peter Vida, 2005. "A Detail-free Mediator and the 3 Player Case," IEHAS Discussion Papers 0511, Institute of Economics, Centre for Economic and Regional Studies, Hungarian Academy of Sciences.
    23. Kalai, Adam Tauman & Kalai, Ehud & Lehrer, Ehud & Samet, Dov, 2010. "A commitment folk theorem," Games and Economic Behavior, Elsevier, vol. 69(1), pages 127-137, May.
    24. Gregory Parkhurst & Jason Shogren, 2005. "Does complexity reduce coordination?," Applied Economics Letters, Taylor & Francis Journals, vol. 12(7), pages 447-452.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ecm:emetrp:v:70:y:2002:i:5:p:1893-1927. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wiley-Blackwell Digital Licensing) or (Christopher F. Baum). General contact details of provider: http://edirc.repec.org/data/essssea.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.